算法与数据结构 · 第 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 优先复习碰撞概率与期望线性性。补练不改变按自然日计算的课号。