COMP5270 Week 6 总结：Hashing and Friends（题解 + 知识点）

Posted on Edited on In , Word count in article: 22k Reading time ≈ 1:21

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 6 - Hashing and Friends, Week 6 - Going further, Week 6 - Tutorial 6 (Solutions)

Part 1: Tutorial 6 详细题解

如果 dictionary / universe / bucket / collision / load factor / chaining / universal hashing / Bloom filter 这些词还不熟，先看下面 Part 2 的「0. 名词与符号速查」，再回来读题解。

本部分按官方 Solutions PDF（Week 6 - Tutorial 6 (Solutions)）整理：每题先给完整题目，再按官方解的思路逐步展开；所有结论与官方一致，比官方更细的推导步骤会标注 【展开】。与 Part 2 讲义详解的对应位置随处交叉引用。

Tutorial 开头的难度/要求说明

Tutorial 6 开头给了每题的建议投入程度（官方原话翻译）。先整理成总览，后面每道题标题下也单独标出。

题目 所属部分 Tutorial 原文难度/要求 复习时怎么安排
Problem 1 Warm-up 需要读讲义或看 lecture，但应该 doable 先分清 hash table 与 Bloom filter 的 guarantee
Problem 2 Warm-up 需要读讲义或看 lecture，但应该 doable 必做，练 universal hashing + indicator 的标准分析
Problem 3 Problem Solving 可以在 lecture 前尝试；跳过也没关系 用来理解 universal 定义里的 不是
Problem 4 Problem Solving 需要几个 non-trivial ideas；概念和算法上都 interesting 值得认真做，练「用 hash table 砍掉一重循环」
Problem 5 Problem Solving quite important；务必尝试并读 solution 重点题，perfect hashing 的 空间证明很常考
Problem 6 Problem Solving quite important，尤其这题；务必尝试并读 solution 重点题，Bloom filter 错误率公式与最优 必须会推
Problem 7 Advanced 有时间值得做，但 not crucial 扩展题，理解删除如何破坏 one-sided error

Warm-up

Problem 1: Hash table 和 Bloom filter 的区别

Tutorial 难度/要求: Warm-up；需要读讲义或看 lecture，但应该 doable。

题目: 检查你的理解：从时间复杂度、空间复杂度、提供的 guarantee 三个角度，总结 hash table 与 Bloom filter 的关键区别。

题解:

官方答案非常浓缩，只有三句话；下面把每一句展开。

① 空间复杂度（官方第一句）

官方给的对比（在 bucket 足够多、即 的设定下）：

其中 通常是常数。

【展开】每一项是哪来的：

  • hash table（以 separate chaining 为例）： 存 hash function（Part 2 Theorem 31/33 的构造）， 是数组加上链表节点——元素本身必须被存下来，每个元素要 bits。当 时，这和讲义写法 是同一回事（Part 2 §10）；
  • Bloom filter： 存 个 hash functions， 是 bit array——注意这一项没有 因子，因为它根本不存元素，只存 bit。

两边都取 、，对比就变成

Bloom filter 把「每个元素 bits」这一项整个抹掉了，空间与元素的编码长度无关。

② 为什么 Bloom filter 能这么省？（官方第二句）

官方原话：Bloom filter 并不真正存储元素，只存「它们是否在集合里」的那些 bits——这正是它有时会出错的原因。 一句话点破本质：空间优势和错误可能性是同一枚硬币的两面。把元素压缩成几个 bit 位置，信息有损，不同元素的「指纹」可能重叠。

③ 时间复杂度与 guarantee（官方第三句）

  • hash table：操作是期望 （例如 separate chaining 的 ，见 Problem 2），但 worst-case 可到 ；结果永远正确，随机性只体现在运行时间上；
  • Bloom filter：Insert 和 Lookup 是 worst-case （ 常数时），时间上反而有确定性保证；但可能出错——只会 false positive（不在却说在），不会 false negative；并且课上看的 simple version 不支持 Remove（怎么补救见 Problem 7）。

汇总表

hash table Bloom filter
空间（） bits
存元素本身？ 是 否，只存 bits
Insert / Lookup 期望 ，worst-case worst-case
Remove 支持 simple version 不支持
出错？ 从不（随机性只在时间） false positive 可能；无 false negative

本题用到的知识点:

  1. Hash table 存元素，Bloom filter 只存 membership bits——省空间与会出错同源。
  2. 随机性的位置不同：hash table 的随机性影响时间，Bloom filter 的随机性影响正确性。
  3. 复杂度对照详见 Part 2 §12 的对照表。

Problem 2: Separate chaining 的期望时间

Tutorial 难度/要求: Warm-up；需要读讲义或看 lecture，但应该 doable。这是 universal hashing + indicator variables 的标准分析，必须熟练。

题目: 证明课上提出的 claim：separate chaining 下 Insert、Lookup、Remove 的期望时间复杂度都是 ，其中 是 hash table 的 load。它们的 worst-case 时间复杂度是多少？

题解:

第一步：三个操作的成本都由一个量决定（官方的关键观察）

官方开门见山：三个操作的成本都取决于对应 bucket 里有多少元素——在「对 取期望、对数据取 worst-case」的意义下（expected worst-case）。

形式化：随机性来自 的选择。设已插入 ，现在要对 执行一个操作。记 为这次 Insert / Lookup / Remove 所需的操作数。无论哪种操作，都是「算出 ，然后沿 bucket 的链表扫」：

  • Lookup：在链表里找 （成功提前停，失败扫完整条链）；
  • Insert：先查重（语义要求「已在则不动」），最坏扫完整条链；
  • Remove：找到 并摘除，最坏扫完整条链。

所以

其中 表示插入 之后 bucket 的大小， 是求 hash 值、访问数组头这些固定开销（这就是结论里「」的来源）。

第二步：用 universality 控制期望 bucket 大小

不失一般性，设 两两不同（官方注明：这是最难的情形——有重复只会让链表更短）。把 bucket 大小写成 indicator 之和：

由 universal hash family 的定义（Part 2 Definition 32.1），对任意 ：

于是由 linearity of expectation：

而 ，所以

合并第一步的 固定开销：

【展开】两个值得自问的细节：

  1. 为什么求和到 、不含 自己？ collision 是「不同元素撞到一起」； 自己那一项不是随机事件（如果 已在表中，它当然在自己的 bucket 里）。universality 也只对 有保证。
  2. 这里用到了多强的随机性？ 只用了「任意一对元素碰撞概率 」——恰好就是 universal 的定义，不需要 strongly universal，更不需要完全独立。这正是 Part 2 §8 方法论的演示：证明里只出现 pairwise collision bound，所以方案三的小 hash family 完全够用。

第三步：worst-case

在绝对 worst case 下（对 和数据都不利时），可能所有 个元素都被 hash 进同一个 bucket——任何一个 bucket 里至多也就是 个元素，所以单次操作 worst-case 是

这与 Part 2 §9 的 Fact 33.2 呼应：即使 真随机，也大概率有 bucket 长到 ；而对抗性数据配上倒霉的 可以做到 。

本题用到的知识点:

  1. Chaining 三操作的成本 bucket 大小。
  2. indicator + linearity of expectation + universal 的 pairwise bound，是本章证明的标准三件套。
  3. 「期望对 、worst-case 对数据」的混合分析视角（expected worst-case）。
  4. 期望 vs worst-case 的反差。

Problem Solving

Problem 3: Universal 定义中的不等号可以严格

Tutorial 难度/要求: Problem Solving；可以在 lecture 前尝试，跳过也没关系。它帮助你理解 universal hashing 的定义是碰撞概率上界，不要求取等。

题目: 给出一个从 universe 到集合 的 universal hash family 的例子，使得下面的不等式不总是等号：

对所有不同的

题解:

官方构造

取 ，family ：

（恒等）

（交换）

【展开】验证它满足要求

universe 里只有一对不同元素：。逐个检查族中函数：

  • ：，不碰撞；
  • ：，不碰撞。

所以无论随机选到哪个 ：

不等式对唯一的 pair 严格成立，而 当然满足 universal 的定义——构造完成。

【展开】这个例子还顺便说明了两件事

  1. 它不是 strongly universal。 若 strongly universal，碰撞概率必须恰好等于 （Part 2 Lemma 32.1 的证明里是等式）。这里是 ，所以这同时是「universal 但非 strongly universal」的一个极简例子——和 Week 4 Tutorial Problem 8 的主题接上了。可以直接验证：。
  2. universal 不要求「足够随机」，只要求「碰撞足够少」。 极端地说，当 时，单个单射函数构成的族 就是 universal 的（碰撞概率恒为 0）！随机性只有在 （鸽笼强迫碰撞存在，Fact 30.1）时才变得必要。定义用 而不是 ，正是为了把这些「碰撞更少」的好族都包括进来（Part 2 §7「为什么是 」）。

官方还附了延伸阅读：Purdue 大学 Hemanta Maji 的 lecture notes（cs.purdue.edu, Fall 2017, Lecture 14）里有更多这类观察。

本题用到的知识点:

  1. Universal 的定义是 inequality guarantee：上界 。
  2. 碰撞概率严格小于 完全合法（甚至更好）。
  3. 严格不等 不可能 strongly universal（后者强迫等号）。

Problem 4: 三数组 的期望 算法

Tutorial 难度/要求: Problem Solving；需要几个 non-trivial ideas，但在概念和算法上都很 interesting。核心想法：用 hash table 把「第三重循环」换成 查询。

题目: 给定三个数组 ，各含 个正整数。判断是否存在 使得

目标是（期望） 时间的算法。（假设给定合适的 hash function 后，对任意输入求值只需常数时间。）

    1. 热身：描述一个 时间的确定性算法。
    1. 描述一个高效的、期望 时间的算法。
    1. 证明其正确性与期望时间复杂度。
    1. 分析其 worst-case 时间复杂度。这里也能做到 吗？

题解:

a) 基线：枚举所有 triple

对所有 的三元组（共 个）逐一检查 ：

for i in 1..n:
  for j in 1..n:
    for k in 1..n:
      if A[i] + B[j] == C[k]: return true
return false

每次检查 ，总计

b) 用 hash table 砍掉一重循环

观察：第三重循环干的事只是「问 这个值是否出现在 里」——这是一个 membership query，正是 dictionary 的本职工作。官方算法：

  1. 建一个 hash table ，把 的全部 个元素插入 ；
  2. 枚举全部 个 pair ，对每个 pair 在 里 Lookup 值 ：命中则说明存在某个 使 ，返回 true；
  3. 所有 pair 都没命中，返回 false。
T = empty hash table          # 取 m' = O(n)，load factor 常数
for k in 1..n:
  T.Insert(C[k])

for i in 1..n:
  for j in 1..n:
    if T.Lookup(A[i] + B[j]):
      return true
return false

c) 正确性 + 期望时间

正确性（两个方向都要说）：

  • （有解 返回 true） 设存在 使 。把 全部插入后， 中含有值 ；于是枚举到 pair 时，对 的 lookup 必然命中，算法返回 true。（hash table 没有 false negative——它是 exact 数据结构。）
  • （返回 true 有解） 反过来，若算法在某个 返回 true，说明 中含有值 ；但我们只往 里插入过 的值（官方原文此处把 误写成了 ""，意思不变），所以必存在下标 使 。

期望时间：算法总共做 次 Insert 和至多 次 Lookup。课上提到的所有碰撞处理方式（linear probing、separate chaining、cuckoo hashing）的插入和查询都是期望 （取 使 为常数；Part 2 §10–11），所以总期望时间

d) worst-case：取决于碰撞处理方式——cuckoo 能救场！

操作总量不变： 次插入 + 至多 次查询。worst-case 按结构分（官方原文）：

  • linear probing 或 chaining：所有操作 worst-case 都是 。于是总 worst-case 是

——退回基线，毫无改进的保证。

  • cuckoo hashing：插入 worst-case 仍是 （驱逐链可能很长、甚至触发 rehash）；但 lookup 即使在 worst case 也只要 （只看两个格子，Part 2 Theorem 36）。于是

所以答案是：能——用 cuckoo hashing，worst-case 也能做到 。

【展开】这步的算法设计启示：本算法的操作 profile 极度不对称—— 次插入 vs 次查询。所以应该选「查询最强」的结构：cuckoo 恰好把 worst-case 保证放在 Lookup（和 Remove）上，插入贵一点无所谓，因为插入只有 次。按操作频率选数据结构，这是 Theorem 36「3 个操作里 2 个 worst-case 」真正的用武之地。

本题用到的知识点:

  1. 「值是否存在」 membership query，交给 dictionary，立省一重循环。
  2. 正确性证明的固定格式：yes 方向 + 反方向（依赖「表里只有 的值」）。
  3. 期望 每操作 总期望 （linearity of expectation 对总时间求和）。
  4. worst-case 分析要看碰撞处理方式；cuckoo 的 worst-case lookup 把总 worst-case 也压到 。

Problem 5: Perfect Hashing（两层 hashing，重点题）

Tutorial 难度/要求: Problem Solving；quite important，务必尝试并读 solution。对应 Part 2 Remark 36.1。两个考点：二层表为什么开 ；总空间为什么仍是期望 。

题目: （Perfect Hashing）考虑如下两层 hashing 策略：和 separate chaining 一样，用一个大小 的 hash table 来容纳 个元素，碰撞交给每个 bucket 自行处理。但每个 bucket 里不用链表，而是改用一个 secondary hash table。我们聚焦静态场景： 个元素在最开始一次性批量插入，之后只关心 lookup。

    1. 设 bucket 分到了 个元素。bucket 里的 hash table 应该开多大，才能保证它发生碰撞的概率至多 ？
    1. 简述如何批量插入全部 个元素（数据结构的初始化）。
    1. 分析对这个数据结构做一次 lookup 的（期望）时间复杂度。
    1. 分析整个数据结构的期望空间复杂度，并证明它是 。

题解:

a) 二层表开多大？——生日悖论反着用

设 bucket 的二层表大小为 ，二层 hash function 从 universal family 中随机选。bucket 内 个元素两两之间都可能碰撞，用 indicator 数碰撞对数：

（每一对碰撞概率 ，共 对，linearity。）

取

则 。因为碰撞数是非负整数随机变量，由 Markov's inequality：

结论：二层表开到 （pair 数的两倍），就有至少 的概率一次碰撞都没有。

【展开】为什么是「平方」？ 这就是 birthday paradox 的反向应用（Part 2 Fact 33.1）： 个元素有 对，想让期望碰撞对数降到常数以下，表就得开到 。第一层不敢这么干（ 个元素开 空间太奢侈），但对单个 bucket 来说 很小，平方得起——这正是两层设计的精髓，d) 会算总账。（边角情形： 时 ，开 1 格即可，不影响任何渐近。）

b) 批量插入（初始化）怎么做？

官方流程：

  1. 选第一层 hash function （从 universal family 随机选），把全部 个元素 hash 一遍，统计出每个 bucket 的占有数 。假设每次 hash ，这一步 ；
  2. 对每个 bucket ：开一个大小 的二层表，随机选二层 hash function ，把分到这个 bucket 的 个元素插进去；若出现任何碰撞，就重新随机选 、整个 bucket 重插（rehash），直到无碰撞为止。

由 a)，每次尝试成功（零碰撞）的概率 ，所以对每个固定的 bucket，重试次数服从参数 的几何分布——期望重试 次（官方：constant number of rehashings in expectation, and with high probability）。

【展开】初始化的总期望时间是 量级（每轮 rehash 的代价正比于 bucket 大小，期望常数轮），由 d) 的结论它也是期望 。

c) Lookup 的时间复杂度

查询 ：

  1. 算第一层 ，定位 bucket —— ；
  2. 算二层 ，直接看二层表的那一个格子，比较 —— 。

官方答案就一句：，因为上一步已经保证了零碰撞。 注意这比期望界更强：初始化阶段已经把每个二层表都重抽到 collision-free 才收工，所以 lookup 是确定性的 worst-case ——两次 hash 求值加一次比较，不需要任何「期望」修饰。这正是 perfect hashing 中 perfect 的含义。

d) 总空间为什么是期望 ？——本题的灵魂

总空间的主项是所有二层表之和 ，所以要证

期望对第一层 取。官方给了完整的推导链，逐步看：

第 1 步（把 写成 indicator 和）：第一层 把每个元素 送进 bucket ，所以

（ 取遍 个存储元素）。

第 2 步（展开平方）：

把双重和拆成对角项（）与交叉项（）：

第 3 步（认清两种期望各是什么）：

  • 对角项：indicator 的平方还是自己，；
  • 交叉项：两个 indicator 的乘积为 1 当且仅当两个事件同时发生，。

第 4 步（交换求和顺序，先对 求和）：

  • 对角部分：（ 总落在恰好一个 bucket——全概率），所以对角部分合计 ；
  • 交叉部分：（「在同一个 bucket」按 bucket 编号分拆），所以交叉部分合计 。

第 5 步（universality 收尾）： 是有序对，共 个；每对由第一层的 universality 满足 ：

最后一步用 （例如 时上式 ）。

【展开】一句话的直觉： 数的是「落在同一 bucket 的有序元素对的个数」（含 的对角对）。对角对恰有 个；每个非对角对成立的概率 ——所以总期望 。第一层只要把元素大致摊开（），平方的总账就塌缩成线性。

加上第一层数组本身的 与各 hash functions 的存储，整个数据结构期望空间 ，lookup worst-case ——这正是 Part 2 Remark 36.1 宣称的 perfect hashing 保证。官方延伸阅读：Jeff Erickson《Algorithms》讲义 §5.7（jeffe.cs.illinois.edu）。

本题用到的知识点:

  1. 期望碰撞数 + Markov 表开 时常数概率零碰撞；失败重抽，几何分布期望常数轮。
  2. 「先证常数成功概率，再 rehash 放大」是随机化构造的通用模板。
  3. 同桶有序对计数：对角贡献 ，交叉对用 universality 各 。
  4. 两层结构的分工：第一层摊匀（线性空间），第二层局部平方（消灭碰撞）。

Problem 6: Bloom filter 的错误率与最优 （本周最重要的题）

Tutorial 难度/要求: Problem Solving；quite important，官方特别点名这题，务必尝试并读 solution。式 (52) 的推导、最优 、以及固定 时错误率 的衰减，都是核心考点。

题目: 分析课上 Bloom filter 的错误概率。我们关注 error rate：「平均而言」Lookup 多常出错。设已把含 个元素的数据集 插入 Bloom filter。做如下（错误、但方便的）truly random 假设： 在所有元素 与所有 hash functions 之间完全独立，且每个 在 上均匀分布：

    1. 固定 。插入 个元素后，数组 的第 位被置 1 的概率 是多少？令 （平均每个元素用的 bit 数）。用近似 （ 小时非常精确）证明 。
    1. Error rate：对一个没有插入过的 key 调用 Lookup(x)，返回 yes 的概率是多少？
    1. 假设目标是每元素 bits 的存储：应该用多少个 hash functions 来最小化错误概率？
    1. 在 、 取 c) 的值时，期望的错误率是多少？
    1. 固定 ，探索空间（参数 ）与错误率的 trade-off——我们可以决定用多于 8 bits/元素的空间。 增大到 12、16、32 bits 时，期望错误率各是多少？

题解:

a) 某一个 bit 被置 1 的概率

固定数组的第 位。对任何一个被插入的元素 和第 个 hash function， 均匀分布在 个位置上，所以这一次写入没打中第 位的概率是

个元素 个 hash functions 次写入，由完全独立性，第 位始终没被置 1 的概率是 ，于是

其中第二步用官方提示的近似 （取 ，则 ），第三步代入 ，即 。

注意 与 无关（对称），它就是「数组中 1 的密度」。 的直觉：总共 个 bit 摊给 个元素，每人 个 bit； 越大数组越满。

b) Error rate（false positive 概率）

查询一个未插入的 返回 yes，当且仅当它的 个探测位

全部为 1。 没被插入过，故（由 truly random 假设）它的探测位置与已写入的内容独立；由 a) 与独立性假设，把 个位置都为 1 的概率相乘：

这正是 Part 2 式 (52)（代 后的形式）。

c) 时的最优 ：把微积分做完

要最小化

官方说：要么画图目测，要么动微积分（也可以丢给 WolframAlpha）。微积分版本（官方给出了导数）：

【展开】求导过程：对 求导：

最后一步用 （分子分母同乘 ）。整理成官方的形式：

由于对所有 都有 ，所以 当且仅当括号内为零：

验证 是解：此时 ，：

（官方注：严格论证这是唯一解还需要更多 calculus，但并不有趣，略。）所以 在

处取最小； 必须取整数，故

一般地（把上面的 8 全部换成 重算一遍即可），官方给出通解：

【展开】一个更漂亮的免求导论证（顺便解释「半满」）：记 （即某 bit 仍为 0 的概率），则 ，且

最小化 等价于最大化 ——这个表达式在 交换下对称，在 处取最大。于是最优解满足

且此时数组中 1 的密度 ：最优参数恰好让 bit array 半满——每个 bit 携带最大信息量。代回得最优错误率

d) 的错误率

代入 b) 的公式：

即调用 Lookup 时的期望 false positive rate 约为

每个元素只花 1 byte，错误率就只有 量级——这就是 Bloom filter 实用性的来源。

e) 固定 、增大 ：错误率多项式下降

错误率作为 的函数：

官方数值（【展开】附计算过程）：

（bits/元素） 计算 错误率
8
12
16
32

下降得相当快。官方进一步问：到底多快？ 答案：固定 时，错误率按

多项式衰减。官方给了两种看法：

  1. log-log 图：若 ，则 ——以 为横轴、 为纵轴画图应是斜率 的直线。对上表数据画 log-log 图，确实近似一条斜率 的直线。
  2. Taylor 展开：当 时 ，用 （ 小）：

【展开】把 c) 和 e) 放在一起看的洞察：固定 时，加空间只能换来多项式下降 ；而如果让 随 一起按最优 增长，错误率是指数下降 。所以「加空间」要配合「加 hash functions」才能吃满收益——这就是式 (51) 与式 (52) 的 trade-off 在参数选择上的全部内容。

本题用到的知识点:

  1. 固定一个 bit → 次独立写入都没打中的概率 。
  2. false positive 「 个探测位全为 1」，独立近似下取 次幂，得式 (52)。
  3. 最优 hash 个数 ；最优点处数组恰好半满，错误率 。
  4. 固定 时错误率 多项式衰减（log-log 直线斜率 ；Taylor ）。
  5. 整个分析建立在「truly random 假设」上——官方明说它是 false but convenient（呼应 Part 2 §8 与 §13）。

Advanced

Problem 7: 给 Bloom filter 加上 Remove

Tutorial 难度/要求: Advanced；有时间值得做，但 not crucial。考点：删除为什么会破坏 Bloom filter 的 one-sided error guarantee。

题目: 扩展课上的 Bloom filter 数据结构，增加 Remove 操作。分析所得数据结构的 guarantee（性能、错误概率、空间与时间复杂度）。

题解:

先想清楚：为什么不能直接删？

普通 Bloom filter 里一个 bit 可能被多个元素共同点亮。若 Remove(x) 简单地把 清零，就可能误伤共享这些 bit 的其他元素——它们之后查询会得到 no，产生 false negative，one-sided guarantee（绝无 false negative）就此报废。所以删除必须换思路。

官方方案（solution sketch）：second Bloom filter 记录删除

再开一个 deletion Bloom filter （参数可以另选 ）：

  • Insert(x)：照旧写主 filter ；
  • Remove(x)：把 插入 （“记录一笔删除”）；
  • Lookup(x)：返回 yes 当且仅当 说 yes 且 说 no。

各项指标：

  • 时间：每个操作仍是 worst-case （常数个 hash 求值）；
  • 空间：，仍是「每元素常数 bit」量级；
  • 错误概率：主 filter 的 false positive 照旧（式 (52)，约 ）。但出现了第二种错误（官方原话强调）： 自己也是 Bloom filter，也有 false positive——它可能错误地声称某个从未被删除的元素被删除过。对主数据结构而言，这就是 false negative：元素明明还在集合里，Lookup 却返回 no。其概率 ，其中 删除次数。

【展开】这个方案的另外两个坑（思考题级别，官方未展开）：

  1. 重插入语义坏掉：若 被删除后又被 Insert 回来， 里关于 的记录抹不掉（Bloom filter 自己不支持删除——这正是我们想解决的问题，递归了），于是 永远被 拦截，false negative 变成永久的；
  2. 删除越多 越满： 的 false positive 率随删除次数增长，长期运行需要周期性重建整个结构。

所以这个方案适合「删除少、且元素不会回头」的场景。

更常用的替代方案：counting Bloom filter

官方在 sketch 末尾指向延伸讨论（cs.stackexchange 上 “Deleting in Bloom filters” 一问及其引文），其中的标准答案是 counting Bloom filter：把每个 bit 换成一个小计数器（典型 4 bits）：

  • Insert(x)： 个对应计数器各 ；
  • Remove(x)： 个对应计数器各 ；
  • Lookup(x)：当且仅当 个对应计数器全部 时返回 yes。

各项指标：

  • 时间：仍是 worst-case ；
  • 空间：每格从 1 bit 变成 bits，总空间乘常数 （典型 ）——仍是 bits 量级，但常数变差；
  • 错误概率：false positive 率与普通 Bloom filter 同公式（位置「非零」的分布和「为 1」一样）；只要（i）计数器不溢出、（ii）只对确实插入过的元素调用 Remove，就仍然没有 false negative。

【展开】counting 版的两个前提为什么重要：（i）计数器太窄会溢出——溢出后无法安全减到零，通常的工程处理是「饱和计数器」（卡在最大值不再增减），这会重新引入少量 false negative 风险（4-bit 计数器溢出概率极小，可以算出来是 常数 级别的小量）；（ii）若删除一个从未插入的元素（或被 false positive 误导而删除），会把别人共享的计数器减少，同样制造 false negative。所以 Remove 只能在「确认元素在集合中」时调用。

两个方案对比

普通 BF deletion-filter 方案（官方） counting BF
Remove 不支持 支持（记账式） 支持（真删除）
false positive 有，式 (52) 有（主 filter） 有，同公式
false negative 无 有（ 的 FP 所致，且重插入后永久化） 无（需计数器不溢出 + 只删在集元素）
空间 bits bits bits（）
操作时间

结论：删除功能不是免费的——要么引入 false negative（deletion filter），要么花常数倍空间并附带使用约束（counting filter）。「简单版 Bloom filter 不支持删除」（讲义脚注 35 说“可以做，但会增加不少复杂性”）说的正是这一整套权衡。

本题用到的知识点:

  1. Bloom filter 的 bit 是共享的，直接清零会误伤他人 不能裸删。
  2. 官方方案：用第二个 Bloom filter 记录删除；代价是引入新错误类型 false negative（来自 的 false positive）。
  3. counting Bloom filter：bit 计数器， 实现插删；保住 no-false-negative，但空间乘常数、且有溢出与「只删在集元素」的约束。
  4. 数据结构改造的通用教训：每个新操作都可能动摇原结构的 guarantee，必须重新过一遍错误类型分析。

Part 2: Week 6 讲义详解（Hashing and Friends）

本部分严格按照讲义《Lecture 6: Hashing and Friends》的行文顺序整理，所有 Fact / Definition / Lemma / Theorem / 公式编号都与讲义一致（Fact 30.1、Theorem 31–36、Definition 32.1、式 (50)(51)(52)……），方便对照原文复习。讲义之外、但对理解或考试有帮助的内容，会明确标注 【补充】。

0. 名词与符号速查

先把本周的术语和符号统一，后面正文里每个概念出现时还会详细解释。

名词 含义
ADT (abstract data type) 「数据的 API」：规定支持哪些操作，不管怎么实现
data structure ADT 的具体实现（算法层面的实现，不是代码层面）
dictionary 维护集合 并支持 Insert / Lookup / Remove 的 ADT，也叫 map、associative array
universe 所有可能元素的集合
bucket / cell hash table 数组 中的一个格子
collision 两个不同元素被 hash 到同一个 bucket：
hash family 一族 hash functions，初始化时从中随机选一个
(strongly) universal 对 hash family 随机性强弱的两种要求，见 §6、§7
load factor ，table 的「装载率」，式 (50)
separate chaining 碰撞处理方式一：每个 bucket 挂一条链表
open addressing 碰撞处理方式二：全部元素直接放数组里，碰撞就继续探测
probing open addressing 中按 依次试位置的过程
tombstone open addressing 删除元素后留下的「墓碑」标记
cuckoo hashing 每个元素只有两个候选位置的 hashing，查删 worst-case
perfect hashing 两层 hashing，完全无碰撞， 空间 + worst-case lookup
Bloom filter 近似 membership 数据结构，只会 false positive
false positive / negative 不在却说在 / 在却说不在
符号 含义
universe，所有可能的数据点
universe size
当前真正存储的元素集合
当前存储的元素个数，随 insert/remove 变化
hash 的目标集合（bucket 集合）
bucket 个数 / table size
hash function
hash family
长度 的数组（hash table 本体 / Bloom filter 的 bit array）
load factor，式 (50)
Bloom filter 的 hash function 个数
空格子、墓碑标记
模 prime 的有限域

记住一个不变的大背景：（universe 很大，数据集很小），我们绝对不想用正比于 的空间。

1. 开场：data structure、ADT、以及两个核心参数 和

前几周的重心是算法；这一周和下一周转向算法的老搭档：数据结构。当然，浓度不减——算法分析、concentration inequalities、前几章的全部数学工具都会继续用。

什么是 data structure？ 讲义的定义：一种存储并组织数据的方式，同时提供一组方法来高效地访问（通常还能更新）这些数据。这组方法就是数据的接口（interface），类比软件里的 API。你在先修课里见过的说法是 ADT（abstract data type）：

  • ADT 规定「数据的 API」：支持哪些操作、操作的语义是什么；
  • data structure 是这个 API 的一个具体实现。

讲义脚注特别强调：这里说的「实现」是算法层面的实现（用什么结构、操作怎么做、复杂度多少），不是写代码——定义并分析完数据结构之后，总还是得找时间把它写成代码的。

我们关心什么？ 两件事：

  1. 时间效率：每个操作要多快；
  2. 空间（内存）效率：整个结构占多少空间。

空间这一点讲义用了一个夸张但精准的例子：如果当前只存了 5 个 -bit strings，我们当然不愿意用 bits 的内存——尽管 正是这些数据所来自的「universe」的大小（一共有 个不同的 -bit string）。

两个核心参数。 为了量化，引入贯穿全章的记号：

  • 我们存 个元素（数据点），每个元素来自一个 universe（所有可能数据点的集合），大小为 ；
  • 会随着插入、删除增大或减小；
  • 通常 ：universe 巨大，数据集很小。

讲义自测题（图片例子）。 要存 10,000 张高清图片，每张 12.5MP（分辨率 ），每像素 8 bits。 和 各是多少？讲义给了三个选项：

选项 对不对？ 这是什么数
✗ 是一张图的像素数
✗ 是一张图的 bit 数，也就是
✓ universe = 所有可能的图片，每张图是一个 -bit string

正确答案是第三个：

讲义边注：把 算成「所有可能的 bit 组合」其实是很粗糙的上界（不是所有像素组合都是合法图片），但作为第一近似足够了。结论也因此更有冲击力：空间正比于 的方案完全没戏。

2. Dictionary ADT 与三种朴素实现

最基本、最重要的 ADT 之一就是 dictionary（讲义边注：也叫 map 或 associative array）。它维护一个集合 ，只要求三个操作：

操作 语义
Insert(x) 把 插入 （若已在 中则什么都不做）
Lookup(x) 返回是否
Remove(x) 把 从 中删除（若不在 中则什么都不做）

注意语义细节：Insert 和 Remove 都要求「重复操作无副作用」，这意味着实现时往往隐含一次查找。

三种你肯定见过的实现（讲义边注：想想每个界是怎么来的，还能想出别的实现吗？）：

实现 空间 Insert / Lookup / Remove（worst-case）
linked list
array（直接寻址）
自平衡 BST（如 AVL）

逐个解释这些界：

  1. Linked list：每个节点存一个元素。写下一个 universe 中的元素需要 bits（区分 个可能性），所以 个节点共 bits。三个操作都可能要把整条链扫一遍（Insert 也要先查重），所以 worst-case 。空间很好，时间太差。
  2. Array：开一个以 universe 元素为下标、长度 的标记数组， 记录 是否在 中。三个操作都是一次直接寻址，worst-case 。时间完美，空间 灾难（回想 ）。
  3. 自平衡 BST（AVL 等）： 个节点每个 bits，空间 ；树高 ，三个操作 worst-case 。两头都不错，但时间不是 。

【补充】「别的实现」比如 sorted array（Lookup 二分 ，但 Insert/Remove 要挪元素 ）、skip list（期望 ）等，都没有突破上面的格局。

本章的目标问题：能不能同时做到

Quiz 知识点：原题问 "设计良好的哈希表支持查找、插入、删除的时间复杂度均为_"，答案是 Expected constant time。哈希表的 guarantee 是期望 O(1)（不是 worst-case）。另原题问 "相比基于数组的字典实现，哈希表更_"，答案是 more space-efficient（更省空间）。

空间且三个操作

讲义的回答是：Not quite, but almost（不完全行，但几乎行）。主角登场：hash table——在高层意义上，它就是用随机化把 array 方案改造得空间高效。

3. Hash table 的基本想法：把大 universe 压进小数组

Hash table 的出发点一句话：

“The universe is a big place, but it's mostly empty.” universe 很大，但绝大部分位置是空的。

如果能找到一个映射，把 universe 映到一个小得多的集合 ，并且任何 个不同元素的子集 都被映成 中仍然两两不同的 个值 ，那就赢了：对 套用 array 方案，空间只要正比于

理想情况下甚至取 。

Sanity check（讲义自问）：能指望 吗？不能—— 个两两不同的元素要映成 个两两不同的值，目标集合至少要有 个值可用。所以 是底线， 已是最优期望。

4. 坏消息：Fact 30.1（鸽笼原理），确定性 hashing 必然失败

不幸的是，上面「任何 个元素都不碰撞」的美好计划不可能由一个固定映射实现：无论选哪个映射，总存在一批元素被映到很少的点上。

Fact 30.1（Pigeonhole Principle）：固定任意两个集合 ，。那么对任意映射 ，存在一个子集 ，

使得 中所有元素都被 映到 中同一个值。

证明（一行鸽笼）： 把 个元素分进 个「原像类」。若每类都少于 个元素，总数就少于 ，矛盾。所以最大的类至少有 个元素，取它为 。

怎么读这个 Fact——两个关键点：

  1. 坏集合 依赖于 。 它不是说某批数据天生有毒，而是说：你先固定 ，对手（或者倒霉的现实）就能针对这个 挑出一组全部碰撞的 key。
  2. 因此，确定性地做从大 universe 到小集合 的映射（“hashing”），一定存在让策略灾难性失败的 worst-case 数据集。

那如果我们随机地做呢？这就是下一节。

5. 引入随机性的三种方案

讲义列出三个候选方案，这一段是全章的方法论地基，值得逐条吃透。

方案一：假设数据是随机的（random data）。 也许我们的 个元素不是 worst-case，而是「典型」的，可以建模成从 中均匀随机抽取。这时 Fact 30.1 的对手论证失效，我们可以放心用一个固定的确定性 ，并在「数据的随机性」上取平均得到不错的保证。

  • 问题：这个假设很不现实。真实数据有结构、有偏、甚至可能被对手操控。在这种假设下证出来的东西，更像「解释实践中为什么可能没事」的 heuristic，而不是严格保证。
  • 讲义的评价很克制：better than no guarantees at all（聊胜于无）。

方案二：hash function 完全随机（totally random hash）。 假设 是真随机函数：所有 相互独立、在 上均匀分布。那分析就太舒服了——我们学过的所有随机变量工具（碰撞概率、每个 bucket 的期望元素数、最大负载……）都能直接上。

  • 致命问题：存不下。把一个真随机函数存下来，相当于对每个 记录 ，需要

——比 array 方案还糟糕！ - 一个看似聪明的补救：lazy 生成——第一次需要 时才现场随机生成，只存用过的值，空间降到 bits。但「只存用过的值」意味着每次都要先查询 的 hash 值是否已经定过……这本身就是一个 dictionary——这恰恰是我们要解决的问题！循环依赖，方案破产。

方案三：hash function「有点随机」（somewhat random）。 单个确定性函数不行（碰撞被针对），完全随机函数也不行（空间爆炸），那就折中：从一个小得多的函数族

中均匀随机选一个 。存这个 只需要

（记录「选了族里第几个」）。剩下的任务就是设计 ，让它同时满足：

  • 够小： 小，空间高效；
  • 够随机：从中随机选 ，行为上接近真随机函数。

三方案对比：

方案 随机性来源 优点 致命伤
1. random data 数据本身 可用固定 假设不现实，只有 heuristic 保证
2. truly random 函数全随机 分析最舒服 存储要 bits
3. random 随机选族中一员 只存 bits 需要证明族「够随机」

幸运的是，方案三可行：这样的 hash families 存在，而且我们在 Chapter 4（Week 4）已经见过它们的雏形。整个课程接下来默认采用方案三：数据可以是 worst-case 的，随机性全部来自数据结构初始化时对 的随机选择。

6. Strongly universal hash family：pairwise independence

先回顾最强的那种「够随机」。

Definition 22.1（回顾，strongly universal hash family）：函数族 是 strongly universal 的，如果对任意一对不同的 ，当 从 中均匀随机选出时，二元组 的分布恰好等于两个独立、均匀分布于 的随机变量。等价地，对所有 ：

这正是 pairwise independence（两两独立）：任取两个不同输入，输出表现得像两个独立均匀随机值。两个直接推论：

  1. 边缘均匀：对每个固定 ， 在 上均匀分布（把上式对 求和即得 ）；
  2. 两两独立： 与 独立。但注意：三个及以上的 hash 值不保证独立——这是它和真随机函数的本质差距。

Fact 22.2（回顾， 的构造）：当 时，存在大小仅为

的 strongly universal family——也就是说存一个 只要 个随机 bits。这就是 Week 4 的 XOR/子集奇偶构造（Tutorial 4 Problem 5 证过：把 看成非零 -bit 串，）。

一般的 怎么办？讲义给出多项式（仿射）构造：

Theorem 31：固定 prime 和整数 。对每个系数向量 ，定义 ：

并令 。那么 是 strongly universal hash family，大小

也就是说，存一个 只需要存 个 系数，约 bits。讲义脚注：自己试着证！ 和 Tutorial 4 的一道练习很像。

【补充】证明梗概：固定 ，它们必在某坐标 上不同（）。把 之外的系数全部条件住，记常数 与 类似。则

把它看成 的映射，其系数矩阵 在域 中行列式为 ，可逆，所以这是 到 的双射。 均匀 均匀，每个取值对概率恰 。

怎么把 Theorem 31 用到一般的 universe （大小 ）和目标 table size 上？ 讲义给了标准流程：

  1. 由 Bertrand's postulate：对每个 ，存在 prime 满足 。取这样的 ，则 的大小是 ；
  2. 取最小的整数 使 ，把每个 编码成向量 ；
  3. 得到从 到大小 的 的 strongly universal family，族大小

即存储 bits。讲义自嘲：a little cumbersome, but it works（有点绕，但能用）。

小岔路：比 pairwise 更强的目标——-wise independence。 还可以要求更强的性质：对任意 个两两不同的 ，其 hash 值 表现得像 个独立均匀随机值。这叫 -wise independent hash family。对 同样有大小 的构造。一般地：

Theorem 32：固定任意整数 。存在一个显式的 -wise independent hash family，从 bits 映到 bits：

即存一个 要 bits——独立性每升一阶，存储成本线性增长。构造与证明见 Vadhan《Pseudorandomness》Corollary 3.34（【补充】思想是有限域上的随机度数 多项式：）。想系统了解 hash families 的构造与理论保证，这本 monograph 是绝佳读物。

7. Universal hash family：更弱、但对 hash table 通常够用

Strongly universal 是个很……strong 的概念。但回头想想：对 hash table 来说，我们最终要的只是碰撞尽量少。那就只对碰撞提要求，得到更弱的定义：

Definition 32.1（universal hash family）：函数族 是 universal hash family，如果对每对 ，：

概率取在 从 中的均匀随机选择上。

为什么右边是 ？ 由 Chapter 3（Balls and Bins）：两个独立均匀的 值碰撞的概率恰好是 。所以这个定义在说：就碰撞而言，至少要做得和「每对 hash 值都像独立均匀随机变量」一样好。

为什么是 而不是 ？ 只要求不等式给设计 留了更多自由度——何乐而不为。讲义边注：tutorial 里会构造出对某些 pair 不等号严格成立的 universal family——这正是本文 Part 1 的 Problem 3（两个函数的小族，唯一一对不同输入永不碰撞，碰撞概率 ）。

这个定义真的更弱吗？ 是：

Lemma 32.1：每个 strongly universal hash family 都是 universal hash family；并且存在 universal 但不 strongly universal 的 hash family。（讲义：证明见 Tutorial 4。）

【补充】前半句的一行证明：若 strongly universal，则对 ，

注意 strongly universal 时碰撞概率恰好等于 。后半句的反例见 Week 4 Tutorial Problem 8（以及 Part 1 Problem 3 那种「碰撞概率严格小于 」的族：碰撞概率不等于 就不可能 strongly universal）。

接下来是本章最重要的构造之一：一个又小又好算的 universal family。固定 prime 满足 （Bertrand 保证存在；注意这里 跟着 universe 大小 走，和 Theorem 31 里 跟着 走不同——因为这次域 要装下整个 universe）：

Theorem 33：固定 prime 。对整数 （，），定义 ：

并令 。那么 是 universal hash family，大小

即存一个 只要存 两个数，约 bits；求值只要一次乘法、一次加法、两次取模。

Theorem 33 的完整证明（按讲义，分五步，每步都值得搞懂）：

第 0 步（族大小）： 的选择有 种（ 有 种， 有 种），所以 。

第 1 步（mod 阶段绝不碰撞）：设 ，。因为 是 prime， 是域，非零元都可逆； 且 都可逆，于是

结论：碰撞只可能发生在第二次取模（）时。

第 2 步（中间值对的分布）：记 ，。对任意给定的目标对 ，线性方程组（在域 中）

当 时有唯一解

且此解自动满足 （因为 ）；当 时无解（第 1 步已排除）。因此，对独立均匀随机的 ：

换句话说： 在所有 个「不同值对」上均匀分布。

第 3 步（什么样的 才造成最终碰撞）： 当且仅当中间值 且

第 4 步（数一数这样的坏对）： 有 种选择。固定 后，与它同余 mod 的其他 形如

在内

个数至多 。又因为 是 prime（），

第 5 步（合并）：

坏对个数（）乘每对的概率（），恰好凑出 。

这节的结论：又小、又好算的 universal（需要时还有 strongly universal）hash family 确实存在。所以从现在起，除非特别说明，默认采用方案三（somewhat random hash functions）。

8. 方法论：证明该在哪个随机模型下进行？

这是讲义里一段非常重要的「游戏规则」说明，直接决定考试里哪些工具能用：

The name of the game：先假装自己处在方案二（truly random hash，分析最方便）里，把想要的命题证出来；然后回头检查证明，确认其中用到的随机性其实只需要方案三（universal / strongly universal family）就能提供。

实践中这意味着：

工具 能不能用 原因
indicator variables + linearity of expectation ✓ 只涉及一对元素的碰撞概率
Markov inequality ✓ 只需要期望
variance / Chebyshev ✓ pairwise independence 就够算方差
Chernoff / Hoeffding ✗ 本课版本要求完全独立，universal family 给不了

讲义脚注：存在使用 limited independence 的 Chernoff-type bounds，但超出本课范围。

这也解释了 Tutorial 里所有 hashing 题的画风：永远是「定义 indicator → 期望线性性 → pairwise collision bound → Markov/Chebyshev」，从不出现 Chernoff。如果你的证明只用了「任意一对元素碰撞概率 」，那 universal hashing 就足够支撑它。

9. Hash table 的三件套，以及「碰撞不可避免」（Fact 33.1 / 33.2）

铺垫完毕，正式定义。一个 hash table 由三样东西组成：

  1. 一个 hash function ，其中 远小于 ，通常 。 在数据结构初始化时从一个「好的」hash family 中随机抽出，之后所有操作都用这同一个 ；
  2. 一个大小为 的数组 ， 处记录元素 是否在数据结构中；
  3. 一个碰撞处理策略：当两个不同的 因为 落进 的同一个 bucket（cell）时怎么办。

你可能会问：搞了半天随机 hash family，不就是为了让碰撞概率小吗？怎么还要专门处理碰撞？

残酷的事实是：碰撞不可避免，无论 hash function 设计得多好。 而且我们早就见过原因——birthday paradox。讲义给出两个 Fact（都来自 Chapter 3 的 balls and bins）：

Fact 33.1（birthday paradox 版）：设 的大小 （ 为绝对常数）。那么，即使 hash function 是真随机的，甚至即使 个数据点本身是独立均匀随机的，仍有至少 99% 的概率：数据结构中至少有两个元素被 hash 进 的同一个 bucket。

【补充】为什么： 个元素有 对，每对碰撞概率 ；无碰撞概率约

当 时这个量是 ，取合适的 就能把碰撞概率压到 以上。直观说：想靠「表开得大」避免碰撞，表得开到 才行——空间又回到不可接受。

而我们想要的 还要更糟：

Fact 33.2（最大负载）：设 的大小 （ 为绝对常数）。那么，即使 真随机、数据独立均匀随机， 中所有 bucket 的期望最大负载也是

也就是说，我们应当预期至少有一个 bucket 攒下这么多碰撞元素。

讲义边注（剧透）：对这一条，我们至少有一个解决思路——the power of two choices 也许能帮忙？往后看，这正是 Cuckoo hashing 的想法。

结论：第 1、2 件套只决定「元素去哪」；真正决定 hash table 品质的是第 3 件套——碰撞处理策略。处理策略分两大家族：separate chaining 和 open addressing。

10. 碰撞处理 I：Separate chaining（拉链法）

最自然的策略：每个 bucket 发一条链表。 若多个数据点被 hash 到 的同一个 bucket，就都挂进这个 bucket 的 linked list： 指向一条链表，存所有满足 的已插入元素 。三个操作全部委托给对应 bucket 的链表：

Insert(x):  A[h(x)].Insert(x)
Lookup(x):  return A[h(x)].Lookup(x)
Remove(x):  A[h(x)].Remove(x)

所以 chaining 是「array 方案 + linked list 方案」的组合，试图取两家之长：hash 把全局问题切成 个小问题，每个小问题用链表硬扛。

Load factor。 定义

为 hash table 的 load factor。当 时它是一个（小）常数。讲义边注：chaining 允许 （一个 bucket 可以挂任意多元素）；下一节的 open addressing 则必须 。

空间：

三项分别是：存 hash function（ bits，见 Theorem 31/33）、数组 本身（ 个表头）、所有链表节点（ 个元素，每个要写下来就得 bits）。和 linked list / BST 方案同级，空间合格。

期望时间：三个操作的开销 = 算一次 + 扫一遍 bucket 的链表，所以关键量是链表长度。固定要操作的 ，对每个已存入的 定义 indicator 。由 universal hashing（注意：这里只需要 universal，不需要 strongly universal）：

于是由 linearity of expectation，bucket 中「别人」的期望个数

所以三个操作的期望时间都是 —— 正是「任意一条给定链表的期望长度」。 时这就是期望 。这正是 Part 1 Problem 2 的内容（那里有更细的逐步推导）。

但是（回想 Fact 33.2 的最大负载论证）：大概率会有某些 bucket 的链表长到

对落在这些 bucket 上的操作，性能退化到和 BST 方案一个量级（讲义边注原话）。这就是 chaining 的天花板：平均（期望）很好，个别 bucket 很差，worst-case 是 （所有元素挤同一桶）。

Chaining 小结：

维度 表现
空间
三操作期望时间 ，只需 universal hashing
worst-case ；且大概率有桶长
实现 简单；Remove 天然支持；允许

11. 碰撞处理 II：Open addressing（开放寻址）

另一大家族是 open addressing，本身又有若干变体。基本想法很简单：不用链表，所有元素直接放进数组 ；不用一个 hash function，而用一串

插入 时先看 bucket ：被占了（collision!）就看 ；又被占就看 ……直到找到空 bucket 为止。这个「依次试位置」的过程叫 probing。

讲义脚注：如果一个空 bucket 都找不到，说明表满了（），必须扩大 并 resize——这是昂贵操作，因为所有元素都要重新 hash。

三个操作的完整伪代码（ 表示空格子， 是特殊标记，马上解释）：

Insert(x):
  for t = 1, 2, ..., m':
    if A[h_t(x)] = x:                  # 已经在表里
      return
    elif A[h_t(x)] = ∅ or A[h_t(x)] = ⊥:
      A[h_t(x)] ← x                    # 放进第一个可用位置
      return

Lookup(x):
  for t = 1, 2, ..., m':
    if A[h_t(x)] = x:
      return yes
    elif A[h_t(x)] = ∅:
      return no    # 若 x 在表中，早该在 ∅ 之前被找到了

Remove(x):
  for t = 1, 2, ..., m':
    if A[h_t(x)] = x:
      A[h_t(x)] ← ⊥   # 特殊标记：这里以前有过元素
      return
    elif A[h_t(x)] = ∅:
      return       # 若 x 在表中，早该在 ∅ 之前被找到了

三条关键的实现逻辑：

  1. Lookup 为什么见到 就能停？ 不变式： 当初插入时走的是同一条探测序列 ，并且放在了第一个可用位置。所以如果沿途撞见一个从未被占用过的空格 ，说明 根本没插进来过——可以放心返回 no。
  2. Remove 为什么不能直接清空成 ，而要写 ？ 假设 存在 ，而另一个元素 当年因为一路碰撞被放在了 ，且 恰好等于 （在 的探测路径上）。如果删除 时把这个格子设回 ，之后 Lookup(z) 走到这里就会提前停止、错误返回 no——我们「截断」了 的搜索路径。（tombstone，墓碑）的语义正是：这里曾经有过元素：lookup 不许在此停下；insert 可以复用这个位置。
  3. probing 序列要满足什么？ 两个愿望：
    • 覆盖所有 bucket：对每个 ， 应当是 的一个排列——保证持续碰撞时最终能探索每个位置；
    • 存得下、算得快：之前为了把一个 hash function 压到 bits 费了九牛二虎之力；现在有 个函数，绝不能让空间膨胀 倍（ 时那就是 ，全完了）。所以实际方案都从一两个 hash function 出发「制造」整条序列（见下面 linear/quadratic/double）。

Theorem 34：理想化分析（uniform permutation probing）

先在一个非常理想化（且不现实）的假设下算一算 open addressing 能有多快：

Theorem 34：假设 probing 序列满足：对每个 ，随机序列 是 的均匀随机排列。则对每个 ，Lookup 的期望时间为

其中 是式 (50) 的 load factor。

完整证明：固定 。因为要的是期望时间的上界，只需考虑 不在表中的情形（unsuccessful lookup）——若 在表中，搜索只会更早结束（找到 就停）。此时运行时间 = 探到第一个空 bucket 为止的步数。

由对称性，任何一个给定 bucket 为空的概率是 。令 为在大小 、已占 个位置的表中做一次 unsuccessful lookup 的步数。

  • 第一次探测命中空 bucket（概率 ）：1 步结束；
  • 否则（概率 ）：继续在剩下的 个 bucket（其中 个被占）里找。关键观察：条件在第一步失败上，剩余序列 仍是剩余 个 bucket 的均匀随机排列——问题自相似。

于是有递推：

对 归纳证明 ：

  • 基例 ： ✓；
  • 归纳步：

中间的不等号用了 。

怎么读这个结果： 时期望约 2 步； 时约 10 步； 时爆炸。open addressing 对 load factor 极其敏感，表必须留出富余空间。Insert（找第一个可用位）的开销本质上同阶；successful lookup 只会更快。

常见的 probing 策略

(a) Linear probing（线性探测）

干脆别要那么多不同的 hash functions 了！只用一个 ，每步看下一个 bucket：

优点：空间上只存一个 hash function；求值飞快（ 快它就快）；【补充】顺序访问内存，cache 极友好——这是它实践中流行的真正原因。

那性能呢？依然由 load factor 决定，但比 Theorem 34 差得多：

Theorem 35（Knuth '62）：简化假设 是真随机函数，且每个 bucket 的负载相互独立。则 linear probing 下 Insert、Lookup、Remove 的期望时间均为

讲义脚注：这个上界对 unsuccessful lookup（查一个不在表里的元素）是紧的。

这相当令人意外（而且是坏消息）：对比 Theorem 34 的理想分析，平方级退化—— 时从约 10 步恶化到约 100 步。讲义给的直觉是 clustering（聚簇）：linear probing 会让表里形成一段段连续被占的「runs」；查一个不存在的元素时，一旦落进某条 run，就要一路走到 run 的尽头才能遇到空格而终止。【补充】更糟的是 runs 有「富者愈富」效应：新元素落进一条长 run 的任何位置都会把它加长（概率正比于 run 长度），相邻 runs 还会合并，于是长 run 越来越长——这就是性能被拖垮的机制。

(b) Quadratic probing（二次探测）

同样的思路，但步长按二次式增长：

其中常数 （）选取得多少有些随意——但必须保证探测序列仍是 的排列。它的目标是比 linear probing 产生更少的 clustering，同时保留「只存一个 hash function」的优点。

(c) Double hashing（双重哈希）

用两个 hash functions ，第二个决定步长：

【补充】好处：两个在 处相撞的元素，几乎不会有相同的 值，于是后续路径立刻分叉——比「所有人撞了都往右挪一格」的 linear probing 更接近理想的随机 probing。代价是要存、要算两个 hash functions。

(d) Cuckoo hashing（布谷鸟哈希，Pagh & Rodler 2001/2004）

讲义称它 really neat：它跳出「期望时间」的框架，对 3 个操作中的 2 个给出 worst-case 保证。它建立在前面课程见过的漂亮想法上——the power of two choices。

结构：两张表、两个 hash functions： 与 。铁律：元素 只可能出现在两个位置之一——

或

于是查找、删除只需检查这两个格子：

Lookup(x):
  if A1[h1(x)] = x or A2[h2(x)] = x:  return yes
  else:                               return no

Remove(x):
  if   A1[h1(x)] = x:  A1[h1(x)] ← ∅
  elif A2[h2(x)] = x:  A2[h2(x)] ← ∅

插入则复杂一些。若 或 有空位，直接放入，结束。若两个位置都被占（比如被 和 占着），就发生 eviction（驱逐）——这正是名字里 cuckoo 的来历：布谷鸟会把别人的蛋挤出巢。 鸠占鹊巢，抢走 ；被踢出的 只能搬去它自己的另一个位置 ；若那里也有人，就再把那个元素踢去它的另一个位置……如此往复，直到链条终止，或达到驱逐次数上限：

Insert(x):
  if A1[h1(x)] = ∅:   A1[h1(x)] ← x;  return
  elif A2[h2(x)] = ∅: A2[h2(x)] ← x;  return
  else:
    T ← 0                       # 驱逐开始
    x' ← A1[h1(x)];  A1[h1(x)] ← x
    while T < Tmax:
      x' 搬去 A2[h2(x')]；若那里有元素，则该元素被踢出，
      轮到它搬去自己在另一张表中的位置……（两表交替）
      T ← T + 1
    # 若达到 Tmax 仍未安顿（链条过长或成环）：换新的 h1,h2 整表 rehash

Theorem 36：Cuckoo hashing 的 Lookup 和 Remove 为 worst-case ，Insert 为期望 。

Lookup/Remove 的保证是显然的（最多看两个格子）。Insert 的期望保证证明则相当复杂，讲义不证（tutorial 中讨论部分内容）；证明的核心是证驱逐链「typically short」：长链条/成环的概率随长度衰减到可忽略。【补充】经典分析还要求表不能太满（每张表大小 ，即总 load factor 低于 ），否则成环概率不再可控、rehash 频繁。

Remark 36.1：还有更多策略！

除了以上这些，还有诸如 2-level hashing（给每个 bucket 再配一个 second-level hash table）的策略。其中的代表作是 perfect hashing：彻底避免碰撞，只用 空间，同时 Lookup 是 worst-case 。讲义边注：perfect hashing 在 tutorial 中详细展开——也就是本文 Part 1 的 Problem 5：

  • 第一层把 个元素散进 个 bucket；
  • 第 个 bucket（装了 个元素）配一个大小 的二层表，反复重抽二层 hash function 直到该 bucket 内零碰撞（生日悖论反着用：表开到平方大，期望碰撞数 ，由 Markov 每次成功概率 ）；
  • 总空间的关键恒等式： 数的是「同桶 ordered pairs」，由 universality，。

完整推导见 Part 1 Problem 5。

12. Bloom filters

定位：上面看到，hash table 能（在期望意义或「典型数据」意义上）极快地存取数据，并且永远不出错——答案总是正确的，随机性只体现在时间上。但 hash table 终究要存元素本身：每个元素 要 bits（），存 个元素就是

这已经很省了，通常完全够用——但有时还是太多（想想 bits 一张的图片；或者路由器里要按每个 packet 查询的黑名单）。

Bloom filter 用大幅更少的空间提供高效的插入和查询：只要

——与元素本身要多少 bits 编码完全无关！代价是：查询结果偶尔会错。但只要设计得当，出错频率很低、而且可控。这是一笔「空间 换 正确性」的交易：从 exact dictionary 退到 approximate membership。

结构与操作。 简单版本只支持 Insert 和 Lookup，没有 Remove（讲义脚注：删除可以做，但会让数据结构复杂不少——见 Part 1 Problem 7 的 counting Bloom filter）。Bloom filter 由两部分组成：

  • 一个大小 的数组 （ 个 bit，初始全 0）；
  • 个不同的 hash functions ，每个都把 universe 映到格子下标：

其中 和 都是待选参数。操作如下：

Insert(x):                 # 把 x 的 T 个位置全部点亮
  for i = 1, ..., T:
    A[h_i(x)] ← 1

Lookup(x):                 # T 个位置全是 1 才说 yes
  for i = 1, ..., T:
    if A[h_i(x)] = 0:
      return no
  return yes

就这么多！注意它不存元素本身，只存「指纹位」。剩下的问题：它到底做对了什么、错误率怎么分析、参数 （hash function 个数）怎么选。

Lookup 会犯哪种错？ Bloom filter 只可能犯一种错误：

错误类型 含义 会发生吗
false positive 元素不在结构中，却返回 yes 可能
false negative 元素在结构中，却返回 no 绝不
  • 绝无 false negative： 插入时它的 个 bit 已全部置 1；简单版没有删除，bit 一旦为 1 永不回 0；所以之后查 必然全 1、必然 yes。插入过的元素永远被报告为 present。
  • 可能 false positive：一个没插入过的元素 ，它的 个位置可能恰好被其他若干元素（每人贡献几个 bit）合力点亮了——Bloom filter 无法分辨这些 1 是谁写的。

讲义的具体例子（，，）。三个 hash functions 的取值表：
1 1 5 10
2 9 4 6
3 1 6 3
4 7 3 8

插入 ，被置 1 的位置（下标从 1 开始）：

现在调用 Lookup(3)：要检查 。而 被元素 1 点亮、 被元素 2 点亮、 被元素 4 点亮——三个全是 1，于是返回 yes，尽管 3 从未被插入。这就是一次活生生的 false positive。

【补充】观察这个例子还能看出参数失衡的后果：插入 3 个元素共写了 次 bit， 个 bit 里 9 个是 1（只有 还是 0）——数组几乎全亮，此时几乎查谁都说 yes。这预示了下面的分析： 必须和 匹配，数组太「满」错误率就会失控。

空间复杂度（式 (51)）。 假设每个 hash function 占 bits、求值 （§6–7 的构造正是如此），Bloom filter 的空间是

—— 个 hash functions 加上 个 bit 的数组。Insert 和 Lookup 的 worst-case 时间都是

注意和 hash table 的对照： vs 。取 、，Bloom filter 就是 bits + 每操作 ，把「每元素 bits」这一项彻底抹掉了。

错误概率（式 (52)）。 在一个理想化（讲义原话：that is: wrong，即明知不对的简化）假设下分析——假设 个 hash functions 表现得像相互独立的真随机函数。设已插入 个元素，查询一个未插入的元素，Lookup 出错（false positive）的概率为

【补充】逐步推导（这是 Part 1 Problem 6 的核心，考试必会）：

  1. 固定数组中的某一个 bit。 插入 个元素共做 次「随机写 1」，每次写到的位置均匀随机，不打中这个 bit 的概率是 ；
  2. 各次写入独立（理想化假设），所以这个 bit 始终是 0 的概率：

（用 ）；于是这个 bit 是 1 的概率约 ；

  1. 查询未插入的 ：当且仅当它的 个探测位全为 1 时出错。把这 个位置的状态近似当作独立，得式 (52)。

（这里其实悄悄用了两层近似： 个探测位置可能重合、各 bit 的状态并非严格独立——但讲义本来就声明了整个假设是理想化的，作为工程估算非常准。）

参数怎么选？ 式 (51)（空间）和式 (52)（错误率）给出了 trade-off 的两端：固定 和目标空间 ，就可以求最优的 来最小化错误概率。

【补充·与 Part 1 Problem 6 衔接】记 bits per element

则式 (52) 变成 。对 求最优（对 求导）得

此时错误率

两个值得记住的直觉：

  • 最优点恰好让数组半满： 时每个 bit 为 1 的概率 ——信息论上也最讲道理（每个 bit 携带最大熵）；
  • 的 trade-off： 太小，每次查询只验少数几位，太容易被「碰巧全亮」糊弄； 太大，每次插入点亮太多位，数组迅速趋于全 1。最优在两者之间。

数值感受（，即每元素 8 bits）：，取 ，错误率 。每元素仅 1 byte 就能把错误压到 ——这就是 Bloom filter 在实践中无处不在的原因（缓存、路由器、数据库、拼写检查……）。更多数值与推导见 Part 1 Problem 6。

和 hash table 的全面对照：

hash table Bloom filter
存什么 元素本身 只有 bits（指纹）
空间 ，可做到 bits
Insert / Lookup 期望 worst-case
Remove 支持 简单版不支持（counting 变体支持，见 Part 1 P7）
错误 从不出错（随机性只在时间） false positive，概率可控；无 false negative

13. 结语：为什么这些东西在实践中表现得这么好？

本章我们把 hash families 和不平凡的数据结构组合起来，证明了严格的性能界。讲义感叹：这件事本身就足够美妙、甚至有点 mind-blowing——我们享受到了真随机函数的绝大部分好处（高效存取），却没有付它的天价（不可行的存储空间）！

但也要诚实：用小 hash family 证出来的理论保证，不如真随机函数下的理想保证强（比如 Chernoff 用不了、有些界只能到 pairwise 独立能撑住的程度）。

然而实践中的现象更神奇：这些用小 hash family 实现的数据结构，表现好于理论预测——和理想化的真随机世界里一样好！为什么？Mitzenmacher 和 Vadhan 给出的解释是：这种 too-good-to-be-true 的行为可能来自两股「半吊子随机性」的合流——

「数据本身有点随机（somewhat random-ish）」 + 「hash function 提供了有限的随机性」 组合起来几乎就是真随机行为。

换句话说：数据不是真随机的（我们也从不这样假设），hash function 的随机性也很有限（比如只有 2-universal），但只要数据流中每个新元素在已知历史的条件下仍含有足够的熵，两者结合就能逼近 ideal hashing。严格的形式化见 Mitzenmacher–Vadhan 的论文 Why simple hash functions work: exploiting the entropy in a data stream（SODA 2008）——也就是本周的 going-further 阅读材料《Week 6 - Going further》。

这给我们的提醒是：理论保证要分清「worst-case 数据」与「带熵数据」两种模型，两者能证出的结论强度不同；而工程实践恰好活在两者之间。

14. 讲义编号结果速查

编号 内容一句话
Fact 30.1 鸽笼：任何确定性 都有 个元素全碰撞，坏集合依赖
Definition 22.1（回顾） strongly universal：任意两个不同输入的 hash 值恰像两个独立均匀随机值
Fact 22.2（回顾） 时存在大小 的 strongly universal family（XOR 构造）
Theorem 31 ：strongly universal，，存储 bits
Theorem 32 -wise independent family（ bits bits）存在，
Definition 32.1 universal：（理想两独立均匀值的碰撞水平）
Lemma 32.1 strongly universal universal；反向不成立
Theorem 33 ：universal，，存储约 bits
Fact 33.1 时（即使真随机） 概率出现碰撞（birthday paradox）
Fact 33.2 时期望最大负载
式 (50) load factor
chaining 空间 ；三操作期望 ；有桶大
Theorem 34 理想随机排列 probing：unsuccessful lookup 期望 （递推 + 归纳）
Theorem 35（Knuth '62） linear probing 退化为 ，对 unsuccessful lookup 紧；元凶是 clustering
Theorem 36 cuckoo hashing：Lookup/Remove worst-case ，Insert 期望 （驱逐链典型很短）
Remark 36.1 2-level / perfect hashing：零碰撞、 空间、worst-case lookup（详见 Part 1 P5）
式 (51) Bloom filter 空间 ；操作 worst-case
式 (52) false positive ；【补充】最优 ，错误率

15. 一张总表：本章所有 dictionary 方案对比

方案 空间 Lookup Insert Remove 出错？
linked list 不出错
array（直接寻址） 不出错
自平衡 BST 不出错
chaining hash table 期望 期望 期望 不出错
open addressing 级 期望 （理想）/ （linear） 同左 同左（需 ） 不出错
cuckoo hashing 级 worst-case 期望 worst-case 不出错
perfect hashing（static） 期望 字 worst-case （静态，预处理建好） （静态） 不出错
Bloom filter bits 简单版不支持 false positive only

读表要点：从上到下是一条「不断花式用随机性换性能」的演化链——hash table 用随机性把时间做到期望 （结果永远正确）；cuckoo/perfect 把部分操作推到 worst-case ；Bloom filter 更进一步，连正确性也拿去交易，换回与元素编码长度无关的 bits 空间。

16. 做题套路（本章证明的固定打法）

  1. 看到 expected chain length / bucket size：对每个其他元素定义 indicator ，期望线性性 + universal 的 ，得 ；
  2. 看到 universal hashing：只能用 pairwise collision bound；要更强独立性必须明说 strongly universal / -wise；Chernoff/Hoeffding 禁用（除非题目给了完全独立）；
  3. 看到 「证明存在无碰撞的 hash function」：算期望碰撞数 ，压到 （或 ），用 Markov 翻成常数成功概率，失败就重抽；
  4. 看到 perfect hashing 空间：把 解释成同桶 ordered pairs，对角项给 ，非对角项每对 ；
  5. 看到 open addressing 期望步数：递推 ，归纳出 ；
  6. 看到 Bloom filter：固定一个 bit → 算它为 0 的概率 → 位全 1 → 式 (52)；要选 就令 ，记 、错误率 、数组半满；
  7. 看到 remove：open addressing 想到 （墓碑）；Bloom filter 想到 counting 变体（以及它引入的新风险）。

本周核心记忆

主题 关键结论
为什么要随机 hash Fact 30.1：确定性 必有坏集合；truly random 要 bits 存不下
方案三 从小族 随机选 ，只存 bits
Strongly universal ：pairwise independent uniform
Universal ；strongly universal，反之不然
两大构造 Thm 31：（strongly）；Thm 33：（universal）
分析工具红线 linearity / Markov / Chebyshev 可用；Chernoff / Hoeffding 需完全独立，禁用
碰撞不可避免 Fact 33.1（ 必撞）；Fact 33.2（ 时 max load ）
Chaining 期望 ，worst-case ；允许
Open addressing 理想 （Thm 34）；linear probing （Thm 35，clustering）；删除用
Cuckoo hashing 两位置任选其一；查删 worst-case ，插入期望 （Thm 36）
Perfect hashing 二层、二次方开桶；期望 空间 + worst-case lookup
Bloom filter 不存元素只存 bits；no false negative / 可能 false positive
Bloom 错误率 （式 52）；，最优 ，错误率
实践之谜 Mitzenmacher–Vadhan：数据的熵 + 简单 hash 的随机性 真随机行为

Part 3: Week 6 Quiz 回顾

来源：Canvas Quiz，整理自 5270-questions-organized.md。

Question 1

[EN] (Properly designed) hash tables allow for lookups, insertions, and deletions in a data structure, all in...

[CN] 设计良好的哈希表支持查找、插入、删除，时间复杂度均为

选项 答案
Worst-case constant time ❌
Expected constant time ✅

Question 2

[EN] Compared to the array-based solution to implement a dictionary, a hash table is...

[CN] 相比基于数组的字典实现，哈希表更

选项 答案
more space-efficient ✅
more randomness-efficient ❌
faster ❌

Question 3

[EN] To store a truly random hash function from a universe of size to a space of size , we would need ____ bits.

[CN] 存储一个从大小为 的全宇宙到大小为 的随机哈希函数，需要____比特。

选项 答案
✅
❌
❌
❌

知识点：真随机哈希需要为每个 存一个映射值，每个值 bits，共 bits。Universal hash family 只需 bits。

Question 4

[EN] By using a good family of hash functions, we can store elements in a hash table of space complexity without any hash collisions (with high probability).

[CN] 使用好的哈希函数族，可以在空间 的哈希表中存储 个元素而没有任何碰撞（whp）。

选项 答案
False ✅
True ❌

知识点：根据生日悖论， 个元素投入 个桶，期望碰撞数 ，碰撞几乎必然发生。

Question 5

[EN] By using a good family of hash functions, we can store elements in a hash table of space complexity without any hash collisions (with high probability).

[CN] 使用好的哈希函数族，可以在空间 的哈希表中存储 个元素而没有任何碰撞（whp）。

选项 答案
True ✅
False ❌

知识点： 个球投入 个箱，期望碰撞 ，无碰撞概率高。

Question 6

[EN] Assess the following two statements: By using linear probing to handle collisions in our hash table, we can achieve load factor greater than 1. By using separate chaining to handle collisions in our hash table, we can achieve load factor greater than 1.

[CN] 判断：线性探测可支持负载因子 > 1？分离链接法可支持负载因子 > 1？

选项 答案
False/False ❌
True/True ❌
True/False ❌
False/True ✅

知识点：线性探测需要空位，；分离链接法无此限制。

Question 7

[EN] When handling collisions with linear probing, insertions, lookups, and deletions have expected time complexity depending on the load factor as:

[CN] 线性探测处理碰撞时，插入、查找、删除的期望时间依赖于负载因子 为

选项 答案
✅
❌
❌
❌

Question 8

[EN] (Properly implemented) cuckoo hashing gives lookups in _____ constant time, deletions in _____ constant time, and insertions in _____ constant time.

[CN] Cuckoo 哈希的查找、删除、插入时间分别为

选项 答案
worst-case/worst-case/expected ✅
expected/worst-case/worst-case ❌
worst-case/expected/worst-case ❌
worst-case/worst-case/worst-case ❌

知识点：查删直接定位（worst O(1)），插入需 rehash 路径（期望 O(1)）。

Question 9

[EN] Bloom filters are _____ space-efficient than hash tables, but have a small probability of __________ error during lookups.

[CN] Bloom filters 比哈希表更_空间高效，但查找时有小的_错误概率。

选项 答案
less/false negative ❌
more/false negative ❌
less/false positive ❌
more/false positive ✅

Question 10

[EN] Bloom filters have both insertions and lookups in _____ (pick the most accurate answer)

[CN] Bloom filters 的插入和查找时间均为

选项 答案
Worst-case constant time ✅
Expected constant time ❌

Week 6 Quiz 速查表

题号 核心概念 正确答案
1 哈希表时间复杂度 Expected constant time
2 哈希表 vs 数组 more space-efficient
3 真随机哈希存储
4 O(n) 空间无碰撞 False
5 O(n²) 空间无碰撞 True
6 线性探测/分离链接负载因子 False/True
7 线性探测时间
8 Cuckoo 哈希时间 worst/worst/expected
9 Bloom filter 性质 more/false positive
10 Bloom filter 时间 Worst-case constant time

高频混淆点： - 哈希表是期望 O(1) 不是 worst-case（Q1） - Bloom filter 是 worst-case O(1)（Q10）——与哈希表相反 - O(n) 空间有碰撞，O(n²) 无碰撞（Q4 vs Q5） - Cuckoo 查删 worst O(1)，插入期望（Q8） - Bloom filter 只可能 false positive（Q9）