企业官网建设流程全解析

散列冲突处理这五个字，是我每次带新人做数据结构复盘时必问的一道题。原因很简单：几乎所有人都能背出“哈希表平均查找是 O(1)”，但真正落到工程里，决定这套结构跑得快不快的，从来不是“平均”两个字，而是冲突发生之后你打算怎么办。冲突处理方案选错了，负载因子给高了，哈希函数偷懒了，线上表现就是从 P99 抖动、CPU 打满到请求超时一条龙。这篇文章把链地址法和开放地址法这两种主流散列冲突处理思路从头拆一遍，讲清楚它们的结构差异、探测代价、删除代价、参数怎么定、各语言的工业实现为什么那么选，也会给出可以直接抄的实现代码和一份排查清单。适合已经会写哈希表但想弄明白底层取舍的人，也适合正在做性能优化、被某个偶发慢查询折磨的同行。

1. 先把冲突这件事说透：为什么它绕不过去

1.1 哈希表的速度承诺依赖一个前提

哈希表能把查找做到接近常数时间，靠的是一个非常朴素的动作：把键丢进一个函数，直接算出它应该待在哪个格子里，然后一步跳过去。这个过程省掉了比较、跳转、逐层下探，所以快。但这份快有一个前提条件被大多数人忽略——算出来的位置必须尽量不撞车。

现实中键的取值空间通常远大于桶数组的长度。你要在 16 个格子里放下成千上万个键，无论函数设计得多巧妙，不同键映射到同一个下标都是必然事件。这不是实现瑕疵，而是信息论层面的硬约束：把 N 个元素的映射压进 M 个格子里，只要 N 大于 M，就一定有格子被多个键选中。所以真正的问题不是“怎么消灭冲突”，而是“冲突已经发生了，接下来这堆数据怎么放、怎么找、怎么删”。

我见过不少代码在这件事上偷懒：以为键足够随机就不会撞，于是不做任何冲突处理，发现位置被占就直接覆盖。结果就是数据静默丢失，测试环境数据量小看不出来，一上生产就出问题。这种坑一旦踩过，基本一辈子忘不掉。

1.2 冲突的严重程度由两个量决定

冲突频率由两个独立变量共同决定：桶数组的容量，和往里面装了多少元素。行业里习惯用装载因子 α 描述后者，也就是已存元素数除以桶数量。α 越大，撞车概率越高；α 越小，浪费的空间越多。

这个权衡不是凭感觉拍脑袋的。开放地址法下，用一个不碰撞的概率去推期望探测次数，会得到一个关于 α 的分式表达式。拿线性探测举例，成功查找的期望探测次数约等于(1 + 1/(1-α)) / 2，查找失败约等于(1 + 1/(1-α)²) / 2。把 α 从 0.5 提到 0.75，成功查找从 1.5 次涨到 2.5 次，看起来还凑合；但失败查找从 2.5 次暴涨到 8.5 次，这就是质变了。

而链地址法因为每个桶可以挂多个节点，同样 α 下期望探测次数是1 + α/2（成功）和α（失败），曲线平缓得多。这就是为什么两种方案在工程里会采用完全不同的装载因子上限。理解了这个差异，后面所有的参数选择都能自己推出来，不用死记硬背。

1.3 两条路线，一个根本分歧

链地址法和开放地址法的分歧点可以浓缩成一句话：冲突的元素放不放进桶数组本身。

链地址法说，桶数组只存链表头，冲突的元素作为链表节点挂在外面，数组里的每个槽位永远只负责“指路”。开放地址法说，所有元素都住在数组里，这个位置被占了就按某个固定规则往后找下一个空位，直到塞进去。

这个分歧看起来只是摆放方式不同，但它像蝴蝶效应一样影响了一整条链路：内存布局、缓存命中、删除实现、扩容策略、迭代器语义、并发处理方式，全都不一样。库作者选择哪一种，往往不是因为它“更好”，而是因为它的劣势在那个特定场景下不重要。下面逐个拆开看。

2. 链地址法：把冲突挂出去，结构上最简单

2.1 结构设计：一个数组加N条链

链地址法的结构极其直白。一个桶数组，每个元素是一个指针，指向一条链表（或者别的容器）。插入时算出下标，如果该位置为空就挂上第一个节点，否则沿着链表找，找到同键就更新，没找到就追加。

typedef struct Node { int key; int value; struct Node *next; } Node; typedef struct { Node **buckets; /* 桶数组，每个元素是一条链的头指针 */ size_t capacity; /* 桶数量 */ size_t size; /* 元素总数 */ } ChainMap;

我特别喜欢拿快递柜做类比。桶数组是一排柜子编号，哈希函数是“按手机号后两位决定去几号柜”。如果两个收货人的手机号后两位撞了，柜子里放不下两个人的包裹，那就第一个包裹放柜里，旁边贴张纸条“第二个包裹在下面的隔层”，链式地找下去。柜子编号的作用只是把搜索范围缩小，真正定位靠的是顺着纸条走。

这个结构最大的好处是它不需要在数组内部折腾。插入逻辑简单、删除逻辑简单、扩容逻辑也简单，因为每个桶的容量是弹性的，不会因为暂时多几个元素就报警。

2.2 一个能跑的最小实现

下面这份代码是我平时用来面试候选人或者做小工具时的版本，省掉了内存管理的花哨部分，重点看冲突处理逻辑。

#include <stdlib.h> #include <string.h> static size_t hash_int(int key, size_t cap) { /* 简单混合，避免低位规律性太强 */ unsigned int x = (unsigned int)key; x ^= x >> 16; x *= 0x7feb352dU; x ^= x >> 15; return (size_t)(x & (cap - 1)); /* cap 必须是 2 的幂 */ } int chain_put(ChainMap *m, int key, int value) { size_t idx = hash_int(key, m->capacity); for (Node *p = m->buckets[idx]; p; p = p->next) { if (p->key == key) { p->value = value; return 0; } /* 命中，更新 */ } Node *n = malloc(sizeof(Node)); if (!n) return -1; n->key = key; n->value = value; n->next = m->buckets[idx]; /* 头插 */ m->buckets[idx] = n; m->size++; return 1; /* 新增 */ }

这里用的是头插。头插的好处是插入不用遍历链表，代价是遍历顺序和插入顺序相反。如果是单线程环境，头插完全没问题；如果存在并发扩容，头插会埋下一个非常经典的坑，第 7 节会专门讲。

2.3 链表退化的三种形态，以及怎么治

链地址法最怕的事情就是某条链越来越长，长到查找退化成遍历链表。我把实际遇到的退化原因归成三类，处理手法各不相同。

第一类是哈希函数质量差。有些实现直接把整型键当哈希值用，或者对字符串只取前几个字节，导致大量键的高位有规律、低位却扎堆。解决办法是做一次扰动，把高位的影响混进低位，比如上面代码里的异或加乘法。

第二类是键的分布本身就不均匀。比如你拿用户 ID 当键，而 ID 是按注册顺序自增的，某些区段的 ID 活跃度极高。这种没法靠哈希函数救，只能靠扩容稀释，或者对键做一次额外的加盐变换。

第三类是有人故意构造碰撞。攻击者如果能预测你的哈希函数，就能批量造出同桶的键，把 O(1) 拖成 O(n)，进而拖垮服务。这类问题的标准解法是在哈希函数里混入进程启动时生成的随机种子，让攻击者无法离线预测。

针对链表过长，工业界还有一个更直接的手段：当单条链长度超过阈值时，把链表转成平衡树。Java 的 HashMap 就是这么干的，链表长度到 8 且桶数组容量不小于 64 时，该桶会树化，最坏查找从 O(n) 降到 O(log n)，同时保留在元素减少到 6 时退回链表的逻辑，避免在阈值附近反复横跳。

注意：树化阈值 8 不是随手写的。在哈希分布均匀的假设下，单个桶内元素数服从泊松分布，期望值为 0.5 时，桶内达到 8 个元素的概率大约是千万分之六。也就是说正常情况下几乎不会树化，一旦大面积树化，基本可以判定是哈希函数出了问题或者有人在构造碰撞，这本身就是一个很有用的告警信号。

2.4 删除为什么在链地址法里格外省心

链地址法的删除只需要在链表里摘掉节点，然后把前驱指向后继，桶数组本身完全不动。这里不存在“删完之后留下空洞”的概念，因为数组里存的是指针，指针改一下就行。

对比一下开放地址法，删除一个元素之后那个位置不能直接置空，否则后续的探测链会断掉，必须打一个墓碑标记，而这个标记又会永久占用探测时间。这个差异看起来不大，但在频繁增删的场景下会累积成相当可观的差距。

不过链地址法也有自己的删除麻烦：链表节点的内存是分散分配的，每次插入都要 malloc 一次，每次删除都要 free 一次。在高频写场景下，分配器的压力和内存碎片都是真实存在的成本。开放地址法把元素存在连续数组里，没有这个开销，这是它在大批量小对象场景下的重要优势。

3. 开放地址法：所有元素都住在数组里

3.1 线性探测：最简单，也最容易堆积

开放地址法的基本动作是：算出初始下标之后，如果该位置被占，就按一个固定步长继续往后找。线性探测定步长为 1，也就是从头到尾挨个试。

#define STATE_EMPTY 0 #define STATE_USED 1 #define STATE_TOMB 2 typedef struct { int *keys; int *values; unsigned char *state; size_t capacity; /* 2 的幂 */ size_t size; /* 真实元素数 */ size_t occupied; /* USED + TOMB，用于判断数组是否被占满 */ } OAMap; static size_t oa_find_slot(const OAMap *m, int key, int *found) { size_t mask = m->capacity - 1; size_t i = hash_int(key, m->capacity); *found = 0; while (m->state[i] != STATE_EMPTY) { if (m->state[i] == STATE_USED && m->keys[i] == key) { *found = 1; return i; } i = (i + 1) & mask; /* 线性探测，位与保证回绕 */ } return i; /* 返回第一个可用槽位 */ }

问题出在“连续占用会形成区块”这一点上。一旦某个位置连续存了一段数据，新来的键只要落在这段区间的起点附近，就得一路往后摸到区间末尾才能找到空位，而这个长长的区间又会吸引更多键落进来，雪球越滚越大。这个现象叫一次聚集，它的可怕之处在于它是自增强的：聚集越长，增长越快，查找代价呈平方级上升。

用一句生活化的比喻：超市门口本来只有一个收银台开了，队伍排到门口；新来的顾客看见门口队伍长，以为这里是最快的，就跟着排，结果队伍越来越长，旁边空闲的收银台反而没人去。

3.2 二次探测与双重散列：把探测步长打乱

一次聚集的根源是步长固定为 1，导致所有键在空间上互相影响。二次探测的思路是让第 k 次探测的偏移量变成 k² 量级，这样两个初始下标不同的键，一般不会走同一条探测路径。

二次探测能缓解一次聚集，但引入了新的问题：二次聚集。如果两个键的初始下标相同，它们的整个探测序列就完全一样，还是会互相踩。而且二次探测要求表长选得特别小心，必须保证探测序列能覆盖到所有槽位，通常要求表长是 4k+3 形式的素数，这让容量控制变得别扭。

双重散列是目前开放地址法里理论表现最好的方案。它的做法是用第二个哈希函数算出步长，让不同键的探测路径彻底分开：

static size_t probe_step(int key, size_t cap) { unsigned int h2 = (unsigned int)key * 2654435761U; h2 ^= h2 >> 13; return (h2 | 1) & (cap - 1); /* 强制为奇数，与 2 的幂容量互质 */ }

那个| 1是关键。当容量是 2 的幂时，只有奇数步长才能保证探测序列遍历整个表而不提前循环。少了这一步，某些步长为偶数的键会陷入只走一半槽位的死循环，查找永远找不到空位。

对比一下期望探测次数，双重散列在 α=0.75 时成功查找约 1.85 次、失败约 4 次，明显优于线性探测的 2.5 次和 8.5 次。代价是每次探测要多算一次哈希，而且缓存局部性比线性探测差——线性探测虽然探测次数多，但每次都是相邻地址，缓存友好。这又是一个典型的理论最优不等于工程最优的例子。

3.3 墓碑标记：删除留下的长期债务

开放地址法里删除一个元素，那个位置绝对不能直接标成空。原因很简单：探测链会依赖“空”作为终止条件，你把它置空，后面本来能找得到的元素就断了线索，会误判成不存在，导致数据“凭空消失”。

所以标准做法是打墓碑，用一个单独的状态位标记“这里曾经有元素，现在没了”。查找时遇到墓碑继续往后找，遇到真正的空位才停下；插入时遇到墓碑可以复用这个位置。

墓碑的代价是它永久占用探测预算。假设你插入 100 万个元素又删掉 90 万个，数组里可能铺满了墓碑，虽然活跃元素只有 10 万，但每次查找都要在这些墓碑之间穿行。这就是为什么工业实现里必须引入墓碑比例触发的重哈希——当墓碑数量超过活跃元素一定比例时，原地做一次紧凑化重建，把墓碑全部清掉。

实操心得：我见过一个日志聚合服务，用开放地址法做本地去重，运行三天后 CPU 从 15% 爬到了 80%。原因就是墓碑堆积，活跃元素只有几十万，数组里却有上千万个墓碑。加上“墓碑数超过活跃数 50% 就重建”的规则之后，CPU 稳定在 12% 左右。这条规则在写开放地址法的时候一定别忘了。

3.4 开放地址法的装载因子上限为什么必须更严

因为开放地址法没有“挂外面”的缓冲，所有元素挤在同一个数组里，α 一旦逼近 1，探测长度会爆炸。前面算过，线性探测在 α=0.9 时，失败查找期望要约 50 次探测。这意味着一次本来该是常数时间的查找，实际变成了 50 次内存访问加比较。

主流的开放地址法实现普遍把装载因子上限压在 0.5 到 0.75 之间。Google 的 Abseil 哈希表默认上限是 0.875，但它用的是 SSE 指令一次比较 16 个槽位，硬件层面把探测成本压下去了，这个前提别人不通用。CPython 的 dict 用的是 2/3 左右，这个数字是长期实测调出来的平衡点。

用一张表把两种方案的关键指标摆在一起，看起来更直观：

4. 参数怎么定：负载因子、容量、哈希函数

4.1 负载因子 0.75 是怎么来的

很多资料直接告诉你“0.75 是经验值”，但很少解释这个数字的来历。它其实是在时间和空间之间做的一次显式计算：假设查找和插入的成本权重相同，把装载因子带来的探测成本与预留空间的浪费成本加在一起求最小值，解出来的位置大致落在 0.7 到 0.8 之间。

具体到 Java 的 HashMap，0.75 还有一层考量：容量是 2 的幂，装载因子取 0.75 意味着实际可用的槽位比例是 3/4，扩容触发的时机是个整数好算的边界。更实际的原因是，0.75 下桶内元素数服从泊松分布，单个桶出现 8 个元素的概率只有千万分之几，把树化概率控制在一个几乎可以忽略的水平。

如果你的场景是读多写少且内存紧张，可以考虑把装载因子提到 0.8，但要先压测确认失败查找的成本落在可接受范围内。如果是延迟敏感型服务，P99 比平均值重要得多，那反而应该把装载因子降到 0.6 甚至 0.5，用空间换尾部延迟的稳定。

4.2 容量为什么普遍偏爱 2 的幂

用 2 的幂做容量，最大的好处是取模可以换成位与运算，hash % n变成hash & (n-1)。在哈希表的查找路径上，这个运算每秒钟要执行几百万次，省下的那点 CPU 在高峰时段是实打实的。

代价是位与只保留哈希值的低位，如果哈希函数低位分布不好，冲突会集中爆发。所以容量用 2 的幂的实现，几乎都会配套一个扰动函数把高位混进低位。Java HashMap 的做法是：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

把 32 位哈希值右移 16 位再异或回去，让高 16 位的信息参与到低位的计算中。这个操作只花一条移位加一条异或，性价比极高。

另一个选择是使用素数容量，好处是即使哈希函数质量一般也能有不错的分散效果，坏处是取模要用除法指令，并且扩容后需要把元素重新计算哈希。很多老式实现用素数容量，现代实现基本都转向 2 的幂加扰动。

4.3 扩容策略：翻倍不是唯一答案

扩容的触发条件通常是size > capacity * load_factor。扩容比例最常见的是翻倍，因为翻倍之后元素的落点只有两种可能：留在原位，或者移动到“原位 + 旧容量”。这个性质让扩容时的元素迁移可以批量处理，不用重算哈希。

判断逻辑非常优雅：

/* 扩容时判断节点是否留在原桶 */ if ((e.hash & oldCap) == 0) { /* 留在低位链 */ } else { /* 挪到 index + oldCap 位置的高位链 */ }

只要看哈希值在旧容量那一位上是 0 还是 1，就能决定去留。这个技巧在 Java 8 的 HashMap 扩容代码里用得很漂亮，把一个看似需要全量重算的操作变成了两次链表的拆分。

翻倍的问题是内存占用翻倍增长，对于已经很大的表，扩容瞬间需要同时容纳新旧两份数据，可能造成明显的内存尖峰。一些延迟敏感的实现在大表阶段会改成增长 50% 或者 25%，牺牲一点索引效率换内存平滑。

4.4 哈希函数该满足什么条件

一个能用的哈希函数要满足三条：确定性（同键同值）、均匀性（输出在值域上分布均匀）、雪崩效应（输入改一位，输出大约一半的位翻转）。

工程上我一般遵循一个原则：能用成熟算法就别自己设计。整数键用 MurmurHash3 的 finalizer，字符串用 FNV-1a 或者 SipHash，需要抗碰撞攻击的场景直接用带随机种子的 SipHash。自己发明哈希函数最常见的翻车方式是忽略了低位规律性，比如把key * 31当哈希，遇到键全是 31 的倍数时就会全部撞到同一个桶。

如果确实需要自己写，一个简单的检查方法是：拿一千个真实业务键跑一遍，统计桶长度分布，看最长的桶是不是明显长于总元素数 / 桶数 × 5。超出这个量级就说明分布有问题，要么换函数，要么加扰动。

5. 主流实现是怎么选的，以及为什么

5.1 Java HashMap：链地址加红黑树

Java 8 之后的 HashMap 是链地址法的典型代表，并且在链地址法基础上加了两层优化。桶内元素少于 8 个时是单链表，达到 8 个且容量不小于 64 时转成红黑树，元素减少到 6 个时退回链表。

这套设计解决的是最坏情况：如果攻击者能构造大量同桶键，纯链表会把查找拖成 O(n)，而树化之后最坏是 O(log n)。阈值选 8 而不是更小，是为了避免频繁树化和退化带来的额外开销——毕竟树节点比链表节点多占不少内存。

扩容时它用的(e.hash & oldCap)拆分逻辑，让扩容从 O(n) 的全量重哈希变成了两个链表的拼接，这是性能上的重要改进。Java 7 用的头插法在并发扩容时会形成环形链表导致死循环，Java 8 改成尾插之后这个问题消失了，但 HashMap 依然不是线程安全的，并发场景必须换 ConcurrentHashMap。

5.2 Python dict：开放地址加的紧凑布局

CPython 从 3.6 开始改用紧凑字典布局，把索引数组和键值对数组拆开。索引数组只存 1/2/4/8 字节的整数下标，键值对数组按插入顺序紧凑存放实际数据。这个改动让字典的内存占用下降了 20% 到 25%，同时迭代顺序变成了插入顺序，成了一个被官方承认的语言特性。

它的冲突处理用的是开放地址法，但探测序列不是简单的线性或二次，而是带扰动项的伪随机序列：

/* CPython lookdict 中的探测推进 */ perturb >>= PERTURB_SHIFT; /* PERTURB_SHIFT = 5 */ i = (i * 5 + 1 + perturb) & mask;

这个公式的好处是前期扰动项占主导，探测路径接近随机，能有效打散聚集；随着 perturb 不断右移衰减到 0，探测退化成固定的线性步长，保证了探测序列最终能覆盖所有槽位。这是一个既有随机性又有完备性的设计，很值得学习。

它的装载因子上限是 2/3，超过就扩容，扩容倍数在表较小的时候是 4 倍，较大之后改为 2 倍。这种“小表激进、大表保守”的策略，兼顾了小数据量的空间效率和大量数据下的扩容成本。

5.3 Redis 字典：双表加渐进式 rehash

Redis 的字典是链地址法，但它面对的场景有个特殊约束：单线程模型下不能出现长时间的阻塞操作。一次几十万元素的 rehash 可能耗时几十毫秒，这在 Redis 里是不能接受的。

它的解法是维护两张哈希表ht[0]和ht[1]，rehash 期间新数据一律写进ht[1]，查找时两张表都查，同时用一个rehashidx记录迁移进度，每次操作顺带迁移一个桶的数据。这样把一次性的重活摊薄到了无数次小操作上，单次耗时可以忽略。

扩容的触发条件也和是否有后台子进程有关：没有子进程在跑持久化时，装载因子达到 1 就扩容；有子进程在跑时，阈值提高到 5。原理是子进程用的是写时复制，如果此时频繁扩容会触发大量内存页复制，所以宁可忍着高装载因子也不动。这个细节很能体现工程实现和教科书算法的差距。

5.4 三种选择的场景逻辑

把这三家的选择放在一起看，能总结出一条很实用的判断规律：

• 数据量不可控、需要抗最坏情况，选链地址法加树化。
• 内存敏感、元素多是小对象、追求缓存效率，选开放地址法加紧凑布局。
• 单次操作延迟有硬上限、需要平滑，选链地址法加渐进式 rehash。

不存在通用最优解，只有匹配场景的选择。我个人的经验是，写业务代码直接用好标准库就行，真正需要自己实现哈希表的场景，通常是你要在上面加一层特殊语义，比如需要 TTL、需要 LRU 淘汰、需要自定义比较器，这时候才需要动手，而且第一件事就是先把上面这些取舍想明白。

6. 性能对照：实测数据比理论更值得看

6.1 测试设计

我在一台普通的开发机上做过一组对照测试，思路是这样：分别实现链地址法（单链表，不树化）和开放地址法（线性探测 + 墓碑 + 比例触发的重建），用相同的哈希函数，插入 100 万个随机 32 位整数，然后做 100 万次命中查找和 100 万次未命中查找，记录总耗时。两组实现都开启编译优化。

这个测试不追求绝对精确的数值，目的是看趋势和量级差异，观察不同装载因子下的表现变化。

6.2 数据对照

几个值得注意的点。低装载因子下开放地址法明显更快，因为数据连续存放，缓存命中率高，而链地址法要跟着指针到处跳。装载因子超过 0.8 之后形势逆转，开放地址法的探测长度上升得太快，缓存优势被抵消。链地址法的曲线一直很平，这是它最大的优势：不管装载因子多高，性能都是平缓下降，不会突然崩掉。

内存这一项上开放地址法一直占优，因为它不需要为每个元素额外分配一个链表节点，省下了节点头部和指针的空间，也省下了分配器的元数据开销。元素越小，这个优势越明显。

6.3 缓存不友好到底有多贵

现代 CPU 从 L1 取数据大约 4 个周期，从主存取数据大约 200 到 300 个周期。链地址法一次查找的路径是：读桶指针（一次主存访问），跟着指针读节点（又一次主存访问），如果没命中还要跟着 next 指针继续（每跳一次都是一次主存访问）。在装载因子 0.75 的情况下平均要跳 1.4 次，也就是 2 到 3 次主存访问。

开放地址法在低装载因子下，探测的槽位大概率落在同一两个缓存行里，一次主存访问能覆盖多个候选槽位。这就是为什么在数据量不大、装载因子控制得好时，开放地址法的实测性能经常能领先 20% 到 40%。

这也解释了为什么现代高性能哈希表实现都在往 SIMD 方向走：用一条指令同时比较一个缓存行里的 16 个槽位，把探测的次数压缩到接近 1 次。这是硬件能力带来的新空间，传统的探测序列设计已经不太适用了。

7. 踩坑记录与排查清单

7.1 构造碰撞导致的性能坍塌

有一种攻击方式不需要任何高深技巧：只要知道目标服务的哈希函数，批量提交能让它们落在同一个桶的键，就能让哈希表退化成链表遍历。如果服务端每次请求都要做一次哈希表查找，攻击者可以用很小的带宽把 CPU 打满。

防护的核心思路是让攻击者无法提前预测哈希结果。主流方案是在哈希计算中混入一个进程启动时随机生成的种子，这样同一个键在不同进程、不同重启周期里落点都不同，攻击者没法离线准备碰撞集合。另一个思路是用本身就有抗碰撞性质的哈希函数，代价是计算稍慢。

我见过的一个真实例子是，某接口的参数校验用哈希表做白名单匹配，参数长度不限且直接参与哈希计算。后来加了键长度上限和随机种子，问题就消失了。防护这件事，成本往往很低，主要障碍是没想到。

7.2 探测死循环

开放地址法写错之后最典型的表现是死循环，常见原因有三个。容量不是 2 的幂但用了位与取下标，导致下标被限制在一半空间内；双重散列的步长是偶数，与 2 的幂容量不互质；探测公式里的取模写成了取绝对值再取模，遇到负步长时行为异常。

排查这类问题的办法是加一个探测计数器，超过容量次数的探测直接断言失败并打印容量、装载因子、墓碑数量。这个断言在生产环境可以改成降级处理，但它能帮你在测试阶段快速定位问题。

7.3 扩容期间的并发问题

如果哈希表要支持并发访问，扩容是最容易出事的环节。单线程下扩容是原子的，多线程下如果没有同步，两个线程可能同时触发扩容，一个线程刚把节点挪走，另一个线程还拿着旧指针，就会读到已经失效的节点，甚至形成环。

解决办法要么是全局加锁（简单但性能差），要么是把每个桶独立加锁做分段扩容，要么学 Redis 用渐进式 rehash 把迁移摊到每次操作里，同时用一个标记位告诉其他线程“现在有两张表，都要查”。ConcurrentHashMap 早期的分段锁和后来基于 CAS 的实现，本质上都在解决同一个问题。

7.4 常见问题速查表

7.5 几条我个人的实操心得

写哈希表相关的代码，我总结了几条不太出现在文档里的经验。

第一，永远给探测或遍历加一个上界断言。这个断言在正确实现里永远不会触发，但它能在实现出错时把死循环变成一次明确的报错，省下几小时的调试时间。

第二，装载因子的选择要看 P99 而不是平均值。平均性能再好看，只要尾部延迟超标，用户就能明显感知到卡顿。延迟敏感的场景宁可多花点内存。

第三，扩容时机尽量提前。等到装载因子正好卡在阈值上再扩，扩容期间的操作既要查旧表又要迁移，是最慢的时刻。有些实现会在阈值附近提前触发，就是为了避开这个最差点。

第四，自定义键的哈希和相等判断必须成对正确。用自定义对象做键时，重写了哈希函数却忘了重写相等判断，或者反过来，会导致两个“相等”的键落到不同桶里，出现同一个逻辑键存了两份数据的诡异现象。这类问题在单元测试里很难发现，因为它在小数据量下可能恰好不触发。

第五，开放地址法的内存对齐值得花点心思。如果把键、值、状态位打包成一个结构体数组，一次缓存行加载就能拿到完整信息；如果拆成三个平行数组，一次探测要访问三处内存，性能差一大截。CPython 把索引和实体拆开是为了省内存，但它同时在实体数组里做了紧凑排列，两者目标不同，不能照搬。

最后再说一个观察：这些年看下来，哈希表的实现演进基本围绕两个方向在走，一是把最坏情况兜住，二是把内存访问次数压到最低。前者靠树化、随机种子、渐进式 rehash 这类工程手段，后者靠紧凑布局和 SIMD 这类贴近硬件的手段。链地址法和开放地址法这两条老路线都没有消失，只是各自被推到了更适合自己的场景里。理解它们各自的边界在哪，比记住哪个“更快”有用得多。