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

Posted on Edited on In , Word count in article: 4.6k Reading time ≈ 17 mins.

课程: 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 详细题解

Warm-up

Problem 1: Hash table 和 Bloom filter 的区别

题目: 从时间、空间复杂度和 guarantee 角度总结 hash table 与 Bloom filter 的关键区别。

题解:

二者都用 hashing，但目标不同。

Hash table

Hash table 是 dictionary data structure，用来维护集合 ，支持：

  • Insert(x);
  • Lookup(x);
  • Remove(x).

它真的存储元素本身，因此只要 collision handling 正确，查询结果不会错。随机性主要影响运行时间。

典型 separate chaining 的空间约为：

其中：

  • 是 universe size；
  • 是 bucket 数；
  • 是已存元素数。

若 ，load factor：

是常数，则 Insert/Lookup/Remove 期望时间都是：

但 worst-case 仍可能是 ，例如所有元素落入同一个 bucket。

Bloom filter

Bloom filter 不存储元素本身，只维护一个 bit array 和 个 hash functions。

插入 时，把：

置为 1。查询 时，若这些位置全为 1，则返回 yes，否则返回 no。

它的空间：

如果 是常数，且 ，则是 bits 级别，不需要为每个元素存 bits。

Bloom filter 的 guarantee：

  • 无 false negative：插入过的元素一定返回 yes；
  • 可能有 false positive：没插入过的元素也可能返回 yes；
  • 经典 simple version 不支持直接删除。

时间上，Insert 和 Lookup 都是 worst-case：

若 是常数，则是 。

本题用到的知识点:

  1. Hash table 存元素，Bloom filter 只存 membership bits。
  2. Bloom filter 牺牲正确性换空间，只会 false positive。
  3. Hash table 的随机性主要控制 expected time，Bloom filter 的随机性控制 error rate。

Problem 2: Separate chaining 的期望时间

题目: 证明 separate chaining 中 Insert, Lookup, Remove 的 expected time 都是 ，其中 。最坏情况是多少？

题解:

Separate chaining 中，每个 bucket 维护一个 list。操作 的成本取决于 bucket：

里已有多少元素。

假设在操作 前已经插入 。令：

表示与 collision 的已有元素数。

若 hash family 是 universal，则对任意 ：

用期望线性性：

每次操作还有常数级基本成本，所以：

Worst-case 中，所有元素都可能落入同一个 bucket，此时单次操作要扫描长度 的 list：

本题用到的知识点:

  1. Universal hashing 控制 pairwise collision probability。
  2. 指示变量 + 期望线性性。
  3. Separate chaining 的成本等于 bucket load。

Problem Solving

Problem 3: Universal hash family 中不一定取等号

题目: 给一个 universal hash family 的例子，使得对某些 ，

不是等号。

题解:

令：

定义两个 hash functions：

令：

对唯一一对不同输入 ，无论选 还是 ：

所以：

但：

于是：

这说明 universal hashing 的定义只要求 collision probability 不超过 ，不要求刚好等于。

本题用到的知识点:

  1. Universal hash family 是 inequality guarantee。
  2. Universal 比 strongly universal 弱。
  3. Collision probability 可以严格小于 。

Problem 4: 三数组 的 expected algorithm

题目: 给三个长度为 的正整数数组 ，判断是否存在 使：

要求 expected 。

题解:

a) 朴素算法

枚举所有 triples：

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

共有 个 triple，所以时间：

b) Hash table 算法

先把 的所有元素插入 hash table 。

然后枚举所有 ，查询：

是否在 中。

算法：

T = empty hash table
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) 正确性

如果存在 使：

那么 已经被插入 。枚举到 时，lookup 会成功，所以返回 true。

反过来，如果算法返回 true，则存在某个 pair 使 在 中。因为 只插入了 中元素，所以存在 ：

因此返回 true 是正确的。

d) 时间复杂度

插入 个元素，expected 。

枚举 个 pair，每次 expected lookup，总计：

Worst-case 取决于 collision handling：

  • chaining / linear probing：单次操作 worst-case ，总 worst-case 可到 ；
  • cuckoo hashing：lookup worst-case ，但 insertion worst-case 仍可能大。

本题用到的知识点:

  1. 用 hash table 把三重枚举降到二重枚举。
  2. Expected hash operation。
  3. Correctness 分 yes case 和 no case。
  4. Expected time 与 worst-case time 的区别。

Problem 5: Perfect hashing 两层结构

题目: 两层 hashing：第一层像 separate chaining，把 个元素分到 个 bucket；每个 bucket 不用 list，而用一个 secondary hash table。分析 lookup 和空间。

题解:

设第一层第 个 bucket 中有 个元素。

a) Secondary table 应该多大?

若第 个 bucket 的 secondary table 大小为 ，其中 collision 数期望：

为了让有 collision 的概率最多 ，用 Markov：

令：

则：

b) Batch insertion

  1. 随机选择第一层 hash function ；
  2. 把所有元素分到 个 bucket，得到 ；
  3. 对每个 bucket ，开一个大小 的 secondary table；
  4. 为该 bucket 随机选择 secondary hash function；
  5. 若发生 collision，则重新选择该 bucket 的 secondary hash function，直到无 collision。

因为每次成功概率至少 ，所以期望重试次数是常数。

c) Lookup 期望时间

查询 ：

  1. 第一层算 ；
  2. 第二层算 ；
  3. 直接查 secondary table 位置。

secondary table 被初始化为无 collision，所以 lookup 是 worst-case：

d) 总空间为什么是 ?

总空间主要是：

需要证明其期望是 。

展开：

所以：

当 时，总贡献是 。

当 时，对每对 ，它们落入同一 bucket 的概率最多 。因此：

若 ，则：

因此 perfect hashing 总空间期望 ，lookup 。

本题用到的知识点:

  1. Two-level hashing / perfect hashing。
  2. 用 Markov 把 expected collisions 转成 collision-free 概率。
  3. 空间分析。
  4. Universal hashing 控制 pairwise collision。

Problem 6: Bloom filter 的 false positive rate

题目: Bloom filter 插入 个元素，array 大小 ，hash function 个数 。假设 hash functions fully random。分析 false positive probability，并讨论 bits per element 时如何选 。

题解:

令：

表示平均每个元素占多少 bit。

a) 某一位被置为 1 的概率

固定 array 中某个 bit 。

一次 hash 不打到它的概率是：

总共有 次 hash 写入，所以该 bit 仍为 0 的概率是：

因此被置为 1 的概率：

用近似：

所以：

b) False positive probability

查询一个没有插入过的 。它会 false positive 当且仅当：

在独立近似下：

c) 时最佳

要最小化：

标准结论是：

因此：

取整数：

一般情况下：

d) 的错误率

即约：

e) 固定 ，改变

错误率：

课程 solution 给出的近似结果：

false positive rate
12 约
16 约
32 约

当 很大时：

所以：

本题用到的知识点:

  1. Bloom filter false positive 来自多个 bit 被其他元素置 1。
  2. 近似 。
  3. 最优 hash 个数 。
  4. 固定 时错误率随 多项式下降。

Advanced

Problem 7: Bloom filter 如何支持 Remove?

题目: 扩展 Bloom filter，使其支持 Remove，并分析 guarantee。

题解:

普通 Bloom filter 不能直接删除，因为一个 bit 可能由多个元素共同置为 1。若删除 时简单把 对应 bit 置回 0，可能会破坏其他元素，造成 false negative。

方法 1: Counting Bloom filter

把 bit array 改成 counter array。

  • Insert(x)：对 对应 counter 加 1；
  • Remove(x)：对应 counter 减 1；
  • Lookup(x)：所有对应 counter 都大于 0 才返回 yes。

优点：

  • 支持删除；
  • 若 counter 不 overflow，仍无 false negative。

代价：

  • 空间从 bit 变成 small counters，增加常数因子；
  • 仍可能 false positive。

方法 2: Deletion Bloom filter

额外维护一个 Bloom filter 记录被删除的元素。查询时：

  • 原 filter 说 yes；
  • deletion filter 没说 deleted；
  • 才返回 yes。

这会引入新错误类型：deletion filter 可能 false positive，导致实际存在的元素被误判为 deleted，即产生 false negative。

所以 practical 上更常用 counting Bloom filter。

本题用到的知识点:

  1. 普通 Bloom filter 无法安全清零 bit。
  2. Counting Bloom filter 用 counter 支持删除。
  3. 删除结构可能引入 false negative。
  4. Bloom filter 的 guarantee 与数据结构变体相关。

Part 2: Week 6 讲义知识点

0. 基础版导读：hashing 解决的根本问题

Week 6 的主题是 Hashing and Friends。它解决的核心问题是：

universe 很大，但真正存储的 key 很少。怎样用接近 key 数量的空间，快速支持 insert、lookup、remove?

如果 universe 是 ，最直接的方法是开一个长度为 的数组。查询 key 时直接看 A[x]。这能做到 worst-case ，但空间是 。当 很大、实际只存 个 key 时，这太浪费。

Hashing 用一个函数：

把大 universe 压到小表里。 是 hash table 的 bucket 数。压缩以后一定可能发生 collision：两个不同 key 被映到同一个 bucket。

为什么 hash function 要随机选?

算法不是每次操作都重新随机。通常做法是：

  1. 初始化时从 hash family 中随机选一个 。
  2. 之后 insert/search/delete 都用同一个 。

这样做是为了避免固定 hash function 被坏输入针对。我们分析的是随机选择 后的期望表现。

两个重要概念：

  • Universal hashing：任意两个不同 key collision 的概率最多 。
  • Strongly universal hashing：任意两个不同 key 的 hash 值像独立均匀随机变量一样。

普通 universal hashing 已经足够证明 separate chaining 的 expected ；strongly universal 更强，在需要更细独立性时有用。

separate chaining 为什么是 ?

Separate chaining 是每个 bucket 放一个链表。设当前存了 个 key，表大小为 ，load factor 为：

查询 key 时，需要扫描 bucket 里的元素。对每个其他 key 定义 indicator：

由 universal hashing：

所以和 撞在一起的元素期望数是：

加上访问本身，查询期望时间是 。如果 ，那么 ，所以 expected lookup 是 。

perfect hashing 的直觉

Perfect hashing 常用于 static dictionary：key 集合提前知道，之后主要查询。

目标是更强的 worst-case lookup。两层 perfect hashing 的结构是：

  1. 第一层把所有 key 分到若干 bucket。
  2. 第 个 bucket 有 个 key。
  3. 给这个 bucket 单独建第二层表，大小约 。
  4. 随机挑第二层 hash function，直到这个 bucket 内无 collision。

为什么用 ? 因为如果有 个元素，collision pairs 大约有 对。表开到平方级后，期望 collision 数可以压到常数以下，因此存在无 collision 的选择。

总空间不是 ，关键要证明：

理解这个式子的方法是： 在数“同 bucket 的 ordered pairs”。每一对不同 key collision 的概率最多 ，所以总期望可以控制住。

Bloom filter 是什么类型的错误?

Bloom filter 做 approximate membership query：

  • 如果回答 not present，一定正确。
  • 如果回答 present，可能是 false positive。
  • 普通 Bloom filter 没有 false negative。

它用一个长度 的 bit array 和 个 hash functions。插入元素 时，把：

对应位置设成 1。查询 时，如果这 个位置全是 1，就回答 present；只要有一个是 0，就回答 absent。

false positive 的原因是： 没插入过，但它的 个位置碰巧都被别的元素设成了 1。

如果插入 个元素，总共做 次置位。某一位仍是 0 的概率近似：

所以某一位是 1 的概率约为：

false positive rate 近似：

如果写成 ，也就是每个元素 bits，则变成：

为什么 Bloom filter 删除麻烦?

普通 Bloom filter 不能直接把某些 bit 从 1 改回 0。因为一个 bit 可能被多个元素共享。删除 时如果把它对应 bit 清零，可能会让另一个仍在集合里的元素查询失败，产生 false negative。

Counting Bloom filter 把 bit 改成 counter：

  • insert 时对应 counters 加 1。
  • delete 时对应 counters 减 1。
  • query 时检查 counters 是否都大于 0。

代价是空间更大，而且要考虑 counter overflow。

做题时怎么下手?

  • 看到 expected chain length：定义 indicator，求 collision 期望。
  • 看到 universal hashing：重点是任意 pair collision probability。
  • 看到 perfect hashing：写 ，把它解释成 pair 数。
  • 看到 Bloom filter：先算某一 bit 为 0/1 的概率，再算 个位置全为 1。
  • 看到 remove：普通 Bloom filter 不安全，优先考虑 counting Bloom filter。

1. Dictionary ADT 与 universe size

Dictionary 维护集合 ，支持：

  • Insert(x);
  • Lookup(x);
  • Remove(x).

设：

  • ；
  • ；
  • 通常 。

直接用大小为 的 array 可以 操作，但空间 太大。Hashing 的目标是把大 universe 映射到小 table：

2. 为什么需要随机 hash functions?

Pigeonhole principle 告诉我们，只要 ，任意 deterministic 都存在大量元素被映射到同一位置。也就是说，固定 hash function 总有 worst-case input 让 collision 崩坏。

解决思路：不是固定一个 hash function，而是从一个小而“足够随机”的 family 中随机选择 。

3. Strongly universal hashing

Strongly universal 要求对任意 ， 和 像两个独立均匀随机变量：

它提供 pairwise independence。

多项式构造：在有限域 上取随机系数：

可得到 strongly universal family。

4. Universal hashing

Universal hashing 更弱，只要求碰撞概率：

Strongly universal 一定 universal，但反过来不一定。

常见构造：

其中 是 prime，，。这是 universal hash family。

5. 分析 hash structures 时常用哪些随机性?

Universal hashing 通常足够做：

  • expected bucket size；
  • expected collision number；
  • Markov / Chebyshev 类证明。

但 Chernoff / Hoeffding 通常需要 full independence，不能随便在 universal hashing 上直接使用。

6. Collision handling

Separate chaining

每个 bucket 存 linked list。空间：

期望操作时间：

Worst-case：

Open addressing

所有元素直接存在 array 中。若当前位置冲突，就按 probing sequence 找下一个位置。

常见方式：

  • linear probing；
  • quadratic probing；
  • double hashing。

理想随机 permutation probing 下，unsuccessful lookup 期望时间：

Linear probing 可能因为 clustering 更差。

Cuckoo hashing

每个元素有两个可选位置。Lookup/Remove 检查两个位置即可：

Insert 可能触发 eviction chain，期望 ，分析更复杂。

7. Perfect hashing

Two-level hashing：

  1. 第一层 table 大小 ；
  2. 第 个 bucket 若有 个元素，第二层开 空间；
  3. 重抽第二层 hash 直到无 collision。

保证：

  • lookup worst-case ；
  • expected total space 。

核心公式：

8. Bloom filter

Bloom filter 使用：

  • bit array ，长度 ；
  • 个 hash functions。

操作：

  • Insert: 将 个位置置为 1；
  • Lookup: 若 个位置全是 1 返回 yes，否则 no。

Guarantee：

  • no false negative；
  • false positive possible；
  • simple version no remove。

空间：

时间：

False positive 近似：

其中 。

最优：

9. Going further: 为什么简单 hash functions 实践中有效?

Week 6 going-further 读物讨论 Mitzenmacher 和 Vadhan 的观点：理论 worst-case 分析下，2-universal 或低独立 hash family 的 guarantee 往往弱于 truly random hashing；但实践中简单 hash functions 表现常常接近 truly random。

解释思路是：真实数据并非 adversarial worst-case，可能本身含有 entropy。若数据流中每个新元素在给定过去元素后仍有足够 Renyi entropy，则 universal hashing + 数据自身随机性可以产生接近 ideal hashing 的效果。

应用包括：

  • linear probing；
  • chained hashing；
  • balanced allocation；
  • Bloom filters。

这个观点提醒：理论保证分 worst-case data 与 random-ish data，两者能得到的结论不同。

本周核心记忆

主题 关键结论
Universal hashing
Strongly universal 两个不同输入输出 pairwise independent uniform
Chaining expected time
Chaining worst-case
Perfect hashing expected space, worst-case lookup
Bloom filter false positive
Bloom optimal
Bloom guarantee no false negative, possible false positive
Counting Bloom filter 支持 remove，但空间变大