算法与数据结构 · 第 9 课
随机哈希与通用哈希:如何把“碰撞概率”变成期望 (O(1))?
2026 年 10 月 28 日|第 2 周 · 第 2 节|正文约 17 分钟(自测另计)
上一课的随机 Quickselect 是“每轮抽一个随机枢轴”。今天讨论另一种随机化:散列表在创建时随机选一个哈希函数,后续操作一直使用它。我们不会直接假定“哈希很均匀”,而是从可证明的两键碰撞概率,推导查询成本。
一、学习目标与模型(约 1 分钟)
本课要能做到四件事:解释冲突为什么不可避免;读懂链地址散列表的插入、查找和删除;证明通用哈希族的碰撞上界;使用指示变量与期望的线性性证明平均每次查找是 (O(1+\alpha)),并指出哪些对抗输入会使保证失效。
约定:存储 (n) 个不同的键,桶数 (m\ge1),负载因子 (\alpha=n/m)。一个桶是一条链表,查找费用统计实际比较了多少个节点关键字;计算一次哈希、数组访问与一次链表操作按 (O(1))。理论上所有键先固定,且不依赖本次随机选出的哈希参数。数值示例先不扩容;实用实现的扩容另行讨论。
二、为什么“取模就能均匀”是错误直觉?(约 2 分钟)
设一个固定哈希函数 (h(x)=x\bmod m)。如果 (m=5),键 (2,7,12,17) 全落到桶 2;更一般地,攻击者可以选 (0,m,2m,\ldots,(n-1)m),令 全部 (n) 个键落在同一桶。哪怕 (n/m) 不大,也可能形成一条长链。
只要可用键空间大于桶数,就不可能保证每个不同键都去不同桶(抽屉原理)。问题不是“能否彻底消除碰撞”,而是:
[ \text{对任意预先固定的 }x\ne y,\qquad \Pr_{h\sim\mathcal H}[h(x)=h(y)]\le\frac1m. ]
满足这一性质的随机函数族称为通用哈希族(universal family)。概率来自选取哈希函数的随机过程;不是给已经固定的函数赋予神秘的“随机输出”,也不是每次查询都重新换函数。
这条性质比“所有键映射相互完全独立且均匀”弱得多。今天推导期望查找长度,只需要两键碰撞概率上界,不需要假设所有桶长独立。
三、数据结构与可执行伪代码(约 2 分钟)
用 (B[0],\ldots,B[m-1]) 表示桶数组。每个桶的节点保存 ((key,value,next)),采用头插法。
初始化:
选定 m 和随机哈希函数 h;创建 m 条空链
FIND(x):
b = h(x)
for node in B[b] 从表头遍历:
if node.key == x: return node.value
return NOT_FOUND
PUT(x, value):
b = h(x)
for node in B[b]:
if node.key == x: node.value = value; return
new_node.next = B[b].head
B[b].head = new_node
n += 1
ERASE(x):
b = h(x)
逐个维护 prev、curr 扫描 B[b]
若找到 x,修改前驱 next(或桶表头),删除节点,n -= 1
否则返回 NOT_FOUND
核心不变量: 在任意一次完整操作结束后,每个已存键 (x) 恰好出现一次,并且只存在于 (B[h(x)]) 中;没有任何其他键会被误删。初始化显然满足;更新已有值不改变位置;插入前查重且只在指定桶新增;删除只移除命中的指定节点,所以归纳保持不变量。
查找也就正确:若 (x) 存在,必定在被扫描的桶;若扫描完仍未找到,则由不变量知表内不存在 (x)。正确性是确定的,随机性只影响要扫描多长的链。
flowchart LR
K["键 x"] --> H["随机初始化后固定的 h(x)"]
H --> I["桶编号 0…m−1"]
I --> B["B[h(x)] 的链表"]
B --> C["逐个比较 key"]
C --> D{"找到 x?"}
D -->|是| E["返回 value"]
D -->|否,链结束| F["NOT_FOUND"]
四、实际 Trace:每个取模和链表顺序都写出来(约 3 分钟)
采用一组演示用的参数(不是说随机算法总会选到它):
[ p=11,\quad m=5,\quad a=3,\quad b=1,\qquad h(x)=\big((3x+1)\bmod 11\big)\bmod5. ]
依次插入互异键 ([2,7,10,4,9]),每次在桶的表头插入:
| 键 (x) | ((3x+1)\bmod11) | 最终桶号 (h(x)) |
|---|---|---|
| 2 | 7 | 2 |
| 7 | 0 | 0 |
| 10 | 9 | 4 |
| 4 | 2 | 2 |
| 9 | 6 | 1 |
最终结构(箭头指向 next):
桶0: 7 → ∅
桶1: 9 → ∅
桶2: 4 → 2 → ∅ ← 4 后插入,位于表头
桶3: ∅
桶4: 10 → ∅
查询 (x=2) 时先算出桶 2,依次比较 4、2,共比较两个已存键。查询不存在的 (x=1) 时算得 (h(1)=4),比较桶 4 的 10 后发现链结束,返回未找到。空桶时需要零次关键字比较;注意不要把哈希运算、指针判空、关键字比较混为同一个计数。
这个示例里 (\alpha=5/5=1),并不表示每条链都正好长 1。负载因子是全部桶的平均长度,不是最长长度,更不是单次查找的最坏上界。
五、构造一个真正有保证的随机哈希族(约 3 分钟)
令键已无碰撞地编码到 ({0,1,\ldots,p-1}),其中 (p) 是素数、(p\ge m)。创建表时独立均匀地抽取
[ a\in{1,\ldots,p-1},\qquad b\in{0,\ldots,p-1}, ]
再固定使用
[ \boxed{h_{a,b}(x)=\big((ax+b)\bmod p\big)\bmod m.} ]
为什么 (a) 不能取 0? 证明里需要有限域模 (p) 的非零数可逆;若 (a=0),所有键都会映成同一个中间余数 (b)。
现在固定两把不同的键 (x\ne y),并记中间余数 (u=(ax+b)\bmod p)、(v=(ay+b)\bmod p)。由于 (p) 是素数且 (y-x\ne0\pmod p),对任意有序且不同的 ((u,v)),方程组
[ a(y-x)\equiv v-u\pmod p,\qquad b\equiv u-ax\pmod p ]
都恰好有一组合法解 ((a,b))。因此随机 ((a,b)) 对应的 ((u,v)) 在 (p(p-1)) 对不同余数上等概率分布。
固定 (u) 以后,(v) 在剩余 (p-1) 个余数中均匀分布。模 (m) 的每个剩余类,在 (0,\ldots,p-1) 中最多包含 (\lceil p/m\rceil) 个整数。与 (u) 最终同桶、但又不同于 (u) 的余数至多 (\lceil p/m\rceil-1) 个,所以
[
\begin{aligned}
\Pr[h(x)=h(y)\mid u]
&\le\frac{\lceil p/m\rceil-1}{p-1}
&\le\frac1m,
\end{aligned}
]
最后一步来自 (\lceil p/m\rceil-1=\lfloor(p-1)/m\rfloor\le(p-1)/m)。对 (u) 再取期望,即得
[ \boxed{\forall x\ne y:\quad\Pr_{a,b}[h_{a,b}(x)=h_{a,b}(y)]\le1/m.} ]
这是逐对键成立的保证。注意:当 (p) 不能被 (m) 整除时,每个桶的边际概率不必完全相等;因此不能把“通用哈希”直接说成“每个输出独立均匀”。
六、从碰撞概率到查找时间:指示变量是桥梁(约 2 分钟)
先分析不存在的、预先固定的查询键 (q\notin S),其中 (S) 是 (n) 个已存键。定义
[
I_y=\begin{cases}
1,&h(y)=h(q),
0,&\text{否则},
\end{cases}
\quad
L_q=\sum_{y\in S}I_y .
]
(L_q) 恰好是查询时需要检查的链表节点数。由于 (\mathbb E[I_y]=\Pr[h(y)=h(q)]\le1/m),所以
[ \boxed{\mathbb E[L_q] =\sum_{y\in S}\mathbb E[I_y] \le \frac nm=\alpha.} ]
这里仅使用期望的线性性;即使各 (I_y) 相互依赖,也可以求和!把计算哈希和查表的 (O(1)) 计入,总期望时间是 (O(1+\alpha))。
如果查询的是已存键 (x\in S),至多扫描本桶的全部节点,包含自己一次与其他同桶键的比较:
[ \mathbb E[\text{比较次数}] \le1+\sum_{y\in S\setminus{x}}\Pr[h(y)=h(x)] \le1+\frac{n-1}{m} \le1+\alpha. ]
因此只要控制 (\alpha=O(1)),针对每个预先固定的查询键,期望查找就是 (O(1))。执行查重的 PUT 和 ERASE 也有同阶的期望桶扫描成本,若没有查询则头插本身是 (O(1))。
七、这里的“期望”究竟不是哪些保证?(约 2 分钟)
不是最坏 (O(1)): 对已经选好的某个 (h),所有键也可能聚到同一桶,查找最坏 (O(n))。碰撞概率低并没有禁止罕见的坏哈希函数。
不是任何输入分布都自动均匀: 一旦固定 (h(x)=x\bmod m),攻击者可挑整倍数键;通用哈希分析是对随机选取 (h) 取期望,并要求被分析的键集与查询在抽参前固定,或至少与秘密抽参过程独立。
不是“见到桶分布再挑查询键”仍能照抄证明: 若查询 (q) 是观察了所选哈希函数或历史碰撞后自适应构造的,那么 (q) 可能依赖 (h),式子 (\Pr_h[h(y)=h(q)]\le1/m) 就不能原样使用。实际抗碰撞攻击还需考虑密钥保密、更强哈希、防滥用策略等,不能靠一句“随机化”包办。
也不是负载可以无限增长: 当 (n\gg m),(\alpha=n/m) 变大,平均桶长自然增加。维护负载因子上界通常要扩容并把全部旧键按新桶数重新哈希。一次重建可耗费 (O(n+m)),与第一周的摊还思想相连;本课固定桶数分析不自动证明任意动态扩容策略的最坏 (O(1))。
最后,哈希计算视为 (O(1)) 依赖于整数与模运算可在机器字长内完成。若“键”是任意长字符串或超大整数,读键和计算哈希本身可能不再常数时间。
八、复杂度、正确性与下节课(约 1 分钟)
| 性质 | 链地址哈希表的结论 | 必要前提 |
|---|---|---|
| 查询正确性 | 一定正确 | 头插/删除正确维护桶归属与唯一键不变量 |
| 固定不存在键的期望比较数 | (\le\alpha) | 通用哈希族、固定键集与查询 |
| 固定已存在键的期望比较数 | (\le1+(n-1)/m) | 同上 |
| 单次查找最坏时间 | (O(n)) | 可能全部撞在一桶 |
| 存储空间 | (O(n+m)) | (m) 个桶头及 (n) 个节点 |
| 负载有界时的期望时间 | (O(1)) | (\alpha=O(1)),计算哈希 (O(1)) |
本课关键链条:
[ \text{随机选函数} \Longrightarrow \Pr(\text{两键碰撞})\le1/m \Longrightarrow \mathbb E\left[\sum I_y\right]\le n/m \Longrightarrow O(1+\alpha). ]
下一课(2026-10-29,第 10 课): 从通用哈希进入开放寻址与探测序列:为什么线性探测会出现 primary clustering、探测成功/失败成本怎样随负载变化,以及 tombstone 删除为什么不能简单清空一个槽。
九、四级自测(共 100 分;首次不显示答案)
题目依次检查随机性对象、手工链表 Trace、保证的适用范围和完整数学证明。前三题客观判分,最后一题由人工/ChatGPT 或参照 rubric 评阅;解析仅保存在独立互动测验 JSON 中。
Lv1|随机哈希的正确保证|15 分|预计 2 分钟|单选
某链地址哈希表在初始化时,从满足对所有固定不同键 (x,y) 都有 (\Pr_h[h(x)=h(y)]\le1/m) 的函数族随机选一个 (h)。下列哪项严格正确?
A. 每次查询都应重新抽取哈希函数,否则概率保证立即失效。
B. 概率针对初始化时抽选的函数;只要键与查询独立于该选择,每对不同键的碰撞概率受控,但固定一次执行仍可能有长链。
C. 因为每对键的碰撞概率很小,所以任意选出的函数都保证最长链为常数。
D. 上述条件自动保证所有 (h(x)) 都相互独立,且在全部桶上严格均匀。
中立提示:概率是在什么随机实验上计算的?“一对键的概率”能否控制“每个随机结果的最坏链长”?
Lv2|逐个取模与头插链表 Trace|20 分|预计 4 分钟|数值
取 (p=13,m=5,a=4,b=2),(h(x)=((4x+2)\bmod13)\bmod5)。将互异键 ([1,4,6,9,12]) 依次按链表头插方式放入散列表。之后按顺序查找键 (1)、键 (9)、以及不存在的键 (2)。只统计与链表节点 key 的比较次数(不计哈希、空指针检查),三次查询的比较次数合计是多少?
中立提示:先画出全部桶的表头顺序;未命中查询必须扫描其所在桶的全部节点。
Lv3|期望界与自适应输入|25 分|预计 4 分钟|多选
对于包含 (n) 个不同键、(m) 个桶的链地址哈希表,若随机函数族满足通用哈希碰撞界,下列哪些判断成立?(选出全部正确项)
A. 若键集 (S) 和不存在的查询键 (q) 在抽取哈希函数前固定,则 (\mathbb E[\text{与 }q\text{ 同桶的已存键数}]\le n/m)。
B. 负载因子 (\alpha=1/2) 意味着任何一次运行中每条链最多只有一个节点。
C. 若攻击者看到已选哈希函数,再按它构造查询键,则固定键的碰撞概率证明不能无条件地直接用于这个自适应查询。
D. 只要两键碰撞概率 (\le1/m),就能推出所有桶占用数相互独立,且最大桶长在每次运行都为 (O(1))。
中立提示:区分“期望中的求和”与“独立随机变量”,并检查查询是否依赖哈希种子。
Lv4|通用哈希的完整证明与数据结构设计|40 分|预计 9 分钟|开放推导
设 (S) 是 (n) 个不同键,键都已无碰撞地编码到 ({0,\ldots,p-1});(p) 是素数且 (p\ge m)。随机独立均匀取 (a\in{1,\ldots,p-1})、(b\in{0,\ldots,p-1}),定义 (h_{a,b}(x)=((ax+b)\bmod p)\bmod m)。
(a)(10 分)写出链地址表的 FIND、PUT、ERASE 关键步骤与桶归属不变量,并说明确定性正确性;(b)(12 分)对任意固定 (x\ne y),从 ((a,b)) 到不同中间余数对 ((u,v)) 的对应关系出发,证明碰撞概率 (\le1/m);(c)(10 分)分别对预先固定的不存在键 (q) 和已存在键 (x),用指示变量与期望线性性推导期望比较次数,并指出是否需要指示变量相互独立;(d)(8 分)解释为什么最坏查询仍可为 (O(n))、自适应输入为什么可能不满足相同界,以及扩容为什么必须重新放置节点。
中立提示:先用模 (p) 的逆元证明中间余数有序对等概率;再数一个模 (m) 余数类最多包含多少个中间余数。对期望长度,先写“同桶”指示变量之和。
十、提交作答与批改
请回复 Lv1:字母;Lv2:数值及桶内顺序;Lv3:全部选项;Lv4:(a)–(d) 分步证明。届时逐题批改,总分 100:80–100 进入下一节,60–79 做一次针对性补练,低于 60 优先复习碰撞概率与期望线性性。补练不改变按自然日计算的课号。