算法与数据结构 · 第 10 课
开放寻址与线性探测:为何删除一个槽可能让另一个键“消失”?
2026 年 10 月 29 日|第 2 周 · 第 3 节|正文约 17 分钟(自测另计)
第 9 课的链地址法把碰撞键放进链表。本课换一种存储方式:所有键直接放在表内,发生碰撞就向后找空槽。它更紧凑,但查找正确性依赖探测路径,且性能容易受连续聚集与删除操作影响。
一、目标与成本模型(约 1 分钟)
学完应能:手工执行线性探测;写出 FIND/PUT/ERASE 并证明正确;解释 primary clustering;用概率尾和证明理想均匀探测模型下的失败查找成本,并知道为什么这个结论不能未经证明直接挪给线性探测。
设表有 (m) 个槽,索引从 (0) 到 (m-1)。键唯一且哈希值 (h(x)\in{0,\ldots,m-1})。每次检查一个槽计 1 次 probe,比较、数组访问均为 (O(1))。槽有三种状态:EMPTY(从未占用或重建后为空)、ACTIVE(存放有效键)、DELETED(墓碑)。活跃键数为 (n),活跃负载因子 (\alpha=n/m)。暂不考虑并发修改。
二、为什么不用链表?线性探测如何工作?(约 2 分钟)
开放寻址(open addressing)把所有元素放在表内,无需为每个桶维护单独的链表节点。键 (x) 的 home slot 是 (h(x))。线性探测的第 (i) 个位置是
[ \boxed{p(x,i)=(h(x)+i)\bmod m,\qquad i=0,1,\ldots,m-1.} ]
例如表长 (m=7),三个键的 home slot 都是 3:
槽号: 0 1 2 3 4 5 6
状态: · · · [A] [B] [C] ·
└──→──→
A 在 home=3;B 从 3 探到 4;C 从 3、4 探到 5。
这能提高缓存局部性,却引入一种风险:一个连续占用区间会吸引后续 home 落在该区间的键,使区间越长、下一次查找越贵。这就是 primary clustering(一次聚集)。
三、正确算法:EMPTY 能停止,DELETED 不能(约 4 分钟)
FIND(x):
for t = 0 .. m-1:
j = (h(x)+t) mod m
if T[j] == EMPTY: return NOT_FOUND
if T[j] == ACTIVE and T[j].key == x: return T[j].value
# 其他 ACTIVE 或 DELETED:继续
return NOT_FOUND
PUT(x, value): # 插入;若已存在则更新
first_deleted = NONE
first_empty = NONE
for t = 0 .. m-1:
j = (h(x)+t) mod m
if T[j] == ACTIVE and T[j].key == x:
T[j].value = value; return UPDATED
if T[j] == DELETED and first_deleted == NONE:
first_deleted = j
if T[j] == EMPTY:
first_empty = j
break # 后面不可能藏着旧 x
if first_deleted != NONE: j = first_deleted
else if first_empty != NONE: j = first_empty
else: return TABLE_FULL
T[j] = ACTIVE(x, value)
n += 1
return INSERTED
ERASE(x):
按 FIND 的同一探测规则定位 x(必须得到槽号)
if 找不到: return NOT_FOUND
把命中槽标成 DELETED # 不能直接改 EMPTY
n -= 1
return DELETED_OK
为什么 PUT 不在遇到第一个 DELETED 时立刻插入? 因为真正的旧键可能在它后面!立即插入会出现相同键存两次。正确办法是记下第一个墓碑,但继续查重直到 EMPTY 或绕表一周,然后复用墓碑。
核心不变量 (I): 对每一个 ACTIVE 键 (x),从 (h(x)) 沿线性探测序列到其实际位置的所有前驱槽都不是 EMPTY(可以是 ACTIVE 或 DELETED)。
这就是查找正确性的关键:FIND 遇到 EMPTY 时,沿后续位置不可能还存在 (x),否则违反 (I)。初始化时没有 ACTIVE 键,(I) 自动成立;PUT 在已扫描过且没有 EMPTY 的路径上选择最早墓碑或第一个 EMPTY,保持 (I);ERASE 用 DELETED 替换 ACTIVE,不会制造 EMPTY,也保持 (I)。因此归纳得到每次操作后都正确。
flowchart TD
A["从 home=h(x) 开始,最多探测 m 槽"] --> B{"当前槽的状态"}
B -->|ACTIVE 且 key=x| C["命中:返回"]
B -->|ACTIVE 其他键| D["继续下一槽"]
B -->|DELETED| D
B -->|EMPTY| E["未找到:停止"]
D --> F{"探测是否已达 m 次"}
F -->|否| B
F -->|是| G["未找到:全表检查完成"]
边界: 如果表里已经没有 EMPTY(例如全被 ACTIVE 与 DELETED 填满),FIND 不能无限循环。至多检查 (m) 个槽;PUT 在全周期查重后仍可以利用已记录的墓碑,否则才报告表满。时间上限是 (O(m))。
四、完整数值 Trace:墓碑为什么不能清空?(约 3 分钟)
令 (m=7),(h(x)=x\bmod7),依次 PUT ([10,17,24,3,11])。它们的 home 分别为 (3,3,3,3,4)。
| 操作 | 实际落点 | 原因 |
|---|---|---|
| PUT(10) | 3 | 3 是 EMPTY |
| PUT(17) | 4 | 3 已占用 |
| PUT(24) | 5 | 3、4 已占用 |
| PUT(3) | 6 | 3、4、5 已占用 |
| PUT(11) | 0 | 从 home 4 探到 0 |
插入完成:
槽号: 0 1 2 3 4 5 6
内容: 11 · · 10 17 24 3
ERASE(17) 后:
槽号: 0 1 2 3 4 5 6
内容: 11 · · 10 † 24 3
墓碑
FIND(24):检查 3(10) → 4(†) → 5(24),共 3 probes。
错误做法:把 4 改成 EMPTY,则 FIND(24) 在 4 结束,误判不存在。
现在执行 PUT(31),其 home 也是 3。按正确的“先查重”策略,依次访问 3、4(†)、5、6、0、1(EMPTY),总共探测 6 次,确定 31 不存在后才放入最早的墓碑槽 4。此后 FIND(31) 只需探测 3、4 两次。
这个例子同时告诉我们:插入的实际存放位置可以靠前,但为避免重复键,插入前的查重扫描可能比最终查找更长。
五、分析期望成本:先建立“理想模型”(约 3 分钟)
假设没有墓碑、(n<m),并且某个未命中查询的探测顺序是所有 (m) 个槽的均匀随机排列,与现有占用集合独立。这个假设叫 uniform probing 的理想化模型,不是线性探测本身。
设 (X) 是访问到第一个 EMPTY 为止的 probe 数。要发生 (X>t),意味着前 (t) 个被访问的槽全部 ACTIVE。因此,对 (0\le t\le n),
[ \Pr(X>t) =\frac{n}{m}\frac{n-1}{m-1}\cdots\frac{n-t+1}{m-t+1} =\frac{(n)_t}{(m)_t} \le\left(\frac nm\right)^t =\alpha^t, ]
其中 (t=0) 时约定空乘积为 1;(t>n) 时该概率为 0。利用尾和公式:
[ \mathbb E[X]=\sum_{t=0}^{\infty}\Pr(X>t) \le\sum_{t=0}^{\infty}\alpha^t =\boxed{\frac1{1-\alpha}}. ]
更精确地,这个随机排列模型的期望是 ((m+1)/(m-n+1)),但本课只需上界。若 (\alpha\le0.7),则理想模型的期望 probe 数不超过 (1/(1-0.7)=10/3)。
重点是证明的作用域: 这个计算依赖“探测路径是均匀随机排列”,绝不是仅凭“哈希函数有两键碰撞概率上界”就可以照搬。线性探测只用第一个 home 地址,其余地址按 +1 确定,访问路径彼此高度相关。
六、一次聚集让线性探测的成本更陡(约 2 分钟)
在没有删除、各键 home 地址独立均匀随机、表长足够大等经典平均情况假设下,线性探测的平均 probe 数有如下常用渐近近似:
[
\begin{aligned}
\mathbb E[\text{成功查找 probes}]
&\approx\tfrac12\left(1+\frac1{1-\alpha}\right),
\mathbb E[\text{失败查找 probes}]
&\approx\tfrac12\left(1+\frac1{(1-\alpha)^2}\right).
\end{aligned}
]
这些是依赖额外随机性假设的经典平均情形表达式,不是对任意输入、任意通用哈希族的定理;也不适用于长期积累墓碑而不清理的表。
| 活跃负载 (\alpha) | 理想随机排列失败查找上界 | 线性探测成功近似 | 线性探测失败近似 |
|---|---|---|---|
| 0.5 | 2 | 1.5 | 2.5 |
| 0.8 | 5 | 3 | 13 |
为什么 (\alpha=0.8) 时可能更慢?一个连续团簇越长,home 落在团簇内部及其前端的查询越容易经过较长扫描;新插入键还可能把这个团簇继续延长。这种依赖在“每个查询独立随机重排槽位”的理想模型中不存在。
同样是负载因子 (\alpha),不能拿链地址法的 (1+\alpha) 期望成本去套线性探测;两个算法的碰撞处理机制不同。
七、删除、墓碑与何时重建(约 1 分钟)
若有 (d) 个 DELETED 槽,则失败查找只会在 EMPTY 处停止。即使活跃负载 (\alpha_{\rm live}=n/m) 很低,非空标记占比
[ \beta=(n+d)/m ]
也可能接近 1,甚至等于 1,导致失败查找要走很长的探测路径或全表扫描。仅监视活跃负载不足以保证性能。
工程上常同时监控 (\alpha_{\rm live})、(\beta) 和墓碑比例:负载较高就扩容;墓碑较多则用同样大小的新表重新插入全部活跃键,消除墓碑。一次重建需要 (O(m+n)) 时间;在合适的阈值和扩容策略下可以做摊还分析,但这不是“每一次操作最坏 (O(1))”的保证。
八、正确性、复杂度及下一课(约 1 分钟)
| 项目 | 保证与前提 |
|---|---|
| FIND/PUT/ERASE 正确性 | 依赖槽状态及“路径无 EMPTY”不变量;每轮最多 (m) 次 probe |
| 单次最坏时间 | (O(m)),即使 (n) 很小也可能受墓碑影响 |
| 空间 | (O(m)) 个槽 |
| 理想随机排列探测、无墓碑 | 失败查找期望 (\le1/(1-\alpha)),须 (\alpha<1) |
| 线性探测、无墓碑 | 在适当随机 home 地址假设下可得到常负载时平均 (O(1)),但有明显 primary clustering |
| 墓碑长期累积 | 上述无墓碑平均界不能直接使用,应考虑清理重建 |
本课主线: 哈希冲突 → 线性探测 → 路径不变量 → 墓碑删除 → 理想概率模型 → 真实聚集效应。
下一课(2026-10-30,第 11 课): Double Hashing 与 Robin Hood Hashing:如何改变探测序列或交换规则以缓解聚集,哪些改动会影响删除和查找不变量。
九、四级自测(100 分;首次不公布答案)
Lv1 机制辨析、Lv2 手工 probe Trace、Lv3 模型假设与反例、Lv4 数据结构不变量及尾概率证明。前三题可客观评分,Lv4 按证明要点评分。题目给出中立提示,不公布答案。
Lv1|机制与删除语义|15 分|预计 2 分钟|单选
在线性探测散列表中,某个键被删除,但它后面可能还有碰撞后插入的键。关于查找和删除,哪一项严格正确?
A. 删除后直接将槽标成 EMPTY;因为键已经删除,后续查找不受影响。
B. 删除后可标成 DELETED;查找要跳过 DELETED,遇到 EMPTY 或检查完 m 个槽后才可确认不存在。
C. 只要活跃键数不超过桶数的一半,查找任何键最多探测两次。
D. 遇到 DELETED 时必须重新随机选哈希函数,否则原有键一定无法找到。
中立提示:沿着一个键从其 home slot 到当前位置的探测路径,想想中间能否出现真正的 EMPTY。
Lv2|插入、墓碑与探测次数|20 分|预计 4 分钟|数值
表长 m=11,线性探测 h(x)=x mod 11,头部第一个待查槽是 h(x)。依次插入 [15,26,37,7,18];删除 26(留下 DELETED)。随后 FIND(37)、PUT(48)(48 不存在,须先查重直到遇到 EMPTY,再优先复用沿途首个 DELETED)、FIND(48)。每访问一个槽算一次 probe,删除操作的 probe 不计。求后三次操作合计探测次数。
中立提示:先画 0..10 的槽位;PUT 即使早早见到 DELETED,也要继续扫描到 EMPTY 才能确认没有重复键。
Lv3|概率模型和聚集的边界|25 分|预计 4 分钟|多选
关于开放寻址的期望成本、聚集与边界,以下哪些说法成立?(多选)
A. 若无 DELETED、探测顺序对每个新查询是与占用状态独立的均匀随机排列,且 n<m,则失败查找期望探测次数不超过 1/(1−n/m)。
B. 只要哈希族满足任意两个固定键的碰撞概率不超过 1/m,就可以不加其他条件,推出线性探测的期望查找成本为 O(1)。
C. 即使活跃负载因子 n/m 很低,若大量槽为 DELETED,失败查找仍可能扫描很长一段探测路径。
D. 因为线性探测每次探测的槽号不同,所以它与每次从所有槽均匀随机选择一个尚未访问槽具有完全相同的期望成本。
中立提示:把“均匀随机排列”与“每次 +1”区分开,再区分活跃键数量和非 EMPTY 槽数量。
Lv4|算法设计、不变量及概率证明|40 分|预计 9 分钟|开放推导
设计支持 FIND、PUT(已存在则更新)、ERASE 的线性探测散列表,槽状态为 EMPTY/ACTIVE/DELETED,表长 m。要求:(a) 给出三种操作伪代码(或精确步骤),尤其是 PUT 遇到 DELETED 时如何查重以及如何避免死循环(12分);(b) 写出“每个 ACTIVE 键的 home slot 至存放槽的探测路径上没有 EMPTY”的不变量,并证明初始化、插入、删除均保持它,从而证明 FIND 正确(10分);(c) 对无 DELETED、均匀随机排列探测模型,使用尾概率证明失败查找的期望 probe 数 ≤1/(1−α),α=n/m<1(10分);(d) 给出一个删除槽直接改成 EMPTY 的最小反例,并解释为什么该随机排列上界不能无条件套用到线性探测或存在大量墓碑的表(8分)。
中立提示:可用两个变量 first_deleted 与 steps;证明时先讨论真正 EMPTY 才终止搜索的理由,再用 E[X]=Σ_{t≥0}Pr(X>t) 求和。
十、作答与反馈
回复 Lv1:字母;Lv2:数值与探测路径;Lv3:全部选项;Lv4:(a)–(d) 推导。我将按 15/20/25/40 分逐题批改。总分 80–100:继续原进度;60–79:加一道针对性巩固;低于 60:优先复习探测不变量与期望尾和。补练不改变既定自然日课号。