算法与数据结构 · 第 12 课

动态哈希表:扩缩容的摊还证明与随机化的失效边界

2026 年 10 月 31 日|第 2 周 · 第 6 节|正文约 17 分钟(自测另计)

前三课分别讨论了通用哈希、线性探测、双重哈希与 Robin Hood Hashing。今天换成一个更完整的系统问题:表不断插入、删除时,怎样保持查询期望高效,又不被反复重建拖垮? 还要分清“数学上的随机哈希”到底能防住哪类对手。

一、学习目标与模型(约 1 分钟)

学完需要掌握:① 设计有迟滞区间(hysteresis)的扩容/缩容规则;② 正确执行 REHASH 并手工跟踪容量;③ 证明一次很贵的重建为什么不会使总更新成本很贵;④ 精确说明“随机哈希期望 O(1)”对输入和随机种子的要求。

为把论证讲清,本课使用链地址法:容量 m 是桶数,n 是不同的活跃键数,负载因子 α=n/m。每桶是链表;计算机器字长键的哈希、访问桶头、搬运一个节点均记 O(1)。固定操作序列与随机哈希参数独立。初始化 m=4、n=0;每次重建独立抽取适用于新桶数的通用哈希函数。这里不使用墓碑;开放寻址的墓碑清理需要额外维护条件。

二、动机:负载因子是“平均”,而非“最长链”(约 2 分钟)

如果只有 m=4 个桶,n 从 1 长到 100 而从不扩容,平均每桶 25 个键,连理想随机哈希也无法让失败查找保持常数期望。反过来,若每插入一个键就重建,查询或许很快,但更新非常昂贵。

我们要同时管理两个预算:

[ \text{查询预算:}\quad \alpha=\frac nm=O(1),\qquad \text{重建预算:}\quad\sum \text{REHASH 成本}=O(U), ]

其中 U 是更新(插入/删除)次数。注意:α≤1 不代表最长链≤1。若固定 h(x)=x mod 4,键 1、5、9、13 会全部落到同一桶;真正支撑期望查找的是上一课证明过的两键碰撞概率界,不是只靠调容量。

三、完整动态规则:增长与缩减之间必须留空隙(约 3 分钟)

采用如下规则:新键插入后若 n>m,容量翻倍;成功删除后若 m>4 且 n<m/4,容量减半;其他情况不重建。这里故意使用严格不等号,可避免边界计数混乱。

INIT:
    m = 4; n = 0
    h = SampleUniversalHash(m)
    B = array of m empty lists

FIND(x):
    scan B[h(x)] for x
    return value or NOT_FOUND

PUT(x, value):
    scan B[h(x)]
    if x exists: update its value; return
    insert (x,value) at head of B[h(x)]
    n += 1
    if n > m: REHASH(2*m)

ERASE(x):
    scan B[h(x)]
    if x absent: return NOT_FOUND
    unlink x from the bucket
    n -= 1
    if m > 4 and n < m/4: REHASH(m/2)

REHASH(new_m):
    new_h = SampleUniversalHash(new_m)  # 新的独立随机参数
    new_B = array of new_m empty lists
    for each ACTIVE node (x,value) in all old buckets:
        move node to head of new_B[new_h(x)]
    B = new_B; h = new_h; m = new_m

REHASH 不能只把 m 改成 2m。 桶号依赖 m 和哈希函数;所有存活键都要按新的 h 重新分配。建新桶数组需要 Θ(new_m),搬运 n 个节点需要 Θ(n),所以一次重建的真实成本是 Θ(new_m+n)。

flowchart TD
  A["PUT 新键 / ERASE 已存键"] --> B["更新 n"]
  B --> C{"n > m ?"}
  C -->|是| D["REHASH(2m),重抽 h,重放全部键"]
  C -->|否| E{"m > 4 且 n < m/4 ?"}
  E -->|是| F["REHASH(m/2),重抽 h,重放全部键"]
  E -->|否| G["保持原容量与哈希函数"]
  D --> H["下次操作"]
  F --> H
  G --> H

四、数值 Trace:为什么边界上的等号重要?(约 2 分钟)

为直观演示桶分布,仅在这个例子中暂用确定性 h_m(x)=x mod m;它不是安全或通用随机哈希的替代品。依次插入 1、5、9、13、17,再删除 17、13、9、5:

操作后状态 n m 本次是否重建、搬运多少键
初始 0 4 否
插入 1、5、9、13 4 4 都不重建(n=m 仍可保留)
插入 17 5 8 增长:重放 5 个键
删除 17、13 3 8 否
删除 9 2 8 否,n=m/4 不满足 n<m/4
删除 5 1 4 缩减:重放剩余的 1 个键

在 m=4 时,四个键 1、5、9、13 同处桶 1;扩到 m=8 后,1、9、17 属于桶 1,5、13 属于桶 5。重建改变桶归属,但不会改变集合里的键。这次操作总共搬运 5+1 个活跃键;不要把普通 PUT/ERASE 的动作计入“重建搬运”。

五、正确性不变量:动态变化时什么必须始终保持?(约 2 分钟)

每次完整操作后保持:

  1. 键唯一且归属正确: 每个活跃键 x 恰好出现一次,只在 B[h(x)] 内;其他桶没有它。
  2. 容量合法: m≥4 且为 2 的幂;0≤n≤m;当 m>4 时还有 n≥m/4。
  3. 同一重建周期的哈希不变: h 只在 INIT 或 REHASH 时选择,周期内 FIND、PUT、ERASE 都用同一个 h。

初始化显然成立。PUT 先查重,已存在只改值;新键只进自己的桶,若超负载就完整重建。ERASE 仅删除命中节点,若低于阈值就完整重建。REHASH 对每个旧节点恰好访问一次,新桶只按照 new_h(x) 放置,因此不丢键、不复制键。归纳证明三个不变量一直保持。

于是 FIND 的结果总是正确:若某键存在,它必在唯一的目标桶中;扫完桶未找到就确实不存在。随机性不改变这个事实,只影响链长。

六、最重要的证明:为什么 U 次更新总重建成本只有 O(U)?(约 3 分钟)

先看每次重建结束后的状态。若从旧容量 m 增长为新容量 m’=2m,那么触发时 n=m+1,因此

[ n=\frac{m’}2+1. ]

若从旧容量 m 缩减为 m’=m/2,那么成功删除使 n 首次小于 m/4;由于 n 每次只减 1,触发时 n=m/4-1,因此

[ n=\frac{m’}2-1. ]

(当 m=4 时禁止缩容;小容量的边界工作是常数。)

所以不论刚扩还是刚缩,表都回到“大约半满”。从 n≈m’/2 到下次触发 n>m’ 或 n<m’/4,至少需要 Ω(m’) 次真实插入/删除。更新已有键、删除不存在键也可能发生,但只会让间隔变长,不会使它缩短。

假设两次相邻重建间旧容量是 M。下一次重建的新容量只能是 2M 或 M/2;建桶加搬运花 O(M)。而在这次重建前,已经有 Ω(M) 次成功改变 n 的操作。把 O(M) 的重建费用平摊给这 Ω(M) 次更新,每次只额外收 O(1)。初始 m=4 到首次重建只涉及常数级工作;对所有重建重复收费得到

[ \boxed{\text{任意 U 次更新的总重建工作}=O(U).} ]

这是确定性的摊还界,不需要随机输入,也不依赖哈希链是否均匀。不过某一次重建仍可搬运 Θ(n) 个键,所以不能把“摊还 O(1)”说成“单次最坏 O(1)”。

七、随机化提供什么?对抗输入在哪一步破坏证明?(约 2 分钟)

对固定的查询键 q 和固定已存集合 S,在抽取当前 h 之前就确定它们,设 I_x=1[h(x)=h(q)]。通用哈希保证对 x≠q 有 Pr(I_x=1)≤1/m。失败查找的比较次数 L 是这些指示变量之和:

[ \mathbb E[L]\le\sum_{x\in S}\frac1m=\frac nm\le1. ]

成功查找最多多比较目标键一次,所以期望比较数≤1+(n−1)/m≤2。这里不需要各次碰撞独立。因此对与随机哈希种子独立、预先固定的 U 次更新及 Q 次查询,普通查找/查重期望 O(1),重建总费用确定性 O(U),合计期望

[ \boxed{\mathbb E[\text{总工作}]=O(U+Q).} ]

但量词顺序很关键:

  • 先固定键和查询,再随机选 h:两键碰撞概率界适用。
  • 先公开 h,再让攻击者挑大量同桶键:查询键依赖 h,不能再直接套用固定两键的概率保证。即使 α≤1,某一条链仍可长达 Θ(n)。

把哈希种子隐藏或在重建时重新随机化可以改变攻击难度,却不能把普通通用哈希直接当成针对任意自适应攻击的密码学安全保证。若键是长字符串,算哈希的成本也不再自动是 O(1)。

八、反例:为什么不在“半满”时立即缩容?(约 1 分钟)

设把缩容条件错误地改为 n≤m/2,增长条件仍为 n>m。旧容量为 M 且 n=M 时,插入一个键使 n=M+1,立刻扩到 2M;随后删除这个键使 n=M,恰好满足 n≤(2M)/2,又缩回 M;再插入、再删除,不停来回。

容量 M、n=M
   插入:n=M+1 → 扩容 2M,搬 Θ(M) 个键
   删除:n=M   → 缩容 M, 搬 Θ(M) 个键
   插入:n=M+1 → 扩容 2M,搬 Θ(M) 个键
   ... 每一两次更新都付出 Θ(M) 重建工作

原规则选择低于 1/4 才缩,是给增长和缩减设置迟滞区间,确保两次大重建之间有足够多的更新来支付成本。

九、复杂度总结与下一课(约 1 分钟)

成本对象 结论 适用条件
FIND、PUT、ERASE 普通桶扫描 期望 O(1) 通用哈希、输入与种子独立、α≤1
单次普通桶扫描最坏 O(n) 同桶键可能很多
单次 REHASH Θ(n+m’) 新建 m’ 桶并搬运 n 个活跃键
任意 U 次更新的全部 REHASH O(U) 翻倍增长、1/4 缩容、m≥4
U 次更新 + Q 次查询总期望 O(U+Q) 上述概率与成本模型同时成立
空间 O(n+m)=O(n+1) 阈值使 m=O(n+1),重建峰值也是同阶

本课最值得保留的两个证明模板:“重建后半满 → 下一次重建前必须经历 Ω(m) 次更新”用于摊还证明;“先固定输入 → 对随机选出的哈希函数做碰撞指示变量求和”用于期望证明。两套证明相互独立,合起来才有完整动态性能保证。

下一课:2026-11-01,第 13 课(第 2 周复习)。 综合对比 Las Vegas/Monte Carlo、通用哈希、开放寻址、Robin Hood、负载控制与自适应对抗,并训练判断每项复杂度声明的前提。

十、四级自测(总分 100;首次仅提供中立提示)

前三题自动判分,Lv4 按推导步骤评分;课堂正文不提供答案或解析,标准答案与评分细则只保存在对应互动测验 JSON 中。

Lv1|负载因子、随机化保证与重建代价|15 分|预计 2 分钟|单选

对链地址哈希表使用“n>m 时桶数翻倍,n<m/4 且 m>4 时减半”,每次重建重新抽取通用哈希函数。下面哪项严格成立?

A. 只要每次操作后 n≤m,就能保证每个桶最多存一个键。

B. 因为一次重建可能是线性成本,所以 U 次更新必然需要 Ω(U²) 总时间。

C. 对独立于哈希随机参数的固定键集和查询,可以得到期望 O(1) 查找;但某次重建仍可能耗时 Θ(n),固定坏哈希函数也可能产生长链。

D. 扩容仅改变桶数,不必重新计算或重新放置任何已有键。

中立提示:分别检查平均负载与最长链、单次最坏与摊还成本、随机期望与确定性保证。

Lv2|动态阈值 trace、重建移动计数|20 分|预计 4 分钟|数值

初态为 m=4、n=0,链地址表在一次插入完成后若 n>m 则扩容为 2m,在一次删除完成后若 n<m/4 且 m>4 则缩容为 m/2。重建时将当时所有 n 个活跃键各搬运一次。先依次插入 A、B、C、D、E;再依次删除 E、D、C、B;最后依次插入 F、G、H、I。仅统计历次重建搬运的活跃键总数(不计普通插入和删除),答案是多少?

中立提示:每一步先更新 n,再检查严格不等号;写出三次可能的容量变化及重建时的 n。

Lv3|对抗性输入、概率适用条件与阈值抖动|25 分|预计 4 分钟|多选

关于动态哈希表的随机化保证及重建策略,下列哪些判断成立?(多选,选出全部正确项)

A. 如果完整操作序列在抽取随机哈希函数前已固定,且重建时重新独立抽取通用哈希函数,那么可以对每次查询使用固定键集的两键碰撞概率界。

B. 只要 n≤m,即使哈希函数已经公开且攻击者可自适应构造键,也总能保证每次 FIND 的最坏时间 O(1)。

C. 如果攻击者先观察已选的 h 再选择许多同桶键,原本针对固定 x≠y 的碰撞概率上界不能直接照搬到这种自适应选择上。

D. 增长条件 n>m 与缩容条件 n≤m/2 一起使用,仍能保证反复一次插入、一次删除时不发生频繁重建。

中立提示:核对随机哈希证明的量词顺序;再看扩容后 n 是否紧靠“半满就缩”的阈值。

Lv4|动态数据结构算法设计、摊还证明、期望界及反例|40 分|预计 10 分钟|开放推导

设计一个带唯一键的动态链地址哈希表,初始 m=4;插入新键后 n>m 扩成2m,删除键后 n<m/4 且 m>4 缩成m/2,每次重建独立选一个通用哈希函数。(a)(10分)写出 FIND、PUT、ERASE、REHASH 的关键伪代码,并给出键唯一、桶归属和负载不变量;(b)(13分)证明任意 U 次合法更新触发的所有重建总工作量为 O(U),明确一次重建为何可能为 Θ(n);(c)(10分)对与哈希种子独立的固定操作序列,用指示变量证明普通查找期望 O(1),从而说明 U 次更新与 Q 次查询的总期望工作量为何可为 O(U+Q);(d)(7分)分别给出“缩容阈值改为 n≤m/2”导致抖动的反例,以及公开哈希函数后自适应构造碰撞键为何不符合上述概率前提。

中立提示:重建后观察 n 与新 m 大致为 1/2 的关系;下一次触发阈值前要积累多少更新?碰撞数可写为若干 0/1 指示变量之和。

十一、提交与反馈

回复 Lv1:字母;Lv2:数字及关键容量变化;Lv3:所有选项;Lv4:(a)–(d) 分步证明。逐题按 15/20/25/40 分批改:80–100 分依原进度继续,60–79 分补一道针对性巩固题,低于 60 分复习“阈值迟滞与摊还收费”和“随机种子的量词顺序”。补练不改变原定课号。