算法分析与设计

Appearance

3.7 哈希与随机化：概率换取效率 ​

这一节，你能解决什么问题 ​

学完这一节，你能够：

  1. 理解哈希的设计哲学：用概率换取期望性能，接受概率性结果
  2. 分析哈希冲突的本质：balls-and-bins 模型，理解"期望好但最坏差"
  3. 理解全域散列的设计原理：为什么 (ax+b) mod p mod m 能保证全域性
  4. 理解 Bloom Filter 的设计原则：假阳性可接受，假阴性不可接受
  5. 判断什么时候用概率性方法，什么时候需要精确保证

问题情境 ​

某团队设计缓存系统。工程师用哈希表存储 URL 缓存。

上线后发现：某些 URL 组总是"碰"在一起，查询变慢。

工程师想："换个更好的哈希函数应该能解决。"

同事说："不是哈希函数的问题，是哈希的本质。"

哈希的本质是什么？

哈希用概率换取性能——期望 O(1)，最坏 Θ(n)。

这不是缺陷，是设计选择。

但问题是：如果攻击者知道你的哈希函数，他可以构造"杀手输入"，让所有 URL 都映射到同一个桶！

问题：为什么哈希冲突不可避免？怎么控制？怎么防止攻击？

直观思路 ​

哈希的本质是 balls-and-bins 问题：把 n 个球随机扔进 m 个桶。

期望：每个桶有 n/m 个球。

问题："最多"一个桶有多少个球？

关键洞察：期望好，但总有一些桶会"倒霉"。

为什么攻击者能构造杀手输入？ ​

如果哈希函数是固定的（确定性），攻击者可以：

  1. 知道哈希函数的规则
  2. 找出所有映射到某个桶的元素
  3. 构造一个全是这些元素的输入

这就是 2011 年 HashDoS 攻击：攻击者构造特殊的 POST 参数，让服务器哈希表退化成 Θ(n²)。

解决方案：随机化哈希函数，让攻击者无法预测。

这个方法是怎么想到的 ​

哈希的视角转换 ​

传统视角：哈希是快速查找的数据结构

新视角：哈希是随机化算法——用概率换取效率

Bloom Filter 的设计哲学 ​

问题：快速判断"是否在集合中"，允许误报。

洞察：

  • 假阳性可以通过后续验证排除
  • 假阴性会直接漏掉真实内容

关键：假阳性可接受，假阴性不可接受。

规范定义 ​

Balls-and-Bins 模型 ​

  • n 个球，m 个桶
  • 每个球随机扔进一个桶
  • 最大负载期望 ≈ ln n / ln ln n（当 m = n）

哈希冲突 ​

  • 期望冲突次数 = n(n-1) / 2m

算法实现 ​

全域散列：消除对输入的依赖 ​

问题：确定性哈希函数可以被攻击。

解决：随机选择哈希函数，让攻击者无法预测。

全域散列定义：一组哈希函数 H，满足：

对于任意两个不同的键 x ≠ y：

P[h(x) = h(y)] ≤ 1/m

其中 h 从 H 中随机选择，m 是桶数。

直觉：即使攻击者知道 H 是什么集合，他也不知道我们选了哪个 h。所以他能构造的"杀手输入"的概率很低。

构造方法：(ax+b) mod p mod m ​

python
def universal_hash(a, b, p, m):
    # 返回一个哈希函数
    def h(x):
        return ((a * x + b) % p) % m
    return h

# 随机选择参数
# p: 大质数，p > 所有键的最大值
# a: 从 {1, 2, ..., p-1} 中随机选择
# b: 从 {0, 1, ..., p-1} 中随机选择
# m: 桶数

为什么能保证全域性？ ​

数学推导：

设 x ≠ y 是两个不同的键，令 r_x = (ax + b) mod p，r_y = (ay + b) mod p。

注意：r_x 和 r_y 都在 {0, 1, ..., p-1} 内，且因为 x ≠ y，所以 r_x ≠ r_y。

冲突条件：h(x) = h(y) 等价于 r_x mod m = r_y mod m。

也就是 r_x - r_y 是 m 的倍数。

设 r_x - r_y = km，其中 k ∈ {1, ..., (p-1)/m}（因为 |r_x - r_y| < p）。

求概率：

对于固定的 x、y 和 k：

r_x - r_y = (ax + b) - (ay + b) mod p
          = a(x - y) mod p
          = km

所以：

a(x - y) ≡ km (mod p)
a ≡ km / (x - y) (mod p)

因为 p 是质数，x - y 在 mod p 下有逆元，所以 a 有唯一解。

也就是说，对于每个 k，只有一个 a 值导致冲突。

a 有 (p-1) 种选择，k 有 (p-1)/m 种可能。

冲突概率：

P[h(x) = h(y)] = P[r_x ≡ r_y (mod m)]
               = P[r_x - r_y 是 m 的倍数]
               = P[a 满足 a(x-y) ≡ km (mod p)]
               = (p-1)/m × 1/(p-1)  （每种 k 对应一个 a）
               = 1/m

结论：对于任意 x ≠ y，P[h(x) = h(y)] = 1/m，满足全域散列定义！

直观理解：

  1. (ax + b) mod p 把键映射到 {0, ..., p-1}，这类似线性变换，不同键映射到不同的值（因为 p 是质数）
  2. 第二步的 mod m 把大范围映射到 m 个桶
  3. 第一步的"线性性"保证了第二步的"冲突"是均匀的
  4. 所以任意两键冲突的概率 ≈ 1/m

Bloom Filter：假阳性可接受 ​

python
class BloomFilter:
    def __init__(self, m, k):
        self.B = [0] * m       # 位数组
        self.hash_funcs = k    # k 个哈希函数
    
    def insert(self, x):
        for h in self.hash_funcs:
            self.B[h(x) % len(self.B)] = 1
    
    def query(self, x):
        return all(self.B[h(x) % len(self.B)] for h in self.hash_funcs)

设计原则：

  • 假阳性概率 > 0（可能误报）
  • 假阴性概率 = 0（不会漏报）

假阳性概率计算：

设 m 位，n 个元素，k 个哈希函数。

某位仍为 0 的概率（插入 n 个元素后）：

P(位为 0) = (1 - 1/m)^(kn) ≈ e^(-kn/m)

假阳性概率（所有 k 位都是 1）：

P(假阳性) = (1 - P(位为 0))^k ≈ (1 - e^(-kn/m))^k

最优 k 值：

k ≈ m/n × ln 2
此时 P(假阳性) ≈ (1/2)^k

MinHash：相似度估计 ​

python
def minhash_similarity(A, B, k):
    # k 个哈希函数
    equal_count = 0
    for h in hash_functions(k):
        if min(h(x) for x in A) == min(h(x) for x in B):
            equal_count += 1
    return equal_count / k  # ≈ Jaccard(A, B)

正确性分析 ​

Bloom Filter 假阴性概率 = 0 ​

插入时把所有 k 个位置设为 1。

查询时检查所有 k 个位置。任何位置是 0 → 元素从未插入。

推导：

  • 如果元素 x 已插入，所有 h(x) 对应的位置都是 1
  • 查询时检查这些位置，一定都是 1
  • 所以不会出现假阴性（不会漏报）

这是确定性的。

MinHash 估计 Jaccard ​

P[h_min(A) = h_min(B)] = Jaccard(A, B) = |A ∩ B| / |A ∪ B|

推导：

  • 设 z 是 A ∪ B 中哈希值最小的元素
  • h_min(A) = h_min(B) iff z ∈ A ∩ B
  • P[z ∈ A ∩ B] = |A ∩ B| / |A ∪ B| = Jaccard(A, B)

复杂度分析 ​

结构期望查询最坏查询空间特点
哈希表O(1)Θ(n)Θ(m)动态集合
全域散列哈希表O(1)Θ(n)Θ(m)抗攻击
Bloom FilterO(k)O(k)Θ(m)假阳性可接受
完美散列O(1)O(1)Θ(n)静态集合

什么时候不该用这个方法 ​

该用哈希的情况 ​

  • 动态集合，需要快速查找
  • 可以接受最坏 Θ(n)（概率很低）

该用全域散列的情况 ​

  • 防止攻击（用户可能构造恶意输入）
  • 要比"期望好"更强的保证

该用 Bloom Filter 的情况 ​

  • 判断"是否在集合中"
  • 假阳性可接受（可以验证排除）
  • 假阴性不可接受

不该用 Bloom Filter 的情况 ​

  • 需要精确判断（不能有假阳性）
  • 需要删除元素（Bloom Filter 不支持）

本节小结 ​

解决了什么问题？

用概率换取效率，控制最坏情况，防攻击。

核心方法是什么？

  • 全域散列：随机选择哈希函数，保证任意两键冲突概率 ≤ 1/m
  • Bloom Filter：假阳性可接受，假阴性不可接受
  • MinHash：概率估计相似度

为什么正确？

  • 全域散列：数学证明 P[h(x)=h(y)] = 1/m
  • Bloom Filter：确定性保证不会漏报
  • MinHash：期望等于 Jaccard 相似度

代价是什么？

  • 哈希：最坏 Θ(n)
  • 全域散列：需要大质数 p
  • Bloom Filter：假阳性

适用场景？

可以接受概率性结果，用验证控制风险。需要防攻击时用全域散列。

练习 ​

基本理解 ​

练习 1：n = 1000, m = 100，计算哈希冲突期望次数。

练习 2：Bloom Filter m = 1000, n = 100, k = 5，计算假阳性概率。

练习 3：集合 A = {1, 2, 3}, B = {2, 3, 4}，Jaccard = 0.5。用 MinHash（5 个哈希函数）验证。

全域散列理解 ​

练习 4：设 p = 7, m = 5, a = 3, b = 4。计算 h(2) 和 h(5)，验证全域性性质。

练习 5：为什么全域散列需要 p 是质数？如果 p 不是质数会怎样？

提示：考虑逆元的存在性。

练习 6：构造一个"杀手输入"针对确定性哈希 h(x) = x mod m。假设 m = 100，构造一组键，让它们全部映射到桶 0。

错误诊断 ​

练习 7：以下场景可以用 Bloom Filter 吗？

场景假阳性影响假阴性影响能用吗？
URL 缓存检查多缓存不存在漏缓存
密码验证漏错误密码漏正确密码
垃圾邮件过滤漏正常邮件漏垃圾邮件

分析每种场景，判断 Bloom Filter 是否适用。

方案比较 ​

练习 8：对比哈希策略：

场景应该用什么？
动态集合，精确查询，无攻击风险
动态集合，防止攻击
静态集合，最坏 O(1)
集合判断，假阳性可接受
相似度估计

上一节：3.6 顺序统计量

下一节：3.8 字符串匹配

新时代的算法课程