哈希表在我心里的地位一直很特殊：看起来就是"数组加个函数"，可真要自己模拟实现一个闭散列版本，尤其是用线性探测处理冲突，你会发现每一行代码都在跟"边界条件"和"状态管理"较劲。今天这篇就专门聊闭散列加线性探测的模拟实现，我会把结构定义、哈希函数、插入查找、负载因子、扩容、删除这些环节逐个拆开，讲清楚每个设计为什么是这样，而不是只贴一段能跑的代码。文章适合正在学数据结构、准备手写哈希表作业或面试的人，也适合想搞明白语言库底层到底发生了什么的那类读者。
1. 哈希表的本质与闭散列方案的选型逻辑
1.1 从数组下标到键值映射：哈希函数在做什么
哈希表的核心思路，是借助一个哈希函数把"键"转换成一个数组下标。数组的随机访问是O(1)，所以如果每个键都能稳定映射到某个下标，插入、查找、删除就都成了O(1)操作。问题在于，绝大多数应用场景里，键的分布你事先并不清楚，字符串、结构体、自定义对象都可能作为键，所以必须有一个统一的办法把它们转成整数。
一个合格的哈希函数需要满足两个条件：计算要快，结果要散。比如对整数键直接强转去取模，对字符串则要设计合理的字符编码累加方式。但无论怎么设计，总会存在两个不同键映射到同一个位置的场景，这个现象就叫哈希冲突，也叫碰撞。
处理冲突的主流方案分两大派系：闭散列和开散列。闭散列也叫开放地址法，冲突发生时，元素还是放进当前表里，只是换一个位置；开散列则是每个数组位置挂一个链表或红黑树，冲突的键在同一个桶里按顺序存。闭散列里最基础的探测策略就是线性探测，也正是今天的主角。
1.2 闭散列 vs 开散列：为什么先学线性探测
线性探测的思路非常直白：当哈希函数算出的下标已经被占用，就往下一个下标继续找，直到找到一个空位放进去。假设表大小是10，键5映射到下标5，但下标5已经被占，就试着放6、7、8……直到放下。
我建议先学闭散列的线性探测，不是因为它在实际工程里用得最多，而是因为它把哈希表的通用矛盾暴露得最彻底。状态标记如何设计、删除时如何不断掉查找链、负载因子为什么要控制在0.7以下、扩容时为什么必须重新映射，这些问题在线性探测里全部绕不开。而这些问题一旦弄明白，再看二次探测、双重散列、链地址法，都会非常轻松，因为核心认知已经建立起来了。
1.3 模拟实现的价值：和语言库的哈希表有什么区别
很多人会觉得C++里有unordered_map，Java里有HashMap，何必自己再造轮子。实际上手写模拟实现有三个实实在在的价值。第一，语言库把内部细节全部封装了，你只知道"插入很快、查找很快"，但遇到极端数据变慢时，如果不懂负载因子和哈希函数，连排查方向都没有。第二，面试和考试经常要求独立完成哈希表的插入、删除、扩容逻辑，这不是背API能应付的。第三，自研场景下你可以按需定制，比如数据规模小且以查为主时，闭散列比链地址法省内存，但前提是你真的能把线性探测写对。
模拟实现最值得关注的地方，恰恰是语言库不会直接暴露的东西：数组中每个格子的状态。我们用了一个额外的状态字段来区分"空位""有效数据""已删除"，这个设计是整个闭散列模拟实现的地基。
2. 闭散列线性探测的骨架搭建：状态标记是它的灵魂
2.1 节点结构里的三态设计：EMPTY / EXIST / DELETE
先看最基础的部分：表里的每个格子，不能再只是保存一个键值对，还必须记录自己当前的状态。我定义了一个三态枚举：
enum State { EMPTY, // 空位，从未被使用过，或者扩容后新开辟的空间 EXIST, // 有有效键值对 DELETE // 之前有数据，但逻辑上已被删除 };每个格子的数据结构长这样：
template <class K, class V> struct HashData { pair<K, V> _kv; // 键值对 State _state; // 当前格子状态 HashData() : _state(EMPTY) {} };用vector来承载这些格子，比裸数组方便得多。vector扩容时，新格子会被默认构造函数初始化为EMPTY状态，不需要手动遍历赋值。哈希表本体除了vector之外，只需要再维护一个有效元素计数：
template <class K, class V, class Hash = DefaultHash<K>> class HashTable { public: HashTable(size_t size = 10) : _tables(size) , _n(0) {} private: vector<HashData<K, V>> _tables; // 底层数组 size_t _n; // 当前有效元素个数，也就是EXIST状态的格子数 };这里_n很关键，后续所有的负载因子计算和扩容判断都依赖它。我把它定义成"有效元素个数"，删除时减少、插入时增加，而不是简单地记录"数组用掉几个位置"，因为DELETE状态的位置不算有效元素，却仍然占用着格子。
2.2 哈希函数的设计：整数类型和字符串类型的差异化处理
闭散列的落位逻辑依赖哈希函数返回一个整数，然后对这个整数取表长余数。对于整数键，最常用的就是直接强转：
template <class K> struct DefaultHash { size_t operator()(const K& key) { return (size_t)key; } };这里要做一点说明：当表长设置成2的幂次时，取模等价于取二进制低几位，这样哈希值的高位信息就浪费了，极端情况下数据分布会变差。很多库在扩容时会选择素数作为桶的数量，就是为了规避这个问题。模拟实现阶段用扩容2倍的做法也可以正常工作，只是如果遇到构造出来的冲突数据，性能会差点。想严格一点的话，可以准备一组素数表，每次取大于当前容量两倍左右的素数作为新容量，这在很多经典教材里都有。
字符串键没法直接强转，需要设计一个从字符串到整数的映射。比较常用的是BKDR算法，可以理解为把字符串当成一个“大整数”，不断乘一个质数再加上当前字符的编码：
template <> struct DefaultHash<string> { size_t operator()(const string& key) { size_t hash = 0; for (size_t i = 0; i < key.size(); ++i) { hash = hash * 131 + key[i]; } return hash; } };乘子取131，是BKDR里常见的质数。为什么用质数？因为偶数的乘子容易导致低位信息丢失，质数能让结果分布更均匀。实际测试里，这个算法对付英文单词、数字串、混合串的表现都还不错。模板参数class Hash = DefaultHash<K>的写法也能让使用者在实例化时传入自定义哈希对象，灵活性更高。
2.3 为什么不能用数字0或-1来标记空位
初学哈希表时，我很长一段时间都觉得用固定值标记空位就行，比如把空格的key设成-1。后来才发现这条路走不通。原因有三个：第一，合法数据里完全可能包含-1，你无法区分它是真数据还是空位；第二，键是字符串时，空字符串也可以成为合法数据；第三，删除操作如果直接把格子内容清成默认值，会切断后续查找的探测链，这点后面专门讲。
所以必须把"格子的物理内容"和"格子的逻辑状态"分开。物理内容就是_kv，状态就是_state。这是闭散列模拟实现里最重要的一步，也是后续所有逻辑正确性的基础。
还有一个很容易被忽略的细节：计算下标时取模的对象必须是_tables.size()，也就是当前实际管理的格子数量，而不是capacity()。vector的capacity是预留容量，不是逻辑长度，用它取模会造成映射错乱。
3. 插入与查找配套实现：负载因子的计算与扩容触发
3.1 插入流程拆解：映射、探测、落位三步走
插入的完整逻辑可以拆成四步：先判重，再检查负载因子并决定是否扩容，然后算初始下标，最后线性探测找一个空位放进去。直接看代码：
bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; // 负载因子判断：_n / _tables.size() >= 0.7 时扩容 if (_tables.size() == 0 || _n * 10 >= _tables.size() * 7) { HashTable<K, V, Hash> newTable(_tables.size() == 0 ? 10 : _tables.size() * 2); for (auto& data : _tables) { if (data._state == EXIST) newTable.Insert(data._kv); } _tables.swap(newTable._tables); swap(_n, newTable._n); } Hash hf; size_t hashi = hf(kv.first) % _tables.size(); size_t index = hashi; size_t i = 1; // 线性探测：当前位置被占用，就往后找 while (_tables[index]._state == EXIST) { index = hashi + i; index %= _tables.size(); ++i; } _tables[index]._kv = kv; _tables[index]._state = EXIST; ++_n; return true; }注意index %= _tables.size()，这一行特别重要。线性探测的表是一个“环形”概念，探测到数组末尾之后必须回头从开头继续，不取模就会越界。很多第一版实现翻车都翻在这里。
插入前先调Find判重，是为了保证同一个key不会被插入两次。如果允许重复插入，第二次大概率会落到另一个空位，表中就会出现两个相同key，查找、删除都会混乱。标准库的 insert 对已存在的key也是不覆盖的，模拟实现保持一致比较省心。如果你希望更新value，可以单独提供一个Set或operator[]的语义，不在插入函数里混着做。
3.2 查找流程拆解：遇到空位才能停下，遇到删除位必须继续
查找逻辑是闭散列里最容易写错的地方。代码长这样：
HashData<K, V>* Find(const K& key) { if (_tables.size() == 0) return nullptr; Hash hf; size_t hashi = hf(key) % _tables.size(); size_t index = hashi; size_t i = 1; while (_tables[index]._state != EMPTY) { if (_tables[index]._state == EXIST && _tables[index]._kv.first == key) { return &_tables[index]; } index = hashi + i; index %= _tables.size(); ++i; } return nullptr; }关键差异在循环条件：只有遇到EMPTY，才能断定探测链已经走完、表中不存在这个key。遇到DELETE不能停，必须继续往后走，因为被删掉的那个元素可能只是占了一个坑，真正想找的目标还在后面。
为了让逻辑更稳妥，我建议在循环里加一个计数器，最多探测_tables.size()次就返回nullptr。虽然正常扩容机制下永远不会出现表被填满找不到空位的情况，但防御性代码不会吃亏，万一某次不小心让负载因子超了，至少程序不会死循环。
3.3 负载因子0.7是怎么来的
负载因子记为 alpha，等于有效元素个数除以表长，也就是_n / _tables.size()。它描述的是整张表的拥挤程度。
线性探测的效率对负载因子非常敏感。当表比较空时，冲突少，探测次数接近1；当表接近满时，冲突链变长，探测次数急剧上升。闭散列必须留出一定量的空位，让探测链始终能终结于EMPTY格子。一般会把扩容阈值定在0.7到0.8之间。
代码里的判断我写成乘法形式：
if (_tables.size() == 0 || _n * 10 >= _tables.size() * 7)这等价于判断_n / _tables.size() >= 0.7，但全程使用整数运算，避免了浮点精度和整数截断带来的边界误差。比如_n * 10 / _tables.size() >= 7这种写法，在某些边界值上可能因为整除截断而产生偏差，用乘法比较则不会。
为什么是0.7而不是0.9？因为线性探测下平均探测次数和负载因子的关系不是线性的。在负载因子为0.7时，一次成功查找平均约需要探测1.5到2次左右，仍然接近常数时间；如果放到0.9，失败查找的探测次数会飙升到几十次，性能会断崖式下跌。这个数学关系我在后面的章节里详细展开。
4. 扩容的完整链路：旧表数据重新映射是高频翻车点
4.1 扩容前必须解决的两个边界问题
第一个边界是空表。如果构造函数允许传0，或者提供默认无参构造，那么_tables.size()一开始就是0。第一次插入时直接hf(kv.first) % _tables.size()会触发除零错误。所以扩容判断的第一条就是_tables.size() == 0，这时需要先分配初始容量，我习惯给10。
第二个边界是扩容时机。必须在插入新元素之前检查负载因子，而不是插入之后再检查。如果等表满了才扩容，旧表里的数据已经是“满”状态，转移过程的探测逻辑本身就很难处理，而且线性探测在表满时查找不存在的key会死循环，非常危险。标准做法是“插入前先判断，超标就先扩容”。
4.2 异地扩容与重新映射：直接拷贝数组为什么是错的
我第一次写哈希表扩容时，第一反应是：新表容量翻倍，然后把旧表元素挨个拷贝过去，最后交换vector。这个方案在闭散列下是错的，而且是隐蔽的错误。
原因在于哈希函数的取模操作依赖表长。同样的key，在旧表里取模得到下标5，在新表里取模可能得到下标13。如果直接把旧表下标5的元素拷到新表下标5，那位置就是错的，后续查找时按新表重新计算下标，会去一个完全不同的地方找，自然找不到。
所以扩容必须做"重映射"：遍历旧表的每一个格子，只把EXIST状态的数据提取出来，然后对新表执行Insert，让每个元素在新表里重新计算下标、重新探测落位。流程如下：
- 创建新表，容量设为旧表两倍
- 遍历旧表，取所有EXIST状态的键值对
- 对每个键值对执行新表的Insert
- 交换新表和旧表的底层数组，以及有效元素计数
这个转移过程是O(n)，不是O(1)。但因为负载因子的存在，平均每插入若干次才会触发一次扩容，分摊到每次插入的代价仍然是常数级别，这就是摊还分析的基本思路。
4.3 关于扩容时复用Insert的递归风险
扩容代码直接复用了newTable.Insert(data._kv)，这里有个潜在的担心：新表在转移过程中，负载因子会不会再次超0.7，导致递归扩容？实际上不会。旧表容量是 oldSize，有效元素最多约0.7oldSize个，新表容量是2oldSize，转移结束后的负载因子最多约为0.35，离0.7还很远，所以不会递归。这个设计是安全的，但建议在注释里写清楚，免得后人看到递归调用心里发慌。
同样要注意的是，转移时只处理EXIST状态。DELETE状态的格子是历史残留，不需要搬进新表，新表的空间重新空闲出来，反而顺带做了一次“碎片整理”。这也是闭散列里重哈希的一种附加收益。
4.4 扩容大小的选择：翻倍背后的成本权衡
新表容量一般取旧表两倍左右。太小会频繁触发扩容，搬移数据的成本升高；太大则浪费内存，且让负载因子被稀释到很低的水平，虽然更“空”了，但空间的利用率下降了。两倍在时间和空间上是比较合理的折中。
如果你想让分布更均匀，可以把“扩容两倍”改成“扩容到下一个素数”。我会在实现时维护一个素数表，比如 7、17、37、79、163、331……每次取第一个大于两倍旧容量的素数。因为表长为素数时，取模和哈希值低位的相关性更弱，冲突会更少。模拟实现阶段不强求，但知道这个优化方向是有价值的。
5. 删除操作的两难：闭散列里为什么不能物理删除
5.1 物理删除会切断探测链
我用一个具体例子来说明。假设表大小10，现在依次插入三个key：1、11、21。它们经过哈希后都落在下标1附近，最终存储结果是这样的：
| 下标 | 1 | 2 | 3 |
|---|---|---|---|
| 状态 | EXIST | EXIST | EXIST |
| key | 1 | 11 | 21 |
如果这时候删除11，并且把格子2的物理数据清空，状态设为EMPTY，会发生什么？查找21时，从下标1开始探测：下标1是key为1的EXIST格，不是21，继续；下标2变成EMPTY，按查找逻辑直接返回nullptr。可21明明存在下标3。这就是探测链被物理删除切断的后果。
所以闭散列下不能真删，只能通过状态标记来“软删除”。
5.2 DELETE状态标记与查找、插入的配合
删除的实现因此变得非常简单：
bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret) { ret->_state = DELETE; --_n; return true; } return false; }这里能这么写，是因为Find返回的是格子指针。找到key之后，不碰_kv，直接改状态，同时把有效元素计数减一。DELETE格子里残留的键值对不参与任何查找匹配，但它作为“探测链上的一环”，依然能帮助后续查找跳过这个位置继续往后走。
插入时，探测循环的条件是while (_tables[index]._state == EXIST)，这意味着遇到DELETE和EMPTY都会停下来，直接把新数据放进去。这样，删除留下的坑会被后续插入重新利用，不会因为历史删除而永久浪费空间。
5.3 删除后的表到底长什么样
继续用前面的例子。删除11之后，表的状态是：
| 下标 | 1 | 2 | 3 |
|---|---|---|---|
| 状态 | EXIST | DELETE | EXIST |
| key | 1 | 11（残留） | 21 |
此时_n等于2，和那张表里EXIST格子数量一致。查找25时，从下标5开始探测：下标5的key是5，不对；下标6是DELETE，跳过继续；下标7找到25。完美避开被切断链的坑。
不过也要知道这种软删除的代价：DELETE格子里的数据虽然逻辑上不存在了，但物理上仍然占着位置，无法通过_kv的析构及时释放资源。如果键值对里持有动态内存，会有一定的延迟释放问题。模拟实现阶段这不是大问题，但在设计生产级闭散列时，可以考虑定期重哈希清理DELETE格子，或者让扩容来吸收这些残留。
6. 线性探测的聚集现象与进阶优化方向
6.1 主聚集的成因与对查找效率的影响
线性探测有一个先天缺陷，叫主聚集。当表中某一段连续区域被占满后，任何一个新元素哈希到这段区域里的任意位置，都会顺着连续段一路探测到末尾的下一个空位，然后停在末尾。结果是这段连续区域越变越长，查找时需要跳过的格子也越来越多。
用一个生活化类比：就像停车场，大家都把车停在靠近入口的位置，一旦入口前的通道被占满，后来的车只能一辆接一辆往深处排。越是高峰时段，排队长龙越长，想找到某辆车就越慢。
主聚集意味着线性探测的效率高度依赖负载因子。表越满，连续区域越长，性能衰减越快。这也再次解释了为什么闭散列一定要把负载因子控制住。
6.2 探测次数期望：为什么负载因子是生死线
线性探测的效率可以用两个近似公式来衡量。设负载因子为 alpha，则：
- 成功查找的平均探测次数约为：(1 + 1/(1-alpha)) / 2
- 失败查找的平均探测次数约为：(1 + 1/(1-alpha)^2) / 2
当 alpha=0.7 时：
- 成功查找约2.17次
- 失败查找约5.06次 这个水平还可以接受。
但当 alpha=0.9 时：
- 成功查找约5.5次
- 失败查找约50.5次 失败查找基本退化成一个接近O(n)的操作，这已经不是“哈希表”该有的性能了。
所以闭散列的负载因子就是生死线。0.7是一个兼顾空间和时间的经验值，它让查找的探测次数维持在个位数级别，同时表又不是太浪费空间。
6.3 二次探测与双重散列的替代思路
理解了线性探测，再往后看其实很自然。线性探测的步长固定为1，所以一旦出现聚集，后面全挤在一起。二次探测把第i次探测的步长改成 i 的平方，探测序列变成 h、h+1、h+4、h+9……这样冲突的键会散布得更开，主聚集会大幅缓解。但二次探测也有自己的约束：表长需要是素数，且负载因子最好控制在0.5以内，否则不一定能找到空位。
双重散列的思路则更进一步：用第二个哈希函数决定探测步长。即使两个key的第一次哈希落点相同，只要第二次哈希算出的步长不同，它们的探测路径就不一样，相互干扰更小。这个方案在理论和实践上都比线性探测更均匀，但实现复杂度也更高。
从学习路径来看，我仍然建议先把线性探测吃透。状态标记、负载因子、扩容重映射这些核心问题，在任何一种闭散列里都存在，先在线性探测里解决一遍，后面学任何方案都会快很多。
6.4 模拟实现后的验证经验
最后分享一个我自己的调试经验。写完这个模拟实现之后，不要直接上几十个随机数据进行测试，那样出了问题根本不知道卡在哪一步。我习惯的做法是：开一个容量只有5的小表，手动插入3个必然冲突的key，然后拿纸笔画一遍探测路径，确认插入位置符合预期。再手动删除中间那个key，继续画一遍查找路径，看能不能找到最后一个key。这个操作能把绝大多数逻辑错误暴露在肉眼可见的层面。
调试时给 HashTable 加一个打印函数也很管用，把每个格子的下标、状态、key全部打印出来。尤其是扩容和删除这两个环节，打完状态变化图基本就能定位问题所在。很多“看起来没毛病但就是找不到数据”的bug，最后都出在扩容没有重新映射，或者删除后没做状态标记这两个点上，打印一下就能一眼看穿。
