1. unordered系列的关联式容器
1.1 引言
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到l o g 2 N log_2 Nlog
2
N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍， unordered_multimap和unordered_multimap可以去自行查看使用文档cplusplus
注意：实际上，unordered系列容器的使用和map/set基本一致，区别就在于unordered系列只支持单向迭代器，并且由于结构的限制，遍历unordered系列容器的顺序是无序的
1.2 unordered_map的使用说明
使用文档
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Lh9sfZMp-1684930297303)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2013.41.16.png)]
void Test_unordered_map() { unordered_map<string, int> countMap; string arr[] = { "苹果", "西瓜", "香蕉","苹果", "西瓜", "西瓜"}; for(const auto& str : arr) { //countMap[str]++; auto it = countMap.find(str); if(it == countMap.end()) { countMap.insert(make_pair(str, 1)); } else { it->second++; } } for(const auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } cout << endl; }
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zQ3hv30X-1684930297304)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2013.48.12.png)]
除了map的接口之外，由于unordered_map的底层是哈希桶，所以，有一些只属于哈希桶的接口
| 函数原型 | 功能介绍 |
| size_t bucket_count() const | 返回哈希桶中桶的总个数 |
| size_t max_bucket_count() const | 返回哈希桶中能够容纳的最大的桶个数 |
| size_t bucket_size(size_t n) const | 返回哈希桶中有效元素个数 |
| **size_t bucket(const K& key) ** | 返回元素key所在的桶号 |
1.3 unordered_set的使用说明
使用文档
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l4MBpovo-1684930297304)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2013.33.08.png)]
void Test_unordered_set() { unordered_set<int> us; us.insert(10); us.insert(2); us.insert(4); us.insert(5); us.insert(3); us.insert(1); us.insert(10); unordered_set<int>::iterator it = us.begin(); while(it != us.end()) { cout << *it << " "; ++it; } cout << endl; }
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YZHaJAyB-1684930297304)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2014.04.56.png)]
1.4 unordered_set和unordered_map的应用
在长度为2*N的数组中找到重复出现N次的数
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xTk0r0sx-1684930297305)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2014.44.00.png)]
1.5 性能比较
void Test_efficient() { const size_t N = 1000000;//测试的数据个数 //构造两个数组，一个有序一个无序，用于测试 vector<int> SortV; vector<int> UnsortV; SortV.reserve(N); UnsortV.reserve(N); srand(time(0)); for (int i = 0; i < N; ++i) { UnsortV.push_back(rand()); SortV.push_back(i); } //开始测试 unordered_set<int> SortUs; unordered_set<int> UnsortUs; set<int> SortS; set<int> UnsortS; cout << "有序插入效率对比" << endl; size_t begin1 = clock(); for (auto e : SortV) { SortS.insert(e); } size_t end1 = clock(); cout << "set insert sorted:" << end1 - begin1 << endl; size_t begin2 = clock(); for (auto e : SortV) { SortUs.insert(e); } size_t end2 = clock(); cout << "unordered_set insert sorted:" << end2 - begin2 << endl; cout << "无序插入效率对比" << endl; size_t begin3 = clock(); for (auto e : UnsortV) { UnsortS.insert(e); } size_t end3 = clock(); cout << "set insert unsort:" << end3 - begin3 << endl; size_t begin4 = clock(); for (auto e : UnsortV) { UnsortUs.insert(e); } size_t end4 = clock(); cout << "unordered_set insert unsort:" << end4 - begin4 << endl; cout << "有序查找效率对比" << endl; size_t begin5 = clock(); for (auto e : SortV) { SortS.find(e); } size_t end5 = clock(); cout << "set find sorted:" << end5 - begin5 << endl; size_t begin6 = clock(); for (auto e : SortV) { SortUs.find(e); } size_t end6 = clock(); cout << "unordered_set find sorted:" << end6 - begin6 << endl; cout << "无序查找效率对比" << endl; size_t begin7 = clock(); for (auto e : UnsortV) { UnsortS.find(e); } size_t end7 = clock(); cout << "set find unsorted:" << end7 - begin7 << endl; size_t begin8 = clock(); for (auto e : UnsortV) { UnsortUs.find(e); } size_t end8 = clock(); cout << "unordered_set find unsorted:" << end8 - begin8 << endl; cout << "有序删除效率对比" << endl; size_t begin9 = clock(); for (auto e : SortV) { SortS.erase(e); } size_t end9 = clock(); cout << "set erase sorted:" << end9 - begin9 << endl; size_t begin10 = clock(); for (auto e : SortV) { SortUs.erase(e); } size_t end10 = clock(); cout << "unordered_set erase:" << end10 - begin10 << endl; cout << "无序删除效率对比" << endl; size_t begin11 = clock(); for (auto e : UnsortV) { UnsortS.erase(e); } size_t end11 = clock(); cout << "set erase sorted:" << end11 - begin11 << endl; size_t begin12 = clock(); for (auto e : UnsortV) { UnsortUs.erase(e); } size_t end12 = clock(); cout << "unordered_set erase:" << end12 - begin12 << endl; }
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wXEUyCsZ-1684930297305)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2015.07.18.png)]
可以看到随机数下unordered系列效率更高，但是有序数的情况下就不太行。
2. 哈希概念
unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构，那么什么是哈希？
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素 时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即**O(l o g 2 N log_2 Nlog
2
N)**搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法:可以不经过任何比较，一次直接从表中得到要搜索的元素。类似通过下标访问数组中任意位置的元素。 如果构造一种存储结构，通过某种函数(HashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中插入元素时：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放；搜索元素时：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功.
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
接下来我们看下面这个例子：
假设有数据集{1, 7, 6, 4, 5, 9};
哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小
按照这种存放方式，如果需要查找4，就直接通过4 % 10 = 4找到hash(key) = 4的位置，直接取出来即可，省略了多次key的比较，节约了时间。
