1. 为什么要封装 myunordered_map 和 myunordered_set前面我们已经知道unordered_map和unordered_set的底层核心是哈希表。unordered_set保存单个 keyunordered_map保存pairconst K, V两者都需要根据 key 计算桶下标两者都需要处理哈希冲突两者都需要查找、插入、删除和遍历。如果分别实现两个容器就会重复编写大量哈希表代码。更合理的方式是先实现一个通用的HashTableK,T,KeyOfT,Hash然后让myunordered_map和myunordered_set只负责适配数据类型。这是一种典型的“底层复用上层适配”设计HashTable负责数据结构KeyOfT负责从节点数据中取出 keyHash负责把 key 转换成哈希值map/set封装层负责暴露不同的接口。2. 哈希桶的基本结构链地址法的哈希表通常由两部分组成一个桶数组每个桶下面的一条节点链表。节点结构可以写成templateclassTstructHashNode{T _data;HashNodeT*_next;explicitHashNode(constTdata):_data(data),_next(nullptr){}};哈希表内部保存桶数组vectorNode*_tables;size_t _n0;插入时先计算size_t hashihash(key)%_tables.size();然后把新节点头插到_tables[hashi]对应的链表中。头插的好处是实现简单时间复杂度是O(1)代价是同一个桶内的遍历顺序与插入顺序相反而且整个unordered容器本身也不保证有序。3. 通用 HashTable 的模板参数为了让一张哈希表同时支持 map 和 set需要把“节点数据是什么”和“key 在哪里”分开。templateclassK,classT,classKeyOfT,classHashclassHashTable;四个模板参数的含义如下参数含义Kkey 的类型T节点实际保存的数据类型KeyOfT从T中取出K的仿函数Hash把K转为哈希值的仿函数对于 setKintTconstintKeyOfT(key)key对于 mapKstring Tpairconststring,intKeyOfT(kv)kv.first这样底层代码只需要写一份K keyKeyOfT()(node-_data);size_t hashiHash()(key)%_tables.size();4. HashFunc 和哈希函数整型 key 可以直接转成size_ttemplateclassKstructHashFunc{size_toperator()(constKkey)const{returnstatic_castsize_t(key);}};字符串需要把多个字符组合成一个整数。常见做法是 BKDR 思想templatestructHashFuncstring{size_toperator()(conststringstr)const{size_t hash0;for(unsignedcharch:str){hashhash*131ch;}returnhash;}};哈希函数最重要的目标不是“绝对没有冲突”而是让数据尽量均匀地分布到各个桶中。哈希函数质量越差桶内链表越长查找效率越容易退化。5. HashTable 的插入、查找和删除5.1 插入插入的基本流程是根据KeyOfT取出 key先查找避免重复 key判断是否需要扩容重新计算桶下标创建节点并头插有效数据数量加一。核心代码可以写成pairIterator,boolInsert(constTdata){KeyOfT keyOf;constKkeykeyOf(data);if(Find(key)!End())return{Find(key),false};if(_n_tables.size()){Rehash(_tables.size()1);}size_t hashiHash()(key)%_tables.size();Node*nodenewNode(data);node-_next_tables[hashi];_tables[hashi]node;_n;return{Iterator(node,this),true};}源码中的扩容条件是_n_tables.size()也就是负载因子达到 1 时扩容。教学实现这样足够直观实际实现可以设置更小的阈值并提供max_load_factor。5.2 查找查找先定位桶再遍历桶内链表IteratorFind(constKkey){KeyOfT keyOf;size_t hashiHash()(key)%_tables.size();Node*cur_tables[hashi];while(cur){if(keyOf(cur-_data)key)returnIterator(cur,this);curcur-_next;}returnEnd();}平均情况下桶内节点很少查找接近O(1)如果大量 key 落入同一个桶最坏情况会退化到O(N)。5.3 删除删除就是单链表删除boolErase(constKkey){size_t hashiHash()(key)%_tables.size();Node*prevnullptr;Node*cur_tables[hashi];while(cur){if(KeyOfT()(cur-_data)key){if(prevnullptr)_tables[hashi]cur-_next;elseprev-_nextcur-_next;deletecur;--_n;returntrue;}prevcur;curcur-_next;}returnfalse;}6. rehash扩容不是简单复制数组当桶数量改变时key 对应的桶下标也可能改变old_indexhash(key)%old_bucket_count;new_indexhash(key)%new_bucket_count;因此扩容必须重新计算每个节点的新桶位这个过程叫 rehash。voidRehash(size_t n){vectorNode*newTables(NextPrime(n),nullptr);Hash hs;KeyOfT keyOf;for(size_t i0;i_tables.size();i){Node*cur_tables[i];while(cur){Node*nextcur-_next;size_t hashihs(keyOf(cur-_data))%newTables.size();cur-_nextnewTables[hashi];newTables[hashi]cur;curnext;}_tables[i]nullptr;}_tables.swap(newTables);}参考代码使用了一组递增素数作为桶数量例如53、97、193、389等。使用素数桶数量可以在一定程度上减少取模造成的规律性冲突。6.1 reserve 和 rehash 的区别标准库中reserve(n)表示希望容器至少能容纳n个元素容器会根据最大负载因子选择合适的桶数量rehash(n)直接要求桶数量至少达到某个值。两者都可能触发重新分桶。因为 rehash 会改变节点所在桶相关迭代器通常会失效所以不要在 rehash 前保存迭代器并在 rehash 后继续使用。7. 哈希表迭代器怎么实现红黑树迭代器可以根据父子关系寻找中序后继而哈希表没有全局有序关系因此迭代器需要保存两个信息Node*_node;constHashTable*_ht;_node表示当前节点_ht用来访问桶数组并寻找下一个非空桶。哈希表迭代器的operator分两种情况当前节点所在链表还有下一个节点直接移动到_next当前桶已经走完从当前桶的下一个位置开始扫描找到下一个非空桶的头节点。代码如下Selfoperator(){if(_nodenullptr)return*this;if(_node-_next){_node_node-_next;return*this;}KeyOfT keyOf;size_t bucketHash()(keyOf(_node-_data))%_ht-_tables.size();bucket;while(bucket_ht-_tables.size()_ht-_tables[bucket]nullptr){bucket;}_nodebucket_ht-_tables.size()?nullptr:_ht-_tables[bucket];return*this;}当前桶走完后继续寻找下一个非空桶。7.1 begin 和 endbegin()要返回第一个非空桶的第一个节点IteratorBegin(){for(size_t i0;i_tables.size();i){if(_tables[i])returnIterator(_tables[i],this);}returnEnd();}end()用空节点表示IteratorEnd(){returnIterator(nullptr,this);}遍历结束的条件就是it!end()8. const_iterator 和 key 不可修改8.1 set 的 key 不能修改如果unordered_setint允许通过迭代器把10改成100那么元素可能应该从原桶移动到新桶但容器并不知道这次修改哈希表结构就会被破坏。所以 set 的底层数据类型应当是HashTableK,constK,SetKeyOfT,Hash并且迭代器解引用得到const K。8.2 map 的 first 不能修改map 的节点类型应当是pairconstK,V这样it-secondvalue;// 正确it-firstkey;// 错误second修改不会影响桶位first修改会影响桶位所以必须限制first。8.3 迭代器模板可以通过Ref和Ptr同时支持普通迭代器与常量迭代器templateclassK,classT,classRef,classPtr,classKeyOfT,classHashstructHTIterator{usingNodeHashNodeT;Node*_node;constHashTableK,T,KeyOfT,Hash*_ht;Refoperator*()const{return_node-_data;}Ptroperator-()const{return_node-_data;}};建议把operator*、operator-声明为const因为读取迭代器本身不应该改变迭代器状态。9. 封装 myunordered_setmyunordered_set的KeyOfT最简单传入什么就返回什么namespacemy{templateclassK,classHashHashFuncKclassmyunordered_set{structSetKeyOfT{constKoperator()(constKkey)const{returnkey;}};usingTreeHashTableK,constK,SetKeyOfT,Hash;public:usingiteratortypenameTree::Iterator;usingconst_iteratortypenameTree::ConstIterator;iteratorbegin(){return_ht.Begin();}iteratorend(){return_ht.End();}const_iteratorbegin()const{return_ht.Begin();}const_iteratorend()const{return_ht.End();}pairiterator,boolinsert(constKkey){return_ht.Insert(key);}iteratorfind(constKkey){return_ht.Find(key);}boolerase(constKkey){return_ht.Erase(key);}private:Tree _ht;};}测试思路一致重复插入不会产生重复节点my::myunordered_setints;s.insert(45);s.insert(5);s.insert(45);for(autoe:s){coute ;}10. 封装 myunordered_mapmyunordered_map需要让KeyOfT从键值对中取firstnamespacemy{templateclassK,classV,classHashHashFuncKclassmyunordered_map{structMapKeyOfT{constKoperator()(constpairconstK,Vkv)const{returnkv.first;}};usingTreeHashTableK,pairconstK,V,MapKeyOfT,Hash;public:usingiteratortypenameTree::Iterator;usingconst_iteratortypenameTree::ConstIterator;iteratorbegin(){return_ht.Begin();}iteratorend(){return_ht.End();}const_iteratorbegin()const{return_ht.Begin();}const_iteratorend()const{return_ht.End();}pairiterator,boolinsert(constpairconstK,Vkv){return_ht.Insert(kv);}Voperator[](constKkey){autoretinsert({key,V()});returnret.first-second;}iteratorfind(constKkey){return_ht.Find(key);}boolerase(constKkey){return_ht.Erase(key);}private:Tree _ht;};}10.1 operator[] 的工作过程dict[C]language;可以拆成三步用C查找节点如果不存在插入{C, V()}返回second的引用并完成赋值。因此下面的代码会插入一个默认 valuedict[new_key];如果只是查找不希望产生新节点应使用find不要随意使用operator[]。11. 自定义类型的哈希函数内置类型可以直接使用默认哈希函数。自定义类型需要同时提供哈希函数相等比较。例如日期类型structDate{int_year;int_month;int_day;booloperator(constDateother)const{return_yearother._year_monthother._month_dayother._day;}};structDateHash{size_toperator()(constDated)const{size_t hash0;hashhash*131d._year;hashhash*131d._month;hashhash*131d._day;returnhash;}};my::myunordered_setDate,DateHashdates;dates.insert({2025,9,15});dates.insert({2025,9,18});哈希相等关系需要满足a b 为真 hash(a) hash(b)否则容器可能把逻辑上相等的对象放到不同桶中导致查找失败。12. 复杂度分析操作平均复杂度最坏复杂度insertO(1)O(N)findO(1)O(N)eraseO(1)O(N)全部遍历O(N)O(N)rehashO(N)O(N)平均O(1)建立在哈希函数分布均匀、负载因子合理、桶内链表较短的前提上。哈希表不是“任何情况下都绝对快”冲突严重时仍然可能退化。13. 总结封装myunordered_map和myunordered_set的关键不是写两个完全独立的容器而是把共同逻辑抽到HashTable哈希函数负责计算桶链地址法负责解决冲突KeyOfT负责提取 keyHash负责支持不同 key 类型迭代器负责桶内和跨桶遍历const K或pairconst K,V防止 key 被修改rehash负责扩容后的重新分桶。最终的适配关系可以概括为set:TconstKKeyOfT(data)data map:TpairconstK,VKeyOfT(data)data.first理解这层关系后unordered_map和unordered_set就不再是两个神秘的标准库容器而是同一套哈希表框架上的两个不同适配器。 C++ 哈希表封装 unordered_map 和 unordered_set
1. 为什么要封装 myunordered_map 和 myunordered_set前面我们已经知道unordered_map和unordered_set的底层核心是哈希表。unordered_set保存单个 keyunordered_map保存pairconst K, V两者都需要根据 key 计算桶下标两者都需要处理哈希冲突两者都需要查找、插入、删除和遍历。如果分别实现两个容器就会重复编写大量哈希表代码。更合理的方式是先实现一个通用的HashTableK,T,KeyOfT,Hash然后让myunordered_map和myunordered_set只负责适配数据类型。这是一种典型的“底层复用上层适配”设计HashTable负责数据结构KeyOfT负责从节点数据中取出 keyHash负责把 key 转换成哈希值map/set封装层负责暴露不同的接口。2. 哈希桶的基本结构链地址法的哈希表通常由两部分组成一个桶数组每个桶下面的一条节点链表。节点结构可以写成templateclassTstructHashNode{T _data;HashNodeT*_next;explicitHashNode(constTdata):_data(data),_next(nullptr){}};哈希表内部保存桶数组vectorNode*_tables;size_t _n0;插入时先计算size_t hashihash(key)%_tables.size();然后把新节点头插到_tables[hashi]对应的链表中。头插的好处是实现简单时间复杂度是O(1)代价是同一个桶内的遍历顺序与插入顺序相反而且整个unordered容器本身也不保证有序。3. 通用 HashTable 的模板参数为了让一张哈希表同时支持 map 和 set需要把“节点数据是什么”和“key 在哪里”分开。templateclassK,classT,classKeyOfT,classHashclassHashTable;四个模板参数的含义如下参数含义Kkey 的类型T节点实际保存的数据类型KeyOfT从T中取出K的仿函数Hash把K转为哈希值的仿函数对于 setKintTconstintKeyOfT(key)key对于 mapKstring Tpairconststring,intKeyOfT(kv)kv.first这样底层代码只需要写一份K keyKeyOfT()(node-_data);size_t hashiHash()(key)%_tables.size();4. HashFunc 和哈希函数整型 key 可以直接转成size_ttemplateclassKstructHashFunc{size_toperator()(constKkey)const{returnstatic_castsize_t(key);}};字符串需要把多个字符组合成一个整数。常见做法是 BKDR 思想templatestructHashFuncstring{size_toperator()(conststringstr)const{size_t hash0;for(unsignedcharch:str){hashhash*131ch;}returnhash;}};哈希函数最重要的目标不是“绝对没有冲突”而是让数据尽量均匀地分布到各个桶中。哈希函数质量越差桶内链表越长查找效率越容易退化。5. HashTable 的插入、查找和删除5.1 插入插入的基本流程是根据KeyOfT取出 key先查找避免重复 key判断是否需要扩容重新计算桶下标创建节点并头插有效数据数量加一。核心代码可以写成pairIterator,boolInsert(constTdata){KeyOfT keyOf;constKkeykeyOf(data);if(Find(key)!End())return{Find(key),false};if(_n_tables.size()){Rehash(_tables.size()1);}size_t hashiHash()(key)%_tables.size();Node*nodenewNode(data);node-_next_tables[hashi];_tables[hashi]node;_n;return{Iterator(node,this),true};}源码中的扩容条件是_n_tables.size()也就是负载因子达到 1 时扩容。教学实现这样足够直观实际实现可以设置更小的阈值并提供max_load_factor。5.2 查找查找先定位桶再遍历桶内链表IteratorFind(constKkey){KeyOfT keyOf;size_t hashiHash()(key)%_tables.size();Node*cur_tables[hashi];while(cur){if(keyOf(cur-_data)key)returnIterator(cur,this);curcur-_next;}returnEnd();}平均情况下桶内节点很少查找接近O(1)如果大量 key 落入同一个桶最坏情况会退化到O(N)。5.3 删除删除就是单链表删除boolErase(constKkey){size_t hashiHash()(key)%_tables.size();Node*prevnullptr;Node*cur_tables[hashi];while(cur){if(KeyOfT()(cur-_data)key){if(prevnullptr)_tables[hashi]cur-_next;elseprev-_nextcur-_next;deletecur;--_n;returntrue;}prevcur;curcur-_next;}returnfalse;}6. rehash扩容不是简单复制数组当桶数量改变时key 对应的桶下标也可能改变old_indexhash(key)%old_bucket_count;new_indexhash(key)%new_bucket_count;因此扩容必须重新计算每个节点的新桶位这个过程叫 rehash。voidRehash(size_t n){vectorNode*newTables(NextPrime(n),nullptr);Hash hs;KeyOfT keyOf;for(size_t i0;i_tables.size();i){Node*cur_tables[i];while(cur){Node*nextcur-_next;size_t hashihs(keyOf(cur-_data))%newTables.size();cur-_nextnewTables[hashi];newTables[hashi]cur;curnext;}_tables[i]nullptr;}_tables.swap(newTables);}参考代码使用了一组递增素数作为桶数量例如53、97、193、389等。使用素数桶数量可以在一定程度上减少取模造成的规律性冲突。6.1 reserve 和 rehash 的区别标准库中reserve(n)表示希望容器至少能容纳n个元素容器会根据最大负载因子选择合适的桶数量rehash(n)直接要求桶数量至少达到某个值。两者都可能触发重新分桶。因为 rehash 会改变节点所在桶相关迭代器通常会失效所以不要在 rehash 前保存迭代器并在 rehash 后继续使用。7. 哈希表迭代器怎么实现红黑树迭代器可以根据父子关系寻找中序后继而哈希表没有全局有序关系因此迭代器需要保存两个信息Node*_node;constHashTable*_ht;_node表示当前节点_ht用来访问桶数组并寻找下一个非空桶。哈希表迭代器的operator分两种情况当前节点所在链表还有下一个节点直接移动到_next当前桶已经走完从当前桶的下一个位置开始扫描找到下一个非空桶的头节点。代码如下Selfoperator(){if(_nodenullptr)return*this;if(_node-_next){_node_node-_next;return*this;}KeyOfT keyOf;size_t bucketHash()(keyOf(_node-_data))%_ht-_tables.size();bucket;while(bucket_ht-_tables.size()_ht-_tables[bucket]nullptr){bucket;}_nodebucket_ht-_tables.size()?nullptr:_ht-_tables[bucket];return*this;}当前桶走完后继续寻找下一个非空桶。7.1 begin 和 endbegin()要返回第一个非空桶的第一个节点IteratorBegin(){for(size_t i0;i_tables.size();i){if(_tables[i])returnIterator(_tables[i],this);}returnEnd();}end()用空节点表示IteratorEnd(){returnIterator(nullptr,this);}遍历结束的条件就是it!end()8. const_iterator 和 key 不可修改8.1 set 的 key 不能修改如果unordered_setint允许通过迭代器把10改成100那么元素可能应该从原桶移动到新桶但容器并不知道这次修改哈希表结构就会被破坏。所以 set 的底层数据类型应当是HashTableK,constK,SetKeyOfT,Hash并且迭代器解引用得到const K。8.2 map 的 first 不能修改map 的节点类型应当是pairconstK,V这样it-secondvalue;// 正确it-firstkey;// 错误second修改不会影响桶位first修改会影响桶位所以必须限制first。8.3 迭代器模板可以通过Ref和Ptr同时支持普通迭代器与常量迭代器templateclassK,classT,classRef,classPtr,classKeyOfT,classHashstructHTIterator{usingNodeHashNodeT;Node*_node;constHashTableK,T,KeyOfT,Hash*_ht;Refoperator*()const{return_node-_data;}Ptroperator-()const{return_node-_data;}};建议把operator*、operator-声明为const因为读取迭代器本身不应该改变迭代器状态。9. 封装 myunordered_setmyunordered_set的KeyOfT最简单传入什么就返回什么namespacemy{templateclassK,classHashHashFuncKclassmyunordered_set{structSetKeyOfT{constKoperator()(constKkey)const{returnkey;}};usingTreeHashTableK,constK,SetKeyOfT,Hash;public:usingiteratortypenameTree::Iterator;usingconst_iteratortypenameTree::ConstIterator;iteratorbegin(){return_ht.Begin();}iteratorend(){return_ht.End();}const_iteratorbegin()const{return_ht.Begin();}const_iteratorend()const{return_ht.End();}pairiterator,boolinsert(constKkey){return_ht.Insert(key);}iteratorfind(constKkey){return_ht.Find(key);}boolerase(constKkey){return_ht.Erase(key);}private:Tree _ht;};}测试思路一致重复插入不会产生重复节点my::myunordered_setints;s.insert(45);s.insert(5);s.insert(45);for(autoe:s){coute ;}10. 封装 myunordered_mapmyunordered_map需要让KeyOfT从键值对中取firstnamespacemy{templateclassK,classV,classHashHashFuncKclassmyunordered_map{structMapKeyOfT{constKoperator()(constpairconstK,Vkv)const{returnkv.first;}};usingTreeHashTableK,pairconstK,V,MapKeyOfT,Hash;public:usingiteratortypenameTree::Iterator;usingconst_iteratortypenameTree::ConstIterator;iteratorbegin(){return_ht.Begin();}iteratorend(){return_ht.End();}const_iteratorbegin()const{return_ht.Begin();}const_iteratorend()const{return_ht.End();}pairiterator,boolinsert(constpairconstK,Vkv){return_ht.Insert(kv);}Voperator[](constKkey){autoretinsert({key,V()});returnret.first-second;}iteratorfind(constKkey){return_ht.Find(key);}boolerase(constKkey){return_ht.Erase(key);}private:Tree _ht;};}10.1 operator[] 的工作过程dict[C]language;可以拆成三步用C查找节点如果不存在插入{C, V()}返回second的引用并完成赋值。因此下面的代码会插入一个默认 valuedict[new_key];如果只是查找不希望产生新节点应使用find不要随意使用operator[]。11. 自定义类型的哈希函数内置类型可以直接使用默认哈希函数。自定义类型需要同时提供哈希函数相等比较。例如日期类型structDate{int_year;int_month;int_day;booloperator(constDateother)const{return_yearother._year_monthother._month_dayother._day;}};structDateHash{size_toperator()(constDated)const{size_t hash0;hashhash*131d._year;hashhash*131d._month;hashhash*131d._day;returnhash;}};my::myunordered_setDate,DateHashdates;dates.insert({2025,9,15});dates.insert({2025,9,18});哈希相等关系需要满足a b 为真 hash(a) hash(b)否则容器可能把逻辑上相等的对象放到不同桶中导致查找失败。12. 复杂度分析操作平均复杂度最坏复杂度insertO(1)O(N)findO(1)O(N)eraseO(1)O(N)全部遍历O(N)O(N)rehashO(N)O(N)平均O(1)建立在哈希函数分布均匀、负载因子合理、桶内链表较短的前提上。哈希表不是“任何情况下都绝对快”冲突严重时仍然可能退化。13. 总结封装myunordered_map和myunordered_set的关键不是写两个完全独立的容器而是把共同逻辑抽到HashTable哈希函数负责计算桶链地址法负责解决冲突KeyOfT负责提取 keyHash负责支持不同 key 类型迭代器负责桶内和跨桶遍历const K或pairconst K,V防止 key 被修改rehash负责扩容后的重新分桶。最终的适配关系可以概括为set:TconstKKeyOfT(data)data map:TpairconstK,VKeyOfT(data)data.first理解这层关系后unordered_map和unordered_set就不再是两个神秘的标准库容器而是同一套哈希表框架上的两个不同适配器。