1. unordered 系列容器是什么unordered_set、unordered_map、unordered_multiset、unordered_multimap是 C 标准库中的无序关联式容器。它们和set/map最大的区别是底层结构不同set/map底层通常是红黑树unordered_set/unordered_map底层通常是哈希表。红黑树通过比较大小维护有序结构增删查改复杂度一般是O(logN)哈希表通过哈希函数直接计算元素所在位置在冲突较少时增删查改平均复杂度可以达到O(1)。所以unordered系列名字里带有 unordered是因为它们不保证按 key 的大小顺序遍历。使用时要记住一句话想要有序遍历用 map/set想要高频查找、插入、删除用 unordered_map/unordered_set。2. unordered_set 的使用unordered_set只存 key不存 value且默认不允许 key 重复。#includeiostream#includeunordered_setusingnamespacestd;intmain(){unordered_setints{2,3,5,6,7,2};s.insert(45);s.erase(3);autoposs.find(5);if(pos!s.end()){cout找到了: *posendl;}for(autoe:s){coute ;}coutendl;return0;}注意输出顺序不一定是插入顺序也不一定是从小到大。unordered_set的常见接口接口作用insert(x)插入元素erase(x)删除 key 为 x 的元素find(x)查找 x返回迭代器count(x)判断 x 出现次数普通 set 结果只可能是 0 或 1size()元素个数empty()判断是否为空clear()清空容器reserve(n)提前扩容减少重哈希3. unordered_map 的使用unordered_map保存的是键值对pairconstK,V其中first是 keysecond是 value。key 不能被修改因为一旦 key 改变它所在的哈希桶可能也会变化。#includeiostream#includestring#includeunordered_mapusingnamespacestd;intmain(){unordered_mapstring,stringdict;dict.insert({insert,插入});dict.insert({sort,排序});dict.insert({test,测试});dict[left]左边;dict[sort]排序算法;for(auto[k,v]:dict){coutk:vendl;}return0;}3.1 insert 和 operator[] 的区别insert遇到已经存在的 key 时不会覆盖原 valueunordered_mapstring,intm;m.insert({apple,1});m.insert({apple,2});coutm[apple]endl;// 仍然是 1operator[]则会返回 key 对应的 value 引用m[apple]2;// 修改m[banana];// 如果不存在会插入 {banana, 0}因此如果只是查找不想产生新数据尽量使用findautoitm.find(banana);if(it!m.end()){coutit-secondendl;}4. unordered 与有序容器的差异4.1 key 的要求不同map/set要求 key 支持小于比较key1key2unordered_map/unordered_set要求 key 能被哈希并且能判断相等hash(key)key1key2标准库已经为常见类型提供了哈希函数例如int、string、指针等。自定义类型需要自己提供哈希函数和相等比较。4.2 迭代顺序不同set/map的遍历顺序是有序的。setints{4,1,8,2};// 遍历结果通常是1 2 4 8unordered_set/unordered_map的遍历顺序由哈希表内部桶分布决定不适合依赖顺序unordered_setintus{4,1,8,2};// 遍历结果不保证顺序4.3 性能差异大多数随机数据场景下哈希表的增删查平均效率更高。但哈希表不是永远更快哈希函数质量差会导致大量冲突数据量很小时红黑树和哈希表差异不明显哈希表扩容时需要重哈希会出现阶段性开销如果需要范围查询、有序输出map/set更合适。测试代码中使用了setint和unordered_setint插入、查找、删除一百万个数据并通过reserve(N)提前为unordered_set扩容unordered_setintus;us.reserve(N);for(autoe:v){us.insert(e);}reserve很重要它可以减少插入过程中的多次扩容和重哈希。5. 哈希表的基本思想哈希表的核心思想是通过一个哈希函数把 key 映射到数组下标。hashihash(key)%M;其中M是哈希表的桶个数。如果 key 的范围很小可以直接用 key 当数组下标这叫直接定址法。例如只统计a到z出现次数intcount[26]{0};for(charch:s){count[ch-a];}但当 key 范围很大时直接定址会浪费大量空间。此时就需要哈希函数把较大的 key 空间压缩到较小的桶数组中。6. 哈希冲突和负载因子不同 key 可能映射到同一个桶这就是哈希冲突。h(19)19%118h(30)30%11819和30都落在下标8就发生了冲突。哈希表无法完全避免冲突只能尽量减少冲突并设计好冲突解决方案。衡量哈希表拥挤程度的指标叫负载因子load_factor元素个数/桶个数负载因子越大空间利用率越高但冲突概率越大负载因子越小冲突概率越低但空间浪费越多。常见处理方式开放定址法所有元素都放在数组中发生冲突后继续寻找空位置链地址法每个桶挂一条链表冲突元素放在同一个桶的链表中。7. 开放定址法实现开放定址法中每个位置有三种状态enumStatus{EXIST,EMPTY,DELETE};为什么需要DELETE因为开放定址查找时可能需要经过多个冲突位置。如果删除元素后直接把位置改成EMPTY可能会截断后续元素的查找路径。比如19和30都从下标8开始探测30因冲突被放到下标9。如果删除19后把下标8改成空查找30时看到下标8是空就会误以为30不存在。所以删除时应标记为DELETE表示这里曾经有数据查找时还要继续向后探测。7.1 数据结构templateclassK,classVstructHashData{pairK,V_kv;Status _statusEMPTY;};哈希表主体templateclassK,classV,classHashHashFuncKclassHashTable{private:vectorHashDataK,V_tables;size_t _n0;};_tables是存储空间_n是有效数据个数。7.2 插入逻辑插入之前先判断是否需要扩容。开放定址法要求负载因子必须小于 1否则表满后一定找不到空位置。实践中通常在负载因子达到某个阈值时扩容例如源码中使用了0.7。if((double)_n/_tables.size()0.7){HashTableK,V,HashnewHT;newHT._tables.resize(__stl_next_prime(_tables.size()1));for(autodata:_tables){if(data._statusEXIST){newHT.Insert(data._kv);}}_tables.swap(newHT._tables);}然后通过线性探测寻找可插入位置Hash hs;size_t hash0hs(kv.first)%_tables.size();size_t hashihash0;size_t i1;while(_tables[hashi]._statusEXIST){hashi(hash0i)%_tables.size();i;}_tables[hashi]._kvkv;_tables[hashi]._statusEXIST;_n;这里用的是线性探测hashi(hash0i)%M;线性探测实现简单但连续冲突时容易形成“堆积”。还有二次探测和双重散列它们可以一定程度缓解堆积但实现会复杂一些。7.3 查找逻辑查找从hash0开始遇到EXIST就判断 key 是否相等遇到DELETE继续探测直到遇到EMPTY才能停止。HashDataK,V*Find(constKkey){Hash hs;size_t hash0hs(key)%_tables.size();size_t hashihash0;size_t i1;while(_tables[hashi]._status!EMPTY){if(_tables[hashi]._statusEXIST_tables[hashi]._kv.firstkey){return_tables[hashi];}hashi(hash0i)%_tables.size();i;}returnnullptr;}7.4 删除逻辑开放定址法删除时不真正清空位置只把状态改成DELETE。boolErase(constKkey){auto*ptrFind(key);if(ptr){ptr-_statusDELETE;--_n;returntrue;}returnfalse;}开放定址法的优点是结构紧凑不需要额外节点指针缺点是删除处理麻烦负载因子不能太高冲突严重时性能下降明显。8. 链地址法实现链地址法也叫哈希桶。它让每个数组位置保存一条链表的头指针所有映射到同一个桶的元素都挂在这条链表上。链地址法是unordered_map和unordered_set更常见的底层思路。相比开放定址法它的优势是删除更自然直接从链表中摘节点负载因子可以大于 1冲突元素不会占用其他桶的位置扩容迁移时可以直接移动节点不必重新构造所有数据。8.1 节点结构templateclassK,classVstructHashNode{pairK,V_kv;HashNodeK,V*_next;HashNode(constpairK,Vkv):_kv(kv),_next(nullptr){}};哈希表内部保存的是vectorNode*templateclassK,classV,classHashHashFuncKclassHashTable{typedefHashNodeK,VNode;private:vectorNode*_tables;size_t _n0;};8.2 插入逻辑先检查 key 是否已经存在if(Find(kv.first))returnfalse;如果负载因子达到 1就扩容if(_n_tables.size()){vectorNode*newtables(__stl_next_prime(_tables.size()1));for(size_t i0;i_tables.size();i){Node*cur_tables[i];while(cur){Node*nextcur-_next;size_t hashihs(cur-_kv.first)%newtables.size();cur-_nextnewtables[hashi];newtables[hashi]cur;curnext;}_tables[i]nullptr;}_tables.swap(newtables);}扩容时注意不能简单把旧数组拷贝过去因为桶个数变了hash(key) % M的结果也变了每个节点都要重新计算桶位。最后头插新节点size_t hashihs(kv.first)%_tables.size();Node*newNodenewNode(kv);newNode-_next_tables[hashi];_tables[hashi]newNode;_n;returntrue;8.3 查找逻辑查找时先定位桶再在桶内链表中逐个比较 keyNode*Find(constKkey){Hash hs;size_t hashihs(key)%_tables.size();Node*cur_tables[hashi];while(cur){if(cur-_kv.firstkey)returncur;curcur-_next;}returnnullptr;}如果哈希函数分布均匀桶内链表平均很短查找效率接近O(1)。如果大量 key 都落入同一个桶桶内链表会变长最坏可能退化到O(N)。8.4 删除逻辑链地址法删除就是链表删除节点boolErase(constKkey){Hash hs;size_t hashihs(key)%_tables.size();Node*prevnullptr;Node*cur_tables[hashi];while(cur){if(cur-_kv.firstkey){if(prevnullptr)_tables[hashi]cur-_next;elseprev-_nextcur-_next;deletecur;--_n;returntrue;}prevcur;curcur-_next;}returnfalse;}9. 哈希函数设计对于整型 key可以直接转换成size_ttemplateclassKstructHashFunc{size_toperator()(constKkey)const{return(size_t)key;}};对于字符串需要把多个字符综合成一个整数。源码中使用了 BKDR 思想templatestructHashFuncstring{size_toperator()(conststringstr)const{size_t hash0;for(autoch:str){hash*131;hashch;}returnhash;}};代码中写法是先hash ch再hash * 131也能达到区分字符串的目的。更常见的写法是先乘再加hashhash*131ch;哈希函数应该尽量让 key 均匀分布。如果哈希函数设计得很差所有 key 都映射到同一个桶再好的哈希表也会退化。10. 仿函数与模板参数标准库中的unordered_set大致有这些模板参数templateclassKey,classHashhashKey,classPredequal_toKey,classAllocallocatorKeyclassunordered_set;Hash是哈希仿函数Pred是相等比较仿函数。一般使用内置类型和string时我们不需要自己传。自定义类型时可以这样写structStudent{string _name;int_id;};structStudentHash{size_toperator()(constStudents)const{returnhashint()(s._id);}};structStudentEqual{booloperator()(constStudents1,constStudents2)const{returns1._ids2._id;}};unordered_setStudent,StudentHash,StudentEqualstus;核心是哈希函数认为相等的 key 不一定必须 hash 值相同但相等比较认为相等的 key必须能被容器正确找到。因此通常会让相等对象产生相同 hash 值。11. unordered_map 和 unordered_set 的封装思路和之前用红黑树封装map/set类似哈希表也可以作为统一底层HashTableK,T,KeyOfT,Hash其中K是 key 的类型T是节点保存的数据类型KeyOfT负责从T中取出 keyHash负责把 key 转成哈希值。对于unordered_setTKKeyOfT(key)key对于unordered_mapTpairconstK,VKeyOfT(kv)kv.first这样底层哈希表不需要关心上层是 set 还是 map。它只要能通过KeyOfT取到 key就能完成插入、查找、删除。最后列出的实现步骤很清晰先实现哈希表再封装unordered_map和unordered_set的框架解决KeyOfT实现普通迭代器实现const_iterator处理 key 不能修改的问题支持operator[]。这和红黑树封装map/set的思想完全一致底层结构复用上层容器只做适配。12. 复杂度分析操作平均复杂度最坏复杂度说明insertO(1)O(N)冲突严重或扩容时会变慢findO(1)O(N)哈希分布差时退化eraseO(1)O(N)需要先定位元素遍历O(N)O(N)遍历全部元素rehashO(N)O(N)需要重新计算桶位哈希表的O(1)是平均意义上的不是绝对保证。它依赖三个条件哈希函数质量不错负载因子控制合理冲突处理策略有效。13. 总结unordered_map和unordered_set的底层核心是哈希表。它们牺牲了有序遍历能力换来了平均O(1)的增删查改效率。学习哈希表时需要抓住四个关键词哈希函数把 key 转成数组下标哈希冲突不同 key 可能落到同一个位置负载因子衡量哈希表拥挤程度扩容重哈希桶个数改变后必须重新计算位置。开放定址法把所有元素都放在数组里结构紧凑但删除和负载因子控制更麻烦链地址法用桶数组加链表处理冲突删除和扩容更自然也是理解unordered系列容器的重点。最后再回到 C 容器使用上需要 key 有序选择map/set只关心快速查找选择unordered_map/unordered_set使用unordered_map时查找用find需要插入或修改 value 时再用operator[]大量插入前可以reserve减少扩容带来的性能波动。理解了哈希表就不只是会用unordered_map和unordered_set还能明白它为什么快、什么时候会慢以及为什么遍历结果看起来“没有规律”。