NJU TCS Workshop'25 | Lecture 3. 现代哈希表设计
Abstract.
问题
现希望维护一个集合，并进行成员判定。问题的规模和记号（这些记号在全文中都适用）如下所示：
定义 1.1（静态字典问题）. 静态字典问题系指如下问题：
数据. 给定一个固定不变的集合 $S$，满足 $|S| = n$，且 $S\subseteq [N] = U$。
询问. 每次给出一个 $x\in U$，判断是否有 $x\in S$。可能需要维护动态插入、删除。
记号. $S$ 系指可能出现的元素集合；$n$ 系指 $|S|$ 的大小；$U$ 系指全集，实为 $\{1, 2, …, N\}$。
为此已有一系列算法。对这些算法的评价指标主要分两个维度：
- 空间复杂度. 存储该数据结构所需比特数。
- 时间复杂度. 单次查询的访存次数。
显然，存在从数据结构到集合的满射，否则不在像中的集合无法被正确维护。因此经简单计数可知空间复杂度的理论下界
$$
2^\mathrm{Space} \geq \binom Nn \quad \Rightarrow \quad \mathrm{Space} \geq n\log N - O(n\log n)
$$
兹假定 $N = O(\mathrm{poly}(n))$，即值域不能大的太离谱。下表列举了一些常见的算法及其时空复杂度，此处方便起见，设计算机的字长为 $O(\log n)$ 级别，空间复杂度以字数而非比特数记。
| 算法 | 空间复杂度 | 查询时间复杂度 | 更新时间复杂度 | 评价 |
|---|---|---|---|---|
| 平衡树 | $O(n)$ | $O(\log n)$ | $O(\log n)$ | 慢 |
| 拉链法哈希表 | $O(n)$ | 期望 $O(1)$ | 期望 $O(\log n)$ | 慢 |
| 朴素完美哈希 | $O(n^2)$ | $O(1)$ | $O(1)$ | 大 |
| FKS 完美哈希 | $O(n)$ | $O(1)$ | $O(1)$ | 大常数 |
| Succint Dictionary | $(1 + o(1))n$ | $O(1)$ | $O(1)$ | 好 |
完美哈希
哈希是求解成员判定问题的经典思路。其思路是从一族 $[N] \rightarrow [m]$ 的函数 $\mathcal{H}$ 当中随机采样一个 $h$，并用 $m$ 个字 $L_1, …, L_m$ 来存储信息。每次查询时，先计算 $h(x)$，然后查看 $L_{h(x)}$ 是否为 $x$。
容易发现，此类方法的核心矛盾点是哈希冲突。即可能存在 $x_1\ne x_2$，$h(x_1) = h(x_2)$。解决哈希的方向有：
- 重新查找. 拉链法、线性探测法、二次探测法等，相信读者在数据结构课程中有所涉猎。
- 增大值域. 取充分大的 $m$ 使得高概率没有冲突。
高概率没有冲突的哈希方法称作完美哈希。
一级完美哈希
首先，考虑接受如下假设：
假设 2.1.1（简单均匀哈希假设，SUHA）. 假设存在一个高效的采样器，从支撑集为一切 $[N]\rightarrow [m]$ 的函数的均匀分布中采样一个 $h$，并且对于任意的此类 $h$ 与 $x$，都可以 $O(1)$ 计算 $h(x)$。
在此假设下，不发生哈希冲突的概率为
$$
\prod_{i = 1}^n \left(1 - \frac{i}{m}\right) = \exp\left(-(1 + o(1))\frac{n^2}{2m}\right)
$$
可知为高概率不出错，须将 $m$ 取作 $\tilde{O}(n^2)$ 级别。
然而，上述假设过于强了。事实上我们只需要：
定义 2.1.1（通用哈希族）. 一族哈希函数 $\mathcal{H}$ 是 $k$-通用的，若对于任意不超过 $k$ 个 $x_1, …., x_k\in U$，都有
$$
\Pr_{h\sim U(\mathcal{H})} \left[h(x_1) = \cdots = h(x_k)\right] \leq \frac{1}{m^{k - 1}}
$$
更进一步，称 $\mathcal{H}$ 是强 $k$-通用的（或 $k$-wise 独立的），若对于任意不超过 $k$ 个 $x_1, …, x_k\in U$ 和 $y_1, …, y_k\in [m]$ 都有
$$
\Pr_{h\sim U(\mathcal{H})} \left[ \bigwedge_{i=1}^k h(x_i) = y_i\right] = \frac{1}{m^k}
$$
显然，$k$-wise 独立蕴含 $k$-通用。
定理 2.1.1. 对于任意的 $N, k, m$，满足 $k\leq m$，$N, m$ 都是 $2$ 的幂次，存在 $k$-wise 独立的从 $[N]$ 到 $[m]$ 的哈希函数族。
证明. 取 $\mathcal{H} := \{ f(x)\bmod m : f\in \mathbb{GF}(N)[x] / (x^{k})\}$，用拉格朗日插值等工具分析概率。$\blacksquare$
Remark. 常用的是 $2$-wise 独立哈希 $\mathcal{H} := \{h_{a, b}(x) = ax + b \pmod m : a, b\in \mathbb{GF}(N)\}$。
那么，可以证明只用 $2$-wise 独立哈希即可做到同样的空间。定义随机变量
$$
Y := \sum_{i, j\in S, i < j} \mathbf{1}[h(i) = h(j)]
$$
则哈希没有冲突等价于 $Y = 0$，而这个概率是 $O\left(\frac{n^2}{2m}\right)$，因为 $2$-wise 独立哈希也是 $2$-通用哈希。因此取 $m = O(n^2)$ 即可保证常数概率正确。
如何将这个 $O(n^2)$ 的空间优化至 $O(n)$？一个自然的想法是双哈希。
算法 2.1.1（Fredman-Komlos-Szemeredi 完美哈希）. 本算法是一个分两级的哈希算法。
- 首先从 $[N]\rightarrow [n]$ 的 $2$-wise 独立哈希族中采样一个 $h$。
- 现在，设 $B_i := |\{x : h(x) = i\}|$。存储 $n$ 个指针 $p_1, …, p_n$，第 $i$ 个指向内存中第 $\sum_{j=1}^{i - 1} B_i^2$ 个字。
- 对于每个 $i$，找 $[N]\rightarrow [B_i^2]$ 的完美哈希。
当询问 $x$ 时，首先查询 $i = h(x)$，然后查看第 $p_i + h_i(x)$ 个字是否为 $x$。
定理 2.1.2. 已知 $S$，可以期望 $O(n)$ 时间预处理出 $h, h_1, …, h_n$ 使得 FKS 哈希表的空间消耗为 $O(n)$。
证明. 结合前述一切结果，惟须证明随机采样 $h$ 之后哈希表的空间复杂度正确。此哈希表使用的空间将是
$$
2 + 2n + \sum_{i=1}^n B_i^2
$$
前两项来自 $h, h_1, …, h_i$ 的参数，我们惟须求后方和式的期望。注意到
$$
Y = \sum_{i=1}^n \binom{B_i}{2} = \frac{1}{2}\sum_{i=1}^n B_i^2 - \frac{n}{2}
$$
两边求期望立即得到
$$
\mathbb{E}\left[\sum_{i=1}^n B_i^2\right] = n + \frac{n^2}{n} = 2n
$$
只需重复采样 $h$ 并验证 $\sum_{i=1}^n B_i^2$ 确实满足要求，然后随机直至找到 $[N]\rightarrow [B_i^2]$ 的完美哈希即可。$\blacksquare$
Succint Dictionaries
本节接受 SUHA（假设 2.1.1）。
定义 3.1（Succint Data Structure）. 称一个数据结构是 succint 的，若其仅使用 $(1 + o(1))n$ 个字。
稍松一些地，称一个数据结构是 compact 的，若其仅使用 $O(n)$ 个字。
注意 FKS 的常数非常大，仅仅是 compact 的，而并不是 succint 的。是否有其他方法能够构造 succint 的字典？
尝试.
从 $[N]\rightarrow [n / \log^3 n]$ 的简单均匀哈希族中采样哈希函数 $h$，将 $n$ 个元素打到 $n / \log^3 n$ 个桶中。定义 $n’ = (1 + 2 / \log n)\log^3 n$。
根据 Chernoff bound，有最大负载高概率不超过 $n’$。计算此方法消耗的额外空间：
- 存储每个桶的开始指针：$n\log n’$。
- 存储所有桶中元素：$n / \log^3 n\cdot n’\log U = (1 + 2 / \log n) n\log U$。
确实只需要 $(1 + o(1))n\log U$ 的空间。
定理 3.1. 只需用 $O(\log n)$ 个比特，便可维护 $O(\log n / \log \log n)$ 个