probing · 聚簇 · tombstone · Robin Hood

开放寻址：冲突就往后挪

链地址法把撞在一起的 key 挪到槽外，open addressing 不挪：全部留在表内，只是换个槽。每个 key 有一条探测序列——首选槽、第二选、第三选……插入时沿序列走到第一个空槽，查找时沿同一条序列走，遇到空槽即断定「不在表里」。

整张表就是一个数组，没有指针、没有额外节点。这是它存在的全部理由：一个 cache line 能一次带回好几个槽，而链地址法每一跳都可能是一次 cache miss。代价有三项，本页依次是探测序列的选择、聚簇、以及删除。

1 · 探测序列必须是全排列

定义 1.1（probe sequence） key $k$ 的探测序列是下标序列 $p_0(k), p_1(k), \dots$ ，其中 $p_0(k) = h(k) \bmod m$ 。合法的探测序列必须是 $0$ 到 $m-1$ 的一个排列——否则表里还有空槽，某些 key 却永远探不到，插入会在表未满时失败。

三种经典写法给出三种序列：

名称	第 $i$ 步	全排列的条件
linear probing	$h + i$	任意 $m$
quadratic probing	$h + i(i+1)/2$	$m$ 为 2 的幂
double hashing	$h + i \cdot h_2(k)$	$h_2(k)$ 与 $m$ 互质

图 1-1 · 三种探测序列在同一 key 上的落点，格内数字是第几步走到该槽。下方表格给出三者各覆盖了多少个不同的槽。可换表长，注意 double hashing 在合数表长下会漏掉大半个表。

quadratic probing 用三角数 $i(i+1)/2$ 而不是 $i^2$ ，正是为了凑那个全排列条件： $i(i+1)/2 \bmod 2^b$ 遍历全部剩余类，而 $i^2 \bmod m$ 一般只覆盖约一半的槽。double hashing 的条件更麻烦——步长由 key 决定，要保证它总与 $m$ 互质，最省事的办法是让 $m$ 取质数，于是除了 $m$ 的倍数以外任何步长都合法。这就是「 $m$ 取 2 的幂」与「用 double hashing」两个选择互相排斥的原因：前者要位与运算的速度，后者要质数的数论性质。

2 · 聚簇是个正反馈

linear probing 的序列最简单、访存最友好，但它有一项别人没有的毛病。

定义 2.1（primary clustering） 表中连续被占用的一段称为一个 cluster。linear probing 下，任何首选槽落在某个 cluster 内部的 key 都会被追加到该 cluster 的末尾；两个 cluster 之间只要填上一个槽就合并成一个更长的 cluster。于是长的 cluster 更容易变得更长。

图 2-1 · 同一串 key 分别装进 linear probing 与 double hashing 的表。橙色是本次探测走过的槽，绿色是落点。下方并列两表的连续段长度与探测距离，以及 Knuth 公式在当前负载下的期望值。可逐个插入或直接装满。

$m = 61$ 装入 52 个 key（ $\alpha = 0.85$ ）的实测：linear 的平均连续段长 10.40、最坏探测距离 13 步、总探测距离 78；double hashing 在同一批 key 上是 6.50、6 步、51。

Knuth 在 1963 年给出了两者的期望探测次数。均匀散列的理想情形（每个 key 的探测序列独立随机）下，未命中期望为 $1/(1-\alpha)$ ；linear probing 是 $\frac{1}{2}(1 + 1/(1-\alpha)^2)$ 。差距随负载急剧张开：

$\alpha$	均匀散列 · 未命中	linear · 未命中
0.50	2.0	2.5
0.75	4.0	8.5
0.90	10.0	50.5
0.95	20.0	200.5

$\alpha = 0.95$ 时相差十倍。这张表解释了为什么开放寻址的实现必须把负载因子卡在 0.7 到 0.9 之间——不是因为渐近复杂度变坏（它一直是 $O(1/(1-\alpha))$ ），而是那个常数在 $\alpha$ 接近 1 时爆掉。链地址法没有这个悬崖，它的代价随 $\alpha$ 线性上升。

3 · 删除要留墓碑

删除是开放寻址最容易写错的地方。

把删除位置空，会切断经过它的探测路径：所有首选槽在这个位置之前、实际落在它之后的 key，从此都找不回来。它们仍在数组里，只是查找走到那个空槽就停了。

图 3-1 · 上表留墓碑（✕），下表直接置空。7 个 key 里 ko、ku、kx、ce 的首选槽都是 8，在 8 到 11 排成一段。可删除段内靠前的 key，再查它后面的，看下表如何丢失。

正确做法是留一个 tombstone（墓碑）标记：它表示「此处曾有 key」，查找经过它继续往后走，插入则可以覆盖它。图 3-1 的实测里，删掉 ko 会让置空版本同时丢掉 ku、kx、ce 三个 key；删掉段尾的 kl 或独占一槽的 ka 则毫无影响。这个差别只在同一段连续区内出现，所以低负载的表可能长期不暴露这个 bug。

墓碑本身是负债。它不占逻辑容量却拉长探测路径，删得多了整张表的查找会持续变慢，而负载因子看起来还很低。工程上的处理是把墓碑数也计入「该扩容了」的判据，或者在墓碑比例过高时原地 rehash 一次（容量不变，只是把墓碑清掉）。

4 · 让富者让位

聚簇的伤害集中在少数 key 上：多数 key 一步到位，个别 key 要走十几步。总探测量未必大，但最坏值很大。1985 年 Celis、Larson 与 Munro 提出的做法只改插入的一行判断。

定义 4.1（Robin Hood 不变量） 记 key 当前所在位置与它首选槽的距离为该 key 的 PSL（probe sequence length）。插入时若途中遇到一个 PSL 比自己小的占位者，就与它交换，再替被换出的 key 继续往后找位置。最终表中沿槽位向后走时，PSL 满足 $\mathrm{psl}(p+1) \le \mathrm{psl}(p) + 1$ 。

图 4-1 · 朴素 linear probing 与 Robin Hood 并排装同一串 key，格子下方数字是各 key 的 PSL。装满后可点「删掉三分之一」，对比墓碑数。可逐个插入观察让位链。

同一批 key 的实测里有一项值得盯住：两表的总距离完全相等，都是 78。Robin Hood 一次探测也没省下——它不可能省，因为哪些 key 落在哪一段由散列值决定，与插入策略无关。变的只是这 78 步怎么分配：朴素表的最远距离 13 步，Robin Hood 是 5 步；方差 6.71 对 1.83。它买到的是尾延迟，不是吞吐。

那条不变量还附带两项收益。其一，未命中查找可以提前终止：沿探测序列走到第 $i$ 步，若占位者的 PSL 小于 $i$ ，说明要找的 key 若存在，早该在这一格让位了，可以立即断定不存在，不必走到空槽。其二，删除不需要墓碑——它走 backward shift：把后续 PSL 大于 0 的 key 依次前移一格，空洞随之后移，不变量自动维持。实测未命中的平均探测步数是 6.65 对 2.95。图 4-1 装满后删掉三分之一，朴素表留下 18 个墓碑，Robin Hood 一个也没有。

代价是插入时多了一次 PSL 计算与可能的多次写入。Rust 标准库的 HashMap 长期用的正是 Robin Hood，到 1.36（2019）才换成 hashbrown 的 Swiss table 布局——不是因为 Robin Hood 不好，而是 control byte 那套用一条 SIMD 指令解决了同一个问题，且顺带免掉了「PSL 要现算」这项开销。

5 · 参考文献

Knuth, D. E. (1963). Notes on "open" addressing. 未刊手稿；结论收入 TAOCP Vol. 3 §6.4。
Celis, P., Larson, P.-Å., & Munro, J. I. (1985). Robin Hood hashing. Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, 281–288.
Pagh, R., & Rodler, F. F. (2004). Cuckoo hashing. Journal of Algorithms, 51(2), 122–144.
Thorup, M., & Zhang, Y. (2012). Tabulation-based 5-independent hashing with applications to linear probing. SIAM Journal on Computing, 41(2), 293–331.