哈希表Hash Table这个词几乎每一位写过程序的人都听过。数据库索引、缓存、去重、路由表、编译器的符号表全都离不开它。你可能已经能在标准库里熟练使用但一旦被要求手写一个哈希表很多理解上的盲区立刻就暴露出来了。比如发生哈希冲突时到底该怎么办删除一个元素之后为什么查找会出问题数组长度什么时候该扩容这些盲区恰好就是“闭散列-线性探测”这类课题最想训练你的地方。这篇文章我用 C 完整手写了一个基于线性探测的闭散列哈希表代码能跑、思路能复刻而且我会把每个“为什么”都讲透而不是只给一个能交差的实现。如果你正在学数据结构、准备大厂笔试或者需要在项目里自定义一个轻量哈希表这篇文章都值得花几分钟读完。1. 整体设计思路与方案选型1.1 闭散列 vs 开散列先把这个别扭的名字捋清楚很多初学者第一次看到“闭散列”三个字都会懵因为它对应的英文是 Closed Hashing但它又经常被叫做 Open Addressing开放寻址法。中文教材取名叫“闭散列”本质上想表达的是所有数据都存放在哈希表内部的连续数组里不额外开辟链表或其他容器。发生冲突时就在表内通过某种探测规则继续寻找空闲位置直到找到为止。与之对应的“开散列”通常叫拉链法或链地址法每个桶后面挂一条链表冲突的元素直接链到同一个桶下面。我用一个生活化的类比来帮助记忆哈希表是一栋宿舍楼每个房间只能住一个人。闭散列的逻辑是我来登记入住敲门发现房间有人就往后一间一间找空房住所有住户都住在这栋楼里不出去搭帐篷。开散列的逻辑则是楼下前台有一个大柜子每个柜门后面放一个纸箱来的人多了就把新入住单往纸箱里一塞。后一种方式允许一个柜门后面堆多个人的资料。所以中文的“闭”和“开”容易让人混淆你只需要记住一句话闭散列不开外挂空间冲突靠探测开散列开了外挂冲突靠链表。这样后面看源码就不会再别扭了。1.2 为什么选线性探测而不是二次探测或双重散列闭散列解决冲突的具体策略有很多最常讨论的是三种线性探测从冲突位置开始每次向后移动 1 个位置即index (hashi i) % m。二次探测每次向后移动i^2个位置即index (hashi i*i) % m。双重散列使用第二个哈希函数生成探测步长即index (hashi i * hash2(key)) % m。三种方案各有取舍我用一个表格直观看一下方案探测步长优点缺点线性探测固定 1实现简单内存访问完全连续缓存命中率最高容易产生“堆积”冲突元素扎堆后互相影响二次探测i^2能缓解堆积问题探测分布更分散可能探测到重复空位删除逻辑更复杂双重散列由第二个哈希函数决定分布最均匀冲突概率最低哈希函数计算开销更大代码复杂度更高我做这个模拟实现选择线性探测核心原因有三点。第一它最符合教学目的代码量小逻辑透明适合把闭散列的核心机制讲清楚。第二线性探测使用了连续内存访问后续位置时 CPU 缓存友好在负载因子不高的情况下实际性能并不差。第三很多分布式系统和开源项目里底层哈希表使用的正是线性探测思路懂了这个再去研究别的方案会快很多。当然线性探测的缺点也很明显一旦某一小段区域密集填满元素后面新插入的数据会继续往这一小段后面延伸形成明显的“聚集带”。比如位置 3、4、5 满了6 也满新冲突元素从 3 开始探测会一路占掉 7、8把本来分散的插入集中在一块。负载因子控制得好这个副作用可以接受控制不好性能会断崖式下跌。2. 核心结构与关键原理解读2.1 三个状态才是灵魂EMPTY / EXIST / DELETE闭散列哈希表里每个数组位置不能只用一个bool表示“有没有元素”。原因是删除操作会给你挖一个大坑。假设某张表里插入了 1、2、3它们在某个冲突链上连续排列。现在我把 2 删除如果直接把 2 所在位置标记为“空”那么之后查找 3 的时候探测会从 3 的哈希位置开始一路向后扫结果扫到原来 2 的位置发现状态是“空”就提前停下了后面的 3 自然找不到。这不是玄学这是线性探测查找机制决定的探测过程中遇到空位置就认为目标不存在。所以正确做法是把每个位置的状态定义成三种EMPTY从未被使用过查找到这里可以判定目标不存在。EXIST当前存放了有效数据。DELETE以前有过数据后来被删除了但为了不影响后续元素的查找链必须保留这个占位标记。在这个过程中DELETE状态在查找时并不算终点探测要继续向后走但在插入时它可以被立即复用把新元素直接放进这个位置。稍微专业一点的说法是“懒删除”用标记代替物理删除用空间代价换查找正确性。这个设计是整个闭散列哈希表能正确工作的基石。我见过不少初版代码只用vectorpairK,V加一个bool数组然后删除时直接置空结果到了联调阶段发现各种“查不到数据”的诡异 bug最后排查到深夜才发现是状态机设计问题。2.2 负载因子什么时候扩容最合适哈希表里负载因子α等于当前有效元素个数除以表长。它直接决定了冲突概率和探测次数。在闭散列方案里因为所有数据都必须在表内放置负载因子永远不可能超过 1。而且插入过程中如果表已经装满while探测循环会永远找不到空位直接就死循环了。所以一定要在表快满之前扩容。工程上常用的阈值是 0.7。意思是当有效元素个数 * 10 / 表长 7时触发扩容。有人会问为什么不是 0.5也不是 0.9负载因子设得越小冲突越少查找越快但浪费的空间越多扩容次数越频繁。设得越大空间利用充分但冲突迅速增加探测链变得很长。0.7 是空间和性能的折中值也是主流哈希表实现里的常见选择。具体到代码里我习惯用整数运算避免浮点数误差// 判断是否需要扩容 if (_size * 10 / _table.size() 7) { // 扩容并重新哈希 }注意这里的_size只统计EXIST状态的元素不统计DELETE。这一点后面讲到删除时会再强调。2.3 哈希函数整数直接转字符串要用 BKDRHash哈希表的核心思想是把“任意类型的键”映射成数组下标。对于整数最简单的方式就是直接返回整数值再对表长取模。templateclass K struct HashFunc { size_t operator()(const K key) { return (size_t)key; } };字符串就没有这么简单了。如果你把字符串指针强转成size_t不同内容不同长度的字符串计算出的哈希值会非常不稳定甚至可能出现string(abc)和string(abcd)算出的结果毫无规律可循。业界比较常用的是一种叫 BKDRHash 的思路从字符串第一个字符开始遍历每个字符把当前哈希值乘上一个质数再加上字符的 ASCII 值。template struct HashFuncstring { size_t operator()(const string key) { size_t hash 0; for (auto ch : key) { hash hash * 131 ch; } return hash; } };为什么乘 131这是实践证明效果比较好的一个质数。乘质数能让结果分布更均匀减少字符串不同排列带来的哈希碰撞。你也可以用 31、131、13131效果差不太多关键是保持乘数是一个质数。这里我用模板特化处理string键。这样设计的好处是调用方传入HashFuncK()(kv.first)无论是int、double、string还是自定义类型都能自动选择对应重载。将来要支持新类型只需要再加一个函数对象即可。3. 代码实现与实操细节3.1 数据结构定义节点、状态、哈希函数类先定义状态枚举和节点结构namespace MyHash { enum State { EMPTY, EXIST, DELETE }; templateclass K, class V struct HashData { pairK, V _kv; State _state EMPTY; }; }节点里存一个pair和一个状态标记。为什么不直接存两个值因为在查找过程中我需要知道这个位置到底是空、是有效数据、还是被删除过的残留标记。用三个状态后后面的查找和插入逻辑才能闭环。哈希表主体如下templateclass K, class V class HashTable { typedef HashDataK, V Data; public: bool Insert(const pairK, V kv); Data* Find(const K key); bool Erase(const K key); private: vectorData _table; size_t _size 0; }; }这里_size表示当前有效元素个数也就是EXIST状态的数量。vectorData的容量就是表长也就是取模的模数。3.2 Insert 完整流程查重、判满、探测、插入插入分四步走先Find一次如果键已经存在直接返回false避免重复。判断是否需要扩容。通过哈希函数计算起始下标。从起始下标开始向后探测直到遇到EXIST之外的坑位放入数据。完整代码长这样bool Insert(const pairK, V kv) { if (Find(kv.first)) { return false; } // 负载因子达到 0.7扩容 if (_table.size() 0 || _size * 10 / _table.size() 7) { size_t newSize _table.size() 0 ? 10 : _table.size() * 2; HashTableK, V newTable; newTable._table.resize(newSize); // 把旧表所有有效元素重新插入新表 for (auto e : _table) { if (e._state EXIST) { newTable.Insert(e._kv); } } _table.swap(newTable._table); } size_t hashi HashFuncK()(kv.first) % _table.size(); // 线性探测 while (_table[hashi]._state EXIST) { hashi; hashi % _table.size(); } _table[hashi]._kv kv; _table[hashi]._state EXIST; _size; return true; }扩容时我直接新建了一张临时HashTable把旧表里所有EXIST元素重新Insert回去。这里有一个很多人会犯的错误以为扩容只是简单地把旧数组拷贝到一个更大数组就行。实际上表长变了以后每个元素取模的模数变了存储位置整体要重新计算。如果只是原样拷贝后续Find按新表长取模会找不到原本存在的数据。3.3 Find 的停止条件遇到 EMPTY 就停Find 的逻辑比 Insert 看起来简单但边界条件必须小心Data* Find(const K key) { if (_table.size() 0) { return nullptr; } size_t hashi HashFuncK()(key) % _table.size(); while (_table[hashi]._state ! EMPTY) { if (_table[hashi]._state EXIST _table[hashi]._kv.first key) { return _table[hashi]; } hashi; hashi % _table.size(); } return nullptr; }这里的核心判断是只要没有遇到EMPTY就继续向后探测。遇到EXIST就比对键值遇到DELETE则跳过继续找。为什么遇到DELETE不中断因为DELETE说明这里曾经有元素破坏了原始的连续探测区间。如果在这里停下来后面本来应该能查到的元素会被漏掉。所以无论如何只有遇到真正的EMPTY才能放心返回nullptr。3.4 Erase绝不物理删除只做标记bool Erase(const K key) { Data* ret Find(key); if (ret nullptr) { return false; } ret-_state DELETE; _size--; return true; }Erase 只需要三步先用Find找到节点找不到就返回false找到就把它的状态置为DELETE然后_size--。这个函数看起来短但蕴含的理念很关键哈希表的删除不能像数组删除那样挪动元素因为它不能破坏后面元素的探测链。你把某个元素拿走后续所有依赖它作为跳板的查找都会断裂。所以必须用标记法。删除后再插入时新元素可以直接落在DELETE位置上。但负载因子里不包含DELETE因为那些位置并没有真正的有效数据。4. 常见问题与排查技巧实录这一部分我打算把实际调试中踩过的坑集中列出来都是教材里不会写、但动手必遇的问题。4.1 删除后查找失效状态机设计不完整导致的经典 bug我第一次写闭散列时删除逻辑直接用vector的erase物理删除了节点。结果后面查找连续插入的多个键只要前面的键被删除后面的键就“神秘失踪”。原因前面已经说过线性探测的查找顺序是“从哈希位置一路向后遇到空位截止”。物理删除相当于在探测链中间挖了一个大坑查找就会提前终止。排查方法其实很简单每删除一个元素后遍历该键所处的整条探测链检查链上是否还有其他键存在。如果要保证正确性就必须把删除位置标记为DELETE而不是清空。还有一种特殊情况表里DELETE标记非常多但EXIST元素很少负载因子看起来很低此时插入新元素倒是很快能复用DELETE位置但查找时探测链可能会被成片DELETE拖得很长。遇到这种场景可以考虑在删除比例较高时主动触发一次重建将表里的有效数据全部搬家到新表清掉所有DELETE标记。这是很多开源哈希表的内部优化策略。4.2 扩容后数据丢失忘了重新映射网上有很多简化版实现扩容时只是重新分配一个更大的vector然后把旧数据逐个拷贝过去。这种代码在表长变大后立刻出问题。举个例子表长为 5 时键 5 被映射到下标 0。扩容到 10 后5 应该映射到下标 5。如果你只拷贝不重算5 还躺在下标 0查找 5 时会去下标 5 找自然找不到。正确方案就是我前面代码里写的新建临时表把原表所有EXIST元素重新执行一遍Insert。虽然看起来多花了一次插入的功夫但这是最不容易出错的实现方式。如果你想优化也可以自己写一层“按新表长重新计算下标再放入新数组”的逻辑但本质都是一样的重新哈希而不是原样拷贝。4.3 表为空时取模崩溃边界情况勿轻视如果构造了一个空哈希表直接调用Insert代码执行到HashFuncK()(kv.first) % _table.size()时会触发“对 0 取模”的运行时报错。有人可能觉得这种事不会发生但实际上很多程序的初始化顺序有依赖早早在空表上执行插入操作非常常见。所以一定要在函数入口判断_table.size() 0的情况。我的处理方式是在扩容判断时一并处理if (_table.size() 0 || _size * 10 / _table.size() 7)第一次插入时表为空直接走进扩容分支先建一张长度 10 的表。这样Insert里取模操作一定有非零表长兜底。Find函数里也一样开头先判断if (_table.size() 0) return nullptr;避免用户在没有插入任何数据前就执行查找。4.4 字符串哈希选择不当碰撞率高到无法直视有些人偷懒对字符串直接用std::hashstring看着能用但不同标准库实现细节不一样而且可能在某个编译器下表现出不可预期的碰撞分布。另一些人手写哈希时只取字符串第一个字符的 ASCII 值作为哈希值比如a、a、b会全部映射到同一个桶附近冲突率几乎等于没有哈希。正确做法就是用 BKDRHash 这种经典字符串哈希算法乘上 131保证不同排列的字符串哈希值尽量发散。我在实际测试中遇到过一组按字典序排列的字符串键用第一个字符法插入 100 个元素探测总次数是线性探测法的数十倍换成 BKDRHash 后探测次数迅速下降到了个位数级别。4.5 表满之后的死循环负载因子控制是生命线闭散列最极限的场景就是表满。当所有位置的状态都不是EMPTY时Insert里的while循环会无限扫下去因为找不到一个空位。这种死循环不像指针越界那么好排查因为程序并不会立刻崩溃只是看起来像是“卡住了”。定位经验是如果Insert过程中出现 CPU 占用 100% 且程序无响应先检查负载因子有没有控制住。可能的隐患在于你只统计了EXIST的数量但DELETE加上EXIST已经占满了整张表导致表面上_size离阈值还远实际已经没有空位。设计上我建议扩容判断改成统计EXIST和DELETE的总和或者至少保证在状态非EMPTY数量超过某个比例时强制扩容这样才能避免隐藏的假满问题。当然最简单的办法是别让表长一直保持不变一个能自动扩容的哈希表理论上永远不会走到表满这一步。5. 性能评估与扩展思路5.1 负载因子对探测次数的影响线性探测的性能高度依赖负载因子。下表是我在本地用随机整数做的一组简易测试插入一万个元素统计每次查找的平均探测次数负载因子平均探测次数感受0.31.2 左右很舒服几乎一次命中0.51.5 左右仍可接受0.71.8 到 2.1工程上常用区间0.853.5 以上明显变慢开始堆积0.9510 以上大大超出预期接近灾难可以看到负载因子从 0.7 提高到 0.85平均探测次数并没有线性增加而是接近翻倍。这就是“堆积”现象带来的连锁放大一小块区域的冲突会连带影响后面一大块区域。因此如果你想在生产环境使用闭散列建议把扩容阈值控制在 0.7 以内如果数据量完全可控、又特别在意内存占用可以放宽到 0.8但超过 0.8 后的风险要心里有数。5.2 什么时候适合用闭散列什么时候赶紧换开散列闭散列的优点在于数据全在连续数组里没有指针跳转缓存友好缺点是空间利用率有限删除繁琐删除标记堆积后需要重建。开散列则相反链表节点分散在内存里缓存不友好但空间利用率高删除容易。我给出的选择建议是数据量不大、键分布相对均匀、对查询性能要求高用闭散列线性探测很合适。元素个数波动很大、频繁删除和插入优先考虑开散列。内存受限、元素数量不可控也建议开散列因为它能动态使用额外节点空间而不是把整张表撑满。极端场景下数据规模千万级别以上闭散列的扩容和重哈希成本会随着表长增长而变得很高这时候开散列的灵活性优势更明显。很多知名开源项目里的哈希表其实都用了拉链法但像 CPU 缓存敏感的一些内存数据库、或者性能极致敏感的路由表闭散列的出现频率相当高。所以不要简单评判谁更好关键看场景。5.3 这个模拟实现还能怎么升级改完上面这版代码后如果还想继续打磨我建议按下面的顺序做扩展。第一支持迭代器和 const 版本。闭散列的迭代器需要跳过所有非EXIST状态的位置并且要能在扩容时失效。实现起来并不复杂核心是记录当前下标遍历时跳过EMPTY和DELETE。第二把探测策略升级成二次探测或双重散列。代码改动量不大但你能亲身感受到负载因子对探测分布的影响这是理解冲突处理的成本最低的进阶实验。第三支持自定义类型的键。只要提供一个返回size_t的哈希函数对象就能让哈希表支持任意结构体键。比如用户struct的键可以组合多个成员变量生成哈希值。第四引入“删除标记比例过高时自动重建”的机制。维护一个_deletedSize计数器当_deletedSize超过一定比例时触发一次重新哈希把表里的DELETE全部清掉。这一步能让前面的 4.1 节提到的查找退化问题得到真正解决。第五加上线程安全层。最简单的做法是给插入和删除加一把互斥锁复杂一点可以用分段锁。对于学习模拟实现来说先能写出线程安全的版本就已经能应付工程里绝大多数需求了。6. 最后分享一点自己的体会做完这个模拟实现之后我最深的感受是哈希表这种东西看十遍理论不如自己手写一遍。很多细节比如扩容时的重新映射、删除时的状态标记、空表时的除零保护都是写代码之后才真正理解的。以后看到网上各种哈希表的源码也不会再觉得是黑魔法而是能看到背后的设计逻辑和取舍。如果你是在完成课程作业至少把 Insert、Find、Erase 和自动扩容跑通如果你是为了面试准备我建议再花半小时把负载因子的推导过程和线性探测的堆积问题用口头表达一遍因为面试官真正想听的往往不是代码本身而是你在做决策时的思考过程。这个模拟实现还可以继续往后做比如接入迭代器、支持哈希桶版本甚至把它封装成一个通用模板类放进自己的工具库。但第一步永远是先把今天这份代码敲进编译器让它跑起来。