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$$

证明的精髓在最后一步「取最优的 $t$」：对每个 $t > 0$，Markov 不等式都给出一个形如 $\e^{g(t)\mu}$ 的界，其中 $g(t) = \e^t - 1 - t(1+\delta)$；我们挑使指数 $g(t)$ 最小的 $t^* = \ln(1+\delta)$，就得到这一族界里最紧的那个。下图画出 $g(t)$ 这条「指数倾斜」曲线——谷底就是最优界的位置。

下尾界

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)$。

下图把这套推导画了出来（取 $n = 10^6$）：单桶负载的尾概率 $\Pr[X_i \ge L]$ 随 $L$ 以 $(\e/L)^L$ 的速度骤降（比指数衰减还快），在 $L^* = \Theta(\log n/\log\log n)$ 处跌破单桶目标 $1/n^2$；再对 $n$ 个桶做联合界，最大负载就以 $\ge 1 - 1/n$ 的概率不超过 $L^*$。

$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$ 附近——大数定律开始发挥作用。

下图用同一套均匀随机扔球的实验对照这两种情形：$m = n$ 时负载呈明显的重尾，最大负载（这里是 $5$）远高于期望 $1$；而 $m = n\ln n$ 时，所有桶的负载都紧紧簇拥在 $\mu \approx 6.9$ 附近，最大负载只比期望略高。这正是上面两段分析的直观写照。

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$。

下图概括了整个论证的两个引擎。左侧是平方机制：要把某个桶从第 $i$ 层抬到第 $i+1$ 层，新球的两个随机选择必须都落在已达第 $i$ 层的 $\nu_i$ 个桶中，概率约为 $(\nu_i/n)^2$——恰是单选择方案 $\nu_i/n$ 的平方。右侧是由此产生的双指数衰减：高层桶的比例 $\nu_i/n$ 每升一层就平方一次，于是只需 $\log_2\log_2 n + O(1)$ 层就跌破 $1/n$，对应最大负载 $O(\log\log n)$。

定义阈值序列 $\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$

下图用一个 $n = 6$ 的具体例子展示整个两级结构：一级哈希把 $6$ 个元素分到 $6$ 个桶（桶 $B_1, B_3, B_5$ 分别收到 $2, 1, 3$ 个元素，允许碰撞），每个桶 $B_i$ 再单独建一张大小为 $|B_i|^2$ 的二级表彻底消除内部碰撞。本例二级表总空间 $4 + 1 + 9 = 14 \le 3n$。绿色路径示意查询 $x_5$ 的全过程：一级定位到桶 $B_5$，二级哈希 $h_5$ 定位到具体单元，比对——全程 $O(1)$。

空间分析

关键问题是：二级表的总空间 $\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)$$

为什么碰撞数是 $\binom{|B_i|}{2}$ 累加？

这里的 $Y$ 统计的是碰撞的元素对数。若桶 $B_i$ 中有 $b=|B_i|$ 个元素，则桶内任意两个不同元素 $x_a,x_b\in B_i$ 都满足 $h(x_a)=h(x_b)=i$，因此每个无序元素对都贡献一次碰撞。这样的元素对数正是 $\binom{b}{2}$。

因此

$$\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 次内存访问，最坏情况确定性保证，没有链表遍历、没有探测序列。

下图追踪一次典型插入：新元素 $x$ 落在已被占用的槽位（$h(x)=1$，被 $a$ 占用），于是把原住户「踢」走；被踢走的 $a$ 去自己的另一个候选槽 $g(a)=4$，又踢走 $b$；如此连锁，直到某次踢替落入空槽（$c$ 落入 $g(c)=9$）。关键在于：每个元素始终只在自己的两个候选位置之间移动。

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)$ 出发的路径重新安排元素。插入成功与否取决于这条边所在连通分量的结构——把每条边（元素）分配给一个端点（槽位）、且每个端点至多被一条边占用，本质上是一个「边定向」问题。

下图按新元素 $x$ 加入后所在连通分量的「边数 $e$ vs 顶点数 $v$」分三类（橙色边始终是新插入的 $x$）：树（$e = v - 1$）必有空槽，沿链把元素移入空槽即可；单环（$e = v$）恰好填满，把环上元素整圈旋转一格就能腾出位置容纳 $x$；坏分量（$e \ge v + 1$，至少两个环）元素比槽位多，由鸽笼原理必有冲突，只能重建。

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

• 路径：从新元素的一个槽位出发，沿已占用的边走到另一个槽位，再沿该槽位对应的元素的另一条边……最终遇到空槽位，即可顺次移动，插入成功。
• 单环：若路径形成一个环（没有空槽），但环上每个顶点恰好连两条边（每个槽位两个可能的位置），则可以将环上所有元素旋转一圈，从而腾出一个位置，插入成功。
• 双环：两个环共享一个顶点，或者更一般地，连通分量中边数 ≥ 顶点数 + 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)$

Method of Four Russians：让「字内 $O(1)$」落地

上一节 Word RAM admonition 里有一个看起来很神秘的承诺：「对一个字内的数据做几乎任意的固定函数，都可以靠预计算查找表在 $O(1)$ 次访存内完成」。这条承诺不是天降——它由一种 1970 年代的经典算法范式 Method of Four Russians（4-Russians 法）兑现。

它的命名稍有点尴尬：1970 年 Arlazarov、Dinic、Kronrod、Faradzhev 四位苏联数学家用这个技巧给出了布尔矩阵乘法的 $O(n^3 / \log n)$ 算法；后来 Aho-Hopcroft-Ullman 教科书把它推广为通用范式后才被沿用至今。它在本节里有两个用处：第一是兑现 Word RAM 的「字内 $O(1)$」假设；第二是在 trie 处理溢出时把整棵小 trie 上的查询也压成 $O(1)$。

核心配方

4-Russians 的精神可以用三个词概括：分块 → 预计算 → 查表。

设输入规模为 $L$ bits。把它切成 $L/b$ 个 $b$-bit 块（$b$ 是参数）。对每一种可能的「块编码 + 局部状态 + 查询输入」组合，预先算好这块的输出（包括传给下一块的状态），存到一张大表里。查询时按块顺序扫，每块用 $O(1)$ 次查表得到「这块的输出」与「下一块的入口状态」，串起来即可。

flowchart LR
    IN["输入<br>L bits"] --> SP["切成 L/b 块"]
    SP --> B1["块 1"]
    SP --> B2["块 2"]
    SP --> BK["块 L/b"]
    B1 --> T1["查表"]
    B2 --> T2["查表"]
    BK --> TK["查表"]
    T1 -->|"状态"| T2
    T2 -->|"状态"| TK
    TK --> ANS["最终答案"]

    classDef in fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef block fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef table fill:#f3e5f5,stroke:#4a148c,stroke-width:2px
    classDef out fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px

    class IN,SP in
    class B1,B2,BK block
    class T1,T2,TK table
    class ANS out

每块的可能编码有 $2^b$ 种，乘上 $\operatorname{poly}(b)$ 个状态/查询变体，表大小约为 $2^b \cdot \operatorname{poly}(b)$ 项，每项 $\operatorname{poly}(b)$ bits。如果令

$$b = \frac{\log n}{c \cdot \mathrm{const}},$$

则 $2^b \le n^{1/(c \cdot \mathrm{const})}$，再乘 $\operatorname{poly}(b) = \operatorname{polylog}(n)$ 得到表大小不超过 $n^{1/c} \cdot \operatorname{polylog}(n)$ bits。这正是「亚线性大小的预计算表 + 常数次查表」的典型形态。

参数 $c$ 是空间-时间权衡的旋钮：$c$ 大 → 块小 → 块数多 → 查询慢一点，但表更小；$c$ 小 → 块大 → 块数少 → 查询快，但表更大。

升温例子：字内 popcount

具体看一个最简单的应用：32 位字的 popcount（数比特中 $1$ 的个数）。

把字分成两个 16 位半字。预计算

$$T[i] = \operatorname{popcount}(i), \qquad i = 0, 1, \dots, 2^{16}-1$$

表项每个 $5$ bits 就够（$\log_2 17$），总表大小约 $40$ KB。查询时

$$\operatorname{popcount}(x) = T[x \,\&\, \mathrm{0xFFFF}] + T[x \gg 16],$$

两次查表 + 一次加，恒为 $O(1)$。如果嫌表太大，可以把字分 4 段每段 8 bits，表降到 $256$ 项；查询变成 4 次查表 + 3 次加，常数略大但仍 $O(1)$。

这就是 4-Russians 的精神：把指数多的可能输入用一张多项式大小的表压缩，查询时只走表。注意「分段」之间需要一个简单的合并操作（这里是加法），更复杂的应用里这一步会通过状态传递完成。

应用：把小字典查询变成字内 $O(1)$

回到主线。每桶用 $O(\log n)$ bits 编码，桶内最多 $m = \log n / \log\log n$ 个 key——整桶塞进一个机器字。怎么让桶内查询 $O(1)$？

按 4-Russians 套路，整张「桶编码 + 查询商」的组合空间是

$$\underbrace{2^{O(\log n)}}_{\text{桶编码}} \times \underbrace{2^{O(\log n)}}_{\text{查询商}} = n^{O(1)}$$

项。预计算每项的输出（「该桶里是否包含查询 key」），写成一张表。查询时一次查表即可。

调一下指数常数（取适当的 $c$），表大小可以压到 $n^{1/3}$ 比特，远小于主表本身——属于「常数空间」级别的辅助开销，整体空间预算被它吸收。Word RAM admonition 里说的「$n^{1/3}$ 比特量级的表」就是这么来的。

进阶应用：在 $O(\log n)$ bit 压缩 Trie 上做前缀查找

接下来是一个稍微复杂、但精神完全相同的应用。后面溢出处理会用到压缩 Trie，那里查询时间也要 $O(1)$，4-Russians 同样适用。

问题

给定一棵用 $O(\log n)$ bits 编码的压缩 Trie，对查询串 $q$，判断「Trie 中是否存在某个存储串是 $q$ 的前缀」，并返回该前缀串在 Trie 中的字典序。要求用 $O(n^{1/c} \log n)$ bits 的预计算表，$O(c)$ 时间完成。$c$ 是可调参数。

固定 Trie 编码。先用平衡括号或 DFS 序列编码树形，再附上每条压缩边的「下一段比较位置和长度」，以及每个终止节点对应串的字典序。整体长度记为 $L \le A \log n$ bits，$A$ 是常数。

分块。把 $L$ bits 切成大小为 $b$ 的块，共 $L/b = O(c)$ 个块。允许每块在边界处复制少量「边界字段」（如入口节点编号、跨块压缩边的剩余长度等），方便独立查表。这些复制的总开销仍在 $O(\log n)$ bits 内，与原编码同量级。

表索引 $T[\text{block}, \text{state}, \text{query-fragment}]$ 三部分含义：

• block：当前 $b$ bits 块的编码，共 $2^b$ 种
• state：进入该块时的局部状态（当前节点编号、压缩边偏移等），共 $O(b^K)$ 种（$K$ 是吸收所有字段的固定常数）
• query-fragment：该块要读取的至多 $b$ 个查询比特，共 $2^b$ 种

表项输出：（离开该块时的新状态，是否在该块内失败，是否遇到一个终止节点，若有则其字典序）。每项 $O(\log n)$ bits 足够。

表大小：

$$2^b \cdot O(b^K) \cdot 2^b \cdot O(\log n) = 2^{2b} \cdot O(b^K) \cdot O(\log n) \text{ bits}$$

取 $b = \dfrac{\log n}{(K+3)c}$。则 $2^{2b} \le n^{2/((K+3)c)}$，且对充分大的 $n$ 有 $b^K \le (\log n)^K \le n^{K/((K+3)c)}$，乘起来不超过 $n^{(K+2)/((K+3)c)} \le n^{1/c}$。再乘 $O(\log n)$ 得到总表大小

$$O(n^{1/c} \log n) \text{ bits}$$

$K+3$ 是怎么来的

$K$ 来自状态字段的总数（节点编号 + 边偏移 + 入口出口标记 + …）；额外的 $+3$ 留出余量，把 $b^K$ 因子和输出长度的 $\log n$ 因子也吸收进 $n^{1/c}$ 内，最终只剩主项 $O(n^{1/c} \log n)$。具体常数不重要，可调。

查询算法。从含根节点的第一块出发，初始状态为「位于根节点」，并在表索引之外维护一个寄存器 ans 记录目前找到的最优前缀字典序：

1. 用当前 (block, state) 决定要读取哪些查询比特，从 $q$ 里用移位/掩码取出 query-fragment
2. 查表得到新状态、是否失败、是否遇到终止节点
3. 若遇到终止节点，更新 ans
4. 转到下一块，直到失败、查询结束或所有块处理完

每块只做 $O(1)$ 次查表 + $O(1)$ 次 word RAM 操作，共 $O(c)$ 块，总查询时间 $O(c)$。

正确性。表对每种 (block, state, query-fragment) 三元组都精确模拟了 Trie 上对应步骤的真实行为。归纳：进入某块时算法状态与真实查询状态一致，则查表后离开时仍一致；遇到终止节点会被 ans 收下。最终算法报告的字典序对应 Trie 中某个作为查询串前缀的存储串。

这就是 4-Russians 在 Succinct 字典里的两次落地：一次为主桶的 $O(1)$ 查询，一次为溢出 trie 的 $O(c)$ 查询。两者都靠「分块 + 多项式大小预计算表」把指数级的局部状态压缩到常数次内存访问。

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

先看一个直观但不完全成功的方案：取 $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 的节点数——即「每次插入平均生长多少层」。

一个直观例子

按顺序插入四个 4-bit key：0110、1001、1011、0111：

1. 插入 0110：trie 只是根 → 一个叶子，没有「生长」可言
2. 插入 1001：与 0110 在第 1 比特就分歧（1 vs 0），不需要延伸——根分两支即可。$G_2 = 0$
3. 插入 1011：沿 1 走到叶子 1001，与之比较：bit 2 都是 0、bit 3 上 0 vs 1 分歧。共同前缀长度 1，$G_3 = 1$
4. 插入 0111：沿 0 走到叶子 0110，比较：bit 2 都是 1、bit 3 都是 1、bit 4 上 0 vs 1 分歧。共同前缀长度 2，$G_4 = 2$

最终的压缩 trie：

flowchart TD
    R(("ε"))
    R -->|"0"| N0(("bit 4"))
    N0 -->|"0"| L0110["0110"]
    N0 -->|"1"| L0111["0111"]

    R -->|"1"| N1(("bit 3"))
    N1 -->|"0"| L1001["1001"]
    N1 -->|"1"| L1011["1011"]

    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 node
    class L0110,L0111,L1001,L1011 leaf

总节点数 $= 7 = 4\, \text{叶子} + 3\, \text{内部节点}$；总生长 $G = 0 + 1 + 2 = 3$；完美对上「叶子数 + 生长数 = 节点数」的恒等式。如果把 key 真的换成均匀随机，每次生长的期望就是 $1$（下面立即推导），符合「平均每次插入加约 $1$ 个内部节点」的直觉。

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？

我们需要的不是 $G$ 的期望（已经知道 $\mathbb{E}[G] = n'$），而是它的尾——$\Pr[G \ge a]$ 多么小。

直接的策略行不通。$G$ 是 $n'$ 个独立几何变量之和，每个分量本身有指数尾，但若对每个分量做 union bound 会损失 $n'$ 倍。Chebyshev 只给多项式尾。我们要的是 Chernoff 量级的指数集中。

MGF 是把独立和的尾压紧的标准武器：因为独立变量之和的 MGF 等于各自 MGF 的乘积，再用 Markov $\Pr[\e^{tG} \ge \e^{ta}] \le \e^{-ta} \mathbb{E}[\e^{tG}]$ 把概率换成 MGF 的比值。整个套路三步：

1. 算单个分量 $G_i$ 的 MGF
2. 用独立性把和的 MGF 写成 $n'$ 个 MGF 的乘积
3. 选具体 $t$ 让 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'}$$

接下来挑 $t$。第三步的诀窍是让 MGF 等于一个干净的常数，这样乘积就是 $\text{常数}^{n'}$。取 $\e^t = 3/2$（即 $t = \ln(3/2)$），落在收敛区间内 $(1, 2)$ 的中点附近，得到 $\mathbb{E}[\e^{tG_i}] = 1/(2 - 3/2) = 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'}$$

注意这个上界把「尾」和「期望」分别对应到两个因子：$(3/2)^{-a}$ 衰减得越快，$a$ 越大；$2^{n'}$ 是 MGF 集体贡献的「质量」。我们需要前者压制后者。

代入溢出处理的尺度：下一小节会证明，每个溢出桶中至多 $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$ 是一个保守但可用的值。

总冗余汇总

把所有冗余来源汇总：

来源	冗余
主桶中 $\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——总空间 $n\log N + o(n\log N) = (1+o(1))\log_2 \binom{N}{n}$ 比特。

但还能更紧。下面用 Feistel 网络把上表第一条进一步从「字」单位压到「比特」单位。

Feistel 网络与 quotienting

一轮 Feistel

Feistel 网络是密码学里构造可逆置换的标准结构。先看最简单的一轮版本——把 $2t$-bit 的输入分成两半 $(x_1, x_2)$，每半 $t$ bits，一轮 Feistel 定义为

$$F_f(x_1, x_2) = (f(x_2) \oplus x_1,\ x_2)$$

其中 $f\colon \{0,1\}^t \to \{0,1\}^t$ 是任意函数（真随机、$k$-universal 哈希、甚至简单的查表都可以），$\oplus$ 是按位 XOR。

flowchart LR
    X1["x₁"] --> XOR(("⊕"))
    X2["x₂"] --> F["f(·)"]
    F --> XOR
    XOR --> Y1["f(x₂) ⊕ x₁"]
    X2 --> Y2["x₂"]

    classDef in fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef func fill:#f3e5f5,stroke:#4a148c,stroke-width:2px
    classDef op fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef out fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px

    class X1,X2 in
    class F func
    class XOR op
    class Y1,Y2 out

它是双射：给定输出 $(y_1, y_2)$，逆映射是

$$F_f^{-1}(y_1, y_2) = (y_1 \oplus f(y_2),\ y_2)$$

注意这里不要求 $f$ 可逆——XOR 自身的可逆性就够了。这是 Feistel 的关键卖点：用一个不可逆的函数 $f$ 也能造出双射。

为什么需要双射？因为我们后面要把 key $x$ 编码成「桶号 $i$ + 桶内商 $q$」的形式，并要求从 $(i, q)$ 能唯一恢复 $x$——这正是双射的诉求。

多轮 Feistel

把单轮 Feistel 串联多次（每轮换一个不同的 $f$），就能构造更强的伪随机置换。Luby-Rackoff (1988) 证明：如果 $f$ 是真随机函数，3 轮 Feistel 已经构成伪随机置换。AES 之类的现代分组密码也用类似结构。但 Succinct 字典只需单轮 + $k$-universal 的 $f$，多轮不展开。

Quotienting：把 key 拆成 (桶号, 商)

回到 succinct 字典。每个 key $x \in [N]$ 长 $\log N$ bits，分桶后桶号 $i \in [n/m]$ 占 $\log(n/m)$ bits，已经在主表索引里编码了。桶内不必再存 $x$ 完整的 $\log N$ bits——只需存能与 $i$ 一起反推 $x$ 的「补差」，称为商（quotient）$q$。

但简单的「把 $x$ 截成高低两段，高段当桶号、低段当商」不行：哈希函数 $h$ 是多对一的，知道 $i = h(x)$ 反推不出 $x$ 的高位。需要一种可逆的「key → (桶号, 商)」映射。

Feistel 给出这种映射。把 $x$ 看成 $(x_1, x_2)$ 两半，用 Feistel 映射成 $(y_1, y_2) = F_f(x_1, x_2)$，整体是 $\log N$ 比特。把这 $\log N$ 比特按需要切成两段：前 $\log(n/m)$ 比特作桶号 $i$，后 $\log(Nm/n)$ 比特作商 $q$。

$$\underbrace{\overbrace{\quad\,i\,\quad}^{\log(n/m)}\quad\overbrace{\quad\quad\,q\,\quad\quad}^{\log(Nm/n)}}_{(y_1,\,y_2)\,\text{的 }\log N\,\text{ 比特}}$$

由于 Feistel 是双射，$(i, q) \leftrightarrow x$ 一一对应；桶内只存 $q$，需要时由 $(i, q)$ 反推回 $x$。每个 key 的存储位数从 $\log N$ 降到 $\log(Nm/n) \approx \log(N/n) + O(\log\log n)$ 比特，节省 $\log(n/m)$ 比特。

把第一条冗余 $O(\delta n)$ 字 = $O(\delta n \log N)$ 比特换成 $O(\delta n \log(N/n))$ 比特，常因 $\log N / \log(N/n)$ 倍——当 $N = n^{O(1)}$ 时这是常数倍的改进，当 $N \gg n$ 时改进更大。

这就是 quotienting 技术的密码学实现：用一个可逆置换把「桶索引带走的信息」干净地从存储里挖掉，只留补差。

在 $[n]$ 上的推广

二进制 Feistel 的灵魂是 XOR。如果 key 来自一般集合 $[n]$（$n$ 不一定是 2 的幂），按位 XOR 失效；但 Feistel 的精神可以照搬到任何阿贝尔群结构——因为 XOR 在 $\{0,1\}^t$ 里只是加法群的一种实现。

最自然的替代是 $[n]$ 上的模加法：

$$\oplus_n\colon [n] \times [n] \to [n], \quad (a, b) \mapsto (a + b) \bmod n$$

把 XOR 全部替换成 $\oplus_n$，得到 $[n]$ 上的 Feistel 一轮置换：

$$F_h(x_1, x_2) = ((x_1 + h(x_2)) \bmod n,\ x_2)$$

其中 $x_1, x_2 \in [n]$，$h\colon X_2 \to [n]$ 来自某个哈希函数族。

$[n]$ 上的 Feistel 是双射

对每个固定的 $x_2$，映射 $x_1 \mapsto (x_1 + h(x_2)) \bmod n$ 是 $[n]$ 上的循环平移，显然是置换；其逆为 $y_1 \mapsto (y_1 - h(x_2)) \bmod n$。整个二元映射

$$F_h^{-1}(y_1, y_2) = ((y_1 - h(y_2)) \bmod n,\ y_2)$$

是 $[n] \times [n]$ 到自身的双射。

保持 $k$-universal 性。设 $h$ 来自 strongly $k$-universal 的哈希函数族（即对任意 $\le k$ 个不同的 $x_2$，哈希值在 $[n]$ 上联合均匀独立）。考察任意 $r \le k$ 个输入对 $(x_{1,1}, x_{2,1}), \dots, (x_{1,r}, x_{2,r})$，假设所有 $x_{2,j}$ 互不相同（这是题目条件）。任取目标 $y_1, \dots, y_r \in [n]$，事件

$$\bigwedge_{j=1}^r (x_{1,j} + h(x_{2,j})) \bmod n = y_j$$

等价于

$$\bigwedge_{j=1}^r h(x_{2,j}) = (y_j - x_{1,j}) \bmod n$$

由 $h$ 的 strongly $k$-universal 性，这 $r$ 个独立联合事件的概率恰好是 $1/n^r$。因此新映射在「第一坐标」上达到了 strongly $k$-universal，把 $x_1 \in [n]$ 均匀随机地映射到 $[n]$。

为什么需要 strongly $k$-universal 而非课程版的 $k$-universal

课程定义的 $k$-universal 只约束「$k$ 个输入哈希到同一个值」的概率，不保证单点均匀，更不保证多点联合均匀。要让上面的推导成立——即新映射的输出 $y_j$ 在 $[n]$ 上「均匀随机」——必须把 $h$ 加强为 strongly $k$-universal。

换句话说，碰撞版 $k$-universal 是「碰撞概率不超过理想值」，strongly $k$-universal 是「联合分布与理想值相等」。Feistel 把 $h$ 的「联合均匀」属性原封不动地传给输出；如果输入的 $h$ 没有这个属性，输出当然也没有。

与二进制版本的关系。二进制 Feistel 是 $n = 2^t$、$\oplus_n =$ 按位 XOR 时的特例。本节里随便用哪个版本都行——具体场景中 $N = n^{O(1)}$ 通常意味着可以选 $N$ 为 2 的幂，于是二进制 XOR 即可；但若 key 集合天然不是 2 的幂（比如一些应用里的素数模数），模加法版本是干净的备选。

综合起来，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 走的是 MGF 路线：$\mathbb{E}[\e^{tX}]$，对独立和而言可以拆成乘积，再用 Markov 把概率换成 MGF 比值。但 $\e^{tX} = \sum_{j \ge 0} (tX)^j / j!$ 是所有阶$X^j$ 的加权和——估计它需要知道 $X_1, \dots, X_n$ 的全部联合矩，必须完全独立才行。

如果只有 $k$-wise 独立，我们只能精确计算前 $k$ 阶的联合矩。能否找到一个只用前 $k$ 阶矩就足以集中的「替代 MGF」？

核心想法：用 $\binom{X}{k}$ 替代 $\e^{tX}$

注意，对 $\{0, 1\}$ 值的随机变量 $X_1, \dots, X_n$ 而言，$X = \sum X_i$ 满足

$$\binom{X}{k} = \sum_{\substack{S \subseteq [n] \\ |S| = k}} \prod_{i \in S} X_i$$

这是一个 $k$ 阶多项式（每项是 $k$ 个 $X_i$ 的乘积），因此

$$\mathbb{E}\left[\binom{X}{k}\right] = \sum_{\substack{S \subseteq [n] \\ |S| = k}} \mathbb{E}\left[\prod_{i \in S} X_i\right]$$

只用到 $X_i$ 的 $k$-wise 联合矩——$k$-wise 独立就够了！

下图对比这两个「检验函数」各自吃掉多少阶联合矩：经典 MGF $\e^{tX} = \sum_j (tX)^j/j!$ 展开后用到所有阶矩，必须完全独立才能逐项计算；而 $\binom{X}{k}$ 是一个 $k$ 次多项式，只用到 $\le k$ 阶联合矩——恰好落在 $k$-wise 独立能精确给出的范围内。这就是把 $\binom{X}{k}$ 看作「截断版 MGF」的来由。

更具体地，假设每个 $X_i$ 是 Bernoulli 且 $\Pr[X_i = 1] = p$（即 $\mu = \mathbb{E}[X] = np$）。在 $k$-wise 独立下，

$$\mathbb{E}\left[\prod_{i \in S} X_i\right] = \prod_{i \in S} p = p^k = \left(\frac{\mu}{n}\right)^k$$

共 $\binom{n}{k}$ 个 $k$-子集，故

$$\mathbb{E}\left[\binom{X}{k}\right] = \binom{n}{k}\left(\frac{\mu}{n}\right)^k$$

接下来用 Markov：注意 $\binom{x}{k}$ 在 $x \ge k$ 时是 $x$ 的单调增函数，所以「$X \ge a$」蕴含「$\binom{X}{k} \ge \binom{a}{k}$」（取 $a \ge k$）。因此

$$\boxed{\Pr[X \ge a] \le \Pr\left[\binom{X}{k} \ge \binom{a}{k}\right] \le \frac{\mathbb{E}\!\left[\binom{X}{k}\right]}{\binom{a}{k}} = \frac{\binom{n}{k}(\mu/n)^k}{\binom{a}{k}}}$$

这就是 $k$-wise 独立下的 Chernoff bound！把 $a = (1+\delta)\mu$ 代入即得

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

解读

右边的两个二项式系数有明确的几何意义：

• 分子 $\binom{n}{k}(\mu/n)^k$ 是「随机选 $k$ 个变量正好都是 1」的事件总质量
• 分母 $\binom{a}{k}$ 是「真实达到 $a$ 时这种事件的容量」
• 比值告诉我们：实际质量被「$k$ 元子集组合数」放大了多少

最优 $k$ 满足 $k \approx \mu\delta / (1 - \mu/n)$（求导可得，但具体数值不重要）。当 $\delta = \Theta(1)$ 且 $\mu$ 不太小时，最优 $k \approx \mu\delta$，bound 大致是

$$\left(\frac{\e\mu}{a}\right)^k = \left(\frac{\e}{1+\delta}\right)^k = \exp(-\Theta(k))$$

和经典 Chernoff 量级一致——只要 $k$ 足够大。

把握全局

把 $\binom{X}{k}$ 当成「截断版 MGF」是理解这套技巧的关键：MGF 用所有阶，需要完全独立；$\binom{X}{k}$ 用前 $k$ 阶，只需 $k$-wise 独立。代价是 bound 的形式不那么干净，但指数尾的精神被保留——只要能把 $k$ 推得足够大，就能复现 Chernoff 的集中度。

应用：$k$-wise 独立下的 Occupancy

直接套用上面的 bound，把课堂讲过的两种 balls into bins 情形翻译过来。固定桶 $j$，令 $X_i = \mathbb{I}[\text{第 }i\text{ 个球落入桶 }j]$，$X = \sum X_i$ 是桶 $j$ 的负载（也就是之前章节中的 $L_j$）。

情况一：$m = n$ 球进 $n$ 桶

每个桶期望负载 $\mu = 1$。要证明 $\max_j X = O(\log n / \log\log n)$ w.h.p.，就要证明对每个桶，

$$\Pr[X \ge L] \le n^{-2}, \qquad L = O(\log n / \log\log n)$$

代入 bound（用 $a = L$，$\mu = 1$）：

$$\Pr[X \ge L] \le \frac{\binom{n}{k}(1/n)^k}{\binom{L}{k}} \le \frac{(n\e/k)^k (1/n)^k}{(L/k)^k} = \left(\frac{\e}{L}\right)^k$$

其中用 $\binom{n}{k} \le (n\e/k)^k$、$\binom{L}{k} \ge (L/k)^k$。

要让上式 $\le n^{-2}$，取 $k = L$，得到 $(\e/L)^L \le n^{-2}$，即 $L\ln(L/\e) \ge 2\ln n$，解出 $L = \Theta(\log n / \log\log n)$。所以 $k = \Theta(\log n / \log\log n)$ 就够，独立度等于最大负载本身。

情况二：$m \ge n\ln n$ 球进 $n$ 桶

每个桶期望负载 $\mu = m/n \ge \ln n$。要证明 $X = O(m/n)$ w.h.p.，取 $a = 2\e\mu$（即 $\delta = 2\e - 1$）：

$$\Pr[X \ge 2\e\mu] \le \frac{\binom{m}{k}(\mu/m)^k}{\binom{2\e\mu}{k}} \le \left(\frac{\e}{2\e}\right)^k = 2^{-k}$$

同样用斯特林上下界。要 $\le n^{-2}$，取 $k = 2\log_2 n$。所以 $k = \Theta(\log n)$ 就够。

总结

情形	所需独立度 $k$	最大负载
$m = n$	$\Theta(\log n / \log\log n)$	$O(\log n / \log\log n)$
$m \ge n\ln n$	$\Theta(\log n)$	$O(m/n)$

两种情形都能用有限独立完全复现完全随机情形下的 max load 上界——只要 $k$ 取得足够大。这就是 succinct dictionary 中能用 $k$-universal 哈希族（求值 $O(k)$、存储 $O(k)$ words）替代「真正随机函数」的理论基础。

警示：$k = 2$ 远远不够——$\sqrt n$ 反例

上面说「$k$-wise 独立够大就行」，那 $k = 2$（两两独立）行不行？答案是远远不行。下面构造一个 strongly 2-universal 的哈希函数族，但 $n$ balls into $n$ bins 时 $L_{\max} = \Theta(\sqrt n)$ 以概率 $1$ 成立——比完全独立时的 $O(\log n / \log\log n)$ 高出指数级。

构造

球集合和桶集合都是 $[n]$。先取一个随机整数 $R$，使其期望和方差满足

$$\mathbb{E}[R(R-1)] = n - 1, \qquad R = \Theta(\sqrt n)$$

具体取法：令 $r$ 满足 $r(r-1) \le n - 1 \le r(r+1)$，即 $r = \Theta(\sqrt n)$。令

$$R = \begin{cases} r + 1, & \text{概率 }\alpha,\\ r, & \text{概率 } 1 - \alpha,\end{cases} \qquad \alpha = \frac{n - 1 - r(r-1)}{2r}$$

代入验证 $\mathbb{E}[R(R-1)] = (1-\alpha)r(r-1) + \alpha r(r+1) = n - 1$。

给定 $R$ 之后，随机生成哈希函数 $h$：

1. 从 $[n]$ 个球中均匀随机选大小为 $R$ 的集合 $T$
2. 从 $[n]$ 个桶中均匀随机选一个桶 $J$
3. 对所有 $x \in T$，令 $h(x) = J$
4. 对所有 $x \notin T$，把它们用一个均匀随机的单射映射到 $[n] \setminus \{J\}$

也就是说：$T$ 中的 $R$ 个球全部塞进同一个桶 $J$，剩下 $n - R$ 个球被无碰撞地分到其他 $n - 1$ 个桶。

Maximum load = $\sqrt n$ 立刻成立

由构造，桶 $J$ 中恰好有 $R$ 个球，其他桶负载 $\le 1$。所以

$$L_{\max} = R = \Theta(\sqrt n) \quad \text{以概率 }1$$

下图画出这个人造哈希的负载分布（取 $n = 64$，故 $R = \sqrt n = 8$）：单独一个桶 $J$ 收下全部 $R$ 个球，其余每个桶至多一个。视觉上它「显然很糟」，最大负载高达 $\sqrt n$；但接下来会证明它恰恰满足 strongly 2-universal——这种「看起来够随机、实际却灾难性失衡」的反差，正是这个反例全部的冲击力所在。

但 $h$ 是 strongly 2-universal

要验证两件事：单点均匀 + 两两独立。

单点均匀。固定球 $x$ 和桶 $a$。分两种情况：

• 若 $x \in T$，则 $h(x) = J$，$\Pr[h(x) = a \mid x \in T] = \Pr[J = a] = 1/n$。
• 若 $x \notin T$，则 $h(x)$ 在 $[n] \setminus \{J\}$ 上均匀随机；$\Pr[h(x) = a \mid x \notin T] = \Pr[J \ne a] \cdot \frac{1}{n-1} = \frac{n-1}{n} \cdot \frac{1}{n-1} = \frac{1}{n}$。

无论哪种情况都有 $\Pr[h(x) = a] = 1/n$。

两两独立。固定两个不同球 $x \ne y$ 和两个桶 $a, b \in [n]$。先算

$$p \coloneqq \Pr[x, y \in T] = \mathbb{E}\!\left[\frac{R(R-1)}{n(n-1)}\right] = \frac{\mathbb{E}[R(R-1)]}{n(n-1)} = \frac{n-1}{n(n-1)} = \frac{1}{n}$$

这就是为什么要让 $\mathbb{E}[R(R-1)] = n-1$。

情况 $a = b$。两个不同球同时进同一个桶只能发生在二者都在 $T$：

$$\Pr[h(x) = a, h(y) = a] = \Pr[x, y \in T] \cdot \Pr[J = a] = \frac{1}{n} \cdot \frac{1}{n} = \frac{1}{n^2}$$

情况 $a \ne b$。$x, y$ 都在 $T$ 时 $h(x) = h(y)$，不可能 $h(x) = a \ne b = h(y)$，所以只考虑「不是二者都在 $T$」的情况。分三小类（$x \in T, y \notin T$；$x \notin T, y \in T$；$x, y \notin T$），逐一计算并合并，各类条件概率都恰好是 $\frac{1}{n(n-1)}$。综合

$$\Pr[h(x) = a, h(y) = b] = (1 - p) \cdot \frac{1}{n(n-1)} = \frac{n-1}{n} \cdot \frac{1}{n(n-1)} = \frac{1}{n^2}$$

两情况合并：对任意 $a, b$，$\Pr[h(x) = a, h(y) = b] = 1/n^2 = \Pr[h(x) = a]\Pr[h(y) = b]$。所以 $h$ 是 strongly 2-universal。

教训

构造出的 $h$ 是 strongly 2-universal（两两独立 + 边际均匀），但 max load $= \Theta(\sqrt n)$，远高于完全独立时的 $O(\log n / \log\log n)$。

这说明：Chernoff 量级的集中绝不仅是「两两独立 + 均匀」就能换来的——它真的依赖更高阶的独立性。课程上一节中之所以要求 $k = \Theta(\log n / \log\log n)$ 而非 $k = 2$，正是为了避免这种「集中失效」的反例。

独立性的代价

$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。

一个直观对比

设 $c = 2$（键由两个字符组成）、字符表为 $\{0, 1, 2, 3\}$。

例 1（可剥离）：$S = \{(0, 0), (0, 1), (1, 2), (2, 3)\}$。

元素	第 1 位	第 2 位	Position character
$(0, 0)$	0（与 $(0,1)$ 相同）	0（唯一）	$(2, 0)$
$(0, 1)$	0（与 $(0,0)$ 相同）	1（唯一）	$(2, 1)$
$(1, 2)$	1（唯一）	2（唯一）	$(1, 1)$ 或 $(2, 2)$
$(2, 3)$	2（唯一）	3（唯一）	$(1, 2)$ 或 $(2, 3)$

每个元素都有至少一个坐标，其值不与集合内其他元素重复——这就是 position character。集合可剥离。

例 2（不可剥离）：$S = \{(a_1, a_2), (a_1, b_2), (b_1, a_2), (b_1, b_2)\}$（即上面 4-universal 失败的「矩形」反例）。

元素	第 1 位	第 2 位
$(a_1, a_2)$	$a_1$（与 $(a_1, b_2)$ 相同）	$a_2$（与 $(b_1, a_2)$ 相同）
$(a_1, b_2)$	$a_1$（与 $(a_1, a_2)$ 相同）	$b_2$（与 $(b_1, b_2)$ 相同）
$(b_1, a_2)$	$b_1$（与 $(b_1, b_2)$ 相同）	$a_2$（与 $(a_1, a_2)$ 相同）
$(b_1, b_2)$	$b_1$（与 $(b_1, a_2)$ 相同）	$b_2$（与 $(a_1, b_2)$ 相同）

没有任何元素有 position character——任何坐标的任何值都被另一个元素分享。这正是 4-universal 失败的根源：四个键的哈希值在 $T_1, T_2$ 上的查表条目两两配对，XOR 全部抵消，输出有线性约束。

下图把这两个例子并排对照：左边的「矩形」四键每个坐标值都被两个键共享，于是每个查表项在四个哈希值里恰好出现两次、XOR 全部抵消，四个哈希值线性相关，4-universal 失效；右边的可剥离集里每个键都有一个「独占坐标」（position character），可以层层剥离，每剥一层其哈希值都独立于其余，从而复现 Chernoff 级别的集中度。

Peeling 过程

如果集合可剥离，可以这样层层剥离它：

1. 在集合 $S$ 中找到一个有 position character 的元素 $x$，则 $h(x)$ 独立于 $\{h(y) : y \in S \setminus \{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$ 的元素按 $c$ 个坐标分别投影：第 $i$ 个坐标的取值集合记为 $S_i = \{x_i : x \in S\}$。由于 $S \subseteq S_1 \times \cdots \times S_c$，有 $\prod_{i=1}^c |S_i| \ge |S| = d$。由 AM-GM（或简单的鸽笼），存在某个 $i^*$ 使得 $|S_{i^*}| \ge d^{1/c}$。在 $S$ 中，对第 $i^*$ 坐标的每个唯一取值挑出一个代表元素，得到大小 $|S_{i^*}| \ge d^{1/c}$ 的子集，子集内每个元素在第 $i^*$ 坐标都唯一——即每个元素都有 position character。这就是一个可剥离子集。

$\log_2 d$ 的证明。归纳：若 $|S| > 1$，则至少在某个坐标 $i$ 上，$S_i$ 不止一个值——也就是说，能选出一个元素 $x$，它在该坐标的取值至多被 $|S|/2$ 个元素分享。挑出这样一个 $x$，它构成一个剥离层；对 $S \setminus \{x\}$ 递归，集合至少减半，所以 $\log_2 d$ 步就能剥完。

两个下界各有适用区间：当 $d$ 大、$c$ 小时 $d^{1/c}$ 主导；当 $d$ 小时 $\log_2 d$ 反而更紧。

把 peeling 接到 Chernoff 上

结合 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 分析可以证明它对几乎所有常见应用都「够好」

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

Tabulation 的扩展

Simple tabulation hashing（也称 Zobrist hashing^[5]）虽然好用，但只有 3-wise 独立，对某些场景仍然不够。围绕 simple tabulation，研究者发展出一系列变体——核心思路都是「在保留 tabulation 工程优势的同时，通过额外的混合层削弱低阶依赖结构」。

Twisted Tabulation Hashing

思想：把键写成 $x = (x_0, x_1, \dots, x_{c-1})$，先用 simple tabulation 从 tail characters $(x_1, \dots, x_{c-1})$ 生成一个「twister」值 $t$，把它 XOR 到 head character 上得到 $x_0' = x_0 \oplus t$，再对 $(x_0', x_1, \dots, x_{c-1})$ 做一次 simple tabulation 输出。Pătraşcu 和 Thorup 在 2013 年提出^[6]。

改善什么。Simple tabulation 失败的核心是「矩形依赖」——四个键 $(a_1, a_2), (a_1, b_2), (b_1, a_2), (b_1, b_2)$ 的查表项两两抵消，使 4-wise 独立失效。Twisted tabulation 让 tail 先影响 head，原本「整齐对称」的矩形结构被打散——每个键的 head 因 tail 不同而不同，原先按位抵消的代数关系失效。

优点：仍然只做常数次查表 + XOR，速度接近 simple tabulation；论文证明它在集中界、linear probing、Cuckoo hashing、min-wise hashing 等具体应用中得到强于 simple tabulation 的概率保证；保留缓存友好的工程优势。

缺点：构造和分析比 simple tabulation 更复杂，需要额外的 tabulation 表来产生 twister；并不在所有意义上是「fully random hashing」的替代品——某些严格要求 strongly $k$-universal 的应用还需别的构造。

Double Tabulation Hashing

思想：做两层 tabulation。第一层 simple tabulation 把原始键扩展成更多 derived characters，第二层再对这些 derived characters 做 simple tabulation：

$$x \xrightarrow{h_1} \text{derived characters} \xrightarrow{h_2} \text{final hash value}$$

Thorup 在 2013 年系统分析了这种结构^[7]。

改善什么。Simple tabulation 只有 3-wise 独立。Double tabulation 利用第一层把键集合「展开」为更容易剥离的 derived characters，再让第二层利用这些可剥离结构产生最终哈希。在合适参数下，整个组合在固定有限集合上可以达到任意高的独立度，而仍然只用常数次查表。

优点：常数次查表获得高独立性效果，绕开了普通 $k$-wise 独立哈希「求值时间随 $k$ 增长」的问题；与 peeling 思想高度对应——第一层人为造出可剥离结构。

缺点：比 simple tabulation 需要更多表和更多查表操作，常数因子更大；理论保证依赖较细的参数（derived characters 数量、字符域大小等），调参不当性能下降。

Mixed Tabulation Hashing

思想：原字符 $(x_0, \dots, x_{c-1})$ 和一组 derived characters $(d_1, \dots, d_k)$（由 simple tabulation 从原字符生成）一起送入最后的 simple tabulation 输出。介于 simple 和 double tabulation 之间。Dahlgaard、Knudsen、Rotenberg、Thorup 2015 年提出^[8]。

改善什么。Sketching、sampling、统计估计等任务往往需要比 3-wise 独立更强的集中保证。Mixed tabulation 通过增加 derived characters，让输出对论文研究的许多分区统计量表现得接近 fully random hashing，从而能直接套用类似完全独立时的 Chernoff 集中界。

优点：仍是 tabulation 风格，速度快；对分区统计量、采样估计等任务有更强 concentration 保证；比 fully $k$-wise independent hashing 更适合工程实现。

缺点：分析门槛高，正确使用需要理解参数约束；与 simple tabulation 相比，表数量和查表次数更多；针对性较强，特别适合「statistics over partitions」场景，未必是所有任务的最简单选择。

三者对比

方法	主要思想	改善的问题	优点	缺点
Simple tabulation	分字符查表 + XOR	普通 $k$-wise 哈希太慢	极快、缓存友好	仅 3-wise 独立
Twisted tabulation	tail 生成 twister 混入 head	矩形依赖结构	接近 simple 的速度，特定应用更强	构造与分析更复杂
Double tabulation	两层 tabulation，先扩展 derived characters	提升可剥离性	常数查表得高独立性	表更多、常数更大
Mixed tabulation	原字符 + derived characters 混合	分区统计场景的集中性	适合 sketching / 统计	参数与证明较复杂

四者共同的权衡：普通 $k$-wise 独立哈希理论性质强但代价高；simple tabulation 极快但独立度低；twisted/double/mixed 用少量额外查表换来在特定算法上的近似 fully random 行为。

总结

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 独立就足以支撑大多数基本应用，但要换来 Chernoff 量级的集中度则需要更高的 $k$-wise 独立——本讲后半段构造了一个 strongly 2-universal 但 max load 高达 $\sqrt n$ 的反例，正面说明这一点。

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

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

Succinct dictionary 用上了一整套工具组合：Method of Four Russians 让字内查询用 $O(1)$ 落地，压缩 trie 处理溢出，Feistel 网络通过 quotienting 把冗余从「字」单位压到「比特」单位。每个工具单看都不复杂，但拼起来正好把信息论下界打到极致。

最后，tabulation hashing 展示了一个深刻的洞见：独立性的「质」比「量」更重要——精心设计的 3-wise 独立哈希在实践和理论上都能匹配需要更高独立性的方案；而 twisted、double、mixed 等扩展进一步证明，这条路线还能继续走得很远。

---

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. Albert L. Zobrist. A New Hashing Method with Application for Game Playing. Technical Report 88, Computer Sciences Department, University of Wisconsin, Madison, 1970. ↩︎

6. Mihai Pătraşcu and Mikkel Thorup. Twisted Tabulation Hashing. Proceedings of SODA 2013, pp. 209–228. ↩︎

7. Mikkel Thorup. Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence. Proceedings of FOCS 2013, pp. 90–99. ↩︎

8. Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, and Mikkel Thorup. Hashing for Statistics over k-Partitions. Proceedings of FOCS 2015, pp. 1292–1310. ↩︎