线性探测

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：即使首页不同，只要进入同一连续运行，后续轨迹也会合流。

期望探测数与概率前提 ​

在首页由理想完全随机函数给出、键集与插入次序预先固定、表由插入构成且没有删除和墓碑的经典分析中，成功查询再对已存键等概率取平均。固定装载率 $\alpha <1$、表长趋于无穷时，成功与失败查找的近似期望理路期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分，概括加权平均与总体质量平衡。探测数分别为

失败查找受长 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。

Robin Hood哈希理路Robin Hood 哈希Robin Hood hashing · 罗宾汉哈希在线性探测中让走得更远的键抢占槽位，用逐键路径证书证明提前失败与后移删除。把此抢占思路补成完整线性接口：逐键路径证书允许住户距离不足时提前否定，并支持无墓碑后移删除。合法距离序列0、1、2、1说明不能把证书误写成全局单调；同键更新、容量失败与跨表尾修复均有独立轨迹。

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

连续探测把查询变成缓存友好的数组扫描，适合中低负载的内存哈希表；扩容与墓碑重建则负责阻止 cluster 和逻辑删除长期累积。若需要 Robin Hood、并发移动或强最坏延迟，应把停止规则、删除协议和概率假设作为新变体重新分析。

用循环距离独立检查可达性 ​

一条探测程序“能查到所有已存键”还不足以说明它没有和测试共同犯错。更直接的表示检查是：对槽 $j$ 中的活动键 $x$，令

从 $h(x)$ 起的前 $d$ 个槽都不得是真空槽。检查器直接查看这些位置，不调用实现的查找函数。再加上物理键唯一、活动数等于 $n$、非空槽数等于 $used$，就能分别发现重复键、错误计数和被截断的探测路径。墓碑满足“非空”，所以删除只改墓碑并不破坏后方键的这项条件。

配套完整历史取 $m=5$、$h(x)=xmod5$。插入 $4,9,14$ 后，键依次占槽 $4,0,1$，一次碰撞同时跨过数组边界。删除 $9$ 后更新 $14$，程序必须经过槽 $0$ 的墓碑，再改槽 $1$，键数保持 $2$。插入新键 $19$ 时也要先走到槽 $2$ 的真空位置，确认没有同键，才能回填首个墓碑 $0$；这次插入检查四槽，而不是检查两槽便停。

同一实验随后达到 $n=4,used=5$：五个槽都曾用过，但仍有一个墓碑。查询不存在的键必须在恰好五次探测后结束；插入必须在完整扫描后，使用已经记住的墓碑。这里的终止证据是“已检查全表”，不是“找到了真空槽”。它仍保持活动负载小于 $1$，却超出了 Open Data Structures §5.2 实现维持的 $m\ge 2used$ 条件；教材的无限式 while 依靠该条件保证会碰到 null，本实验用有界循环额外检验低层接口的边界。这个压力状态不享有教材正常负载下的期望常数保证。

从空表出发，错误停止的最短可观察反例需要四次调用：put(0,a)、put(3,b)、delete(0)、get(3)，容量为 $3$。前两步建立碰撞和被遮挡键，第三步产生前方墓碑，第四步观察漏报。少于四步无法同时完成这三个准备动作并查询受影响的不同键。把最后一步换成 put(3,b)，就得到提前复用墓碑所制造的两个物理副本；即便两副本的值相同，唯一性检查仍会失败。