1. 为什么要封装 myunordered_map 和 myunordered_set

前面我们已经知道，unordered_map和unordered_set的底层核心是哈希表。

• unordered_set保存单个 key；
• unordered_map保存pair<const K, V>；
• 两者都需要根据 key 计算桶下标；
• 两者都需要处理哈希冲突；
• 两者都需要查找、插入、删除和遍历。

如果分别实现两个容器，就会重复编写大量哈希表代码。更合理的方式是先实现一个通用的：

HashTable<K,T,KeyOfT,Hash>

然后让myunordered_map和myunordered_set只负责适配数据类型。

这是一种典型的“底层复用，上层适配”设计：

• HashTable负责数据结构；
• KeyOfT负责从节点数据中取出 key；
• Hash负责把 key 转换成哈希值；
• map/set封装层负责暴露不同的接口。

2. 哈希桶的基本结构

链地址法的哈希表通常由两部分组成：

1. 一个桶数组；
2. 每个桶下面的一条节点链表。

节点结构可以写成：

template<classT>structHashNode{T _data;HashNode<T>*_next;explicitHashNode(constT&data):_data(data),_next(nullptr){}};

哈希表内部保存桶数组：

vector<Node*>_tables;size_t _n=0;

插入时先计算：

size_t hashi=hash(key)%_tables.size();

然后把新节点头插到_tables[hashi]对应的链表中。

头插的好处是实现简单，时间复杂度是O(1)；代价是同一个桶内的遍历顺序与插入顺序相反，而且整个unordered容器本身也不保证有序。

3. 通用 HashTable 的模板参数

为了让一张哈希表同时支持 map 和 set，需要把“节点数据是什么”和“key 在哪里”分开。

template<classK,classT,classKeyOfT,classHash>classHashTable;

四个模板参数的含义如下：

对于 set：

K=intT=constintKeyOfT(key)=key

对于 map：

K=string T=pair<conststring,int>KeyOfT(kv)=kv.first

这样，底层代码只需要写一份：

K key=KeyOfT()(node->_data);size_t hashi=Hash()(key)%_tables.size();

4. HashFunc 和哈希函数

整型 key 可以直接转成size_t：

template<classK>structHashFunc{size_toperator()(constK&key)const{returnstatic_cast<size_t>(key);}};

字符串需要把多个字符组合成一个整数。常见做法是 BKDR 思想：

template<>structHashFunc<string>{size_toperator()(conststring&str)const{size_t hash=0;for(unsignedcharch:str){hash=hash*131+ch;}returnhash;}};

哈希函数最重要的目标不是“绝对没有冲突”，而是让数据尽量均匀地分布到各个桶中。哈希函数质量越差，桶内链表越长，查找效率越容易退化。

5. HashTable 的插入、查找和删除

5.1 插入

插入的基本流程是：

1. 根据KeyOfT取出 key；
2. 先查找，避免重复 key；
3. 判断是否需要扩容；
4. 重新计算桶下标；
5. 创建节点并头插；
6. 有效数据数量加一。

核心代码可以写成：

pair<Iterator,bool>Insert(constT&data){KeyOfT keyOf;constK&key=keyOf(data);if(Find(key)!=End())return{Find(key),false};if(_n==_tables.size()){Rehash(_tables.size()+1);}size_t hashi=Hash()(key)%_tables.size();Node*node=newNode(data);node->_next=_tables[hashi];_tables[hashi]=node;++_n;return{Iterator(node,this),true};}

源码中的扩容条件是：

_n==_tables.size()

也就是负载因子达到 1 时扩容。教学实现这样足够直观；实际实现可以设置更小的阈值，并提供max_load_factor。

5.2 查找

查找先定位桶，再遍历桶内链表：

IteratorFind(constK&key){KeyOfT keyOf;size_t hashi=Hash()(key)%_tables.size();Node*cur=_tables[hashi];while(cur){if(keyOf(cur->_data)==key)returnIterator(cur,this);cur=cur->_next;}returnEnd();}

平均情况下桶内节点很少，查找接近O(1)；如果大量 key 落入同一个桶，最坏情况会退化到O(N)。

5.3 删除

删除就是单链表删除：

boolErase(constK&key){size_t hashi=Hash()(key)%_tables.size();Node*prev=nullptr;Node*cur=_tables[hashi];while(cur){if(KeyOfT()(cur->_data)==key){if(prev==nullptr)_tables[hashi]=cur->_next;elseprev->_next=cur->_next;deletecur;--_n;returntrue;}prev=cur;cur=cur->_next;}returnfalse;}

6. rehash：扩容不是简单复制数组

当桶数量改变时，key 对应的桶下标也可能改变：

old_index=hash(key)%old_bucket_count;new_index=hash(key)%new_bucket_count;

因此扩容必须重新计算每个节点的新桶位，这个过程叫 rehash。

voidRehash(size_t n){vector<Node*>newTables(NextPrime(n),nullptr);Hash hs;KeyOfT keyOf;for(size_t i=0;i<_tables.size();++i){Node*cur=_tables[i];while(cur){Node*next=cur->_next;size_t hashi=hs(keyOf(cur->_data))%newTables.size();cur->_next=newTables[hashi];newTables[hashi]=cur;cur=next;}_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++分两种情况：

1. 当前节点所在链表还有下一个节点，直接移动到_next；
2. 当前桶已经走完，从当前桶的下一个位置开始扫描，找到下一个非空桶的头节点。

代码如下：

Self&operator++(){if(_node==nullptr)return*this;if(_node->_next){_node=_node->_next;return*this;}KeyOfT keyOf;size_t bucket=Hash()(keyOf(_node->_data))%_ht->_tables.size();++bucket;while(bucket<_ht->_tables.size()&&_ht->_tables[bucket]==nullptr){++bucket;}_node=bucket==_ht->_tables.size()?nullptr:_ht->_tables[bucket];return*this;}

当前桶走完后，继续寻找下一个非空桶。

7.1 begin 和 end

begin()要返回第一个非空桶的第一个节点：

IteratorBegin(){for(size_t i=0;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_set<int>允许通过迭代器把10改成100，那么元素可能应该从原桶移动到新桶，但容器并不知道这次修改，哈希表结构就会被破坏。

所以 set 的底层数据类型应当是：

HashTable<K,constK,SetKeyOfT,Hash>

并且迭代器解引用得到const K&。

8.2 map 的 first 不能修改

map 的节点类型应当是：

pair<constK,V>

这样：

it->second=value;// 正确it->first=key;// 错误

second修改不会影响桶位，first修改会影响桶位，所以必须限制first。

8.3 迭代器模板

可以通过Ref和Ptr同时支持普通迭代器与常量迭代器：

template<classK,classT,classRef,classPtr,classKeyOfT,classHash>structHTIterator{usingNode=HashNode<T>;Node*_node;constHashTable<K,T,KeyOfT,Hash>*_ht;Refoperator*()const{return_node->_data;}Ptroperator->()const{return&_node->_data;}};

建议把operator*、operator->声明为const，因为读取迭代器本身不应该改变迭代器状态。

9. 封装 myunordered_set

myunordered_set的KeyOfT最简单，传入什么就返回什么：

namespacemy{template<classK,classHash=HashFunc<K>>classmyunordered_set{structSetKeyOfT{constK&operator()(constK&key)const{returnkey;}};usingTree=HashTable<K,constK,SetKeyOfT,Hash>;public:usingiterator=typenameTree::Iterator;usingconst_iterator=typenameTree::ConstIterator;iteratorbegin(){return_ht.Begin();}iteratorend(){return_ht.End();}const_iteratorbegin()const{return_ht.Begin();}const_iteratorend()const{return_ht.End();}pair<iterator,bool>insert(constK&key){return_ht.Insert(key);}iteratorfind(constK&key){return_ht.Find(key);}boolerase(constK&key){return_ht.Erase(key);}private:Tree _ht;};}

测试思路一致，重复插入不会产生重复节点：

my::myunordered_set<int>s;s.insert(45);s.insert(5);s.insert(45);for(autoe:s){cout<<e<<" ";}

10. 封装 myunordered_map

myunordered_map需要让KeyOfT从键值对中取first：

namespacemy{template<classK,classV,classHash=HashFunc<K>>classmyunordered_map{structMapKeyOfT{constK&operator()(constpair<constK,V>&kv)const{returnkv.first;}};usingTree=HashTable<K,pair<constK,V>,MapKeyOfT,Hash>;public:usingiterator=typenameTree::Iterator;usingconst_iterator=typenameTree::ConstIterator;iteratorbegin(){return_ht.Begin();}iteratorend(){return_ht.End();}const_iteratorbegin()const{return_ht.Begin();}const_iteratorend()const{return_ht.End();}pair<iterator,bool>insert(constpair<constK,V>&kv){return_ht.Insert(kv);}V&operator[](constK&key){autoret=insert({key,V()});returnret.first->second;}iteratorfind(constK&key){return_ht.Find(key);}boolerase(constK&key){return_ht.Erase(key);}private:Tree _ht;};}

10.1 operator[] 的工作过程

dict["C++"]="language";

可以拆成三步：

1. 用"C++"查找节点；
2. 如果不存在，插入{"C++", V()}；
3. 返回second的引用并完成赋值。

因此下面的代码会插入一个默认 value：

dict["new_key"];

如果只是查找，不希望产生新节点，应使用find，不要随意使用operator[]。

11. 自定义类型的哈希函数

内置类型可以直接使用默认哈希函数。自定义类型需要同时提供：

1. 哈希函数；
2. 相等比较。

例如日期类型：

structDate{int_year;int_month;int_day;booloperator==(constDate&other)const{return_year==other._year&&_month==other._month&&_day==other._day;}};structDateHash{size_toperator()(constDate&d)const{size_t hash=0;hash=hash*131+d._year;hash=hash*131+d._month;hash=hash*131+d._day;returnhash;}};my::myunordered_set<Date,DateHash>dates;dates.insert({2025,9,15});dates.insert({2025,9,18});

哈希相等关系需要满足：

a == b 为真 => hash(a) == hash(b)

否则容器可能把逻辑上相等的对象放到不同桶中，导致查找失败。

12. 复杂度分析

平均O(1)建立在哈希函数分布均匀、负载因子合理、桶内链表较短的前提上。哈希表不是“任何情况下都绝对快”，冲突严重时仍然可能退化。

13. 总结

封装myunordered_map和myunordered_set的关键，不是写两个完全独立的容器，而是把共同逻辑抽到HashTable：

• 哈希函数负责计算桶；
• 链地址法负责解决冲突；
• KeyOfT负责提取 key；
• Hash负责支持不同 key 类型；
• 迭代器负责桶内和跨桶遍历；
• const K或pair<const K,V>防止 key 被修改；
• rehash负责扩容后的重新分桶。

最终的适配关系可以概括为：

set:T=constKKeyOfT(data)=data map:T=pair<constK,V>KeyOfT(data)=data.first

理解这层关系后，unordered_map和unordered_set就不再是两个神秘的标准库容器，而是同一套哈希表框架上的两个不同适配器。