尧图网页设计 
哈希表这个东西搞 C 的迟早都要直面它。不管你用没用过 unordered_map只要你面试、写算法题、或者做高性能服务端总会碰到“哈希”这两个字。说实话STL 里的 unordered_map 确实好用但正因为好用很多人反而不知道它底层到底怎么工作的。哈希冲突是什么负载因子为什么要 0.7为什么删除元素要打标记这些问题光看文档是理解不了的。我自己当年学哈希就是从手写一个简单的模拟实现开始的这一步跨过去之后再看 STL 源码、再看各种开源项目里的哈希设计真的是豁然开朗。这篇东西不是要带你抄一遍 STL 源码而是用最简单、最贴近底层的方式把哈希表的完整骨架搭出来。你跟着走一遍能理解闭散列和开散列两种冲突处理方案的区别能自己实现插入、查找、删除还能处理扩容和 string 特化。适合刚学完 C 语法、想深入理解数据结构的人也适合面试前想快速把哈希底层补起来的同学。我尽量把每一步的关键细节和为什么这么写都讲清楚保证不是你网上随手能搜到的那种贴一段代码就完事的水文。1. 核心原理与设计选型1.1 哈希表到底解决什么问题先想一个最朴素的问题给你一堆整数怎么快速判断某个数在不在里面最容易想到的办法是开一个数组以这个数的值作为下标存进去。这一步哈希表的核心思路就已经出来了——通过一个函数把关键字映射到数组的下标。不过现实中关键字不一定是连续的小整数可能是很大的数可能是字符串可能是自定义对象。所以我们需要一个“转换”过程把任意类型的关键字变成一个合法的数组下标这个转换函数就是哈希函数。哈希函数设计得好不好直接决定整个表的性能。理想情况下每个关键字都映射到不同的下标这样查找就是 O(1)。但现实中关键字的数量远大于数组容量而且哈希函数的映射是“多对一”的必然会存在多个关键字映射到同一个下标的情况这就叫哈希冲突。冲突没法完全避免但我们可以通过合适的哈希函数让冲突尽量少同时用一套冲突处理策略让表在冲突存在时依然能高效工作。1.2 除留余数法与哈希函数的选型最常见的哈希函数就是除留余数法取关键字除以表容量得到的余数作为下标。size_t index key % capacity;这个公式简单到不能再简单但有几个细节要注意。关键是capacity表容量的取值。理论研究和工程实践都表明容量取质数时哈希分布会更均匀。为什么因为如果容量是合数比如 10那么 key 的个位数就决定了下标所有以相同个位数结尾的 key 全部冲突而容量取质数比如 11key 的个位数和下标的关系就会被“打散”不同的 key 更大概率落在不同位置。在 C 的 STL 实现里unordered_map 的默认桶数并不是随便取的而是一个质数序列。从 193、389 开始按一定倍率增长。我们做模拟实现时可以直接定义一个质数表每次扩容时取下一个质数static const size_t PRIME_LIST[] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241 };用这个表的好处是扩容的时候不用临时算质数直接索引取下一个就行效率高而且分布性有保障。1.3 冲突处理闭散列与开散列怎么选冲突处理是哈希表设计的核心分野。业界基本就两条路闭散列开放定址法发生冲突时在表内继续寻找下一个空位。典型的有线性探测和二次探测。开散列链地址法每个下标位置挂一条链表冲突的元素直接链在同一个桶里。STL 的 unordered_map 用的就是这种。两者怎么选闭散列的优点是缓存友好数据都在一块连续内存里但缺点是删除麻烦、冲突时容易产生“堆积”负载因子控制必须很保守通常不超过 0.7。开散列把冲突元素独立链起来删除容易、对负载因子容忍度更高一般到 1 才扩容虽然多了一次指针寻址但综合表现更好。我写这篇文章的模拟实现闭散列和开散列都会写一遍。原因是这两个方案代表了两套完全不同的思维模式闭散列让你理解“状态标记”和“探测序列”开散列让你理解“桶 链表”的结构管理。面试时面试官问你“哈希冲突怎么解决”你说得出两种方案的适用场景和实现细节和你只会背一个“链地址法”效果完全不一样。2. 闭散列开放定址法的模拟实现2.1 状态标记为什么不能用值本身判断空位闭散列遇到的一个大坑是删除。假如某个下标存了元素 A后来 A 被删了你要不要把那个位置“清空”如果你直接把位置标记为空那么查找元素 B 的时候如果 B 原本在 A 后面线性探测时 B 探测到了 A 的位置探测到 A 的这个空位时就会提前停止——B 明明存在你却查不到。解决办法是给每个位置加一个状态标记。我用一个枚举enum State { EMPTY, // 从来没用过 EXIST, // 当前位置有有效元素 DELETE // 曾经有元素但已删除 };查找时遇到 DELETE 不能停要跳过遇到 EMPTY 才停止。插入时遇到 EMPTY 或者 DELETE 都可以直接覆盖。这一下就把“删了还能不能继续探测”的问题解决了。2.2 闭散列框架哈希表的基本结构先定义哈希表的成员。我直接用 C 的 vector 作为底层存储但为了讲清楚原理不会用 STL 的现成容器来掩盖逻辑templateclass K, class V class HashTable { private: struct Elem { pairK, V _val; State _state; }; vectorElem _table; size_t _size 0; // 实际存储的有效元素个数 };注意我用了一个_size记录当前有效元素数量这个值是判断要不要扩容的依据。_table.size()是容量它和_size是两回事千万别混。2.3 插入线性探测与扩容的完整逻辑插入逻辑分三步先查哈希函数算出初始下标遇到冲突就向后探测找空位找不到说明满了就扩容。bool Insert(const pairK, V kv) { // 负载因子接近 0.7 就扩容 if (_size * 10 / _table.size() 7) { Expand(); } size_t index kv.first % _table.size(); // 线性探测遇到 EXIST 就继续向后找 while (_table[index]._state EXIST) { // 如果 key 已存在直接返回 if (_table[index]._val.first kv.first) { return false; } // 小心不要越界 index (index 1) % _table.size(); } _table[index]._val kv; _table[index]._state EXIST; _size; return true; }细节上要注意index (index 1) % _table.size()这个取模保证了探测到数组末尾后可以回绕到开头继续探测。如果不做取模表尾附近插入频繁时冲突概率会剧增。2.4 扩容的关键重新哈希扩容不是简单地复制一份数据因为容量变了哈希函数的结果也变了。原来key % 10算出的下标和key % 97算出的下标完全不同所以必须把每个元素重新按新容量计算下标再插入新表void Expand() { size_t newSize GetNextPrime(_table.size()); vectorElem oldTable; oldTable.swap(_table); _table.resize(newSize); _size 0; for (auto e : oldTable) { if (e._state EXIST) { Insert(e._val); } } }这个重新哈希的过程是哈希表性能的关键。如果不扩容冲突越来越多插入和查找会退化成链表一样的 O(n)。每扩容一次所有元素重新分布一次哈希表才能保持“摊还 O(1)”的性能。2.5 查找与删除状态标记决定了边界条件查找的逻辑和插入类似但更微妙Elem* Find(const K key) { size_t index key % _table.size(); while (_table[index]._state ! EMPTY) { if (_table[index]._state EXIST _table[index]._val.first key) { return _table[index]; } index (index 1) % _table.size(); // 防止死循环 } return nullptr; }有一个隐藏 bug 容易踩当表中全是 DELETE 状态、没有 EMPTY 时查找可能陷入死循环。所以在 while 循环里最好加一个计数保护或者规定删除后必须保证至少留一个 EMPTY 位置。工程上的做法是控制负载因子上限只要负载因子不超过 0.7表中永远至少有三成位置是 EMPTY理论上不会出现全 DELETE 的死循环。但保险起见还是可以在循环里判断是否已经遍历了一圈for (size_t i 0; i _table.size(); i) { // ... }删除就更直观了bool Erase(const K key) { Elem* ret Find(key); if (ret nullptr) { return false; } ret-_state DELETE; --_size; return true; }看到没删除并没有真正清空数据只是把状态标记改成 DELETE。这样做的好处是查找时还能继续往后探测坏处是这些位置占着茅坑不拉屎会慢慢消耗EMPTY位置。所以闭散列对删除操作频繁的场景不够友好这也是它不如开散列通用的原因之一。3. 开散列哈希桶/链地址法的模拟实现3.1 结构设计一个数组挂 N 条链表开散列的结构很好理解底层是一个指针数组每个指针指向一条链表桶所有哈希到同一个下标的元素都挂在这条链上。templateclass K, class V struct HashNode { pairK, V _kv; HashNodeK, V* _next; HashNode(const pairK, V kv) : _kv(kv), _next(nullptr) {} }; templateclass K, class V class HashBucket { private: vectorHashNodeK, V* _table; size_t _size 0; };每个桶是无序的插入时直接头插。头插比尾插方便不用遍历链表找末尾O(1) 完成。3.2 插入哈希并直接挂在桶上bool Insert(const pairK, V kv) { // 判断已存在 if (Find(kv.first)) { return false; } // 扩容负载因子达到 1 再扩容 if (_size _table.size()) { Expand(); } size_t index kv.first % _table.size(); HashNodeK, V* newNode new HashNodeK, V(kv); // 头插 newNode-_next _table[index]; _table[index] newNode; _size; return true; }开散列的负载因子可以放宽到 1。因为即使某个桶冲突了也只是链表的长度增加其他桶完全不受影响。闭散列是“牵一发而动全身”开散列是“各人自扫门前雪”。3.3 扩容旧节点迁移而不是复制和闭散列类似扩容量变后哈希结果会变。但开散列扩容时有一个区别不需要重新 new 节点直接把旧节点摘下来重新计算下标挂到新桶上。这样避免了重复分配和释放内存的开销。void Expand() { size_t newSize GetNextPrime(_table.size()); vectorHashNodeK, V* newTable(newSize, nullptr); for (size_t i 0; i _table.size(); i) { HashNodeK, V* cur _table[i]; while (cur) { HashNodeK, V* next cur-_next; size_t index cur-_kv.first % newSize; // 头插到新桶 cur-_next newTable[index]; newTable[index] cur; cur next; } _table[i] nullptr; } _table.swap(newTable); }很多人第一次写会犯一个错在遍历旧表时直接用一个指针 cur 往下走忘记保存 next结果 cur 被挂到新桶后_next 变了就找不到原来链表的下一个节点了。所以上面代码里HashNodeK, V* next cur-_next;必须在 cur 被修改前保存好。3.4 析构函数每个桶都要单独释放开散列必须自己管理内存。析构时不能只把 vector 释放掉每个桶里的链表节点都要 delete~HashBucket() { for (size_t i 0; i _table.size(); i) { HashNodeK, V* cur _table[i]; while (cur) { HashNodeK, V* next cur-_next; delete cur; cur next; } _table[i] nullptr; } }很多人写哈希表只写了 Insert 和 Find忘了写析构结果内存泄漏。在写模拟实现的时候一定要把 RAII 原则贯彻到底——你自己 new 出来的东西必须有对应的地方 delete 干净。3.5 查找和删除同一个桶里线性扫查找分两步先算桶下标再到桶里链表上遍历。HashNodeK, V* Find(const K key) { size_t index key % _table.size(); HashNodeK, V* cur _table[index]; while (cur) { if (cur-_kv.first key) { return cur; } cur cur-_next; } return nullptr; }删除稍微复杂一点因为单链表删节点要维护前驱指针bool Erase(const K key) { size_t index key % _table.size(); HashNodeK, V* cur _table[index]; HashNodeK, V* prev nullptr; while (cur) { if (cur-_kv.first key) { if (prev nullptr) { // 删除的是头节点 _table[index] cur-_next; } else { prev-_next cur-_next; } delete cur; --_size; return true; } prev cur; cur cur-_next; } return false; }别忘了prev nullptr时说明要删的是桶里的第一个节点更新_table[index]否则更新上一个节点的_next。这个边界条件是单链表操作的经典坑。4. 泛型设计与哈希函数特化4.1 不只是 int仿函数与通用哈希上面的实现只支持整型 key 取模。但实际使用中key 可能是 string、double甚至自定义对象。要做成通用的哈希表模板第一步是把“取模”抽象成一个仿函数。另外如果封装 unordered_map还需要一个提取 key 的仿函数KeyOfT因为插入时传入的是pairK, V但计算哈希要用pair里的first字段。模板参数设计成templateclass K, class V, class HashFunc HashK class HashBucket { // ... }; templateclass K struct Hash { size_t operator()(const K key) { return (size_t)key; } };4.2 字符串哈希BKDRHash 特化string 没法直接%运算需要把字符串变成一个整数。最常用的方法是BKDRHashstruct HashString { size_t operator()(const string key) { size_t hash 0; size_t seed 131; // 131、1313、13131... for (char c : key) { hash hash * seed c; } return hash; } };这个公式的核心思想是把字符串当成一个 131 进制的数每个字符是一个“位”。为什么选 131 而不是 10 或者 100因为实践测下来131 这个乘子在常规字符串集合上的分布效果比较好。很多开源库也使用类似的 BKDRHash 变种。有了 HashString 特化我的哈希表就能存 string 的 key 了。你还可以继续特化 double、float方法都是先把字节拆成整数再哈希。4.3 封装 unordered_map / unordered_set 的思路有了开散列再往上封装 unordered_map 就很容易。unordered_set 存的是 key 本身unordered_map 存的是 key-value 对。两者的区别在于传给底层哈希表的数据类型不同unordered_setK底层存储HashBucketK, Kunordered_mapK, V底层存储HashBucketK, pairK, V但取 key 时要通过_kv.first取所以底层需要加一个KeyOfT仿函数模板参数用来从存储的数据里提取 keytemplateclass K, class V, class KeyOfT, class HashFunc class HashBucket { // ... private: size_t GetIndex(const V data) { K key KeyOfT()(data); return HashFunc()(key) % _table.size(); } };对 unordered_map 来说KeyOfT 返回的是kv.first对 unordered_set 来说KeyOfT 直接返回 data 本身。这个抽象是 STL 实现的关键自己写一遍后看源码会顺畅很多。5. 常见问题与调试技巧实录5.1 闭散列查找死循环前面提过一次这里再说清楚。闭散列的 while 循环里如果表里全是 DELETE 和 EXIST没有 EMPTY查找一个不存在的 key循环会一直转。触发条件通常是表很满、删除频繁。解决思路有两个一是严格控制负载因子别等到 0.7 以上才扩容二是 Find 里加计数器最多循环_table.size()次就退出。工程上更推荐第一种因为负载因子控制得当的情况下EMPTY 位置始终存在循环一定会终止。我实际调试时见过一次负载因子失控导致的死循环排查了半天才发现是扩容条件写错了导致_size一直小于_table.size() * 0.7但实际有效位置很少。加个_size打印日志一眼就看出来。5.2 扩容后数据丢失闭散列扩容时要注意旧表的状态是 DELETE 的节点不能迁移。原因是删除时虽然状态标记是 DELETE但_val里的数据已经废弃了如果还迁移到新表会造成脏数据。所以Expand里必须判断if (e._state EXIST) { Insert(e._val); }很多初学者栽在这个点上因为表面上看 delete 过的位置数据还在Insert 到新表也没报错但实际查出来的是“已经被删掉的旧值”。现象是删除一个 key 后把它重新插入再查找返回的却是老数据。排查方法是用状态标记打日志确认状态是否一致。5.3 开散列节点内存泄漏开散列的 Insert 每次new一个节点如果忘记写析构函数程序退出后内存没释放。这个在个人练习中可能察觉不到但写服务端代码就会留下隐患。建议写完后用 valgrind 或者 AddressSanitizer 跑一遍g -fsanitizeaddress -g hash.cpp -o hash ./hashAddressSanitizer 报出来的LeakSanitizer信息会精确到代码行号配合源码分析非常高效。实测下来我自己的练习代码第一次跑 ASan 都会报几个 leak无外乎就是析构没写或者删除节点后忘了delete。5.4 性能退化从 O(1) 到 O(n)哈希表最怕的就是退化成链表。开散列中如果一个桶挂了特别多节点查找效率就从 O(1) 退化到 O(n)。触发原因通常是哈希函数选得不好或者容量太小没及时扩容。我在调试中发现一个典型问题用Hashint直接对 int 取模没问题但如果你存的对象哈希值永远是一个固定值比如某些自定义对象的哈希函数写得不好那么所有元素都堆到一个桶里哈希表直接废掉。排查方法很简单写一个测试函数统计每个桶的节点数量。如果出现极端分布就该换哈希函数或者调整负载因子。void DebugPrintBucketLengths() { for (size_t i 0; i _table.size(); i) { size_t len 0; HashNodeK, V* cur _table[i]; while (cur) { len; cur cur-_next; } if (len 0) { cout bucket[ i ] length len endl; } } }我实际测过一个随机 10000 个 int 的情况质数容量分布非常均匀几乎每个桶都是 1 到 2 个节点。换了合数容量后明显出现几个桶节点特别多。5.5 关于%运算与负数 key 的问题C 的%运算结果是带符号的负数%正数得到负数。如果直接用这个当数组下标会越界崩溃。解决方法是转成无符号数size_t index HashFunc()(key) % _table.size();哈希函数返回size_t无符号数这样就不会出问题。但如果你的哈希函数返回的是int一定要先强转return (size_t)key % _table.size();这个细节看着小但真的能让你在调试时崩溃到怀疑人生。我最早写实现的时候用int类型做哈希函数返回值往表里插一个负数 key程序秒崩gdb 一看就是下标直接变成无符号大数了。5.6 拷贝构造与赋值运算符重载如果你打算让哈希表作为对象在容器中传递拷贝构造和赋值运算符必须自己实现。默认的浅拷贝会导致两个哈希表指向同一批节点析构时 double free。参考实现HashBucket(const HashBucket other) { _table.resize(other._table.size(), nullptr); for (size_t i 0; i other._table.size(); i) { HashNodeK, V* cur other._table[i]; while (cur) { HashNodeK, V* newNode new HashNodeK, V(cur-_kv); newNode-_next _table[i]; _table[i] newNode; cur cur-_next; } } _size other._size; }赋值运算符重载可以复用拷贝构造用“拷贝并交换”的技巧HashBucket operator(HashBucket other) { _table.swap(other._table); swap(_size, other._size); return *this; }这种写法简洁且异常安全。6. 完整测试用例与基准思路6.1 功能测试插入、查找、删除的闭环写完模拟实现第一步要做的是基本的增删改查测试。我习惯用一个小脚本验证各种边界情况尤其是空表、满表、删除后重新插入这些场景void TestHashBucket() { HashBucketint, int, HashInt ht; // 插入 for (int i 0; i 100; i) { ht.Insert({i, i * 10}); } // 查找全部存在 for (int i 0; i 100; i) { auto ret ht.Find(i); assert(ret ret-_kv.second i * 10); } // 删除一半 for (int i 0; i 50; i) { assert(ht.Erase(i)); } // 已删除的不存在 for (int i 0; i 50; i) { assert(ht.Find(i) nullptr); } // 重新插入已删除的 key for (int i 0; i 50; i) { bool ok ht.Insert({i, i * 100}); assert(ok); } // 扩容之后数据仍然正确 for (int i 50; i 200; i) { ht.Insert({i, i * 5}); } for (int i 0; i 200; i) { auto ret ht.Find(i); assert(ret ! nullptr); if (i 50) { assert(ret-_kv.second i * 100); } else if (i 100) { assert(ret-_kv.second i * 10); } else { assert(ret-_kv.second i * 5); } } cout all tests passed endl; }这个测试覆盖了插入、查找、删除、删除后重新插入、扩容后的数据一致性。边界条件多能帮你快速捕获常见的逻辑 bug。6.2 压力测试随机操作序列验证光测固有用例不够因为哈希表的状态会随着操作序列变化很多 bug 只有随机操作时才触发。我写了一个随机操作测试每次随机插入或删除用标准 unordered_map 作为“参照物”对比结果void StressTest() { std::unordered_mapint, int ref; HashBucketint, int, HashInt ht; srand(2024); for (int i 0; i 100000; i) { int key rand() % 10000; int opt rand() % 4; if (opt 0) { // 删除 bool r1 ref.erase(key) 0; bool r2 ht.Erase(key); assert(r1 r2); } else { // 插入 int val rand(); ref[key] val; ht.Insert({key, val}); assert(ht.Find(key) ! nullptr); } // 每 1000 次随机检查一次一致性 if (i % 1000 0) { for (int k 0; k 10000; k) { auto it ref.find(k); bool exists (it ! ref.end()); auto found ht.Find(k); if (exists ! (found ! nullptr)) { cout mismatch at key k endl; abort(); } } } } cout stress test passed endl; }这个思路最重要的价值在于用 STL 验证自研代码的正确性。只要随机操作规模和检查频率够高绝大多数隐藏 bug 都会暴露出来。我实际跑这个测试抓过至少三个问题扩容丢数据、删除后找不到既有元素、以及状态标记更新遗漏。6.3 性能基准和 unordered_map 对比模拟实现不需要追求超越 STL但做个对比能直观看到自己的实现处在什么水平。用一千万元素连续插入和查找void BenchTest() { const int N 10000000; std::unordered_mapint, int stlMap; HashBucketint, int, HashInt myMap; auto t1 chrono::steady_clock::now(); for (int i 0; i N; i) { stlMap[i] i; } auto t2 chrono::steady_clock::now(); cout STL unordered_map insert: chrono::duration_castchrono::milliseconds(t2 - t1).count() ms endl; auto t3 chrono::steady_clock::now(); for (int i 0; i N; i) { myMap.Insert({i, i}); } auto t4 chrono::steady_clock::now(); cout My HashBucket insert: chrono::duration_castchrono::milliseconds(t4 - t3).count() ms endl; }实测下来我的模拟实现通常比 STL 慢 20% 到 50%这是正常的。STL 的哈希函数更优化、内存分配策略更好、甚至还有局部性优化。模拟实现能到 STL 七八成的性能说明思路和结构已经合格了。如果慢得离谱先检查是不是哈希函数太弱导致冲突过多再用上面的桶分布统计定位问题。写在最后的经验把闭散列和开散列两种方案都完整实现一遍再封装出 unordered_map 和 unordered_set这一步走下来你对哈希表的理解会和看文档完全不一样。我自己最大的体会是哈希表的结构本身不难难的是细节之间的耦合。状态标记、负载因子、扩容重哈希、析构和拷贝每一个环节单独看都很清晰但彼此咬合在一起时任何一个环节出错表现都不是报错而是“偶尔查不到”“偶尔内存泄漏”“偶尔死循环”这种玄学 bug。这也是为什么哈希表特别适合拿来练手——它逼你把内存管理、模板设计、边界条件处理这些 C 的基本功全部调动起来。最后分享一个我排查问题时的绝招在小规模数据上把每一步操作后的表内容完整打印出来插入、删除、扩容各打印一次用人眼盯着数据迁移过程看。这个方法虽然笨但比任何调试器都好使。有一次我扩容后数据错乱就是看着打印出来的旧表和新表逐行对比才定位到是漏了 DELETE 状态的判断。写得久了你就会发现数据结构这种东西写得越多对“为什么 STL 要这么设计”的理解就越深。你也试试把这份模拟实现从头到尾写一遍跑通所有测试你对哈希的理解绝对会上一个台阶。 C++哈希表底层原理：从手写模拟到闭散列与开散列实现
哈希表这个东西搞 C 的迟早都要直面它。不管你用没用过 unordered_map只要你面试、写算法题、或者做高性能服务端总会碰到“哈希”这两个字。说实话STL 里的 unordered_map 确实好用但正因为好用很多人反而不知道它底层到底怎么工作的。哈希冲突是什么负载因子为什么要 0.7为什么删除元素要打标记这些问题光看文档是理解不了的。我自己当年学哈希就是从手写一个简单的模拟实现开始的这一步跨过去之后再看 STL 源码、再看各种开源项目里的哈希设计真的是豁然开朗。这篇东西不是要带你抄一遍 STL 源码而是用最简单、最贴近底层的方式把哈希表的完整骨架搭出来。你跟着走一遍能理解闭散列和开散列两种冲突处理方案的区别能自己实现插入、查找、删除还能处理扩容和 string 特化。适合刚学完 C 语法、想深入理解数据结构的人也适合面试前想快速把哈希底层补起来的同学。我尽量把每一步的关键细节和为什么这么写都讲清楚保证不是你网上随手能搜到的那种贴一段代码就完事的水文。1. 核心原理与设计选型1.1 哈希表到底解决什么问题先想一个最朴素的问题给你一堆整数怎么快速判断某个数在不在里面最容易想到的办法是开一个数组以这个数的值作为下标存进去。这一步哈希表的核心思路就已经出来了——通过一个函数把关键字映射到数组的下标。不过现实中关键字不一定是连续的小整数可能是很大的数可能是字符串可能是自定义对象。所以我们需要一个“转换”过程把任意类型的关键字变成一个合法的数组下标这个转换函数就是哈希函数。哈希函数设计得好不好直接决定整个表的性能。理想情况下每个关键字都映射到不同的下标这样查找就是 O(1)。但现实中关键字的数量远大于数组容量而且哈希函数的映射是“多对一”的必然会存在多个关键字映射到同一个下标的情况这就叫哈希冲突。冲突没法完全避免但我们可以通过合适的哈希函数让冲突尽量少同时用一套冲突处理策略让表在冲突存在时依然能高效工作。1.2 除留余数法与哈希函数的选型最常见的哈希函数就是除留余数法取关键字除以表容量得到的余数作为下标。size_t index key % capacity;这个公式简单到不能再简单但有几个细节要注意。关键是capacity表容量的取值。理论研究和工程实践都表明容量取质数时哈希分布会更均匀。为什么因为如果容量是合数比如 10那么 key 的个位数就决定了下标所有以相同个位数结尾的 key 全部冲突而容量取质数比如 11key 的个位数和下标的关系就会被“打散”不同的 key 更大概率落在不同位置。在 C 的 STL 实现里unordered_map 的默认桶数并不是随便取的而是一个质数序列。从 193、389 开始按一定倍率增长。我们做模拟实现时可以直接定义一个质数表每次扩容时取下一个质数static const size_t PRIME_LIST[] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241 };用这个表的好处是扩容的时候不用临时算质数直接索引取下一个就行效率高而且分布性有保障。1.3 冲突处理闭散列与开散列怎么选冲突处理是哈希表设计的核心分野。业界基本就两条路闭散列开放定址法发生冲突时在表内继续寻找下一个空位。典型的有线性探测和二次探测。开散列链地址法每个下标位置挂一条链表冲突的元素直接链在同一个桶里。STL 的 unordered_map 用的就是这种。两者怎么选闭散列的优点是缓存友好数据都在一块连续内存里但缺点是删除麻烦、冲突时容易产生“堆积”负载因子控制必须很保守通常不超过 0.7。开散列把冲突元素独立链起来删除容易、对负载因子容忍度更高一般到 1 才扩容虽然多了一次指针寻址但综合表现更好。我写这篇文章的模拟实现闭散列和开散列都会写一遍。原因是这两个方案代表了两套完全不同的思维模式闭散列让你理解“状态标记”和“探测序列”开散列让你理解“桶 链表”的结构管理。面试时面试官问你“哈希冲突怎么解决”你说得出两种方案的适用场景和实现细节和你只会背一个“链地址法”效果完全不一样。2. 闭散列开放定址法的模拟实现2.1 状态标记为什么不能用值本身判断空位闭散列遇到的一个大坑是删除。假如某个下标存了元素 A后来 A 被删了你要不要把那个位置“清空”如果你直接把位置标记为空那么查找元素 B 的时候如果 B 原本在 A 后面线性探测时 B 探测到了 A 的位置探测到 A 的这个空位时就会提前停止——B 明明存在你却查不到。解决办法是给每个位置加一个状态标记。我用一个枚举enum State { EMPTY, // 从来没用过 EXIST, // 当前位置有有效元素 DELETE // 曾经有元素但已删除 };查找时遇到 DELETE 不能停要跳过遇到 EMPTY 才停止。插入时遇到 EMPTY 或者 DELETE 都可以直接覆盖。这一下就把“删了还能不能继续探测”的问题解决了。2.2 闭散列框架哈希表的基本结构先定义哈希表的成员。我直接用 C 的 vector 作为底层存储但为了讲清楚原理不会用 STL 的现成容器来掩盖逻辑templateclass K, class V class HashTable { private: struct Elem { pairK, V _val; State _state; }; vectorElem _table; size_t _size 0; // 实际存储的有效元素个数 };注意我用了一个_size记录当前有效元素数量这个值是判断要不要扩容的依据。_table.size()是容量它和_size是两回事千万别混。2.3 插入线性探测与扩容的完整逻辑插入逻辑分三步先查哈希函数算出初始下标遇到冲突就向后探测找空位找不到说明满了就扩容。bool Insert(const pairK, V kv) { // 负载因子接近 0.7 就扩容 if (_size * 10 / _table.size() 7) { Expand(); } size_t index kv.first % _table.size(); // 线性探测遇到 EXIST 就继续向后找 while (_table[index]._state EXIST) { // 如果 key 已存在直接返回 if (_table[index]._val.first kv.first) { return false; } // 小心不要越界 index (index 1) % _table.size(); } _table[index]._val kv; _table[index]._state EXIST; _size; return true; }细节上要注意index (index 1) % _table.size()这个取模保证了探测到数组末尾后可以回绕到开头继续探测。如果不做取模表尾附近插入频繁时冲突概率会剧增。2.4 扩容的关键重新哈希扩容不是简单地复制一份数据因为容量变了哈希函数的结果也变了。原来key % 10算出的下标和key % 97算出的下标完全不同所以必须把每个元素重新按新容量计算下标再插入新表void Expand() { size_t newSize GetNextPrime(_table.size()); vectorElem oldTable; oldTable.swap(_table); _table.resize(newSize); _size 0; for (auto e : oldTable) { if (e._state EXIST) { Insert(e._val); } } }这个重新哈希的过程是哈希表性能的关键。如果不扩容冲突越来越多插入和查找会退化成链表一样的 O(n)。每扩容一次所有元素重新分布一次哈希表才能保持“摊还 O(1)”的性能。2.5 查找与删除状态标记决定了边界条件查找的逻辑和插入类似但更微妙Elem* Find(const K key) { size_t index key % _table.size(); while (_table[index]._state ! EMPTY) { if (_table[index]._state EXIST _table[index]._val.first key) { return _table[index]; } index (index 1) % _table.size(); // 防止死循环 } return nullptr; }有一个隐藏 bug 容易踩当表中全是 DELETE 状态、没有 EMPTY 时查找可能陷入死循环。所以在 while 循环里最好加一个计数保护或者规定删除后必须保证至少留一个 EMPTY 位置。工程上的做法是控制负载因子上限只要负载因子不超过 0.7表中永远至少有三成位置是 EMPTY理论上不会出现全 DELETE 的死循环。但保险起见还是可以在循环里判断是否已经遍历了一圈for (size_t i 0; i _table.size(); i) { // ... }删除就更直观了bool Erase(const K key) { Elem* ret Find(key); if (ret nullptr) { return false; } ret-_state DELETE; --_size; return true; }看到没删除并没有真正清空数据只是把状态标记改成 DELETE。这样做的好处是查找时还能继续往后探测坏处是这些位置占着茅坑不拉屎会慢慢消耗EMPTY位置。所以闭散列对删除操作频繁的场景不够友好这也是它不如开散列通用的原因之一。3. 开散列哈希桶/链地址法的模拟实现3.1 结构设计一个数组挂 N 条链表开散列的结构很好理解底层是一个指针数组每个指针指向一条链表桶所有哈希到同一个下标的元素都挂在这条链上。templateclass K, class V struct HashNode { pairK, V _kv; HashNodeK, V* _next; HashNode(const pairK, V kv) : _kv(kv), _next(nullptr) {} }; templateclass K, class V class HashBucket { private: vectorHashNodeK, V* _table; size_t _size 0; };每个桶是无序的插入时直接头插。头插比尾插方便不用遍历链表找末尾O(1) 完成。3.2 插入哈希并直接挂在桶上bool Insert(const pairK, V kv) { // 判断已存在 if (Find(kv.first)) { return false; } // 扩容负载因子达到 1 再扩容 if (_size _table.size()) { Expand(); } size_t index kv.first % _table.size(); HashNodeK, V* newNode new HashNodeK, V(kv); // 头插 newNode-_next _table[index]; _table[index] newNode; _size; return true; }开散列的负载因子可以放宽到 1。因为即使某个桶冲突了也只是链表的长度增加其他桶完全不受影响。闭散列是“牵一发而动全身”开散列是“各人自扫门前雪”。3.3 扩容旧节点迁移而不是复制和闭散列类似扩容量变后哈希结果会变。但开散列扩容时有一个区别不需要重新 new 节点直接把旧节点摘下来重新计算下标挂到新桶上。这样避免了重复分配和释放内存的开销。void Expand() { size_t newSize GetNextPrime(_table.size()); vectorHashNodeK, V* newTable(newSize, nullptr); for (size_t i 0; i _table.size(); i) { HashNodeK, V* cur _table[i]; while (cur) { HashNodeK, V* next cur-_next; size_t index cur-_kv.first % newSize; // 头插到新桶 cur-_next newTable[index]; newTable[index] cur; cur next; } _table[i] nullptr; } _table.swap(newTable); }很多人第一次写会犯一个错在遍历旧表时直接用一个指针 cur 往下走忘记保存 next结果 cur 被挂到新桶后_next 变了就找不到原来链表的下一个节点了。所以上面代码里HashNodeK, V* next cur-_next;必须在 cur 被修改前保存好。3.4 析构函数每个桶都要单独释放开散列必须自己管理内存。析构时不能只把 vector 释放掉每个桶里的链表节点都要 delete~HashBucket() { for (size_t i 0; i _table.size(); i) { HashNodeK, V* cur _table[i]; while (cur) { HashNodeK, V* next cur-_next; delete cur; cur next; } _table[i] nullptr; } }很多人写哈希表只写了 Insert 和 Find忘了写析构结果内存泄漏。在写模拟实现的时候一定要把 RAII 原则贯彻到底——你自己 new 出来的东西必须有对应的地方 delete 干净。3.5 查找和删除同一个桶里线性扫查找分两步先算桶下标再到桶里链表上遍历。HashNodeK, V* Find(const K key) { size_t index key % _table.size(); HashNodeK, V* cur _table[index]; while (cur) { if (cur-_kv.first key) { return cur; } cur cur-_next; } return nullptr; }删除稍微复杂一点因为单链表删节点要维护前驱指针bool Erase(const K key) { size_t index key % _table.size(); HashNodeK, V* cur _table[index]; HashNodeK, V* prev nullptr; while (cur) { if (cur-_kv.first key) { if (prev nullptr) { // 删除的是头节点 _table[index] cur-_next; } else { prev-_next cur-_next; } delete cur; --_size; return true; } prev cur; cur cur-_next; } return false; }别忘了prev nullptr时说明要删的是桶里的第一个节点更新_table[index]否则更新上一个节点的_next。这个边界条件是单链表操作的经典坑。4. 泛型设计与哈希函数特化4.1 不只是 int仿函数与通用哈希上面的实现只支持整型 key 取模。但实际使用中key 可能是 string、double甚至自定义对象。要做成通用的哈希表模板第一步是把“取模”抽象成一个仿函数。另外如果封装 unordered_map还需要一个提取 key 的仿函数KeyOfT因为插入时传入的是pairK, V但计算哈希要用pair里的first字段。模板参数设计成templateclass K, class V, class HashFunc HashK class HashBucket { // ... }; templateclass K struct Hash { size_t operator()(const K key) { return (size_t)key; } };4.2 字符串哈希BKDRHash 特化string 没法直接%运算需要把字符串变成一个整数。最常用的方法是BKDRHashstruct HashString { size_t operator()(const string key) { size_t hash 0; size_t seed 131; // 131、1313、13131... for (char c : key) { hash hash * seed c; } return hash; } };这个公式的核心思想是把字符串当成一个 131 进制的数每个字符是一个“位”。为什么选 131 而不是 10 或者 100因为实践测下来131 这个乘子在常规字符串集合上的分布效果比较好。很多开源库也使用类似的 BKDRHash 变种。有了 HashString 特化我的哈希表就能存 string 的 key 了。你还可以继续特化 double、float方法都是先把字节拆成整数再哈希。4.3 封装 unordered_map / unordered_set 的思路有了开散列再往上封装 unordered_map 就很容易。unordered_set 存的是 key 本身unordered_map 存的是 key-value 对。两者的区别在于传给底层哈希表的数据类型不同unordered_setK底层存储HashBucketK, Kunordered_mapK, V底层存储HashBucketK, pairK, V但取 key 时要通过_kv.first取所以底层需要加一个KeyOfT仿函数模板参数用来从存储的数据里提取 keytemplateclass K, class V, class KeyOfT, class HashFunc class HashBucket { // ... private: size_t GetIndex(const V data) { K key KeyOfT()(data); return HashFunc()(key) % _table.size(); } };对 unordered_map 来说KeyOfT 返回的是kv.first对 unordered_set 来说KeyOfT 直接返回 data 本身。这个抽象是 STL 实现的关键自己写一遍后看源码会顺畅很多。5. 常见问题与调试技巧实录5.1 闭散列查找死循环前面提过一次这里再说清楚。闭散列的 while 循环里如果表里全是 DELETE 和 EXIST没有 EMPTY查找一个不存在的 key循环会一直转。触发条件通常是表很满、删除频繁。解决思路有两个一是严格控制负载因子别等到 0.7 以上才扩容二是 Find 里加计数器最多循环_table.size()次就退出。工程上更推荐第一种因为负载因子控制得当的情况下EMPTY 位置始终存在循环一定会终止。我实际调试时见过一次负载因子失控导致的死循环排查了半天才发现是扩容条件写错了导致_size一直小于_table.size() * 0.7但实际有效位置很少。加个_size打印日志一眼就看出来。5.2 扩容后数据丢失闭散列扩容时要注意旧表的状态是 DELETE 的节点不能迁移。原因是删除时虽然状态标记是 DELETE但_val里的数据已经废弃了如果还迁移到新表会造成脏数据。所以Expand里必须判断if (e._state EXIST) { Insert(e._val); }很多初学者栽在这个点上因为表面上看 delete 过的位置数据还在Insert 到新表也没报错但实际查出来的是“已经被删掉的旧值”。现象是删除一个 key 后把它重新插入再查找返回的却是老数据。排查方法是用状态标记打日志确认状态是否一致。5.3 开散列节点内存泄漏开散列的 Insert 每次new一个节点如果忘记写析构函数程序退出后内存没释放。这个在个人练习中可能察觉不到但写服务端代码就会留下隐患。建议写完后用 valgrind 或者 AddressSanitizer 跑一遍g -fsanitizeaddress -g hash.cpp -o hash ./hashAddressSanitizer 报出来的LeakSanitizer信息会精确到代码行号配合源码分析非常高效。实测下来我自己的练习代码第一次跑 ASan 都会报几个 leak无外乎就是析构没写或者删除节点后忘了delete。5.4 性能退化从 O(1) 到 O(n)哈希表最怕的就是退化成链表。开散列中如果一个桶挂了特别多节点查找效率就从 O(1) 退化到 O(n)。触发原因通常是哈希函数选得不好或者容量太小没及时扩容。我在调试中发现一个典型问题用Hashint直接对 int 取模没问题但如果你存的对象哈希值永远是一个固定值比如某些自定义对象的哈希函数写得不好那么所有元素都堆到一个桶里哈希表直接废掉。排查方法很简单写一个测试函数统计每个桶的节点数量。如果出现极端分布就该换哈希函数或者调整负载因子。void DebugPrintBucketLengths() { for (size_t i 0; i _table.size(); i) { size_t len 0; HashNodeK, V* cur _table[i]; while (cur) { len; cur cur-_next; } if (len 0) { cout bucket[ i ] length len endl; } } }我实际测过一个随机 10000 个 int 的情况质数容量分布非常均匀几乎每个桶都是 1 到 2 个节点。换了合数容量后明显出现几个桶节点特别多。5.5 关于%运算与负数 key 的问题C 的%运算结果是带符号的负数%正数得到负数。如果直接用这个当数组下标会越界崩溃。解决方法是转成无符号数size_t index HashFunc()(key) % _table.size();哈希函数返回size_t无符号数这样就不会出问题。但如果你的哈希函数返回的是int一定要先强转return (size_t)key % _table.size();这个细节看着小但真的能让你在调试时崩溃到怀疑人生。我最早写实现的时候用int类型做哈希函数返回值往表里插一个负数 key程序秒崩gdb 一看就是下标直接变成无符号大数了。5.6 拷贝构造与赋值运算符重载如果你打算让哈希表作为对象在容器中传递拷贝构造和赋值运算符必须自己实现。默认的浅拷贝会导致两个哈希表指向同一批节点析构时 double free。参考实现HashBucket(const HashBucket other) { _table.resize(other._table.size(), nullptr); for (size_t i 0; i other._table.size(); i) { HashNodeK, V* cur other._table[i]; while (cur) { HashNodeK, V* newNode new HashNodeK, V(cur-_kv); newNode-_next _table[i]; _table[i] newNode; cur cur-_next; } } _size other._size; }赋值运算符重载可以复用拷贝构造用“拷贝并交换”的技巧HashBucket operator(HashBucket other) { _table.swap(other._table); swap(_size, other._size); return *this; }这种写法简洁且异常安全。6. 完整测试用例与基准思路6.1 功能测试插入、查找、删除的闭环写完模拟实现第一步要做的是基本的增删改查测试。我习惯用一个小脚本验证各种边界情况尤其是空表、满表、删除后重新插入这些场景void TestHashBucket() { HashBucketint, int, HashInt ht; // 插入 for (int i 0; i 100; i) { ht.Insert({i, i * 10}); } // 查找全部存在 for (int i 0; i 100; i) { auto ret ht.Find(i); assert(ret ret-_kv.second i * 10); } // 删除一半 for (int i 0; i 50; i) { assert(ht.Erase(i)); } // 已删除的不存在 for (int i 0; i 50; i) { assert(ht.Find(i) nullptr); } // 重新插入已删除的 key for (int i 0; i 50; i) { bool ok ht.Insert({i, i * 100}); assert(ok); } // 扩容之后数据仍然正确 for (int i 50; i 200; i) { ht.Insert({i, i * 5}); } for (int i 0; i 200; i) { auto ret ht.Find(i); assert(ret ! nullptr); if (i 50) { assert(ret-_kv.second i * 100); } else if (i 100) { assert(ret-_kv.second i * 10); } else { assert(ret-_kv.second i * 5); } } cout all tests passed endl; }这个测试覆盖了插入、查找、删除、删除后重新插入、扩容后的数据一致性。边界条件多能帮你快速捕获常见的逻辑 bug。6.2 压力测试随机操作序列验证光测固有用例不够因为哈希表的状态会随着操作序列变化很多 bug 只有随机操作时才触发。我写了一个随机操作测试每次随机插入或删除用标准 unordered_map 作为“参照物”对比结果void StressTest() { std::unordered_mapint, int ref; HashBucketint, int, HashInt ht; srand(2024); for (int i 0; i 100000; i) { int key rand() % 10000; int opt rand() % 4; if (opt 0) { // 删除 bool r1 ref.erase(key) 0; bool r2 ht.Erase(key); assert(r1 r2); } else { // 插入 int val rand(); ref[key] val; ht.Insert({key, val}); assert(ht.Find(key) ! nullptr); } // 每 1000 次随机检查一次一致性 if (i % 1000 0) { for (int k 0; k 10000; k) { auto it ref.find(k); bool exists (it ! ref.end()); auto found ht.Find(k); if (exists ! (found ! nullptr)) { cout mismatch at key k endl; abort(); } } } } cout stress test passed endl; }这个思路最重要的价值在于用 STL 验证自研代码的正确性。只要随机操作规模和检查频率够高绝大多数隐藏 bug 都会暴露出来。我实际跑这个测试抓过至少三个问题扩容丢数据、删除后找不到既有元素、以及状态标记更新遗漏。6.3 性能基准和 unordered_map 对比模拟实现不需要追求超越 STL但做个对比能直观看到自己的实现处在什么水平。用一千万元素连续插入和查找void BenchTest() { const int N 10000000; std::unordered_mapint, int stlMap; HashBucketint, int, HashInt myMap; auto t1 chrono::steady_clock::now(); for (int i 0; i N; i) { stlMap[i] i; } auto t2 chrono::steady_clock::now(); cout STL unordered_map insert: chrono::duration_castchrono::milliseconds(t2 - t1).count() ms endl; auto t3 chrono::steady_clock::now(); for (int i 0; i N; i) { myMap.Insert({i, i}); } auto t4 chrono::steady_clock::now(); cout My HashBucket insert: chrono::duration_castchrono::milliseconds(t4 - t3).count() ms endl; }实测下来我的模拟实现通常比 STL 慢 20% 到 50%这是正常的。STL 的哈希函数更优化、内存分配策略更好、甚至还有局部性优化。模拟实现能到 STL 七八成的性能说明思路和结构已经合格了。如果慢得离谱先检查是不是哈希函数太弱导致冲突过多再用上面的桶分布统计定位问题。写在最后的经验把闭散列和开散列两种方案都完整实现一遍再封装出 unordered_map 和 unordered_set这一步走下来你对哈希表的理解会和看文档完全不一样。我自己最大的体会是哈希表的结构本身不难难的是细节之间的耦合。状态标记、负载因子、扩容重哈希、析构和拷贝每一个环节单独看都很清晰但彼此咬合在一起时任何一个环节出错表现都不是报错而是“偶尔查不到”“偶尔内存泄漏”“偶尔死循环”这种玄学 bug。这也是为什么哈希表特别适合拿来练手——它逼你把内存管理、模板设计、边界条件处理这些 C 的基本功全部调动起来。最后分享一个我排查问题时的绝招在小规模数据上把每一步操作后的表内容完整打印出来插入、删除、扩容各打印一次用人眼盯着数据迁移过程看。这个方法虽然笨但比任何调试器都好使。有一次我扩容后数据错乱就是看着打印出来的旧表和新表逐行对比才定位到是漏了 DELETE 状态的判断。写得久了你就会发现数据结构这种东西写得越多对“为什么 STL 要这么设计”的理解就越深。你也试试把这份模拟实现从头到尾写一遍跑通所有测试你对哈希的理解绝对会上一个台阶。