开放定址哈希

探测接口 ​

容量为 $m$ 的表使用

$$h:K\times \{0,\dots ,m-1\}\to \{0,\dots ,m-1\},$$

并要求固定键的探测序列覆盖所有槽。查找依次检查 $h(k,0),h(k,1),\dots$，命中键或遇到从未使用的空槽停止；插入选首个可用槽。线性探测、二次探测和双重哈希给不同序列，不能共享所有概率结论。

期望探测数 ​

负载 $\alpha =n/m<1$。在 simple uniform hashing 假设下，失败查找期望探测至多

$$\frac{1}{1-\alpha },$$

成功查找至多约 ${\alpha }^{-1}\ln (1/(1-\alpha ))$。这是对随机探测排列取期望的分析，不是任意实际哈希函数面对任意键序列的保证；$\alpha \to 1$ 时成本急剧发散，扩容重哈希是结构的一部分。

删除链例子 ​

若键 $a,b$ 冲突并依次落在槽 4、5，删除 $a$ 后直接把槽 4 标为空，会让查找 $b$ 在 4 提前停止。墓碑标记表示“这里无键但探测不能停止”，可保持正确性，却会累积并拖慢失败查找；backward-shift deletion 只在与探测规则配套时安全。

边界与重建 ​

墓碑率或负载越过阈值后应全局重建公理库全局重建Global rebuilding在坏度量越界时从活动元素重建结构，并把线性成本收费给足够多次更新。。阈值需要迟滞，避免插删交替反复扩缩。开放定址利用连续数组局部性，但不等同于 chaining；删除语义、最大装载率和并发发布顺序都不同。若哈希随机种子暴露给自适应对手，期望界还需更强哈希假设。

三类探测的不同前提 ​

线性探测 $h(k,i)=h_0(k)+imodm$ 必遍历全表，但有 primary clustering；二次探测能减少主聚簇，却未必覆盖所有槽，表长与系数需匹配；双重哈希 $h_1(k)+i{h}_2(k)$ 只有当步长与 $m$ 互素时才形成全排列。

Uniform hashing 分析把探测序列视为随机排列，强于“首页位置均匀”。现实方法可能有更专门的 cluster 分析；不能把 $1/(1-\alpha )$ 公式同时当作所有探测法的精确性能。

两种占用率与重建时机 ​

含墓碑的实现要区分活键负载 ${\alpha }_{live}=n/m$ 与已用槽比例 ${\alpha }_{used}=(n+t)/m$，其中 $t$ 是墓碑数。成功查询更多受前者影响，失败查询要穿过墓碑，更接近由后者控制；连续插删可让 ${\alpha }_{live}$ 很低而 ${\alpha }_{used}$ 接近 1。

因此重建条件通常同时监控“活键过多”和“墓碑过多”。原地把新键写进首个墓碑前，仍要继续探测到真空槽或已有同键，否则可能为同一键建立两个副本。

一次扩容应新建更大表并重新插入所有有效键，墓碑不能原样复制。若扩容阈值固定低于 1，每次重建后的容量至少成比例增长，累计搬迁为线性，从而保持插入摊还常数；这仍不提供单次操作最坏延迟。

参考资料

• Donald Knuth, The Art of Computer Programming, Vol. 3, Hashing.
• Cormen et al., Introduction to Algorithms, Open Addressing.
• Mihai Pătraşcu, Mikkel Thorup, The Power of Simple Tabulation Hashing, JACM, 2012.