【C++ unordered_map与unordered_set】哈希版关联容器入门

C unordered_map与unordered_set哈希版关联容器入门大家好前面 map 和 set 用得挺顺但它们底层是红黑树、按 key 有序。这篇介绍哈希版本——unordered_map 和 unordered_set底层换成哈希表增删查平均 O(1)代价是遍历无序。这是一篇承上启下的文章先把这两个容器怎么用、和 map/set 差在哪讲清楚为后面学习哈希表打底。目录一、为什么叫 unordered 而不是 hash二、unordered_set 是什么三、unordered_set 和 set 的三个差异四、性能对比实测五、unordered_map 和 map 的三个差异六、unordered_multimap / unordered_multiset七、Buckets 和 Hash policy 接口八、哈希版和树版怎么选一、为什么叫 unordered 而不是 hashC11 之前标准库只有 map 和 set底层是红黑树。C11 引入哈希版本时命名犯了难直接叫hash_map容易让人误会——以为 map 是大类、hash_map 是它的一个子类但实际上哈希版和红黑树版是平级的两套东西不存在谁包含谁。最终标准选了unordered_这个前缀意思是无序的和原来有序的 map/set 从语义上拉开区分。顺便对比一下 JavaJava 出得晚设计时就把两套都想好了直接叫TreeMap/TreeSet和HashMap/HashSet一看就懂。所以要吐槽 C 命名只能吐槽它出得太早了 -_- 。二、unordered_set 是什么官方参考文档https://legacy.cplusplus.com/reference/unordered_set/先看模板声明templateclassKey,classHashhashKey,classKeyEqualequal_toKey,classAllocallocatorKeyclassunordered_set;四个模板参数日常只需要传第一个Key存的 key 的类型Hash把 Key 转成整数的仿函数默认hashKeyKeyEqual判断两个 Key 是否相等的仿函数默认equal_toKeyAlloc空间配置器默认用标准的。后三个参数大多数情况都用默认值不用自己传。什么时候才需要自己写比如你的 Key 是个自定义结构体默认hash和不认识它这时才自己写一个仿函数传进去。底层是哈希桶实现增删查平均 O(1)。迭代器遍历不再有序——为了和 set 区分所以叫 unordered_set。三、unordered_set 和 set 的三个差异set 和 unordered_set 功能高度相似接口insert / erase / find用法几乎一样这里只讲差异。差异一对 Key 的要求不同set 要求 Key 支持小于比较因为红黑树要靠它排大小unordered_set 要求 Key 支持转成整数算哈希值和相等比较解决哈希冲突后判断是不是同一个 key。这两个要求本质是哈希表的要求后面学习了哈希表时会彻底理解现在先记住结论。差异二迭代器和遍历顺序set 的 iterator 是双向迭代器底层红黑树走中序遍历出来有序 去重unordered_set 的 iterator 是单向迭代器只能不能--底层哈希表遍历出来无序 去重。差异三性能红黑树增删查是 O(logN)哈希表增删查平均 O(1)。大多数场景下 unordered_set 更快下面实测代码跑一下就有直观感受。pairiterator,boolinsert(constvalue_typeval);size_typeerase(constkey_typek);iteratorfind(constkey_typek);四、性能对比实测下面这段代码生成 100 万个数据分别塞进 set 和 unordered_set对比插入、查找、删除的耗时。测试代码也没啥意思不讲大家 copy 下来自己跑#includeunordered_set#includeunordered_map#includeset#includevector#includeiostreamusingnamespacestd;inttest_set2(){constsize_t N1000000;unordered_setintus;setints;vectorintv;v.reserve(N);srand(time(0));for(size_t i0;iN;i){//v.push_back(rand()); // N比较大时重复值比较多v.push_back(rand()i);// 重复值相对少//v.push_back(i); // 没有重复有序}size_t begin1clock();for(autoe:v){s.insert(e);}size_t end1clock();coutset insert:end1-begin1endl;size_t begin2clock();us.reserve(N);for(autoe:v){us.insert(e);}size_t end2clock();coutunordered_set insert:end2-begin2endl;intm10;size_t begin3clock();for(autoe:v){autorets.find(e);if(ret!s.end()){m1;}}size_t end3clock();coutset find:end3-begin3-m1endl;intm20;size_t begin4clock();for(autoe:v){autoretus.find(e);if(ret!us.end()){m2;}}size_t end4clock();coutunordered_set find:end4-begin4-m2endl;cout插入数据个数: s.size()endl;cout插入数据个数: us.size()endlendl;size_t begin5clock();for(autoe:v){s.erase(e);}size_t end5clock();coutset erase:end5-begin5endl;size_t begin6clock();for(autoe:v){us.erase(e);}size_t end6clock();coutunordered_set erase:end6-begin6endlendl;return0;}intmain(){test_set2();return0;}跑出来 unordered_set 三项基本都比 set 快尤其查找差距最明显。五、unordered_map 和 map 的三个差异unordered_map 和 map 的关系跟 unordered_set 和 set 完全对称差异也是同样三条对 Key 的要求map 要求 Key 支持小于比较unordered_map 要求 Key 支持转整数 相等比较。迭代器和遍历顺序map 是双向迭代器遍历按 key有序unordered_map 是单向迭代器遍历无序。性能红黑树 O(logN)哈希表平均 O(1)。接口上 insert / find / operator[] 的用法跟 map 一样不再重复演示。六、unordered_multimap / unordered_multiset这两个跟 multimap / multiset 是一对允许 key 冗余同一个 key 可以存多份。它们和对应 multimap/multiset 的差异也是那三条key 要求、迭代器和遍历顺序、性能。用法照抄 multimap/multiset底层换成哈希表即可。七、Buckets 和 Hash policy 接口unordered 系列还有一组跟哈希桶和负载因子相关的接口桶数、桶里有几个元素、最大负载因子、扩容时机等等。日常使用我们不用太关注等后面学了哈希表、理解了负载因子和扩容逻辑之后再回头看这组接口就一目了然。八、哈希版和树版怎么选一句话选型需要按 key 有序遍历、取范围比如按时间排序输出、找 [a, b] 区间→ 用 map / set只关心快速查找、不要求顺序比如缓存、去重、计数→ 用 unordered_map / unordered_set平均更快。这篇只是把怎么用讲了哈希表为什么能做到 O(1)、哈希冲突怎么解决、负载因子和扩容怎么回事——下一篇我们正式学习哈希表把这些底层原理拆开看看。