开放定址哈希

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

随机探测排列模型把每次访问看成从尚未检查的槽中均匀取下一个位置，所以剩余空槽比例 $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 的概率碰撞。控制不同键在所选哈希函数下碰撞的概率，可作为哈希族比较入口，但它不等价于均匀随机探测排列，也不能单独为经典随机探测排列界背书。线性探测和 tabulation hashing 等具体组合有各自的聚簇分析；若随机种子暴露给自适应对手，还需明确更强的独立性、安全重播或重建假设。

重定位方案为何需要不同停止条件 ​

Cuckoo Hashing理路Cuckoo Hashingcuckoo hashing · 布谷鸟哈希为每个键提供两个候选槽，以踢出链和必要的重哈希换取常数最坏查找。也把记录保存在表槽中，因此属于广义开放定址；但它只允许一个键占用两张表中的两个候选位置，插入会把旧键踢到另一候选槽。查询检查这两处，不沿覆盖全表的探测排列走到首个空槽。

Hopscotch哈希理路Hopscotch 哈希Hopscotch hashing · 跳房子哈希用首页所属的邻域位图精确查找，通过逐次搬移旧键让空槽靠近新键，并明确有空槽仍会插入失败。采用另一种候选约束：每键只许位于首页后H格内，属于首页的位图直接列出可能位置。插入通过搬动旧键让空洞靠近；局部邻域已满时，即使全表仍有空槽也会失败。该位图顺序版的查询、删除与失败语义不依赖普通线性探测的遇空即停。

例如键 $x$ 的候选位置为第一张表的槽 $2$ 与第二张表的槽 $5$，且实际保存在后者。即使前者后来变空，也必须检查第二个位置；“碰到第一个空槽就停止”会漏报。这说明本页前半的空槽证据和随机探测公式属于经典方案，不能扩展为所有表内存储方案的公理。

配套实验 ​

字典契约实验给出跨数组边界的同键更新、全 used 但仍有墓碑的有限扫描，以及首墓碑复用的逐步状态；独立检查器直接检验活动键的可达路径，不借用被测查询作为标准答案。