哈希桶底层写完再用同一套代码同时封装出unordered_map和unordered_set是我数据结构进阶阶段收获最大的一次练习。哈希桶其实就是链地址法处理哈希冲突的一张表每个桶是一个单链表UnorderedSet只存键UnorderedMap存键值对表面上是两个容器底层完全可以共用同一个哈希表骨架。这篇文章我把整个封装过程拆开讲重点放在三个地方模板参数怎么设计、迭代器怎么跨桶移动、operator[]为什么能读又能写。适合已经会写基本链表和模板想深入理解 STL 容器实现、或者准备面试手撕哈希表的朋友照着思路可以自己完整复现一套。1. 项目整体设计与核心思路1.1 哈希桶是什么为什么这次选它而不是开放定址法哈希表本质上是“用数组下标快速定位元素”理想情况一个 key 对应一个下标时间复杂度 O(1)。但哈希函数不可能是完美的不同的 key 可能算到同一个下标这就是哈希冲突。解决冲突有两大流派开放定址法线性探测、二次探测和链地址法也就是哈希桶。开放定址法的思路是冲突了就往下一个空位置放删除节点时必须打上“已删除”标记否则会影响后续查找负载因子还得严格控制不然表很快就满了。哈希桶的思路就直观得多数组每个下标挂一条单链表冲突的节点直接串在这条链表上就像每个格子里放一个抽屉抽屉一层层摞着放不下的东西。我这次选择哈希桶理由很实在。第一实现简单插入、查找、删除只需要维护单链表不需要处理“伪删除”标记。第二删除天然安全找到节点直接摘下来 delete 就行不像开放定址法还要考虑探测序列的连续性。第三负载因子可以承受得更高就算每个桶平均挂了两三个节点查找也只是多走几步链表。STL 里 unordered 系列容器的实现底层思路也和链地址法一致手搓一遍等于把标准库的黑盒打开了一角。第四面试官问哈希表时开链法几乎是必问考点落地过一次和只看书的感觉完全不一样。可能有人会问那直接用std::vectorstd::liststd::pairK,V不就行了不行。这样做虽然也实现了桶的概念但性能上会多一层 list 节点的分配和管理而且迭代器结构也和真正哈希表的迭代器不同。我们要的是自己控制的单链表节点每个节点就是data next紧凑、好搬移、扩容时能把旧节点直接摘下来挂到新桶里不用复制一份再删掉。1.2 封装复用为什么一份哈希表能同时变成 Map 和 Set核心思路是这样的哈希表的节点里存什么类型由模板参数T决定。对UnorderedSet来说T K节点只存 key对UnorderedMap来说T pairK, V节点存完整的键值对。哈希表本身只负责管理桶、链表、扩容这些通用逻辑它不关心T内部长什么样。但问题来了插入、查找、删除都得拿 key 去比对和计算哈希值。如果T是pairK,V那 key 就是pair.first如果T就是K那 key 就是它自己。哈希表怎么知道怎么从T里取 key答案是仿函数。用户提供一个KeyOfT这个仿函数只有一个职责给一个T类型的对象返回对应的 key 引用。struct MapKeyOfT { const K operator()(const pairK, V kv) const { return kv.first; } }; struct SetKeyOfT { const K operator()(const K key) const { return key; } };这一个仿函数就把 map 和 set 的统一性问题解决了。哈希表内部所有需要 key 的地方一律KeyOfT()(data)来取完全不关心 data 到底是个 pair 还是个裸 key。这也是整个封装项目里最核心的一个设计点把“存储对象”和“从存储对象里提取 key 的方式”解耦。后面不管是写红黑树版的 map/set还是其他需要 key 的容器这套仿函数提取思路都能直接平移。2. 底层哈希桶结构与模板参数选型2.1 模板参数逐个说清楚K、T、KeyOfT、Hash 各管什么哈希桶这个类的模板参数我最终定为下面四个templateclass K, class T, class KeyOfT, class Hash HashFuncK class HashTable;K是 key 的类型比如int、string、自定义的Date。T是节点真正存储的数据类型在UnorderedMap里是pairK, V在UnorderedSet里就是K。KeyOfT是一个仿函数类型用来从T里拿到K。Hash是一个哈希函数对象用来把K转成size_t的哈希值。这四个参数里K和T解决“存什么”的问题KeyOfT解决“key 怎么取”的问题Hash解决“哈希值怎么算”的问题。这样拆开之后HashTable 内部逻辑就非常干净了。插入一个数据时先用KeyOfT拿到 key再用Hash计算哈希值然后哈希值 % 桶数得到桶号最后在对应桶的单链表里操作。哈希函数这里要注意不能直接用key % 桶数。原因是很多类型不支持取模比如string、pair而且负数取模还有符号问题。所以哈希表的做法分两步先把 key 通过Hash转成一个size_t的哈希值再用这个哈希值对桶数取模。整型直接转字符串就得用类似 BKDR 的字符串哈希算法。我会在后面常见问题里专门写这个。2.2 节点结构和哈希表成员定义节点用单链表结构成员就两个数据域_data和指向下一个节点的指针_next。templateclass T struct HashNode { T _data; HashNodeT* _next; HashNode(const T data) : _data(data) , _next(nullptr) {} };哈希表本身的成员也简单就是一个vectorNode*和一个元素个数计数器。templateclass K, class T, class KeyOfT, class Hash class HashTable { typedef HashNodeT Node; public: // 迭代器相关声明后面讲 private: vectorNode* _tables; size_t _n 0; };_tables的每个元素是一个链表的头指针。_tables[i]为nullptr表示第 i 个桶是空的不为空就指向桶里第一条链表的第一个节点。这个桶数组本身只存指针不存节点对象所以扩容的时候搬移的是一个个节点指针不是整个节点拷贝。明白这一点才能理解扩容那一步为什么能写出“拆旧节点挂新桶”的骚操作。2.3 载荷因子与扩容策略为什么要控制在 0.7 左右载荷因子定义为α 存储的元素个数 / 桶个数它直接反映冲突的剧烈程度。α 越大每个桶平均挂的节点越多查找时链表遍历长度就越长哈希表的优势就没了。α 越小空桶越多内存浪费越严重。实测下来 0.7~0.8 是一个比较平衡的点这也是很多工业级哈希表的经验选择。判断是否扩容时不要写浮点比较有精度问题还容易绕晕。推荐用整数乘法判断if (_n 0 || 10 * _n 7 * _tables.size()) { // 触发扩容 }10 * _n 7 * _tables.size()等价于_n / _tables.size() 0.7但全程没有浮点数。初次插入时_tables是空的直接给它 10 个桶然后正常往里面挂。扩容系数我选 2 倍也就是新桶数组大小是旧的两倍。为什么是 2 倍不是 1.5 倍哈希表的取模分布和扩容倍数有一定关系2 倍扩容在工程上实现简单节点重新分布之后冲突往往会有比较明显的缓解而且内存分配器对 2 的倍数的内存块也友好一些。扩容这一步是整个哈希桶最容易写错的地方常见的错误是直接vector拷贝然后旧节点继续用旧数组的映射关系导致取模混乱。正确做法是搬移节点而不是新建节点。遍历旧表所有桶把每个节点摘下来按新表的容量重新计算桶号然后头插到新表对应桶里。旧节点没有被释放只是换了位置挂最后释放旧表。这样省了一次new/delete循环性能也好。3. 核心实现插入、删除、迭代器到底怎么写3.1 插入去重、头插、扩容三步走插入接口的返回类型设计成pairiterator, bool这是对标 STL 的做法。bool表示插入是否成功iterator指向的是新插入的节点或者已存在的那条旧节点。先看核心代码pairiterator, bool Insert(const T data) { KeyOfT kot; Hash hs; // 空表或载荷因子超过阈值先扩容 if (_n 0 || 10 * _n 7 * _tables.size()) { size_t newSize _tables.size() 0 ? 10 : _tables.size() * 2; vectorNode* newTables; newTables.resize(newSize); for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; size_t hashi hs(kot(cur-_data)) % newTables.size(); cur-_next newTables[hashi]; newTables[hashi] cur; cur next; } _tables[i] nullptr; } _tables.swap(newTables); } // 计算桶号在对应链表中查找 size_t hashi hs(kot(data)) % _tables.size(); Node* cur _tables[hashi]; while (cur) { if (kot(cur-_data) kot(data)) { return make_pair(iterator(cur, this), false); } cur cur-_next; } // 没有重复头插新节点 Node* newnode new Node(data); newnode-_next _tables[hashi]; _tables[hashi] newnode; _n; return make_pair(iterator(newnode, this), true); }头插而不是尾插是因为单链表尾插需要先遍历到末尾头插永远 O(1)。既然哈希表不保证元素顺序头插天然合适。还有一个隐藏的好处扩容搬移时也是从头往后摘节点顺序刚好和头插对应逻辑不会乱。pairiterator, bool这个返回类型对 map 的operator[]特别关键后面封装UnorderedMap时会看到它的妙用。这里迭代器构造带上了this指针原因在迭代器那一节再展开先记住这个动作。3.2 查找与删除单链表操作的水位线查找逻辑不复杂算桶号遍历链表用KeyOfT拿 key 来比对找到返回迭代器找不到返回end()。iterator Find(const K key) { KeyOfT kot; Hash hs; if (_tables.empty()) { return iterator(nullptr, this); } size_t hashi hs(key) % _tables.size(); Node* cur _tables[hashi]; while (cur) { if (kot(cur-_data) key) { return iterator(cur, this); } cur cur-_next; } return iterator(nullptr, this); }删除时要特别注意单链表删节点必须维护前驱指针否则摘不掉。如果删的是头节点要直接更新_tables[hashi]指向下一个节点如果删的是中间节点让前驱的_next绕过当前节点。两种情况都要记得delete cur和--_n。bool Erase(const K key) { KeyOfT kot; Hash hs; if (_tables.empty()) { return false; } size_t hashi hs(key) % _tables.size(); Node* prev nullptr; Node* cur _tables[hashi]; while (cur) { if (kot(cur-_data) key) { if (prev nullptr) { _tables[hashi] cur-_next; } else { prev-_next cur-_next; } delete cur; --_n; return true; } prev cur; cur cur-_next; } return false; }我之前写第一版的时候偷懒想用“记录当前节点的 next然后把这个节点值拷贝给前驱”的方式省前驱指针写出来又绕又容易越界。后来老老实实加一个prev代码立刻变清晰了。链表操作这种东西宁可多一个指针不要多一份聪明。3.3 迭代器设计为什么迭代器要同时持有节点指针和哈希表指针哈希桶的迭代器比普通链表迭代器多了一层复杂性。普通链表迭代器持有一个节点指针就够了就是node node-next。但哈希桶的节点走到单链表末尾之后next是空指针这个时候不能直接停在空指针而是要跳到下一个非空桶的第一个节点。问题来了下一个非空桶是哪个取决于迭代器属于哪个哈希表对象。所以迭代器只存节点指针完全不够还必须保存一份哈希表的指针。templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash struct HashIterator { typedef HashNodeT Node; typedef HashIteratorK, T, Ref, Ptr, KeyOfT, Hash Self; Node* _node; const HashTableK, T, KeyOfT, Hash* _ht; HashIterator(Node* node, const HashTableK, T, KeyOfT, Hash* ht) : _node(node) , _ht(ht) {} Ref operator*() { return _node-_data; } Ptr operator-() { return _node-_data; } Self operator() { if (_node-_next) { _node _node-_next; } else { KeyOfT kot; Hash hs; size_t hashi hs(kot(_node-_data)) % _ht-_tables.size(); hashi; while (hashi _ht-_tables.size() _ht-_tables[hashi] nullptr) { hashi; } _node (hashi _ht-_tables.size()) ? nullptr : _ht-_tables[hashi]; } return *this; } Self operator(int) { Self tmp *this; (*this); return tmp; } bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } };operator的边界情况在于当前节点是所在桶的最后一个节点时要先根据当前节点的 key 算出它在哪个桶然后从下一个桶开始往后扫直到找到第一个非空桶。如果后面全是空桶说明已经到end()也就是节点指针为nullptr。这里我通过_node-_data来重新计算hashi比在迭代器里额外记录桶号更省事也不容易出错。因为迭代器知道节点节点的 key 通过KeyOfT一取就能拿到再哈希取模就得到当前桶号。为什么不直接用_node-_next为空来判断已经到最后一个节点就直接置空因为哈希表还有下一个非空桶必须跳过去。这是哈希桶迭代器和顺序容器迭代器最大的区别。很多第一次写的人倒在这一步迭代器走到链表尾就停了结果遍历只能输出一个桶的数据。关于 const 版本模板参数Ref和Ptr就是干这个的typedef HashIteratorK, T, T, T*, KeyOfT, Hash iterator; typedef HashIteratorK, T, const T, const T*, KeyOfT, Hash const_iterator;一份迭代器类通过模板参数生成了普通版本和 const 版本。普通版本operator*返回T可以修改元素const 版本返回const T只能读。后面封装 Set 时这个 const 版本直接帮了大忙。begin()的实现也要注意从头遍历桶数组跳过所有空桶找到第一个非空桶的第一个节点。如果全表为空begin()就等于end()也就是节点指针为nullptr。4. UnorderedMap 和 UnorderedSet 的封装技巧4.1 仿函数 KeyOfT两个容器统一到一套底层的关键封装层其实没什么魔法就是给 HashTable 指定合适的模板参数。UnorderedSet里T传KKeyOfT传SetKeyOfTUnorderedMap里T传pairK,VKeyOfT传MapKeyOfT。templateclass K, class Hash HashFuncK class UnorderedSet { struct SetKeyOfT { const K operator()(const K key) const { return key; } }; HashTableK, K, SetKeyOfT, Hash _ht; public: typedef typename HashTableK, K, SetKeyOfT, Hash::const_iterator iterator; typedef typename HashTableK, K, SetKeyOfT, Hash::const_iterator const_iterator; iterator begin() { return _ht.CBegin(); } const_iterator begin() const { return _ht.CBegin(); } iterator end() { return _ht.CEnd(); } pairiterator, bool Insert(const K key) { return _ht.Insert(key); } bool Erase(const K key) { return _ht.Erase(key); } iterator Find(const K key) { return _ht.Find(key); } };注意这里UnorderedSet的iterator直接 typedef 成了哈希表的const_iterator。这是故意的。Set 的语义是 key 不可修改如果开放普通迭代器用户就能通过迭代器改掉 key把整个哈希表的组织结构破坏掉。我不打算在 Set 内部保留普通迭代器直接把对外暴露的迭代器类型锁死成 const 版本。为了让 Set 能拿到 const 迭代器HashTable 里还提供一个CBegin()和CEnd()它们返回 const 迭代器。Set 的begin()不管对象是不是 const都调用CBegin()返回值类型自然就是 const 迭代器。这样写比搞一个 iterator 到 const_iterator 的转换构造省事得多。4.2 UnorderedMap 封装迭代器、插入、查找一个都不能少UnorderedMap的封装也很直白区别在于T是pairK,V所以 KeyOfT 返回kv.first。templateclass K, class V, class Hash HashFuncK class UnorderedMap { struct MapKeyOfT { const K operator()(const pairK, V kv) const { return kv.first; } }; HashTableK, pairK, V, MapKeyOfT, Hash _ht; public: typedef typename HashTableK, pairK, V, MapKeyOfT, Hash::iterator iterator; typedef typename HashTableK, pairK, V, MapKeyOfT, Hash::const_iterator const_iterator; iterator begin() { return _ht.Begin(); } const_iterator begin() const { return _ht.Begin(); } iterator end() { return _ht.End(); } pairiterator, bool Insert(const pairK, V kv) { return _ht.Insert(kv); } V operator[](const K key) { pairiterator, bool ret _ht.Insert(make_pair(key, V())); return ret.first-second; } };Map 的迭代器类型就是哈希表的普通迭代器因为 map 的 value 必须允许修改。Set 禁改 keyMap 要能改 value这个差异完全由迭代器模板参数承担下来了。框架搭好之后差异只是一行的区别。pairiterator, bool ret _ht.Insert(...)这一步bool表示 key 是否已经存在。如果 key 不存在Insert 会构造一个新节点并插入此时迭代器指向新节点ret.first-second是默认构造的 value如果 key 已经存在Insert 直接返回旧节点迭代器ret.first-second就是旧值。返回引用之后用户读写都走同一个入口读就是dict[apple]取 value写就是dict[apple] 3赋新值。这就是operator[]读和写通吃的根本原因它内部永远执行一次“查找并插入默认值”然后返回 value 引用。4.3 测试效果与使用姿势封装完之后用起来感觉和标准库的unordered_map/unordered_set已经非常接近了UnorderedMapstring, int dict; dict[apple] 3; dict[banana] 5; dict[apple] 2; cout dict[apple] endl; // 5 UnorderedSetint s; s.Insert(1); s.Insert(2); s.Insert(1); // 第二次插入返回 false for (auto it s.begin(); it ! s.end(); it) { cout *it ; }基本的使用体验没啥差别。当然我没有实现标准库的全部接口比如bucket_count、load_factor、rehash这些但核心功能已经通了。一个小细节是operator[]要求V可以默认构造因为make_pair(key, V())需要临时构造一个默认 value。如果自定义类型没有默认构造函数那operator[]就用不了了这和标准库行为一致只能改用insert或emplace。5. 踩过的坑与常见问题排查5.1 字符串哈希不能用强转BKDR 才是稳妥选择我一开始偷懒写了一个通用的HashFuncK里面直接用return (size_t)key。对整型没问题对string直接编译报错因为 string 不能强转成 size_t。后来加了一个 string 特化版本用的是 BKDR 字符串哈希算法遍历每个字符乘一个质数再加字符 ASCII 值。这个质数取 31 或者 131 都可以实测分布比较均匀。template struct HashFuncstring { size_t operator()(const string key) const { size_t hash 0; for (size_t i 0; i key.size(); i) { hash hash * 131 key[i]; } return hash; } };为什么乘 131这个数字的经验来源是 BKDR 算法的经典参数乘法让字符串中靠后的字符也参与进哈希值的高位减少同前缀字符串的冲突概率。如果直接累加 ASCII 码“abc”和“cba”会算成同一个值那哈希表就退化成链表了。5.2 空表取模除零这是新手最容易崩的地方第一次跑测试插入第一个元素时程序直接崩了。定位发现_tables.size()是 0hs(key) % 0直接除零异常。所以插入入口的第一步必须判断空表。我在扩容判断里统一处理了_n 0时先把桶数组扩容到 10 个桶再继续走正常流程。Find和Erase里也加了_tables.empty()的提前返回防止空表状态下被调用。还有一个类似的坑取模运算的结果可能很大但_tables.size()是size_t运算结果也是size_t不会有负数问题。但如果你哈希函数返回的是有符号整数比如把负数 key 直接返回那取模结果可能为负访问_tables[hashi]就下标越界。所以哈希函数的返回值一律设计成size_t整型强转的时候也要注意。5.3 迭代器失效问题一定要心里有数很多人写容器时对“迭代器失效”这个概念很模糊手写哈希桶时会踩一个大坑插入导致扩容之后之前拿到的迭代器还能不能用分两步想。扩容时节点本身没有释放只是重新挂到了新桶里所以迭代器里的_node指针本身还指向一个有效节点。问题出在操作迭代器想要跳桶时需要通过_ht-_tables.size()来取模计算当前桶号。如果_ht已经指向一个被swap出去的旧表_tables已经不是当前哈希表的桶数组那么算出来的桶号自然不对。所以结论是扩容之后的迭代器不建议继续使用严格来说它已经失效了。STL 标准也是这样规定的unordered_map的插入操作如果触发 rehash会使所有迭代器失效。我在封装文档里没有强行处理这个语义但心里要清楚循环里一边 insert 一边用外部迭代器做第一轮扩容就可能翻车。排查时可以打日志观察扩容时机把_tables.size()和_n的变化打出来。5.4 删除时的两个特殊场景删除头节点和删除中间节点是两种逻辑。头节点删除要更新_tables[hashi]否则桶指针还指着已经被delete的节点下次访问直接踩野指针。中间节点删除要维护prev。我最初写的时候漏了头节点的情况单测里删第一个元素就崩。后来加强了一个习惯所有链表删除操作先判断prev nullptr。还有一种场景同一个 key 被删了之后再插入此时_n减少如果之前删除后表变得很空要不要缩容工业级哈希表一般不缩容最多在资源紧张时做 rehash。我这次也不缩容因为缩容同样会导致迭代器大规模失效而且重复插入删除的场景下频繁扩容缩容会有抖动。不做缩容代码还简单一点。5.5 自定义类型做 key需要提供什么如果 key 是自定义类型比如日期类直接往UnorderedSetDate里插会编译报错因为编译器不知道Date怎么哈希。解决办法是给HashFunc写一个特化版本或者给哈希表传一个自定义Hash参数。struct Date { int year; int month; int day; bool operator(const Date d) const { return year d.year month d.month day d.day; } }; struct DateHash { size_t operator()(const Date d) const { return d.year * 10000 d.month * 100 d.day; } }; UnorderedSetDate, DateHash s;同时要保证Date重载了operator因为插入去重和查找时哈希表内部用比较 key。这里会暴露一个问题哈希表内部直接用了K的operator没有再做一层KeyEqual模板参数。标准库把相等比较也抽象出来了我这里从简但使用者必须保证K可比较。真的要让自定义类型的 key 正常工作两个条件缺一不可能哈希能判等。5.6 扩展建议这套封装还能怎么往后走这次封装做完之后我列了一个扩展清单后面有空逐个补。第一把相等比较也参数化成KeyEqual模板参数对标标准库。第二支持移动语义Insert的参数改成转发引用避免pair和string的多余拷贝。第三给迭代器加转换构造函数让普通迭代器能隐式转成 const 迭代器这样 Set 的封装就不用靠CBegin绕路。第四补上reserve、rehash、load_factor、bucket_count这些接口方便用户精细控制哈希表状态。第五试试用同样的模板思路封装红黑树版的Map和Set你会发现除了底层结构不同上层封装几乎是一模一样的。这次手写哈希桶给我最大的感受是unordered_map和unordered_set看起来是两个容器本质上就是一个哈希表换了两套模板参数。把“从数据中提取 key”这个动作通过仿函数解耦出来代码复用立刻变得干净利落。另一个体会是迭代器的 const 版本千万别懒Set 要禁改 key、Map 要能改 value全靠迭代器模板参数和 const 重载撑起来。你要是也想练手建议先只写UnorderedSet通了之后再拆出Map最后回头对比一下差异你会对 C 模板和容器设计有完全不一样的理解。