开放定址哈希

开放定址把冲突处理变成数组内的一段搜索轨迹：当前位置已占用，就沿该键自己的探测序列继续。连续数组常带来良好的缓存局部性，却也让停止条件成为正确性的一部分——从未使用的空槽证明键不在后续位置，曾经使用后又删除的槽则不能提供同样证明。

随机探测排列模型把每次访问看成从尚未检查的槽中均匀取下一个位置，所以剩余空槽比例 $1-\alpha$ 控制失败查找长度。实际线性探测、二次探测和双重哈希具有更强结构，聚簇、表长和步长会改变分析；“使用某个随机哈希族”不自动生成均匀随机排列。

删除链例子 ​

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

三类探测的不同前提 ​

线性探测 $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，每次重建后的容量至少成比例增长，累计搬迁为线性，从而保持插入摊还常数；这仍不提供单次操作最坏延迟。

墓碑率或负载越过阈值后应全局重建公理库全局重建Global rebuilding在坏度量越界时从活动元素重建结构，并把线性成本收费给足够多次更新。。扩张与收缩阈值需要迟滞，避免插删交替时反复搬迁；重建必须生成新的探测状态，不能把墓碑原样复制。开放定址与 chaining 都实现哈希字典，却在删除、最大装载率、内存局部性和并发发布顺序上使用不同不变量。

Universal hashing公理库通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。控制不同键在所选哈希函数下碰撞的概率，可作为哈希族比较入口，但它不等价于 simple uniform hashing，也不能单独为经典随机探测排列界背书。线性探测和 tabulation hashing 等具体组合有各自的聚簇分析；若随机种子暴露给自适应对手，还需明确更强的独立性、安全重播或重建假设。