线性探测

探测序列与接口 ​

容量为 $m$ 的表为每个键 $x$ 选择首页 $h(x)\in [0,m)$，并依次探测

$$h(x),h(x)+1,h(x)+2,\dots (\mathrm{mod}m).$$

查找在命中键或遇到从未使用的空槽时停止；插入占用首个可用槽。表中键数为 $n$，活动负载因子 $\alpha =n/m$ 必须严格小于 $1$。所有探测访问相邻数组单元，缓存与硬件预取通常优于随机跳转。

这只是 开放定址公理库开放定址哈希open addressing · closed hashing把所有键直接存入表数组，并沿键相关探测序列处理冲突的哈希模型。的一种序列。二次探测和双重哈希不形成同样的连续 cluster，不能借用本页的精确概率公式或删除规则。

Cluster 如何自我放大 ​

Cluster 是循环表中一段极大的连续占用区。键只要哈希到 cluster 内部或它之前紧邻的空隙，就会穿过已有键并停在 cluster 尾部，使这段运行更长；后续更多首页因此落入它的吸引范围，这称为 primary clustering。

例如表长 $10$，三个键首页依次为 $3,3,4$。它们落在槽 $3,4,5$，形成长度 $3$ 的 cluster。下一个首页为 $4$ 的键要检查 $4,5,6$ 才能插入，cluster 延伸到 $6$；首页为 $3,4,5,6$ 的后续键都会继续放大同一段。

Secondary clustering 指首页相同的键共享完全相同探测序列。线性探测既有这一现象，也有更强的 primary clustering：即使首页不同，只要进入同一连续运行，后续轨迹也会合流。

期望探测数与概率前提 ​

在首页由理想完全随机函数给出、插入键集预先固定的经典分析中，成功查找与失败查找的近似期望探测数分别为

$$\frac{1}{2}(1+\frac{1}{1-\alpha }),\frac{1}{2}(1+\frac{1}{(1-\alpha {)}^2}).$$

失败查找受长 cluster 的平方尾部影响更大。当 $\alpha$ 从 $1/2$ 接近 $1$ 时，这些量迅速增长，所以扩容阈值和重建是结构的一部分。

Pairwise independence 只控制键对的首页碰撞，不能自动控制长连续区间内的总负载，因而不足以无条件推出经典线性探测界。较高阶独立性可恢复常数期望；simple tabulation 虽独立性有限，也能凭专门分析得到常数负载下的期望界。引用结论时必须写出函数族和对手是否在种子揭示前固定键序列。

删除、墓碑与 Backshift ​

直接把被删槽改成“从未使用”会截断仍在其后的键的查找路径。墓碑保持路径可穿越，却不再为失败查找提供停止点；活动负载低而墓碑很多时，查询仍可能像高负载表一样慢。

Backward-shift deletion 沿 cluster 向后扫描，把其首页到当前位置的循环探测路径跨过空洞的键前移，直到遇到真正空槽。它能消除墓碑，但正确性依赖线性连续序列，不能直接用于任意 double hashing。

全局重建公理库全局重建Global rebuilding在坏度量越界时从活动元素重建结构，并把线性成本收费给足够多次更新。会重新插入全部活动键并清空墓碑。若重建只复制槽位而不重走探测，就可能保留不可达键和旧 cluster。

Robin Hood 变体 ​

Robin Hood hashing 在冲突时比较 probe distance，让离首页更远的键夺取槽位，把较近的键继续向后赶，目标是压低探测距离方差和尾部。查找停止规则、删除和键交换都随之改变；它不是对普通线性探测做一个不影响证明的 tie-break。

缓存局部性也不是渐近正确性保证。表跨越缓存层或 cluster 很长时，连续扫描仍会产生大量访问；并发插入还需同步整段移动，不能从单线程期望探测数推出并发吞吐。

参考资料

• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998.
• Mihai Pătraşcu and Mikkel Thorup, “The Power of Simple Tabulation Hashing,” Journal of the ACM 59(3), 2012.
• Anna Pagh, Rasmus Pagh, and Milan Ružić, “Linear Probing with Constant Independence,” STOC, 2007.