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, \dots, 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, \dots, 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）：不是将请求随机分配到一台服务器，而是随机选两台、挑负载低的那台。

严格证明

严格证明采用逐层归纳的策略：定义「负载至少为 $i$ 的桶数」为 $\nu_i$，并设置一个递减的阈值序列 $\beta_i$。希望证明：对每个 $i$，事件 $\mathcal{E}_i \colon \nu_i \le \beta_i$ 同时成立的概率至少为 $1-O(1/n)$。一旦 $\beta_i$ 降到 $<1$，就意味着没有桶的负载能达到 $i$，从而最大负载 $L < i$。

定义阈值序列 $\beta_6 = n/6, \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)$。

• $\nu_i$ ：负载 $\ge i$ 的桶的数量（随机变量）
• $\beta_i$：$\nu_i$ 的阈值，满足 $\nu_i \le \beta_i$，是确定性数列。
• $\mathcal{E}_i$：事件 $\left\lbrace \nu_i \le \beta_i\right\rbrace$，是随机事件。

通过构造一个上界序列 $\beta_i$，希望逐层证明 $\mathcal E_i$ 大概率成立，最终如果某个 $\beta_i<1$，那就意味着 $\nu_i=0$。

递推式 $\beta_{i+1} = 2\e\beta_i^2/n$ 来自于前面的直觉分析：$\nu_{i+1} \approx \nu_i^2 / n$，为了使用 Chernoff bound，阈值通常取成期望的一个常数倍，这里是 $2\e$，从而可以使用 $\Pr(X \ge L) \le 2^{-L}\quad(L \ge 2\e \mu)$。

在 two choices 下，只有当这个球的两个候选桶都已经负载至少 $i$ 才会制造一个 $(i+1)$-高桶。所以，在任意时刻，如果当前负载 $\ge i$ 的桶数不超过 $\beta_i$，那么一个新球「进入 $i$-高桶」的条件概率最多是 $\left(\beta_i / n\right)^2$

总共有 $n$ 个球。对每个球来说，「把某个桶抬到 $i+1$ 层」的概率都至多是 $(\beta_i/n)^2$。因此给定 $\mathcal{E}_i$，落入负载 $\ge i$ 的桶的球数近似 $\mathrm{Bin}(n, \beta_i^2/n^2)$。

严格说这些事件不是独立的，所以不能说「恰好服从」二项分布；更准确的说法是：

在事件 $\mathcal E_i$ 下，$\nu_{i+1}$ 可以用 $\mathrm{Bin}\left(n,\beta_i^2/n^2\right)$ 来支配。即

$$\nu_{i+1}\preceq\mathrm{Bin}\left(n,\frac{\beta_i^2}{n^2}\right)$$

令 $X \sim \mathrm{Bin}(n, \beta_i^2 / n^2),\, \mu = \mathbb{E}[X] = \beta_i^2 / n$，于是由 Chernoff 上尾界 $\Pr[X \ge 2\e\mu] \le 2^{-2\e\mu}$，从而有

$$\Pr[X \ge \beta_{i+1}] = \Pr[X \ge 2\e\mu] \le 2^{-2\e\mu} = 2^{-2\e\beta_i^2/n}$$

即

$$\Pr[\lnot\mathcal{E}_{i+1} \mid \mathcal{E}_{\le i}] \le 2^{-2\e\beta_i^2/n}$$

第一种情况：当 $\beta_i^2/n \ge \log_2 n$ 时，$\Pr[\lnot\mathcal{E}_{i+1} \mid \mathcal{E}_{\le i}] \le 1/n^{2\e}$，这是一个足够小的失败概率。由于需要考虑的层数只有 $O(\log\log n)$ 层，因此对所有层做 union bound 仍有 $\Pr\left[\bigwedge_i \mathcal E_i\right]\ge 1-O(1/n)$。

第二种情况：当 $\beta_i^2 / n < \log_2 n$ 时，有 $\nu_i \le \beta_i < \sqrt{n \log_2 n}$，这时候高层桶的数量已经非常少了。继续递推，期望只有 $\mu_i = \beta_i^2 / n < \log_2 n$，即 $\nu_{i+1}$ 急剧缩小到 $O(\log n)$ 量级。由 Chernoff bound，存在常数 $C > 2\e$（如 $C=6$）使得

$$\Pr[\nu_{i+1} \ge C\log_2 n \mid \mathcal{E}_i] \le 2^{-C\log_2 n} = \frac{1}{n^C} \le \frac{1}{n^2}$$

若进一步有 $\nu_{i+1} < C \log n$，则一个球被抬到 $i+2$ 层的概率至多是 $(C\log n / n)^2$，因此 Markov 不等式给出

$$\Pr[\nu_{i+2} \ge 1 \mid \nu_{i+1} < C \log n] \le n \left(\frac{C\log n}{n}\right)^2 = O\left(\frac{\log^2 n}{n}\right)$$

因此再往上两层，$\nu_{i+2} = 0$ 的概率至少为 $1 - O(\log^2 n / n)$。从而 $\Pr[\mathcal{E}_{i+2} \mid \mathcal{E}_i] \ge 1 - O(\log^2 n / n)$，几乎不可能再出现负载至少 $i+2$ 的桶。

在情况一中，阈值满足递推

$$\beta_{i+1}=\frac{2e\beta_i^2}{n}$$

这表明 $\beta_i/n$ 以「平方」的速度衰减；也就是说，每升高一层，「高层桶所占比例」大致会平方一次。因此经过 $j$ 层后，这个比例大约形如 $\frac{\beta_{6+j}}{n}\le 2^{-2^j}$（忽略常数因子）。

当 $\frac{\beta_i^2}{n}<\log n$ 时，就进入情况二。由上述双指数衰减可知，这发生在 $i=\log_2\log n+O(1)$ 层附近。

进入情况二后，再经过至多两层，负载达到该层的桶数就降为 0。因此再多经过常数层后，就以高概率不存在负载达到该层的桶。

综上，最大负载满足

$$L_{\max}\le \log_2\log n + O(1) \qquad \text{with high probability}$$

Birthday Paradox

经典分析

Birthday paradox（生日佯谬）是 balls into bins 最经典的应用：在一个班级中，58 个人就有超过 $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 \exp(-x)$（当 $x = o(1)$ 时）：

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

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

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

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

成对独立下的 Birthday Paradox

上面的分析需要球的位置完全独立。如果我们只有 2-universal 哈希函数（成对独立，$\Pr[h(x_i) = h(x_j)] \le \frac{1}{m}$），还能得到类似的结论吗？

定义碰撞数 $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 \sum_{i<j} \dfrac{1}{m} = \binom{n}{2} \cdot \frac{1}{m} = \frac{n(n-1)}{2m} \le \frac{n^2}{2m}$$

当 $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, \dots, 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, \dots, x_k \in U$：

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

更强的版本：$\mathcal{H}$ 是 strongly $k$-universal（$k$-wise 独立）的，如果对任意 $\le k$ 个不同元素和任意目标值 $y_1, \dots, 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, \dots, 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)$。思路是使 $n = \sum_i n_i,\, \sum_i n_i^2 = O(n)$。

FKS Perfect Hashing

分级：

1. 第一级：用 2-universal 哈希 $h\colon [N] \to [n]$ 将 $n$ 个元素分到 $n$ 个桶中，桶 $i$ 收到的元素集合记为 $B_i$（有碰撞）
2. 第二级：对每个桶 $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 LR
    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 \dots 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 TB
    subgraph fail["插入失败"]
        direction LR
        d1["双环"] --- d1a["无法分配，需重建"]
        l1["过长路径"] --- l1a["踢移代价过高"]
    end

    subgraph success["插入成功"]
        direction LR
        p1["路径"] --- p1a["x → a → b → c → 空"]
        c1["单环"] --- c1a["可沿环旋转腾出位置"]
    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

插入一个元素相当于在图中增加一条新边，然后尝试为所有边（元素）分配一个端点（槽位），使得每个顶点最多被一条边占用（每个槽位最多存一个元素）。这个分配过程沿着图上的路径或环进行：

• 路径：从新元素的一个槽位出发，沿已占用的边走到另一个槽位，再沿该槽位对应的元素的另一条边……最终遇到空槽位，即可顺次移动，插入成功。
• 单环：若路径形成一个环（没有空槽），但环上每个顶点恰好连两条边（每个槽位两个可能的位置），则可以将环上所有元素旋转一圈，从而腾出一个位置，插入成功。
• 双环：两个环共享一个顶点，或者更一般地，连通分量中边数 ≥ 顶点数 + 1^[1]，此时无法通过踢移完成分配，需要重建。
• 过长路径：即使最终能成功，但踢移次数太多（如超过对数级），也会触发重建以保持性能。

期望插入时间分析

核心引理

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

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

更具体一点，假设有 $k$ 个旧元素被依次踢走，那么路径可以写成：

$$x,\ s_0,\ y_1,\ s_1,\ y_2,\ s_2,\ \dots,\ y_k,\ s_k$$

这里：

• $x$ 是新插入元素
• $y_1,\dots,y_k$ 是被依次踢走的元素
• $s_0,\dots,s_k$ 是经过的槽位
• 路径长度可以理解为有 $k$ 次「踢替」。

最后如果 $s_k$ 是空槽，就成功了。

对新元素 $x$，它必须能从 $s_0$ 开始，也就是 $h(x)$ 或 $g(x)$ 必须等于 $s_0$，这大致给出一个 $1/m$ 量级的概率约束（$\frac{2}{m}$）。

对每个被踢走的元素 $y_i$，它必须恰好连接相邻两个槽位，即 $y_i \leftrightarrow (s_{i-1}, s_i)$。也就是说 $y_i$ 的两个哈希位置必须正好是这两个槽位。如果哈希函数独立且均匀，那么这件事的概率大约是 $\Theta(1/m^2)$，因为它的两个哈希值都得命中指定位置。所以 $k$ 个元素总共给出大约 $(1/m^2)^k = 1/m^{2k}$ 的概率约束。

再乘上新元素开始位置那个 $1/m$，得到 $1/m^{2k+1}$。

长度 $\ge k$ 的路径存在的概率需要对所有可能的路径求联合界：对长度为 $k$ 的插入路径做粗略计数：每一层至多选择一个 key 和一个 slot，因此候选序列数可由 $(nm)^k$ 上界^[2]，每条概率 $\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)$，即负载因子 $n / m = \Theta(1) = c < 1$，是 $c^k$ 级别的衰减。

同理，$\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)$^[3]
• $\mathbb{E}[\text{环长度}] \le O(1)$，计算方法同上
• $\Pr[\text{双环（更一般地，坏连通分量）}]$：更一般地，设某个坏连通分量有 $v$ 个槽、$e$ 条边，且 $e \ge v+1$（即边数至少比顶点数多 1）。
  • 固定这样一个分量后，选择其边和顶点的方式至多有 $n^e m^v$ 种，而每条边必须恰好连接指定的两个端点，概率为 $m^{-2e}$，因此该结构出现的概率至多 $\frac{n^e m^v}{m^{2e}}$。
  • 由于 $e \ge v+1$，有 $v \le e-1$，于是 $\frac{n^e m^v}{m^{2e}}\le\frac{n^e}{m^{e+1}}$。
  • 当 $n=c m\quad (c<1)$ 时，$\frac{n^e}{m^{e+1}} = \frac{1}{m}\left(\frac{n}{m}\right)^e = \frac{1}{n}c^{e+1}$。
  • 对所有可能的 $e$ 求和，即 $\sum\limits_{e=1}^n c^{e+1} \frac{1}{n} \le \frac{1}{n} \sum\limits_{e\ge 1} c^{e+1} = O\left(\frac{1}{n}\right)$，得到总的双环概率为 $O(1/n)$。
• $\Pr[\text{路径} \ge 2\log n] \le \exp(-\Omega(\log n)) = 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_2\binom{N}{n}$ 比特）^[4]。

方案	空间	查询时间	更新时间
平衡搜索树	$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)$

表面上 FKS 已经追平了信息论下界的数量级 $\Theta(n \log N)$，但 Succinct dictionary 追求的是一个更精细的目标：不仅是 $O(n\log N)$ 比特，而是 $(1 + o(1))$ 倍的信息论下界。换句话说，冗余（overhead）要比主项严格低阶：

$$\text{总空间} = \underbrace{\log_2 \binom{N}{n}}_{\text{信息论下界}} + \underbrace{o(n\log N)}_{\text{低阶冗余}}$$

这几乎是空间复杂度的「天花板」：信息论告诉我们冗余不能是负的，而 succinct 意味着冗余是主项的 $o(1)$ 倍。在海量小字典、只读索引等空间敏感的场景中，这个改进是实打实的。

FKS 究竟浪费在哪

FKS 看起来已经达到 $O(n \log N)$ 比特，那还能怎么挤出空间？关键是把「实际存储」拆开看。

设每个元素占 $v$ 比特（通常 $v = \log N$）。FKS 的空间由两部分构成：

• 原始数据：$n$ 个元素，每个 $v$ 比特，共 $n v$ 比特
• 结构开销：一级/二级桶的哈希参数、桶边界指针、表大小描述等，合计 $O(n \log n)$ 比特——每个元素大致需要 $O(\log n)$ 比特来「定位自己」

于是

$$\text{FKS 总空间} = n v + O(n \log n) = n v \cdot \left(1 + O\left(\tfrac{\log n}{v}\right)\right) \text{ 比特}$$

关键观察：当 $\log n \ll v$（元素位宽远大于索引位宽），结构开销 $O(n \log n)$ 相对于数据 $nv$ 只是低阶项，FKS 自动就是 succinct 的。比如用 FKS 维护 $n = \operatorname{polylog}(N)$ 个 key，开销 $O(n \log n) = O(n \log\log N) = o(n \log N)$。

但当 $v$ 与 $\log n$ 同阶（比如 key 就是个小整数，$N = n^{O(1)}$），情形就糟糕了：结构开销与数据本身相当，FKS 不再 succinct。这就是我们要攻克的情形。

换个角度看：FKS 为每个桶维护一整套二级数据结构——哈希函数参数、表大小、表内容指针等。这套「结构」的开销与桶内元素数无关：桶里即便只有一两个元素，也得照付一整套。桶数大、每桶元素少时，这种「为每桶付一份结构税」的方式就显得浪费。

Succinct 的思路：把每个桶压成「一个字」

既然 FKS 的浪费来自「为每个桶维护传统数据结构」，一个激进的想法是：当桶足够小时，干脆不要结构，而是把整个桶直接编码成一小块连续的比特，查询时在这块比特上用位运算直接搜。

Word RAM 模型

假设机器字长为 $w$ 比特，且 $w \ge \log_2 (\text{问题规模})$——本节约定 $w = \Theta(\log n)$。模型给出两条关键假设：

• 一个字内的算术 / 逻辑 / 位运算（加、比较、AND、XOR、移位等）都在 $O(1)$ 时间完成
• 更强地，对一个字内的数据做几乎任意的「固定函数」，都可以靠预计算查找表在 $O(1)$ 次访存内完成。一张 $n^{1/3}$ 比特量级的表就足以支撑常见的小字内操作

直觉：字长只有 $\Theta(\log n)$ 比特，一个字里能装的信息不过 $O(\log n)$ 比特；对这么少的信息做查询，本质上只是在一个 $n^{O(1)}$ 大小的函数表里查一次——$O(1)$ 时间是合理的。

这条性质决定了一个核心尺寸选择：把桶编码到 $O(\log n)$ 比特（即一个机器字），则桶内查询可以 $O(1)$ 时间完成。反推桶能装多少元素——这里直接接受一个非平凡的结论（完整论证依赖后文的 Feistel 压缩）：

小字典的目标

经过合适的编码，可以把 $m = \log n / \log\log n$ 个 key 用 $O(\log n)$ 比特存储，且支持 $O(1)$ 字内查询。

这个数字 $m = \log n / \log\log n$ 不是随意选的：它是让上述编码目标成立的典型尺寸。

直觉：落入同一个桶的 key 共享哈希值，所以桶索引已经「带了一半信息」，桶内只需存每个 key 的「差异部分」。这部分差异能压得多紧，决定了 $m$ 能取多大——具体的压缩由 Feistel 网络完成，见本节末尾。

带着这个假设，整个 Succinct 字典的骨架就清晰了：

1. 把 $n$ 个元素分到 $n/m$ 个主桶（每桶 $m = \log n / \log\log n$ 个 key，编码 $O(\log n)$ 比特）
2. 分析溢出——一些桶会超过 $m$ 个 key
3. 溢出元素用另一种数据结构（trie）处理
4. 把所有冗余加起来，证明 $o(n \log N)$

第一次尝试：大桶方案的失败

先看一个直观但不完全成功的方案：取 $m = \log^3 n$，把 $n$ 个元素分到 $n / \log^3 n$ 个桶。每桶期望负载 $\mu = m = \log^3 n$。用 Chernoff 上尾界（简化形式 $\exp(-\mu \delta^2 / 3)$，上节中「$0 < \delta < 1$」那一支），取 $\delta = 2/\log n$：

$$\Pr\left[\text{某桶负载} \ge (1 + \tfrac{2}{\log n}) \log^3 n\right] \le \exp\left(-\tfrac{\mu \delta^2}{3}\right) = \exp\left(-\tfrac{\log^3 n \cdot 4/\log^2 n}{3}\right) = \exp\left(-\tfrac{4\log n}{3}\right) = n^{-4/3}$$

课件用稍紧的 $\exp(-\mu\delta^2/2)$ 给出 $n^{-2}$，差异仅在常数，都是多项式小。联合界（$n/\log^3 n$ 个桶）给出最大负载 $\le (1 + 2/\log n)\log^3 n$ 以高概率。

设 $n' \coloneqq (1 + 2/\log n)\log^3 n$ 为每桶允许的最大 key 数。每桶用一个 small dictionary 存这些 key，其结构冗余（即 key 本身需要的 $n'v$ 比特之外所多占的空间，来自哈希参数、桶内指针等）约为 $O(n' \log n')$ 比特。两类冗余汇总：

$$\underbrace{(n/\log^3 n) \cdot O(n' \log n') \coloneq \textcolor{ff0099}{O(n\log\log n)}}_{\text{所有桶的结构冗余}} + \underbrace{\textcolor{ff0099}{(2/\log n) \cdot n \log N}}_{\text{$\delta$ 预留的空位}} = o(n \log N)$$

从空间上看似乎已经 succinct 了。但致命问题在查询时间：

• 每桶要装 $\log^3 n$ 个 key，即便用桶索引「吸收」部分信息（quotienting），剩下的商 $q$ 每个至少 $\Omega(1)$ 比特，桶总编码 $\gg \log n$ 比特
• 更直白地：桶编码大约 $\log^3 n \cdot (\text{每 key 的最小商位数})$ 比特，远远超过一个机器字（$\log n$ 比特）

这意味着桶内查询要跨越多个字，桶内基本操作不再是 $O(1)$——前面 Word RAM 的「$n^{1/3}$ 比特查找表」只覆盖单个字大小的数据，桶一旦跨字这个加速就不适用了。

为了让查询回到 $O(1)$，必须收紧 $m$，让每桶编码恰好塞进一个字。

正确选择：$m = \log n / \log\log n$ 与可控溢出

取 $m = \log n / \log\log n$，把 $n$ 个元素分到 $n / m$ 个桶。这个 $m$ 是让「每桶编码 $\le O(\log n)$ 比特」成立的几乎最大值，每桶恰好能在 $O(1)$ 次字内操作内查询（借助预计算表）。

代价是：桶容量更小，会出现溢出，即某些桶装不下所有落入它的元素。我们允许这部分元素「溢出」，交给另一套机制处理。

先量化溢出。每桶期望负载 $\mu = m$。目标：选一个 $\delta$，使 Chernoff 上尾界给出足够小的失败概率。取 $\delta = c \log\log n / \sqrt{\log n}$（常数 $c$ 暂时悬空，稍后确定），用上尾简化形式 $\exp(-\mu\delta^2/3)$：

$$\Pr[\text{某桶负载} \ge (1 + \delta)m] \le \exp\left(-\tfrac{m\delta^2}{3}\right)$$

把 $m, \delta$ 代入指数：

$$\frac{m \delta^2}{3} = \frac{1}{3} \cdot \frac{\log n}{\log\log n} \cdot \frac{c^2 (\log\log n)^2}{\log n} = \frac{c^2 \log\log n}{3}$$

所以

$$\Pr[\text{某桶溢出}] \le \exp\left(-\tfrac{c^2 \log\log n}{3}\right) = (\log n)^{-c^2/3}$$

换句话说，$c$ 越大，溢出率多项式越小。稍后「溢出的两级处理」需要溢出率 $\le \log^{-9} n$（以便把所有溢出元素塞进 $n/\log^9 n$ 个次级桶），即 $c^2/3 \ge 9$，也就是 $c \ge \sqrt{27}$。取 $c = 6$ 就绰绰有余，且仍有 $\delta = o(1)$。

期望溢出元素数：由线性期望，每个元素独立以 $\le \log^{-12} n$ 的概率落入溢出桶，于是

$$\mathbb{E}[N_{\text{overflow}}] \le n \cdot \log^{-12} n = \frac{n}{\log^{12} n}$$

$\delta$ 这个数是怎么选出来的？

两个约束必须同时成立：

• 失败概率要足够小：后面「溢出的两级处理」把溢出元素分到 $n/\log^9 n$ 个次级桶，要保证每桶期望负载 $o(1)$，需要 $N_{\text{overflow}} \ll n/\log^9 n$——故溢出率 $\le \log^{-9}n$ 或更小，即 $m\delta^2/3 \ge 9\log\log n$
• $\delta$ 预留的空位不能太多：$\delta \cdot n\log N$ 是这套方案固有的冗余之一（第一次尝试里已经出现过），需要 $o(n\log N)$，即 $\delta = o(1)$

把 $m = \log n/\log\log n$ 代入第一个条件，解出 $c^2 \ge 27$。取 $c = 6$ 既满足此下界，也满足 $\delta = O(\log\log n / \sqrt{\log n}) = o(1)$。两个约束在此量级勉强兼容：$\delta$ 再小失败概率不够小，再大则预留空位主导冗余。

现在剩下的问题是：如何为 $O(n/\log^{12} n)$ 个溢出元素维护一个 succinct 字典？

前置：前缀树（Trie）

处理溢出用到的主要工具是前缀树（trie）。

前缀树

前缀树（trie）是一种按「共享前缀」组织字符串的多叉树。把每个 key 视为比特串 $x_1 x_2 \dots x_l$，trie 的构造如下：

• 根节点代表「空前缀」，每个内部节点代表一段前缀
• 从根节点开始，每一层按 key 的一个比特（0 或 1）决定往左还是往右走
• 插入 key 时，沿对应路径下行，遇到未创建的节点就新建，最终 key 对应树中一个叶子（或被标记的内部节点）

查询 / 插入时间是 $O(l)$（key 长度）。空间是所有 key 共享前缀之后的总节点数。

flowchart TD
    R(("ε")) --> N0(("0"))
    R --> N1(("1"))
    N0 --> N00(("00"))
    N0 --> N01(("01"))
    N01 --> L011["011"]
    N1 --> N10(("10"))
    N10 --> L100["100"]
    N10 --> L101["101"]
    N00 --> L001["001"]

    classDef root fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef node fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    classDef leaf fill:#fff3e0,stroke:#ef6c00,stroke-width:2px

    class R root
    class N0,N1,N00,N01,N10 node
    class L001,L011,L100,L101 leaf

标准 trie 有一个缺点：节点数可能远大于 key 数。比如只存 000011 这一个 key 就得建 6 层节点链——大量中间节点只有一个子节点，毫无信息量。

压缩 trie（compressed trie）通过「只保留真正分叉的节点」解决这个问题：

压缩 Trie

若一条路径上的节点只有一个子节点，则把这整段路径折叠成一条边（不再为其上每个比特建节点）。分叉点（两个或更多 key 在此处才分歧）仍保留为节点。

• 节点数 = 分叉数 $\le O(\text{key 数})$
• 插入沿路径下行，直到某个叶子；继续比较直到发现新的分歧点，在该处「生长」出一小段新路径，使两个 key 在此分开

我们要分析的，就是随机 key 下压缩 trie 的节点数——即「每次插入平均生长多少层」。

Trie 编码溢出元素：空间分析

假设 key 独立均匀随机（哈希后的残余对此近似成立）。考察第 $i$ 次插入所带来的「生长层数」 $G_i$：新 key 沿已有路径下行到叶子，与叶子上的旧 key 比较，从两者的首个不同位开始把路径延伸——二者共同前缀越长，这次延伸就越多。

单次生长的几何分布：两个独立均匀随机比特串前 $k$ 位一致的概率恰好是 $2^{-k}$，所以对 $k \ge 1$

$$\Pr[G_i \ge k] = 2^{-k}$$

对应的分布是 $\Pr[G_i = k] = 2^{-(k+1)},\, k = 0, 1, 2, \dots$（这是「做 Bernoulli($1/2$) 试验到第一次失败前的成功次数」的分布）。期望值

$$\mathbb{E}[G_i] = \sum_{k \ge 1} \Pr[G_i \ge k] = \sum_{k \ge 1} 2^{-k} = 1$$

这里用了非负整数随机变量的尾和公式 $\mathbb{E}[Y] = \sum_{k \ge 1}\Pr[Y \ge k]$。

累计生长：插入 $n'$ 个 key 后，压缩 trie 的总「生长层数」

$$G = \sum_{i=1}^{n'} G_i, \qquad \mathbb{E}[G] = n' \cdot \mathbb{E}[G_i] = n'$$

注意压缩 trie 的节点数 $\le n' + G$（$n'$ 个叶子 + $G$ 层生长出来的内部节点），所以节点数量级由 $G$ 决定。

尾界（用 MGF + Markov）：先算单个 $G_i$ 的 MGF。对 $\e^t < 2$：

$$\mathbb{E}\left[\e^{tG_i}\right] = \sum_{k \ge 0} \e^{tk} \cdot 2^{-(k+1)} = \frac{1}{2} \sum_{k \ge 0}\left(\frac{\e^t}{2}\right)^k = \frac{1}{2 - \e^t}$$

由独立性，$n'$ 个变量之和的 MGF 为各自 MGF 的乘积：

$$\mathbb{E}[\e^{tG}] = (2 - \e^t)^{-n'}$$

取一个具体的值 $\e^t = 3/2$（即 $t = \ln(3/2)$），则 $\mathbb{E}[\e^{tG_i}] = 2$，从而

$$\mathbb{E}[\e^{tG}] = 2^{n'}$$

由 Markov 不等式 $\Pr[\e^{tG} \ge \e^{ta}] \le \e^{-ta}\mathbb{E}[\e^{tG}]$，对任意 $a > 0$

$$\Pr[G \ge a] \le (3/2)^{-a} \cdot 2^{n'}$$

代入溢出处理的尺度：下一小节会证明，每个溢出桶中至多 $m = \log n/\log\log n$ 个 key。我们先以这个尺度代入——设 $n' = O(\log n / \log\log n)$，取 $a = C \log n$：

• $2^{n'} = 2^{O(\log n / \log\log n)} = n^{O(1/\log\log n)} = n^{o(1)}$
• $(3/2)^{-a} = n^{-C \log_2(3/2)} \approx n^{-0.58\, C}$

选 $C$ 足够大（例如 $C = 4$）：

$$\Pr[G \ge C\log n] \le n^{-\Omega(1)}$$

结论：高概率下，压缩 trie 的总节点数是 $O(\log n)$——这是一棵非常小的二叉树。

编码成比特：一棵有 $O(\log n)$ 节点的二叉树可以用 $O(\log n)$ 比特编码。最标准的办法是平衡括号编码：按 DFS 序遍历，每次进入一个节点写一个 (，退出一个节点写一个 )，共 $2 \cdot (\text{节点数})$ 个比特。再加上每个叶子处的「附加信息」（比如它对应的 key 是哪一部分），仍是 $O(\log n)$ 比特。所以这棵 trie 本身就是一个 succinct 结构。

溢出的两级处理

回到主线。现在情况是：

• 主表：$n / m$ 个桶，每桶编码 $\le O(\log n)$ 比特
• 溢出：$\le n / \log^{12} n$ 个 key 还没有家

如果为每个主桶各自挂一棵 trie，总共 $n / m$ 棵 $\times O(\log n)$ 比特 $= O(n \log\log n)$ 比特——已经接近 $n \log N$ 的数量级，浪费了。必须把所有溢出元素汇总后再次分桶。

取 $B \coloneqq n / \log^9 n$ 为溢出桶的个数（这里用 $B$ 以免与上一小节的 $n'$ 混淆），把溢出元素总数 $N_{\text{overflow}} \le n/\log^{12} n$ 映射到这 $B$ 个桶。选这个 $B$ 的目的有二：

1. 让每桶期望负载 $\le N_{\text{overflow}} / B \le 1/\log^3 n = o(1)$，从而以高概率每桶至多 $O(\log n / \log\log n)$ 个 key
2. 让总桶数 $B$ 足够小，使得「每桶一棵 $O(\log n)$ 比特 trie」的总空间仍是 $o(n \log N)$

最大负载分析：为简化，按「$B$ 个球进 $B$ 个桶」分析（真实球数 $N_{\text{overflow}} \le B/\log^3 n$ 远少于 $B$，结论只会更强）。对固定桶，

$$\Pr[\text{负载} \ge m] \le \sum_{k \ge m} \binom{B}{k} \left(\frac{1}{B}\right)^k$$

用 $\binom{B}{k} \le (B \e / k)^k$（标准的斯特林上界 $\binom{a}{b} \le (a\e/b)^b$）：

$$\binom{B}{k} \left(\frac{1}{B}\right)^k \le \left(\frac{\e}{k}\right)^k$$

尾部求和用几何级数粗化：考察相邻项比值

$$\frac{(\e/(k+1))^{k+1}}{(\e/k)^k} = \frac{\e}{k+1} \cdot \left(\frac{k}{k+1}\right)^k \xrightarrow{k\to\infty} \frac{\e}{k+1} \cdot \frac{1}{\e} = \frac{1}{k+1}$$

当 $k \ge m$ 且 $m$ 充分大（譬如 $m \ge 2$），这个比值 $\le 1/2$，整个尾部被首项 $(\e/m)^m$ 的 2 倍控制：

$$\Pr[\text{负载} \ge m] \le \sum_{k \ge m} \left(\frac{\e}{k}\right)^k \le 2 \cdot \left(\frac{\e}{m}\right)^m = \exp\big(\ln 2 - m(\ln m - 1)\big) = \exp(-\Omega(m \log m))$$

取 $m = \log n / \log\log n$，则

$$m \log m = \frac{\log n}{\log\log n} \cdot \log\left(\frac{\log n}{\log\log n}\right) = \frac{\log n}{\log\log n} \cdot (\log\log n - \log\log\log n) \sim \log n$$

所以单桶失败概率 $\le \exp(-\Omega(\log n)) = n^{-\Omega(1)}$。联合界（$B \le n$ 个桶）之后总失败概率仍是 $n^{-\Omega(1)}$——以高概率，每个溢出桶的负载都不超过 $m = \log n / \log\log n$。

于是每个溢出桶都可以套用上一小节的 trie 分析（那里的 $n'$ 对应这里的桶内 key 数，$= O(\log n / \log\log n)$）：

• 单桶 trie 节点数：$O(\log n)$
• 单桶编码：$O(\log n)$ 比特

溢出处理总空间：$B \cdot O(\log n) = O((n / \log^9 n) \cdot \log n) = O(n / \log^8 n)$ 比特。

为什么恰好是 $\log^9 n$？

这里的 9 没有特别意义——它只是「足够大的多项式」。真正的约束是：

• 下界：溢出桶数 $B$ 要足够大，让每桶期望负载 $o(1)$，即 $B \gg N_{\text{overflow}}$；前一小节取 $\delta$ 时让 $N_{\text{overflow}} \le n/\log^{12} n$，所以 $B = n/\log^9 n$ 给出每桶期望负载 $\le 1/\log^3 n$
• 上界：$B \cdot O(\log n) = o(n\log N)$，即 $B = o(n\log N / \log n) = o(n)$

任何 $B = n / \log^c n$ 对 $1 \le c < 12$ 都可行。课件选 $c = 9$ 是一个保守但可用的值。

总冗余与 Feistel 的最后一步

把所有冗余来源汇总：

来源	冗余
主桶中 $\delta m$ 的额外空位	$O(\delta n)$ 字 $= O(\delta n \log N)$ 比特
主桶「字长对齐」的尾部浪费	$O(n / m)$ 比特（每桶常数比特，共 $n/m$ 桶）
溢出两级处理	$O(n / \log^8 n)$ 比特

主项是第一条：$O(\delta n \log N)$ 比特。代入 $\delta = 6\log\log n / \sqrt{\log n}$（常数 6 只是先前取定的一个足够大的 $c$，任何 $c$ 都行，被 $O$ 吸收）：

$$O(\delta n \log N) = O\left(\frac{\log\log n}{\sqrt{\log n}} \cdot n \log N\right) = o(n \log N)$$

因为 $\log\log n / \sqrt{\log n} \to 0$。已经足以声明 succinct。

Feistel 优化：课件提到可以用 Feistel 网络把 $O(\delta n)$ 字进一步压到 $O(\delta n \log(N/n))$ 比特。这里简要说明它的作用——细节可以跳过。

Feistel 网络在 Succinct 字典里的角色

Feistel 网络 是密码学里构造可逆伪随机置换的经典结构：给定若干轮函数 $f_1, f_2, \dots$，通过「交替异或 + 交换」把一个 $2w$ 比特的输入打乱成同长度的输出，且这一过程可逆（只要知道轮函数就能倒推出输入）。

在 succinct 字典中，Feistel 充当可逆哈希。对每个 key $x$，用 Feistel 把它映射成 $(i, q)$ 对——$i$ 是桶索引（$\log(n/m)$ 比特），$q$ 是桶内的「商」（quotient）。由于 Feistel 可逆，从 $(i, q)$ 可以恢复 $x$。

这意味着桶内只需存商 $q$，位数是 $\log(N) - \log(n/m) = \log(Nm/n)$，约 $\log(N/n) + O(\log\log n)$ 比特，而非原本的 $\log N$ 比特。把冗余「从桶索引吸收走」之后，每个桶的编码从 word-level 降到 bit-level——这就是 $O(\delta n) \text{ 字} \to O(\delta n \log(N/n))$ 比特 的来源。

这是 quotienting 技术的密码学实现。

综合起来，Succinct dictionary 的总空间是

$$n \log N + o(n \log N) = (1 + o(1)) \log_2 \binom{N}{n} \text{ 比特}$$

同时支持 $O(1)$ 时间的查询、插入、删除。这是 succinct 数据结构领域最重要的里程碑之一。

flowchart LR
    BB["n 个元素"] --> BIN["n/m 个主桶<br>m = log n / log log n"]
    BIN --> SD1["每桶编码 ≤ O(log n) 比特<br>= 一个机器字"]
    SD1 --> WORD["字内 O(1) 查询<br>（借助预计算表）"]

    BIN -.->|"每桶以 ≤ 1/log¹² n 概率溢出"| OVF["溢出元素<br>≤ n/log¹² n 个"]

    OVF --> OVF2["B = n/log⁹ n 个溢出桶"]
    OVF2 --> LOAD["每桶负载 ≤ log n / log log n<br>（w.h.p.）"]
    LOAD --> TRIE["压缩 trie 编码<br>每棵 O(log n) 节点 = O(log n) 比特"]

    classDef main fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef hot fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef cold fill:#f3e5f5,stroke:#4a148c,stroke-width:2px

    class BB,BIN,SD1,WORD main
    class OVF hot
    class OVF2,LOAD,TRIE cold

Chernoff Bound 的推广

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

有限独立下的 Chernoff

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

$k$-wise 独立下的 Chernoff Bound

设 $X_1, \dots, X_n \in \{0,1\}$ 为 $k$-wise 独立的，$X = \sum X_i,\, \mu = \mathbb{E}[X]$。对任意 $\delta > 0$，只要 $k \le \dfrac{\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}$ 可以改写为 $\displaystyle \sum_{i \le n} \alpha_i \sum_{j_1 < \dots < j_i} X_{j_1} \dots X_{j_i}$（其中 $\alpha_i \ge 0$）^[5]。如果 $X_1, \dots, X_n$ 只是 $k$-wise 独立的，那么 $\mathbb{E}[X_{j_1} \dots X_{j_i}]$ 只在 $i \le k$ 时可以精确计算。

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

1. 用 Markov 不等式得到上界 $\Pr[X \ge a] = \Pr\left[ \e^{tX} \le \e^{t a} \right] \le \dfrac{\sum_i \alpha_i \mathbb{E}\left[\binom{X}{i}\right]}{\sum_i \alpha_i \binom{a}{i}} = \sum_i \alpha_i \dfrac{\binom{n}{i}(\mu/n)^i}{\binom{a}{i}}$
2. 观察到对每个 $i$，比值 $\dfrac{\binom{n}{i}(\mu/n)^i}{\binom{a}{i}}$ 的大小不同，有 $\dfrac{\binom{n}{i+1}(\mu/n)^{i+1}}{\binom{a}{i+1}} {\LARGE/} \dfrac{\binom{n}{i}(\mu/n)^i}{\binom{a}{i}} = \dfrac{n-i}{a-i} \dfrac{\mu}{n}$
3. 当 $i$ 增大时先减后增，在最优点 $i^* = \dfrac{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, \dots, x_c),\, x_i \in [u]$。维护 $c$ 个完全随机的查找表 $T_1, \dots, T_c\colon [u] \to [m]$。哈希值为

$$h(x) = T_1[x_1] \oplus T_2[x_2] \oplus \dots \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, \dots\}$，如果存在坐标 $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, \dots] = \mathbb{E}[X_\alpha]$）配合 Chernoff bound 的推广（对有固定期望但非独立的随机变量），得到与完全独立相同的集中度保证。

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

• $d^{1/c}$ 的证明：$S \subseteq S_1 \times \dots \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, \dots$ 为 $[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 LR
    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 独立哈希在实践和理论上都能匹配需要更高独立性的方案。

---

1. 因为每个元素必须选择它那条边的一个端点来存放。也就是说：每条边代表一个元素、要给每条边选择一个端点、并且每个顶点最多只能被一条边选中。对于一个连通分量，如果边数 ≥ 顶点数 + 1，那么无论如何选择，都至少有一个顶点被两条边选中，导致冲突。 ↩︎

2. 这里没有排除重复出现的 key 或 slot，也没有要求序列一定对应简单路径；但由于我们只是在做联合界，这样的过计数不会影响上界的正确性。 ↩︎

3. 尾和公式：对非负整数随机变量 $L$ 有 $\mathbb{E}[L] = \sum_{t \ge 1} \Pr[L \ge t]$。 ↩︎

4. 当 $n \ll N$ 时，信息论下界 $\log_2 \binom{N}{n}$ 近似于 $n \log_2 (N/n) + O(n)$。这里粗略写成 $O(n\log N)$，但更精细的版本其实是 $n\log(N/n)$。 ↩︎

5. 这可以通过二项式展开和组合计数来理解：$\displaystyle \e^{tX} = \exp \left(t\sum_{i=1}^n X_i\right) = \prod_{i=1}^{n} \exp (t X_i) = \prod_{i=1}^n (1 + (e^t - 1)X_i)$，展开后每项对应一个 $X$ 的子集的乘积，系数 $\alpha_i$ 就是对应 $i$ 个变量的组合数和 $t$ 的函数。 ↩︎