算法与数据结构 · 第 13 课

第二周复习:随机化、哈希与摊还分析——四种“快”的保证不能混为一谈

2026 年 11 月 1 日|第 2 周 · 第 7 天(复习日)|讲授约 17 分钟,自测另计

今天不讲新的哈希变体,而是把第 8–12 课串成一条完整推理链:算法是否一定正确?单次最坏多慢?随机期望有多快?连续更新的摊还成本如何证明? 它们是四个不同的问题。

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

能解释随机 Quickselect 与 Monte Carlo 的不同;从通用哈希的两键碰撞概率推导链地址表的期望查找代价;比较线性探测、双重哈希、Robin Hood 的正确性不变量;证明动态重建总摊还工作,并识别自适应攻击、墓碑与负载阈值带来的例外。

记号统一:表长 / 桶数为 (m),活跃键数为 (n),负载 (\alpha=n/m)。随机 Quickselect 的规模也会写作 (n),但它处理的是一次选择任务;哈希表处理的是多次字典操作。

二、一张地图:到底是哪一种复杂度?(约 2 分钟)

结论 随机变量 / 量词 可以说什么 不可以偷换成什么
Las Vegas 正确性 对每条合法随机轨迹 返回答案一定正确 每条轨迹都很快
随机 Quickselect 期望 (O(n)) 固定输入、对内部随机枢轴取期望 预先固定的坏排列也有线性期望 最坏 (O(n))
通用哈希的查找期望 (O(1+\alpha)) 固定键与查询、随机选哈希函数 平均碰撞数受控 最长链一定很短
动态表重建摊还 (O(1)) 对任意合法更新序列求总成本 (U) 次更新的重建总成本 (O(U)) 某次扩容最坏 (O(1))

尤其重要:期望是对随机数取平均;摊还是把同一操作序列中偶尔昂贵的步骤分摊到其他步骤。这两个概念可同时出现在一个算法中,但不能相互替代。

flowchart TD
  A["准备评价一个算法"] --> B{"答案每次都正确吗?"}
  B -->|否| MC["Monte Carlo:需要错误概率界"]
  B -->|是| LV["确定性 / Las Vegas"]
  LV --> C{"时间保证针对什么?"}
  C --> W["单次最坏:必须覆盖所有执行"]
  C --> E["期望:固定输入后对随机性平均"]
  C --> AM["摊还:任意 U 次操作的总成本"]
  E --> H["例:通用哈希碰撞指示变量"]
  AM --> R["例:扩缩容阈值与重建间隔"]

三、复盘一:随机 Quickselect 的证明骨架(约 3 分钟)

对数组的当前区间随机抽枢轴 (p),做三路分区 (L(<p),E(=p),G(>p))。求局部第 (k) 小时:

a = |L|; b = |E|
if k <= a:         继续在 L 查第 k 小
else if k <= a+b:  返回 p
else:              继续在 G 查第 (k-a-b) 小

核心不变量:目标排名始终落在保留的区间内。 即使枢轴很坏,答案仍然正确,因此这是 Las Vegas 型随机算法,而不是允许小概率错答的 Monte Carlo。

再看运行时间。对当前 (s) 个元素,若每轮重新从当前位置均匀随机取枢轴,则至少一半排名位于中间一半;选到这样的“好枢轴”时,下一子问题最多保留约 (3s/4) 个元素。即使有重复值,用位置标签分析随机排名、按键值三路分区,等值段整体移除也不会恶化规模。

在任何历史条件下,好枢轴概率至少 (1/2);等待好枢轴的期望分区次数不超过 2。规模阶段于是满足

[ \mathbb E[T(n)]\le 2cn+2c(3n/4)+2c(3/4)^2n+\cdots=O(n). ]

这并不排除一种罕见执行:每轮都选到最差端点,扫描 (n+(n-1)+\cdots+2=\Theta(n^2))。

数值回顾: (A=[2,2,5,7,7,7,9]),求第 5 小。若枢轴为 7,(L=[2,2,5])、(E=[7,7,7])、(G=[9])。因为 (3<5\le6),立刻返回 7。可见三路分区也避免了全相等输入的二路退化。

四、复盘二:从“两键碰撞”到“期望常数”(约 3 分钟)

链地址法每个桶维护一条链;预先固定互异键集 (S)(大小 (n))和一个不在表内的查询 (q)。初始化时从通用哈希族随机选函数 (h),要求对任何固定不同的 (x,y) 有

[ \Pr_h[h(x)=h(y)]\le \frac1m. ]

定义 (I_x=1) 当且仅当 (h(x)=h(q))。失败查找检查的节点数为 (L=\sum_{x\in S}I_x),于是

[ \mathbb E[L]=\sum_{x\in S}\Pr[h(x)=h(q)] \le\frac{n}{m}=\alpha. ]

成功查找至多还要比较目标键一次,即期望比较数不超过 (1+(n-1)/m)。不需要假设这些碰撞事件相互独立,只需要期望的线性性。

注意与随机 Quickselect 的区别:Quickselect 在每轮重新抽枢轴;散列表在一次建表 / REHASH 时抽出 (h),然后在该周期内固定使用,否则旧键的桶位置会失效。

量词边界: 若攻击者先看到已选 (h),再挑选许多同桶键,新的键集依赖 (h);不能直接套用“先固定 (x,y),再随机取 (h)”的证明。负载因子 (\alpha\le1) 仅限制平均链长,不限制某次执行的最长链。

五、复盘三:开放寻址的正确性不变量比较(约 3 分钟)

策略 探测规则 必须维护的不变量 / 限制
线性探测 ((h(x)+i)\bmod m) ACTIVE 键抵达存放槽前不能遇到 EMPTY;墓碑 DELETED 不可当 EMPTY
双重哈希 ((h_1(x)+i h_2(x))\bmod m) (\gcd(h_2(x),m)=1) 才能走完全部槽;查找沿同一路径
Robin Hood 仍逐槽 (+1),位移更大者抢位 无墓碑标准布局中,查询距离超过占用者位移可提前停止;删除用 backward shift 维护布局

一个具体反例: 线性探测 (m=7,h(x)=x\bmod7),先插入 10(在槽3),再插入 17(在槽4)。删除 10 后若将槽3直接标 EMPTY,FIND(17) 从 home 3 开始会立刻错误地返回不存在。正确的墓碑删除把槽3标为 DELETED,查询必须继续探测。

Robin Hood 则可使用另一种设计:不留墓碑,删除时把紧随其后的、位移大于 0 的键逐个左移,遇到 EMPTY 或位移为 0 的键停止。这个操作不能未经证明替换到任意开放寻址布局。

双重哈希还有一个独立的数论条件:步长 (s) 的探测周期是 (m/\gcd(s,m))。例如 (m=12,s=4),只能反复经过 3 个不同槽;即使其他位置空着也到不了。

概率模型不可混用。 “每轮探测是独立于占用状态的均匀随机排列”可推出无墓碑失败查找期望 probes (\le1/(1-\alpha))((\alpha<1)),但线性探测按连续地址访问,会产生 primary clustering;仅有两键通用哈希碰撞界不足以直接继承这个上界。

六、复盘四:动态重建的摊还证明(约 3 分钟)

考虑链地址表:初始 (m=4),新键插入后若 (n>m) 则 (m\leftarrow2m);成功删除后若 (m>4) 且 (n<m/4) 则 (m\leftarrow m/2)。每次 REHASH 都建新桶数组、重新抽 (h) 并搬迁每个存活键;一次费用 (\Theta(m_{\text{new}}+n))。

PUT(x,v):
    若 x 存在:只更新值
    否则插入唯一新节点;n += 1
    若 n > m:REHASH(2*m)

ERASE(x):
    若 x 不存在:返回
    否则摘除节点;n -= 1
    若 m > 4 且 n < m/4:REHASH(m/2)

REHASH(new_m):
    创建 new_m 个空桶;独立抽取新 h
    每个旧活跃节点按 new_h(x) 移入新桶
    替换旧表、旧 h、旧 m

重建后的表总是大约半满:扩容后 (n=m_{\text{new}}/2+1),缩容后 (n=m_{\text{new}}/2-1)(小容量例外由常数处理)。要再触发 (n>m) 或 (n<m/4),至少需要 (\Omega(m)) 次真正改变活跃键数的操作。下一次重建费 (O(m)),可由这些更新分摊,故

[ \boxed{\text{任意 }U\text{ 次更新的全部重建成本}=O(U).} ]

这里不依赖哈希函数是否随机。普通桶扫描另算:若预先固定的操作序列不依赖哈希种子且每次重建独立抽通用哈希,则 (\alpha\le1),桶扫描的期望总工作为 (O(U+Q))。两者合并,得到所有操作的期望 (O(U+Q)),而不是每次最坏 (O(1))。

反例提醒: 若把缩容阈值改为 (n\le m/2),从满表 ((n,m)=(M,M)) 插入 1 个键触发扩到 (2M),立即删除该键又缩回 (M)。反复两次更新就能产生 (\Theta(M)) 重建;(1/4) 阈值的作用是消除这种“容量抖动”。

七、六句自检与后续安排(约 2 分钟)

读任意数据结构论文中的“常数时间”声明,先问:最坏、期望还是摊还? 如果是期望,随机性在哪一层、对什么固定输入取平均? 如果是摊还,哪段更新序列为大操作付费? 如果是开放寻址,删除后探测路径仍正确吗? 如果是哈希表,负载因子和墓碑数量都控制了吗? 如果面对攻击者,键是否在种子选定后才构造?

本次是第二周复习,不额外推进专题。下一课(2026-11-02,第 14 课)进入第 3 周:高级树与持久化,从二叉搜索树和旋转不变量出发,过渡到平衡树及区间查询的设计动机。

八、四级自测(100 分;首次不显示答案)

前三题可客观判分;Lv4 根据证明步骤给分。四题考察不同维度,课堂正文只有中立提示,标准答案与解析仅保留在独立测验 JSON 中。

Lv1|随机化保证的量词与数据结构边界|15 分|预计 2 分钟|单选

对随机 Quickselect 和链地址通用哈希表,以下哪项表述同时严格成立?

A. 对任意预先固定的输入,每轮均匀随机选枢轴且正确三路分区的 Quickselect 一定返回正确结果、期望 O(n),但存在 Θ(n²) 的执行;通用哈希表对独立于哈希种子的固定键与查询可保证期望 O(1+α) 查找,却不能保证每次查找最坏 O(1)。

B. Las Vegas 算法允许小概率错误,但要求运行时间严格固定;Monte Carlo 必须返回绝对正确答案。

C. 链地址哈希表只要 α=n/m≤1,就保证每个桶的长度不超过 1,与哈希函数如何选取无关。

D. Robin Hood Hashing 和 Double Hashing 均能保证任何键集、任何哈希函数下的单次最坏 O(1) 查询。

中立提示:分别检查答案正确性、时间的概率保证,以及负载因子究竟控制平均值还是最长链。

Lv2|Robin Hood 插入、后移删除与探测路径|20 分|预计 4 分钟|数值

表长 m=7,h(x)=x mod 7,无墓碑 Robin Hood 线性探测:仅当待插入键的当前位移严格大于占用键的位移时交换(相等不交换)。依次插入 [0,1,7,14,8,15],然后删除 7 并使用 backward-shift deletion。随后依次 FIND(15) 和 FIND(22),启用“占用者位移小于查询距离即可提前停止”,每访问一个槽计 1 probe,删除成本不计。求这两次 FIND 的 probe 总数。

中立提示:先用 d=(槽号-home+m) mod m 标出每个键的位移;删除后从洞开始连续左移,再分别按各自 home 顺序查询。

Lv3|双重哈希周期、提前终止条件、概率模型与对抗输入|25 分|预计 4 分钟|多选

下列关于哈希探测和概率界的断言,哪些成立?(多选,选出全部正确项)

A. 在双重哈希 p_i=(h1+i·s) mod 12 中,若 s=8,则从任意 home 出发最多访问 3 个不同槽。

B. 在没有墓碑且由标准 Robin Hood 插入与 backward-shift deletion 维护的表中,查询到某槽时,若占用键位移小于查询键走到此处的距离,可以正确提前报告不存在。

C. 只要初始哈希函数族满足两键碰撞概率≤1/m,就可不加其他假设地将‘均匀随机排列探测’的失败查找期望≤1/(1−α)直接用于线性探测。

D. 如果攻击者先看到所选哈希函数,再按其碰撞情况构造键集,针对预先固定两键的通用哈希碰撞界不能无条件直接套用到这些自适应键上。

中立提示:分别核对模运算的周期、Robin Hood 布局不变量,以及“随机 home”与“独立随机探测排列”是不是同一模型。

Lv4|动态散列表设计、摊还分析、期望证明及对抗反例|40 分|预计 10 分钟|开放推导

设计一张动态链地址散列表,初始 m=4 个桶、n=0 个互异键;新键插入后若 n>m 则扩容至 2m;成功删除后若 m>4 且 n<m/4 则缩容至 m/2。每次 REHASH 都为新桶数独立抽取满足两键碰撞概率上界 1/m 的通用哈希函数,重新安置全部键。要求:(a)(10分)给出 FIND、PUT、ERASE、REHASH 的关键伪代码和保证正确性的桶归属、唯一键不变量;(b)(12分)对任意 U 次更新证明全部重建工作为 O(U),但单次重建可达 Θ(n),说明为何 1/4 缩容阈值避免抖动;(c)(10分)当整个操作序列预先固定且不依赖哈希随机参数时,用碰撞指示变量证明每次普通链表扫描期望 O(1),并推出 U 次更新、Q 次查询的总期望 O(U+Q);(d)(8分)给出公开哈希函数后自适应攻击的边界解释,并将其随机性保证与随机 Quickselect 的 Las Vegas 正确性、期望/最坏运行时间作对照。

中立提示:将证明拆为两部分:重建后容量大致半满意味着要经历 Ω(m) 次改变 n 的更新才能再重建;固定查询的同桶节点数则是若干 0/1 碰撞指示变量之和。

九、作答与反馈

可回复 Lv1:字母;Lv2:总 probes 与关键槽位;Lv3:全部选项;Lv4:(a)–(d) 分步推导。逐题按 15/20/25/40 分评分:80–100 分按原计划推进;60–79 分针对错因补一题;低于 60 分优先复习分区不变量、哈希随机性量词与摊还收费。复习与补练不修改自然日课号。