Hashing

从 Sketching 到 Hashing

上两讲中，哈希函数是我们反复使用的工具：Flajolet-Martin 用哈希值的末尾零估计不同元素个数，Count-Min Sketch 用哈希将元素分桶，Bloom filter 用多个哈希函数实现近似成员查询。但我们一直把哈希函数当作黑盒使用——给它一个元素，它返回一个「看起来随机」的值。

本讲要打开这个黑盒。我们将系统地研究哈希的理论基础：什么样的哈希函数「够好」？它需要多少随机性？能在多少空间内实现 $O(1)$ 查询？这些问题的答案构成了从数据结构到流算法的理论根基。

一切从一个最基本的概率模型开始：将球随机扔进桶里（Balls into Bins）。

Balls into Bins

随机函数与球桶模型

将 $m$ 个球独立均匀随机地扔进 $n$ 个桶（每个球等概率落入任一桶），每种分配方案出现的概率为 $1/n^m$。这等价于从 $[m]$ 到 $[n]$ 的均匀随机函数 $f$——每个 $f$ 的概率恰好也是 $1/n^m$。

这个看似简单的模型蕴含了丰富的问题：

问题	描述	关注点
Birthday	是否有两个球落入同一桶？	碰撞
Coupon Collector	多少球才能覆盖所有桶？	覆盖
Occupancy	最满的桶有多少球？	最大负载
Pre-image Size	某个桶收到多少球？	桶大小分布

其中占有问题（Occupancy Problem）与哈希表的性能直接相关——哈希表中最长链表的长度就是最大负载。

最大负载分析

每个桶 $i$ 收到的球数 $X_i$ 边际上服从二项分布 $X_i \sim \text{Bin}(m, 1/n)$（$m$ 个球，每个以概率 $1/n$ 落入桶 $i$），期望 $\mu = m/n$。我们关心最大负载 $\max\limits_{1 \le i \le n} X_i$ 的上界。

用 Markov 和 Chebyshev 分析这个问题太粗糙了。以 $m = n$ 为例（$\mu = 1$）：

• Markov 只能给出 $\Pr[X_i \ge k] \le 1/k$，联合界得到 $\Pr[\max_i X_i \ge k] \le n/k$。
  • 这告诉我们最大负载不超过 $n$，毫无用处。
• Chebyshev 利用 $X_i \sim \operatorname{Bin}(n, 1/n)$ 有 $\text{Var}(X_i) =np(1-p)=1-p \le 1$，得到 $\Pr[|X_i - 1| \ge \sqrt{n}] \le 1/n$。
  • 最大负载不超过 $O(\sqrt{n})$，有所改善但仍然很松。

真正有效的工具是 Chernoff bound。在分析最大负载之前，让我们先完整地建立这个重要的概率工具。

Chernoff Bound

上一讲已经使用过 Chernoff-Hoeffding 界来分析 median trick 的置信度提升。当时直接给出了结论而没有证明（虽然已经在《数据科学基础》课程中证明过）。本讲将完整推导 Chernoff bound——它不仅是分析 balls into bins 的核心工具，也是本课程中反复出现的技术。

矩生成函数

Chernoff bound 的关键在于矩生成函数（Moment Generating Function, MGF）。

矩生成函数

随机变量 $X$ 的矩生成函数定义为

$$M_X(t) = \mathbb{E}[\e^{tX}] = \sum_{k \ge 0} \frac{t^k \mathbb{E}[X^k]}{k!}$$

它「编码」了 $X$ 的所有矩信息——$k$ 阶矩 $\mathbb{E}[X^k]$ 可以从 $M_X^{(k)}(0)$ 中读出。

为什么矩生成函数比直接用矩更有力？因为对于独立随机变量之和，MGF 有乘法性质：$M_{X+Y}(t) = M_X(t) \cdot M_Y(t)$。这让我们能把 $n$ 个独立变量的联合行为转化为单个变量的乘积。

独立 Bernoulli 之和的 MGF：设 $X_1, \ldots, X_n \in \{0,1\}$ 独立，$\Pr[X_i = 1] = p_i$，$X = \sum X_i$，$\mu = \mathbb{E}[X] = \sum p_i$。则

$$\begin{aligned} M_X(t) = \mathbb{E}[\e^{tX}] &= \prod_{i=1}^n \mathbb{E}[\e^{tX_i}] = \prod_{i=1}^n (\e^t p_i + (1 - p_i)) \\ &\le \prod_{i=1}^n \e^{(\e^t - 1)p_i} = \e^{(\e^t - 1)\mu} \end{aligned}$$

第二步用了独立性（独立随机变量的 MGF 等于各自 MGF 的乘积），第三步对每个因子用了 $1 + x \le \e^x$：注意 $\e^t p_i + (1 - p_i) = 1 + (\e^t - 1)p_i$，令 $x = (\e^t - 1)p_i$ 即得 $\le \e^{(\e^t - 1)p_i}$。

上尾界

Chernoff 上尾界

设 $X_1, \ldots, X_n \in \{0,1\}$ 独立，$X = \sum X_i$，$\mu = \mathbb{E}[X]$。对任意 $\delta > 0$：

$$\Pr[X \ge (1+\delta)\mu] \le \left(\frac{\e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu$$

证明

对任意 $t > 0$，用指数函数的单调性将概率界转化为 MGF 界：

$$\Pr[X \ge (1+\delta)\mu] \le \Pr[\e^{tX} \ge \e^{t(1+\delta)\mu}] \le \e^{-t(1+\delta)\mu} \cdot \mathbb{E}[\e^{tX}]$$

第二步是 Markov 不等式。

代入 MGF 的上界 $\mathbb{E}[\e^{tX}] \le \e^{(\e^t - 1)\mu}$：

$$\Pr[X \ge (1+\delta)\mu] \le \e^{(\e^t - 1 - t(1+\delta))\mu}$$

指数中的函数 $g(t) = \e^t - 1 - t(1+\delta)$ 在 $t = \ln(1+\delta)$ 处取到最小值（令 $g'(t) = \e^t - (1+\delta) = 0$）。代入：

$$g(\ln(1+\delta)) = \delta - (1+\delta)\ln(1+\delta)$$

因此

$$\Pr[X \ge (1+\delta)\mu] \le \e^{(\delta - (1+\delta)\ln(1+\delta))\mu} = \left(\frac{\e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu$$

下尾界

Chernoff 下尾界

对任意 $0 < \delta < 1$：

$$\Pr[X \le (1-\delta)\mu] \le \left(\frac{\e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^\mu$$

证明方法完全对称：取 $t = \ln(1-\delta) < 0$，利用 $\Pr[X \le (1-\delta)\mu] = \Pr[\e^{tX} \ge \e^{t(1-\delta)\mu}]$（注意 $t < 0$ 翻转了不等号方向）和相同的 MGF 上界。

简化形式

精确的 Chernoff bound 涉及 $(1+\delta)^{(1+\delta)}$，使用时不太方便。以下是两个常用的简化形式：

上尾：

$$\Pr[X \ge (1+\delta)\mu] \le \begin{cases} \e^{-\mu\delta^2/3} & \text{若 } 0 < \delta < 1 \\ 2^{-(1+\delta)\mu} & \text{若 } (1+\delta) \ge 2\e \end{cases}$$

下尾：

$$\Pr[X \le (1-\delta)\mu] \le \e^{-\mu\delta^2/2}$$

第一个上尾简化在 $\delta$ 较小时有用（精度要求）；第二个在 $\delta$ 很大时有用（超出期望数倍）。

何时用哪个简化形式？

• 需要 $(1 \pm \varepsilon)$ 乘法近似时：用 $\e^{-\mu\delta^2/3}$ 形式
• 需要证明某事「几乎不可能」（超大偏差）时：用 $2^{-(1+\delta)\mu}$ 形式
• 上一讲中 median trick 的分析实际上用的是 Chernoff-Hoeffding 界（对有界随机变量），与这里的 Bernoulli 版本是同一族的工具

回到最大负载

$m = n$ 的情形

现在我们用 Chernoff bound 分析 $m = n$ 个球扔进 $n$ 个桶时的最大负载。每个桶 $i$ 的球数 $X_i \sim \text{Bin}(n, 1/n)$，期望 $\mu = 1$。

取 $L = \dfrac{\e\ln n}{\ln\ln n}$。由于 $\mu = 1$，Chernoff 的精确形式给出

$$\Pr[X_i \ge L] \le \dfrac{\e^L}{\e L^L}$$

代入 $L$ 并验证：$L \ln(L/\e) = \dfrac{\e\ln n}{\ln\ln n} \cdot \ln\!\left(\dfrac{\ln n}{\ln\ln n}\right) = \dfrac{\e\ln n}{\ln\ln n}(\ln\ln n - \ln\ln\ln n) \approx \e\ln n$ 对大 $n$。因此 $(\e/L)^L \le 1/n^2$ 对充分大的 $n$ 成立。

$$\Pr[X_i \ge L] \le \dfrac{\e^L}{\e L^L} \le \frac{1}{n^2}$$

最后一步需要 $L\ln(L/\e) \ge 2\ln n$，上面已经验证这对大 $n$ 成立。

由联合界（union bound）：

$$\Pr\left[\max_{1 \le i \le n} X_i \ge L\right] \le \sum_{i=1}^n \Pr[X_i \ge L] \le n \cdot \frac{1}{n^2} = \frac{1}{n}$$

因此，以高概率（with high probability, w.h.p.），最大负载为

$$\max_{1 \le i \le n} X_i = O\left(\frac{\log n}{\log\log n}\right)$$

为什么是 $\log n / \log\log n$ 而不是 $\log n$？

直觉上，$L$ 个球同时落入一个桶的概率是 $(1/n)^L$。要让 $n$ 个桶中至少有一个达到负载 $L$，需要 $n \cdot (1/n)^L \approx 1$，即 $n^{1-L} \approx 1$，也就是 $L \approx 1$——这太粗糙了。

更精确地，$\Pr[X_i \ge L] \approx \binom{n}{L}(1/n)^L \approx (\e/L)^L$（斯特林近似）。令 $(\e/L)^L = 1/n^2$，取对数得 $L(\ln L - 1) \approx 2\ln n$，解出 $L = \Theta(\log n / \log\log n)$。

$m \ge n\ln n$ 的情形

当球数远多于桶数时，每个桶的期望负载 $\mu = m/n \ge \ln n$ 足够大，Chernoff bound 给出更紧的集中度。取 $(1+\delta) = 2\e$：

$$\Pr\left[X_i \ge \frac{2\e m}{n}\right] = \Pr[X_i \ge 2\e\mu] \le 2^{-2\e\mu} \le 2^{-2\e\ln n} \le \frac{1}{n^2}$$

联合界得到 $\max_i X_i = O(m/n)$，以高概率。直觉上，当球足够多时，每个桶的负载都集中在 $m/n$ 附近——大数定律开始发挥作用。

Power of Two Choices

从 $\log n / \log\log n$ 到 $\log\log n$

$O(\log n / \log\log n)$ 看起来已经不错了，但能不能做得更好？答案是肯定的——只需一个极其简单的改进：给每个球两个候选桶，选负载更小的那个。

Power of Two Choices

每个球独立均匀随机选择两个桶 $h_1(x)$ 和 $h_2(x)$，放入当前负载更小的桶中。

这个看似微小的改变带来了指数级的改进：最大负载从 $\Theta(\log n / \log\log n)$ 降到了 $\Theta(\log\log n)$。

直觉分析

为什么两个选择的效果如此显著？定义 $B_i$ 为负载 $\ge i$ 的桶的数量。

在单选择方案中，一个球落入负载 $\ge i$ 的桶的概率是 $B_i / n$。在双选择方案中，一个球要落入负载 $\ge i$ 的桶，需要两个候选桶的负载都 $\ge i-1$，概率约为 $(B_{i-1}/n)^2$。因此：

$$\mathbb{E}[B_i] \approx n \cdot (B_{i-1}/n)^2 = B_{i-1}^2 / n$$

这意味着 $B_i / n \approx (B_{i-1}/n)^2$——每上升一层，比例平方衰减。从 $B_2/n \le 1/2$ 出发：

$$\frac{B_{2+j}}{n} \le \frac{1}{2^{2^j}}$$

最大负载 $L$ 满足 $B_L/n < 1/n$，即 $2^{2^{L-2}} > n$，解出 $L \approx \log_2\log_2 n + O(1)$。

从 1 到 2 的飞跃

增加到三个或更多选择只会带来边际改善——真正的飞跃发生在从 1 个选择到 2 个选择之间。这使得 power of two choices 成为一个极具性价比的策略：仅多做一次比较，就获得指数级的负载均衡改进。

这个原理在实践中被广泛应用于负载均衡系统（如 HAProxy、Nginx）：不是将请求随机分配到一台服务器，而是随机选两台、挑负载低的那台。

严格证明思路

严格证明采用逐层归纳的策略。定义阈值序列 $\beta_6 = n/(2\e), \beta_{i+1} = 2\e\beta_i^2/n$，以及事件 $\mathcal{E}_i\colon \text{负载 }\ge i\text{ 的桶数 }\nu_i \le \beta_i$。目标是证明 $\Pr[\bigwedge_i \mathcal{E}_i] = \prod_i \Pr[\mathcal{E}_i \mid \mathcal{E}_{<i}] \ge 1 - O(1/n)$。

关键观察：给定 $\mathcal{E}_i$，落入负载 $\ge i$ 的桶的球数近似 $\text{Bin}(n, \beta_i^2/n^2)$，因此 $\nu_{i+1}$ 可以用 Chernoff bound 控制。当 $\beta_i^2/n \ge \log^2 n$ 时，$\Pr[\lnot\mathcal{E}_{i+1} \mid \mathcal{E}_i] \le 1/n^{2\e}$；当 $\beta_i$ 更小时，$\nu_i$ 已经 $< \sqrt{n}\log^2 n$，此后 $\nu_{i+1}$ 急剧缩小到 $O(\log^2 n)$，再过一层就降为 0。

Birthday Paradox

经典分析

Birthday paradox（生日悖论）是 balls into bins 最经典的应用：在一个班级中，57 个人就有超过 $99\%$ 的概率出现生日相同的两人。

Birthday Paradox

将 $n$ 个球扔进 $m$ 个桶（注意这里的 $n, m$ 是 birthday paradox 的标准记号，与前面 occupancy problem 中的 $m$ 个球 $n$ 个桶相反），所有球落入不同桶的概率为

$$\Pr[\text{无碰撞}] = \prod_{i=0}^{n-1} \left(1 - \frac{i}{m}\right)$$

用链式法则理解：第 1 个球任意放，第 2 个球避开 1 个桶的概率为 $(1-1/m)$，第 $i$ 个球需要避开前 $i-1$ 个桶的概率为 $(1-(i-1)/m)$，全部相乘。

利用近似 $1 - x \approx \e^{-x}$（当 $x = o(1)$ 时）：

$$\Pr[\text{无碰撞}] \approx \prod_{i=0}^{n-1} \e^{-i/m} = \e^{-n(n-1)/(2m)} \approx \e^{-n^2/(2m)}$$

令碰撞概率为 $1 - p$，则需要

$$n \approx \sqrt{2m \ln(1/p)}$$

个球就有概率 $1 - p$ 出现碰撞。对于生日问题，$m = 365$，$p = 0.5$ 时 $n \approx 23$。

成对独立下的 Birthday Paradox

上面的分析需要球的位置完全独立。如果我们只有 2-universal 哈希函数（成对独立），还能得到类似的结论吗？

定义碰撞数 $Y = \sum_{i < j} \mathbb{I}[X_i = X_j]$，其中 $X_i = h(x_i)$ 是第 $i$ 个球的位置。由线性期望：

$$\mathbb{E}[Y] = \sum_{i < j} \Pr[X_i = X_j] \le \binom{n}{2} \cdot \frac{1}{m}$$

当 $n \le \sqrt{2m\varepsilon}$ 时，$\mathbb{E}[Y] \le \varepsilon$。由 Markov 不等式：

$$\Pr[\text{有碰撞}] = \Pr[Y \ge 1] \le \mathbb{E}[Y] \le \varepsilon$$

这个结论的意义在于：birthday paradox 只需要成对独立——2-universal 哈希函数就足够了。这为后面的完美哈希奠定了基础。

哈希表

字典问题

字典问题

• 数据：一个集合 $S = \{x_1, \ldots, x_n\} \subseteq U = [N]$
• 查询：给定 $x \in U$，判断 $x \in S$ 是否成立

表示一个 $n$ 元子集的信息论下界为 $\log_2\binom{N}{n} = O(n\log N)$ 比特。

数据结构	空间	查询时间	更新时间
平衡搜索树	$O(n\log N)$ 比特	$O(\log n)$	$O(\log n)$
链式哈希表	$O(n\log N)$ 比特	期望 $O(1)$	期望 $O(1)$
完美哈希	$O(n\log N)$ 比特	$O(1)$ 最坏	$O(1)$

链式哈希表

回顾：链式哈希表

选取哈希函数 $h\colon U \to [m]$，维护 $m$ 个链表。元素 $x$ 存储在链表 $L_{h(x)}$ 中。

• Insert($x$)：计算 $h(x)$，插入到链表头部 — $O(1)$
• Search($x$)：计算 $h(x)$，遍历链表 $L_{h(x)}$ — 时间取决于链表长度
• Remove($x$)：从链表中删除 — $O(1)$（给定指针）

最坏情况下，所有元素哈希到同一位置，查询退化为 $\Theta(n)$。

链式哈希表的性能完全取决于哈希函数的质量。如果使用 SUHA（Simple Uniform Hash Assumption，即完全随机的哈希函数），期望链表长度为 $n/m$，查询时间期望 $O(1)$（取 $m = \Theta(n)$）。但存储一个完全随机的哈希函数本身就需要 $\Omega(N\log m)$ 比特——比数据还大。

这就引出了核心问题：能否用少量随机比特描述一个「足够好」的哈希函数？

Universal Hashing

定义

Carter 和 Wegman（1979）提出的 universal hashing 正是对「足够好」的精确刻画。

$k$-Universal 哈希函数族

一个哈希函数族 $\mathcal{H} = \{h\colon U \to [m]\}$ 称为 $k$-universal 的，如果对任意 $\le k$ 个不同元素 $x_1, \ldots, x_k \in U$：

$$\Pr_{h \sim \mathcal{H}}[h(x_1) = \cdots = h(x_k)] \le \frac{1}{m^{k-1}}$$

更强的版本：$\mathcal{H}$ 是 strongly $k$-universal（$k$-wise 独立）的，如果对任意 $\le k$ 个不同元素和任意目标值 $y_1, \ldots, y_k \in [m]$：

$$\Pr_{h \sim \mathcal{H}}\left[\bigwedge_{i=1}^k h(x_i) = y_i\right] = \frac{1}{m^k}$$

$k$-universal 保证碰撞概率不超过理想随机的水平；strongly $k$-universal 进一步要求任意 $k$ 个不同元素的哈希值联合均匀分布——这等价于 $k$-wise 独立性。简言之，$k$-universal 是碰撞概率的保证，strongly $k$-universal（= $k$-wise 独立）是联合分布的保证，后者严格强于前者。上一讲中使用的 2-universal 哈希（也称成对独立哈希）就是 $k = 2$ 的情形。

线性同余构造

线性同余哈希族

选取大于 $N$ 的素数 $p$，定义

$$\mathcal{H} = \{h_{a,b}(x) = ((ax + b) \bmod p) \bmod m \mid a \in \mathbb{Z}_p \setminus \{0\},\, b \in \mathbb{Z}_p\}$$

该族是 2-wise 独立的。描述一个函数 $h_{a,b}$ 只需存储 $a, b$ 两个参数，共 $O(\log N)$ 比特。

推广到 $k$-wise 独立：使用 $\mathbb{Z}_p$ 上的 $k-1$ 次随机多项式

$$h_{a_0, \ldots, a_{k-1}}(x) = \left(\sum_{i=0}^{k-1} a_i x^i \bmod p\right) \bmod m$$

可以构造 $k$-wise 独立的哈希族，存储 $k$ 个系数需要 $O(k\log N)$ 比特。

二进制域上的构造：对于 $\text{GF}(2^w) \to \text{GF}(2^l)$ 的映射（$\text{GF}(2^w)$ 是包含 $2^w$ 个元素的有限域，运算基于 XOR 和多项式乘法），可以用 $h_{a,b}(x) = (a \cdot x + b) \gg (w - l)$，其中乘法和加法在 $\text{GF}(2^w)$ 上进行。这在实现上非常高效，因为有限域运算可以用位运算完成。

Perfect Hashing

现在我们有了理论上「够好」的哈希函数族。下一个问题是：能否实现 $O(1)$ 最坏情况查询时间？链式哈希表只能保证期望 $O(1)$，最坏情况可能是 $\Theta(n)$。

一级完美哈希

最直接的想法：选一个哈希函数 $h\colon [N] \to [m]$，使得 $S$ 中的 $n$ 个元素没有碰撞。这样每个位置最多存一个元素，查询时间恒为 $O(1)$。

由 birthday paradox（成对独立版本），使用 2-universal 哈希族，取 $m > \binom{n}{2}$（即 $m = \Theta(n^2)$），碰撞概率

$$\Pr[\text{不完美}] \le \frac{n(n-1)}{2m} < 1$$

因此 存在一个 $h \in \mathcal{H}$ 使得 $S$ 上无碰撞。查询只需 $O(1)$ 时间，但空间是 $O(n^2)$——二次方的空间开销在 $n$ 较大时不可接受。

FKS 两级完美哈希

Fredman、Komlós 和 Szemerédi（1984）给出了一个精妙的两级方案，将空间降到了 $O(n)$。

FKS Perfect Hashing

第一级：用 2-universal 哈希 $h\colon [N] \to [n]$ 将 $n$ 个元素分到 $n$ 个桶中，桶 $i$ 收到的元素集合记为 $B_i$。

第二级：对每个桶 $B_i$，用一个独立的 2-universal 哈希 $h_i\colon [N] \to [|B_i|^2]$，建立一个大小为 $|B_i|^2$ 的完美哈希表（一级方案，无碰撞）。

查询 $x$：

1. 计算 $i = h(x)$，定位到桶 $i$
2. 计算 $h_i(x)$，在桶 $i$ 的二级表中查找
3. 检查该位置是否存储了 $x$

flowchart TD
    S["集合 S：n 个元素"] --> h["一级哈希 h: [N] → [n]"]
    h --> B1["桶 B₁"]
    h --> B2["桶 B₂"]
    h --> Bn["桶 Bₙ"]

    B1 --> h1["h₁: [N] → [|B₁|²]"]
    B2 --> h2["h₂: [N] → [|B₂|²]"]
    Bn --> hn["hₙ: [N] → [|Bₙ|²]"]

    h1 --> T1["二级表 T₁<br>无碰撞"]
    h2 --> T2["二级表 T₂<br>无碰撞"]
    hn --> Tn["二级表 Tₙ<br>无碰撞"]

    classDef data fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef hash fill:#f3e5f5,stroke:#4a148c,stroke-width:2px
    classDef bucket fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef table fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px

    class S data
    class h,h1,h2,hn hash
    class B1,B2,Bn bucket
    class T1,T2,Tn table

空间分析

关键问题是：二级表的总空间 $\sum_{i=1}^n |B_i|^2$ 有多大？

回顾碰撞数 $Y = \sum_{i < j} \mathbb{I}[h(x_i) = h(x_j)]$。注意到

$$Y = \sum_{i=1}^n \binom{|B_i|}{2} = \frac{1}{2}\sum_{i=1}^n |B_i|(|B_i| - 1)$$

因此

$$\sum_{i=1}^n |B_i|^2 = 2Y + \sum_{i=1}^n |B_i| = 2Y + n$$

由 2-universal 性，$\mathbb{E}[Y] \le \binom{n}{2}/n < n/2$，所以

$$\mathbb{E}\left[\sum_{i=1}^n |B_i|^2\right] = 2\mathbb{E}[Y] + n < 2n$$

由 Markov 不等式，存在一个一级哈希函数 $h$ 使得 $\sum |B_i|^2 \le 3n$（例如取阈值为期望的 3 倍，成功概率 $\ge 2/3$）。对每个桶，由一级方案的存在性论证，存在无碰撞的二级哈希函数。

总空间：$O(n)$ 个字（每个字 $O(\log N)$ 比特），查询时间 $O(1)$ 最坏情况。

FKS 的历史意义

FKS 完美哈希解决了一个长期悬而未决的问题：是否可能同时实现 $O(n)$ 空间和 $O(1)$ 最坏情况查询。答案是肯定的——代价是数据结构是静态的（不支持高效的插入/删除）。

原始论文中给出了一个具体的例子：$S = \{2, 4, 5, 15, 18, 30\}$，$p = 31$，$n = 6$，总表大小为 $6n = 36$，每次查询只需 5 次内存访问。

Dietzfelbinger 等人（1994）进一步给出了 FKS 的动态版本，支持期望 $O(1)$ 的插入和删除。

Cuckoo Hashing

FKS 哈希是静态的——适合一次性构建后只做查询的场景。如果需要动态地插入和删除元素，同时保持 $O(1)$ 最坏情况查询，该怎么办？

Cuckoo hashing（布谷鸟哈希）巧妙地解决了这个问题。它的名字来源于布谷鸟（cuckoo bird）的寄生行为：布谷鸟会把蛋下在别的鸟巢里，雏鸟孵化后把原来的蛋和幼鸟挤出去——cuckoo hashing 中，新元素可以「踢走」已有元素，被踢走的元素再去找自己的替代位置。

Cuckoo Hashing

使用两个独立的哈希函数 $h, g\colon [N] \to [m]$，维护哈希表 $A[1 \ldots m]$。

• 查询 $x$：检查 $A[h(x)]$ 和 $A[g(x)]$，时间恒为 2 次内存访问
• 插入 $x$：若 $A[h(x)]$ 或 $A[g(x)]$ 为空，直接放入；否则踢走已有元素，被踢走的元素去它的另一个位置，如此反复；若循环过长则重建
• 空间：$O(n)$

查询的优势极其明显：恰好 2 次内存访问，最坏情况确定性保证，没有链表遍历、没有探测序列。

Cuckoo 图

分析 cuckoo hashing 的关键工具是 Cuckoo 图（Cuckoo Graph）。定义多重图 $G = (V, E)$：

• $V = [m]$（所有槽位）
• $E = \{(h(x), g(x)) : x \in S\}$（每个元素对应一条边）

每次插入 $x$ 时，需要沿着 cuckoo 图中从 $h(x)$ 或 $g(x)$ 出发的路径重新安排元素。插入成功与否取决于图的局部结构：

flowchart LR
    subgraph success["插入成功"]
        direction LR
        p1["路径"] --- p1a["x → a → b → c → 空"]
        c1["单环"] --- c1a["可沿环旋转腾出位置"]
    end

    subgraph fail["插入失败"]
        direction LR
        d1["双环"] --- d1a["无法分配，需重建"]
        l1["过长路径"] --- l1a["踢移代价过高"]
    end

    classDef ok fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    classDef bad fill:#ffebee,stroke:#c62828,stroke-width:2px

    class success,p1,p1a,c1,c1a ok
    class fail,d1,d1a,l1,l1a bad

• 路径：沿路径踢移，最终找到空位 — 成功
• 单环：沿环旋转一圈腾出一个位置 — 成功
• 双环：两个环共享顶点，无法通过踢移解决 — 需要重建
• 过长路径：踢移代价太高 — 需要重建

期望插入时间分析

核心引理：一条固定的长度为 $k$ 的插入路径存在的概率不超过 $m^{-2k-1}$。

路径形如 $x, \text{slot}_1, y, \text{slot}_2, z, \text{slot}_3, \ldots$（key-slot 交替）。路径上有 $k$ 个 key 和 $k+1$ 个 slot。每个 key 需要恰好被哈希到路径上的两个相邻 slot（通过 $h$ 和 $g$），每次匹配的概率为 $1/m$，共 $2k+1$ 次匹配（包括起始元素 $x$ 的一次）。

长度 $\ge k$ 的路径存在的概率需要对所有可能的路径求联合界：有 $n$ 种选择 key、$m$ 种选择 slot 的方式，总共 $(nm)^k$ 条可能路径，每条概率 $\le m^{-2k-1}$：

$$\Pr[\text{路径长度} \ge k] \le \frac{(nm)^k}{m^{2k+1}} \le \frac{n^k}{m^{k+1}} = \exp(-\Omega(k))$$

其中用到了 $m = \Theta(n)$。同理，$\Pr[\text{环长度} \ge k] = \exp(-\Omega(k))$。

插入的期望时间 $\mathbb{E}[T]$ 可以分解为：

$$\mathbb{E}[T] \le \underbrace{\mathbb{E}[\text{路径长度}]}_{O(1)} + \underbrace{\mathbb{E}[\text{环长度}]}_{O(1)} + \underbrace{\Pr[\text{双环或过长路径}] \cdot n \cdot \mathbb{E}[T]}_{\text{重建代价}}$$

其中：

• $\mathbb{E}[\text{路径长度}] \le \sum_{k \ge 1} \exp(-\Omega(k)) = O(1)$
• $\mathbb{E}[\text{环长度}] \le O(1)$
• $\Pr[\text{双环}]$：最简单的情形（两条边共享两个端点）概率为 $n^2 m^2 / m^6$。一般的双环有 $k$ 条边 $k$ 个槽（边数 $\ge$ 槽数 $+ 1$），概率为 $n^k m^k / m^{2k+2}$。当 $m = cn$（$c > 1$）时，总的双环概率为 $O(1/n)$
• $\Pr[\text{路径} \ge 2\log n] \le 1/n^{\Omega(1)}$

因此 $\mathbb{E}[T] \le O(1) + O(1/n) \cdot n \cdot \mathbb{E}[T]$，解出 $\mathbb{E}[T] = O(1)$。

Cuckoo Hashing 性能总结

指标	复杂度
空间	$O(n)$
查询	2 次内存访问（最坏情况）
插入	期望摊还 $O(1)$

Succinct Dictionaries

从最优到极致

到目前为止，FKS 和 cuckoo hashing 都实现了 $O(n)$ 字的空间——但这里的「字」是 $O(\log N)$ 比特，总空间为 $O(n\log N)$ 比特。信息论下界也是 $\Theta(n\log N)$ 比特（表示一个 $n$ 元子集需要 $\log\binom{N}{n}$ 比特）。

方案	空间	查询时间	更新时间
平衡搜索树	$O(n\log N)$ 比特	$O(\log n)$	$O(\log n)$
链式哈希	$O(n\log N)$ 比特	期望 $O(1)$	期望 $O(1)$
一级完美哈希	$O(n^2\log N)$ 比特	$O(1)$	—
FKS 二级完美哈希	$O(n\log N)$ 比特	$O(1)$	$O(1)$
Cuckoo 哈希	$O(n\log N)$ 比特	2 次访问	期望摊还 $O(1)$
Succinct dictionary	$(1+o(1))n\log N$ 比特	$O(1)$	$O(1)$

Succinct dictionary 追求的是空间的极致——不仅是 $O(n\log N)$，而是 $(1 + o(1))$ 倍的信息论下界。这意味着冗余空间（overhead）是 $o(n\log N)$ 比特。

FKS 的空间精析

FKS 的实际空间由两部分组成：

• 一级指针与哈希参数：$O(n\log n)$ 比特
• 原始数据：$n \cdot v$ 比特（$v = \log N$ 是每个元素的存储位数）

当 $\log n \ll v$（即元素位宽远大于地址位宽）时，一级开销 $n\log n$ 相对于数据 $nv$ 是低阶项，FKS 本身就是 succinct 的。但当 $v$ 与 $\log n$ 同阶时，overhead 就不可忽略了。

Small Dictionary

核心思路：将 $n$ 个元素分到 $n/m$ 个桶中（$m = \log n / \log\log n$），每个桶作为一个「小字典」。

为什么选这个 $m$？因为 $m$ 个键只需 $O(m\log N)$ 比特存储，而 $m = O(\log n / \log\log n)$ 意味着整个小字典可以装进 $O(\log n)$ 比特——恰好是常数个机器字（字长 $\Omega(\log n)$）。在常数个机器字内，查找、插入等基本操作都可以用位操作在 $O(1)$ 时间内完成（可能需要一个 $n^{1/3}$ 比特的预计算查找表）。

由 Chernoff bound，取 $\delta = \Omega(\log\log n / \sqrt{\log n})$，桶负载超过 $(1+\delta)m$ 的概率为 $\exp(-m\delta^2/2)$。少数溢出的元素（总计约 $n / \text{polylog}\,n$ 个）用前缀树（trie）处理。

具体地，溢出元素的处理分为两级：先将 $n' = n/\log^9 n$ 个溢出元素再次分桶（$n'$ 个球进 $n'$ 个桶），每个桶最多 $O(\log n / \log\log n)$ 个键（由直接的二项分布尾界保证，概率 $\exp(-\Omega(\log n))$）。

Trie 的空间分析：假设键是随机的，每次插入在 trie 上生长 $k$ 层的概率为 $2^{-k}$（几何分布）。插入 $n'$ 个键后，trie 的节点数以高概率为 $O(\log n)$，因此整棵 trie 可以用 $O(\log n)$ 比特编码——这是一棵非常小的二叉树。

总冗余空间：

• 桶内小字典的冗余：$O(\delta n)$ 个字 $= O(\delta n \log(N/n))$ 比特（可以用 Feistel 网络进一步压缩）
• 溢出处理：$O(n'\log n) = O(n/\log^8 n)$ 比特
• 总计 $= o(n\log N)$ 比特

Chernoff Bound 的推广

上面所有的分析都假设完全独立的哈希函数——但正如我们所见，$k$-wise 独立哈希只能用 $O(k)$ 的时间和空间实现。在 succinct dictionary 的构造中，我们需要在有限独立下仍然得到 Chernoff 级别的集中度保证。这就引出了 Chernoff bound 的推广。

有限独立下的 Chernoff

标准 Chernoff bound 要求随机变量完全独立。但在哈希应用中，我们往往只有 $k$-wise 独立。能否在有限独立下得到类似的集中不等式？

$k$-wise 独立下的 Chernoff Bound

设 $X_1, \ldots, X_n \in \{0,1\}$ 为 $k$-wise 独立的，$X = \sum X_i$，$\mu = \mathbb{E}[X]$。对任意 $\delta > 0$，只要 $k \le \mu\delta/(1 - \mu/n)$：

$$\Pr[X \ge (1+\delta)\mu] \le \frac{\binom{n}{k}(\mu/n)^k}{\binom{(1+\delta)\mu}{k}}$$

这个界的形式不如经典 Chernoff 简洁，但关键信息是：$k$-wise 独立足以给出有意义的尾概率界，只要 $k$ 足够大。

从 MGF 到广义 Chernoff

经典 Chernoff 的证明利用 MGF $\mathbb{E}[\e^{tX}]$，通过选择最优的 $t$ 来最小化上界。这里的 $\e^{tX} = \sum_{k \ge 0} (tX)^k / k!$ 涉及 $X$ 的所有阶矩——因此需要完全独立。

广义 Chernoff 的思路是：能否找到一个只依赖前 $k$ 阶矩的「替代 MGF」？

核心观察：$\e^{tX}$ 可以改写为 $\sum_{i \le n} \alpha_i \sum_{j_1 < \cdots < j_i} X_{j_1} \cdots X_{j_i}$（其中 $\alpha_i \ge 0$）。如果 $X_1, \ldots, X_n$ 只是 $k$-wise 独立的，那么 $\mathbb{E}[X_{j_1} \cdots X_{j_i}]$ 只在 $i \le k$ 时可以精确计算。

广义 Chernoff 的策略是：不再使用所有的 $\alpha_i$，而是只保留一项——选择使上界最紧的那个 $i$：

1. 用 Markov 不等式得到上界 $\Pr[X \ge a] \le \dfrac{\sum_i \alpha_i \mathbb{E}\left[\binom{X}{i}\right]}{\sum_i \alpha_i \binom{a}{i}}$
2. 观察到对每个 $i$，比值 $\binom{n}{i}(\mu/n)^i / \binom{a}{i}$ 的大小不同——当 $i$ 增大时先减后增
3. 在最优点 $i^* = (a - \mu)/(1 - \mu/n)$ 处取到最小值
4. 令 $\alpha_{i^*} = 1$，其余 $\alpha_i = 0$

这样只需要 $i^*$-wise 独立就够了。当 $k \ge i^*$ 时，就得到了上面的 $k$-wise 独立 Chernoff bound。

独立性的代价

$k$-wise 独立哈希的求值时间和存储空间都是 $O(k)$。不同应用需要的独立性程度不同：

应用	所需独立度
链式哈希 / 最大负载	$\Theta(\log n / \log\log n)$
线性探测	$\le 5$（充分），$\ge 5$（必要）
Cuckoo 哈希	$O(\log n)$
$F_2$ 估计	4
Min-wise 独立	$\Theta(\log(1/\varepsilon))$
Siegel（1989）证明了一个下界：如果求值时间为 $t < k$，则存储空间需要 $	U	^{1/t}$；特别地，$\Omega(1)$-universality 在$O(1)$时间内需要$	U	^{\Omega(1)}$空间。这说明通用的$k$-wise 独立哈希不可能同时做到低独立度开销和高效求值。

Tabulation Hashing

Siegel 的下界似乎说明了高效哈希是不可能的——但实践中有一种方法工作得出奇地好。

构造

Tabulation Hashing（Zobrist, 1979）

将键 $x \in [u^c]$ 分解为 $c$ 个字符 $x = (x_1, \ldots, x_c)$，$x_i \in [u]$。维护 $c$ 个完全随机的查找表 $T_1, \ldots, T_c\colon [u] \to [m]$。哈希值为

$$h(x) = T_1[x_1] \oplus T_2[x_2] \oplus \cdots \oplus T_c[x_c]$$

其中 $\oplus$ 表示按位异或（XOR）。

• 空间：$cu$ 个字
• 求值时间：$O(c)$（$c$ 次查表 + $c-1$ 次 XOR）

以 32 位键为例，取 $c = 4$，$u = 256$（每个字符 1 字节）。每个查找表 $256$ 个条目，总共 $4 \times 256 = 1024$ 个字——轻松放进 L1 缓存。求值只需 4 次查表和 3 次 XOR，在现代硬件上只需约 5 纳秒。

独立性分析

Tabulation hashing 是 3-universal 的，但不是 4-universal 的。

3-universal 的证明思路：对于任意三个不同的键 $x, y, z$，它们之间至少有一个坐标 $i$ 使得三者的第 $i$ 个字符互不相同。$T_i$ 在这三个字符上的取值是完全随机的，提供了所需的独立性。

但 4-universal 可以被显式反例击破：取四个键 $(a_1, a_2)$, $(a_1, b_2)$, $(b_1, a_2)$, $(b_1, b_2)$，则

$$h(a_1, a_2) \oplus h(a_1, b_2) \oplus h(b_1, a_2) \oplus h(b_1, b_2) = 0$$

恒成立（每个 $T_i$ 的每个条目恰好出现偶数次，XOR 全部抵消）。因此四个哈希值不可能独立。

为什么它仍然有效：Peelability

尽管只有 3-wise 独立，tabulation hashing 在实践中（以及理论上）对许多应用都工作得很好——包括本来需要更高独立性的 cuckoo hashing 和线性探测。

关键概念是可剥离性（peelability）。

Position Character 与独立性

对于键 $x$ 和一组其他键 $\{y_1, y_2, \ldots\}$，如果存在坐标 $i$ 使得 $x_i \ne y_{j,i}$ 对所有 $j$ 成立，则称 $(i, x_i)$ 是 $x$ 关于该集合的 position character。

当 $x$ 有 position character 时，$h(x)$ 独立于 $\{h(y_j)\}$——因为 $T_i[x_i]$ 只出现在 $h(x)$ 中，不影响其他键的哈希值。

一个集合 $S$ 是可剥离的（peelable），如果 $S$ 中每个元素都有 position character。

Peeling 过程的思路是：

1. 在集合 $S$ 中找到一个有 position character 的元素 $x$，$h(x)$ 独立于其余元素
2. 将 $x$ 「剥离」出去，对 $S \setminus \{x\}$ 递归
3. 每次剥离都得到一层独立的元素

这使得我们可以将原本需要全局独立性的分析分解为层层独立的分析。虽然每次剥离出的独立集不是全局独立的，但可以利用条件期望的性质——$\mathbb{E}[X_\alpha \mid X_\beta = x_\beta, \ldots] = \mathbb{E}[X_\alpha]$——配合 Chernoff bound 的推广（对有固定期望但非独立的随机变量），得到与完全独立相同的集中度保证。

可剥离子集大小的下界：对于任意 $|S| = d$ 的集合，存在一个可剥离子集，大小至少为 $\max\{d^{1/c}, \log_2 d\}$。

• $d^{1/c}$ 的证明：$S \subseteq S_1 \times \cdots \times S_c$，存在某个 $i$ 使得 $|S_i| \ge |S|^{1/c}$
• $\log_2 d$ 的证明：递归——只要 $|S| > 1$，就能找到某个 $|S_i| > 1$，挑出一个元素后集合至少减半

结合 balls-into-bins 的分析和 Chernoff bound 的推广形式，可以证明 tabulation hashing 在以下应用中达到与最优 $k$-wise 独立哈希相同的性能。具体地，peeling 分析需要一个对 $[0, d]$ 有界随机变量的 Chernoff 变体：

Chernoff Bound for Bounded Variables with Fixed Means

设 $X_1, X_2, \ldots$ 为 $[0, d]$ 中的随机变量（不要求独立，但期望固定），$\mu = \mathbb{E}[\sum X_i]$。则

$$\Pr\left[\sum X_i \ge (1+\delta)\mu\right] \le \left(\frac{\e^\delta}{(1+\delta)^{1+\delta}}\right)^{\mu/d}$$

这与标准 Chernoff 的区别在于指数从 $\mu$ 变成了 $\mu/d$——每个变量的范围越大，集中度越弱。

Peeling 的每一层剥离出一个独立集 $S_\alpha$，其大小 $|S_\alpha| \le n^{1-1/c}$。在 $n \le m^{1-\varepsilon}$ 的条件下（即桶数远多于元素），$S_\alpha$ 中有 $d$ 个球落入某个桶的概率不超过 $m^{1-\varepsilon t/c}$（其中 $t$ 是 peeling 的层数）。逐层累积，最终得到与完全独立相同量级的最大负载保证。

应用	Tabulation 的保证
链式哈希 / 最大负载	$O(\log n / \log\log n)$
线性探测	$O(1)$ 期望
Cuckoo 哈希	$O(1)$ 期望摊还插入
$F_2$ 估计	无偏，方差 $\le 2F_2^2$
Min-wise 独立	$O(\log(1/\varepsilon))$-近似

理论与实践的桥梁

Tabulation hashing 是一个理论与实践完美结合的例子：

• 实践上：极快（几纳秒），缓存友好，实现简单
• 理论上：只有 3-wise 独立，但通过 peelability 分析可以证明它对几乎所有常见应用都「够好」

这提醒我们，独立性不是越高越好——关键是结构化的独立性能否被利用。

总结

flowchart TD
    BB["Balls into Bins<br>随机函数模型"] --> OCC["Occupancy Problem<br>最大负载 O(log n/log log n)"]
    BB --> BD["Birthday Paradox<br>碰撞阈值 √m"]
    BB --> POW["Power of Two Choices<br>最大负载 O(log log n)"]

    BD --> UH["Universal Hashing<br>用 O(log N) 比特<br>模拟「足够好」的随机"]
    OCC --> UH

    UH --> CH["链式哈希表<br>期望 O(1) 查询"]
    UH --> PH["Perfect Hashing<br>O(1) 最坏查询"]
    UH --> CK["Cuckoo Hashing<br>O(1) 查询 + 动态"]

    PH --> FKS["FKS 两级方案<br>O(n) 空间"]
    FKS --> SD["Succinct Dictionary<br>(1+o(1))·OPT 空间"]

    POW --> CK

    UH --> TAB["Tabulation Hashing<br>3-universal 但<br>实践中够用"]

    classDef model fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef result fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    classDef hash fill:#f3e5f5,stroke:#4a148c,stroke-width:2px
    classDef structure fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef advanced fill:#fce4ec,stroke:#c62828,stroke-width:2px

    class BB model
    class OCC,BD,POW result
    class UH,TAB hash
    class CH,PH,CK,FKS structure
    class SD advanced

本讲围绕一个核心问题展开：如何用有限的随机资源实现高效的字典数据结构？

从 balls into bins 的概率模型出发，我们建立了分析哈希表性能的理论工具（Chernoff bound、birthday paradox）。Universal hashing 回答了「多少随机性足够」的问题：2-wise 独立就足以支撑大多数基本应用。

在此基础上，我们看到了三条不同的优化路线：

• 查询时间最优：FKS perfect hashing — $O(1)$ 最坏查询，$O(n)$ 空间，但静态
• 动态最优：Cuckoo hashing — $O(1)$ 最坏查询，期望摊还 $O(1)$ 插入
• 空间极致：Succinct dictionary — $(1+o(1))$ 倍信息论下界

最后，tabulation hashing 展示了一个深刻的洞见：独立性的「质」比「量」更重要——精心设计的 3-wise 独立哈希在实践和理论上都能匹配需要更高独立性的方案。