哈希表与通用哈希
数据结构与符号表问题
数据结构的核心作用：封装数据，支持特定操作，我们关注操作的效率
符号表 \(T\) 存储 \(n\) 条记录，每条记录 \(x\) 包含键 \(\text{key}[x]\) 和卫星数据
需要支持的操作： - \(\text{INSERT}(T, x)\)：将记录 \(x\) 插入到表 \(T\) 中 - \(\text{DELETE}(T, x)\)：从表 \(T\) 中删除记录 \(x\) - \(\text{SEARCH}(T, k)\)：在表 \(T\) 中查找键为 \(k\) 的记录
直接访问表
假设键集合 \(K \subseteq \{0, 1, \ldots, m-1\}\)，且所有键互不相同
建立数组 \(T[0 \ldots m-1]\)：
\[T[k] = \begin{cases} x & \text{如果 } k \in K \text{ 且 } \text{key}[x] = k \\ \text{NIL} & \text{否则} \end{cases}\]
所有操作 \(\Theta(1)\)
问题：键的范围可能非常大，64 位整数有 \(2^{64}\) 种可能的键，字符串更多，无法为每个可能的键分配一个槽位
哈希函数与哈希表
使用哈希函数 \(h: U \rightarrow \{0, 1, \ldots, m-1\}\) 将全域 \(U\) 映射到表中，\(m \ll |U|\)
冲突：当一条待插入的记录映射到已被占据的槽位时发生
由于\(|U| > m\)，由鸽巢原理知，冲突不可避免
链接法解决冲突
将映射到同一槽位的所有记录链接成链表
1 | T[0] → [记录] → [记录] → NIL |
链接法的分析
简单均匀哈希假设 (SUHA)：每个键被哈希到表的每个槽位的概率相等，且独立
装载因子：\(\alpha = \frac{n}{m}\)（每个槽位中平均键的数量）
球入箱模型：将 \(n\) 个球随机均匀扔入 \(m\) 个箱子，所有投掷相互独立
查找一个给定键的期望时间：
\[\text{期望查找时间} = \Theta(1 + \alpha)\]
\(\Theta(1)\) 计算哈希函数并访问槽位，\(\alpha\) 搜索链表的期望代价
若 \(\alpha = O(1)\)（即 \(n = O(m)\)），期望查找时间为 \(\Theta(1)\)
选择好的哈希函数
好的哈希函数应当将键均匀分布到各槽位，键分布中的规律性不应影响均匀性
乘法方法
假设键为整数，\(m = 2^r\)，字长 \(w\) 位
\[ h(k) = (A \cdot k \mod 2^w) \text{ rsh } (w - r) \]
- \(A\) 是奇整数，\(2^{w-1} < A < 2^w\)
- \(\text{rsh}\) 为右移运算符
不要选太接近 \(2^w\) 的 \(A\)
示例：\(m = 8 = 2^3\)，\(w = 7\) 位
1 | A = 1011001 (二进制) |
点积方法
\(m\) 为素数，将键 \(k\) 分解为 \(r+1\) 位 \(k = \langle k_0, k_1, \ldots, k_r \rangle\)，\(0 \leq k_i < m\)
随机选择 \(a = \langle a_0, a_1, \ldots, a_r \rangle\)：
\[ h_a(k) = \left(\sum_{i=0}^{r} a_i k_i\right) \mod m \]
实践中表现优异，但计算代价较高
制表哈希
Patrascu-Thorup (2012) 提出，将键分解为若干字节，每个字节通过查表获取随机值，然后异或
\[ h(k) = h_1[k_1] \oplus h_2[k_2] \oplus h_3[k_3] \oplus h_4[k_4] \]
\(h_i\) 存储在小型查找表中，只需几次查表和异或，实践中非常高效，也可用于哈希字符串
通用哈希
固定哈希函数的弱点
对于任何固定的哈希函数 \(h\)，总存在一组键使得所有键映射到同一槽位
即可以选择所有键来自 \(\{k \in U | h(k) = i\}\)
解决方案：随机选择哈希函数，独立于键的选择
通用哈希的定义
设 \(\mathcal{H}\) 为有限哈希函数集合，如果对于所有 \(x, y \in U\)（\(x \neq y\)）
\[ \Pr_{h \in \mathcal{H}}[h(x) = h(y)] \leq \frac{1}{m} \]
则称 \(\mathcal{H}\) 是通用的
等价表述： \[ |\{h \in \mathcal{H} | h(x) = h(y)\}| \leq \frac{|\mathcal{H}|}{m} \]
通用哈希的示例
从 \(\{a, b\}\) 映射到 \(\{0, 1\}\)：
通用：
\(h_1: a\to0, b\to0\)；
\(h_2: a\to0, b\to1\)；
\(h_3: a\to1, b\to0\)；
\(h_4: a\to1, b\to1\)
\(h(a) = h(b)\) 的有 \(h_1, h_4\)
即 \(\frac{2}{4} = \frac{1}{2} = \frac{1}{m}\)
非通用：\(h_1: a\to0, b\to0\)；
\(h_2: a\to1, b\to1\)
\(h(a) = h(b)\) 的有 \(h_1, h_2\)，
即 \(\frac{2}{2} = 1 > \frac{1}{m}\)
通用哈希的性质
定理：设 \(h\) 从通用哈希函数集 \(\mathcal{H}\) 中均匀随机选取，将 \(n\) 个键哈希到大小 \(m\) 的表中，对于给定键 \(x\)： \[ E[\text{与 } x \text{ 冲突的次数}] < \frac{n}{m} \]
点击查看证明
定义指示器随机变量 \[ c_{xy} = \begin{cases} 1 & \text{如果 } h(x) = h(y) \\ 0 & \text{否则} \end{cases} \]
\(E[c_{xy}] = \Pr\{h(x) = h(y)\} \leq \frac{1}{m}\)（通用性）
记 \(C_x = \sum_{y \in T - \{x\}} c_{xy}\)
\[ E[C_x] = \sum_{y \in T - \{x\}} E[c_{xy}] \leq \sum_{y \in T - \{x\}} \frac{1}{m} = \frac{n - 1}{m} < \frac{n}{m} \]
构造通用哈希函数族
点积哈希函数族
\(m\) 为素数，\(h_a(k) = (\sum_{i=0}^{r} a_i k_i) \mod m\)
\(\mathcal{H} = \{h_a\}\) 大小为 \(m^{r+1}\)
点击查看通用性证明
设 \(x \neq y\) 在位置 0 上不同（\(x_0 \neq y_0\)）
\(h_a(x) = h_a(y)\) 等价于
\[\sum_{i=0}^{r} a_i (x_i - y_i) \equiv 0 \pmod{m}\]
即
\[a_0(x_0 - y_0) \equiv -\sum_{i=1}^{r} a_i(x_i - y_i) \pmod{m}\]
已知 \(m\) 为素数时，对任何 \(z \in \mathbb{Z}_m\)（\(z \neq 0\)），存在唯一 \(z^{-1}\) 使得 \(z \cdot z^{-1} \equiv 1 \pmod{m}\)
由于 \(x_0 \neq y_0\)，\((x_0 - y_0)\) 的逆存在，则：
\[ a_0 \equiv -(x_0 - y_0)^{-1} \sum_{i=1}^{r} a_i(x_i - y_i) \pmod{m} \] 对 \(a_1, \ldots, a_r\) 的任何选择，恰好有一个 \(a_0\) 使得 \(x\) 和 \(y\) 冲突
导致冲突的 \(h_a\) 数量为 \(m^r = \frac{|\mathcal{H}|}{m}\)，满足通用性定义
Carter-Wegman 通用哈希族 (1979)
\[h_{a,b}(k) = ((ak + b) \mod p) \mod m\]
- \(p\) 是大于所有键值的素数
- \(a \in \{1, 2, \ldots, p-1\}\)，\(b \in \{0, 1, \ldots, p-1\}\)
- \(m\) 可以是任意正整数
对 \(k \neq l\)，映射 \((k, l) \mapsto (ak + b \mod p, al + b \mod p)\) 是双射，冲突概率 \(\leq 1/m\)
优点：只需两个数 \(a, b\) 表示一个函数，实现简单
完美哈希
给定 \(n\) 个键的静态集合，构造大小 \(m = O(n)\) 的哈希表，SEARCH 最坏 \(\Theta(1)\)
两级方案
核心思想：两级都使用通用哈希
第一级：用 \(h\) 将 \(n\) 个键映射到 \(m\) 个槽位（\(m = O(n)\)）
第二级：对每个槽位 \(j\)（有 \(n_j\) 个键），用大小 \(m_j = n_j^2\) 的二级表和独立的通用哈希函数，第二级没有冲突
示例
键集合 \(\{31, 14, 27, 26, 9, 86, 40, 37, 22\}\)，\(m = 9\)：
1 | T[1]: S₁ → {14, 27}，m₁ = 4 |
第二级无冲突的保证
定理：设 \(\mathcal{H}\) 是通用哈希函数类，表大小 \(m = n^2\)。若用随机 \(h \in \mathcal{H}\) 将 \(n\) 个键哈希到表中，期望冲突数最多 \(\frac{1}{2}\)
点击查看证明
由通用性，任意两个键冲突概率为 \(\frac{1}{m} = \frac{1}{n^2}\)
可能冲突的键对数量为 \(\binom{n}{2}\)，期望冲突数为：
\[ \binom{n}{2} \cdot \frac{1}{n^2} = \frac{n(n-1)}{2n^2} = \frac{n-1}{2n} < \frac{1}{2} \]
由 Markov 不等式：\(\Pr\{X \geq 1\} \leq E[X] < \frac{1}{2}\)
因此无冲突概率 \(> \frac{1}{2}\)，期望只需测试 2 次即可找到无冲突的函数
存储空间分析
定理：将 \(n\) 个键存在大小 \(m = n\) 的一级表中，使用从通用类中随机选择的哈希函数 \(h\)，则： \[ E\left[\sum_{j=0}^{m-1} n_j^2\right] < 2n \]
点击查看证明
\[ \sum_{j=0}^{m-1} n_j^2 = \sum_{j=0}^{m-1} (n_j + 2\binom{n_j}{2}) = n + 2 \cdot (\text{冲突总数}) \]
冲突总数期望 \(\leq \binom{n}{2} \cdot \frac{1}{m} = \frac{n(n-1)}{2n} = \frac{n-1}{2}\)
\[ E\left[\sum n_j^2\right] \leq n + 2 \cdot \frac{n-1}{2} = 2n - 1 < 2n \]
二级表总大小期望 \(< 2n\)，完美哈希总空间 \(O(n)\)
完美哈希的构造
- 找好的一级哈希函数：从通用族随机选择 \(h\)，检查 \(\sum n_j^2 < 4n\)，期望约一半函数满足，期望尝试 2 次
- 对每个桶构造无冲突的二级哈希函数：大小 \(n_j^2\) 的表，随机选择 \(h_j\)，无冲突概率 \(\geq 1/2\)，期望尝试 2 次
总构造时间 \(O(n)\) 期望
开放寻址
不使用哈希表以外的额外存储空间，插入时系统地探测表中槽位直到找到空槽
哈希函数依赖键和探测序号：\(h: U \times \{0, 1, \ldots, m-1\} \rightarrow \{0, 1, \ldots, m-1\}\)
探测序列 \(\langle h(k,0), h(k,1), \ldots, h(k,m-1) \rangle\) 应该是 \(\{0, 1, \ldots, m-1\}\) 的一个排列
插入示例
1 | 插入 k = 496: |
查找使用相同的探测序列，找到目标键则成功，遇到空槽则失败
探测策略
线性探测
\[ h(k, i) = (h'(k) + i) \mod m \]
实现简单，但存在一次聚集问题：已占用槽位形成的长连续段倾向于变得更长（长度为 \(t\) 的段被新元素”击中”概率正比于 \(t\)，导致正反馈）
双重哈希
\[ h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m \]
通常产生很好的结果，\(h_2(k)\) 必须与 \(m\) 互素
一种方法是让 \(m\) 为 2 的幂，\(h_2(k)\) 只产生奇数
开放寻址的分析
均匀哈希假设：每个键以等概率产生 \(m!\) 种排列中的任一种作为探测序列（比 SUHA 更强）
不成功查找的期望探测次数
定理：装载因子 \(\alpha = \frac{n}{m} < 1\)，不成功查找（或插入）期望探测次数最多 \(\frac{1}{1 - \alpha}\)
点击查看证明
设 \(X\) 为探测次数，事件 \(A_i\)：第 \(i\) 次探测命中已占用槽
\[\{X \geq i\} = A_1 \cap A_2 \cap \cdots \cap A_{i-1}\]
\[\Pr\{A_1 \cap \cdots \cap A_{i-1}\} = \Pr\{A_1\} \cdot \Pr\{A_2 | A_1\} \cdots\]
各项概率： - \(\Pr\{A_1\} = \frac{n}{m} = \alpha\) - \(\Pr\{A_2 | A_1\} = \frac{n-1}{m-1} \leq \alpha\) - \(\Pr\{A_j | A_1 \cap \cdots \cap A_{j-1}\} = \frac{n-j+1}{m-j+1} \leq \alpha\)
因此 \(\Pr\{X \geq i\} \leq \alpha^{i-1}\)
\[ E[X] = \sum_{i=1}^{\infty} \Pr\{X \geq i\} \leq \sum_{i=1}^{\infty} \alpha^{i-1} = \frac{1}{1 - \alpha} \]
成功查找的期望探测次数
定理：\(\alpha < 1\) 时，期望探测次数最多 \(\frac{1}{\alpha} \ln \frac{1}{1 - \alpha}\)
点击查看证明
搜索第 \((i+1)\) 个插入的元素的期望探测次数 \(\leq \frac{1}{1-\frac{i}{m}} = \frac{m}{m-i}\)
对所有 \(n\) 个键取平均：
\[ \frac{1}{n} \sum_{i=0}^{n-1} \frac{m}{m-i} = \frac{1}{\alpha} \sum_{i=0}^{n-1} \frac{1}{m-i} = \frac{1}{\alpha} (H_m - H_{m-n}) \\ \leq \frac{1}{\alpha} \ln \frac{m}{m-n} = \frac{1}{\alpha} \ln \frac{1}{1-\alpha} \]
实际意义
| 装载因子 \(\alpha\) | 不成功查找 \(\frac{1}{1-\alpha}\) | 成功查找 \(\frac{1}{\alpha}\ln\frac{1}{1-\alpha}\) |
|---|---|---|
| 0.5 | 2 | 1.39 |
| 0.75 | 4 | 1.85 |
| 0.9 | 10 | 2.56 |
| 0.95 | 20 | 3.15 |
\(\alpha\) 为常数（\(< 1\)）时，访问需常数时间，但接近满载时性能急剧下降
布谷鸟哈希
Pagh 和 Rodler (2001) 提出
结构：两个哈希表 \(T_1, T_2\)，各大小 \(m = (1+\varepsilon)n\)，两个哈希函数 \(h_1, h_2\)
查找：检查 \(T_1[h_1(x)]\) 和 \(T_2[h_2(x)]\)，最坏 2 次访问
插入算法
1 | Insert(x, i): |
像布谷鸟一样”驱逐”现有居民，循环直到找到空位
插入失败的处理
失败原因：空间不足、路径形成循环、链太长
标准方案：重新哈希——选择新哈希函数，重新插入所有元素
改进方案 (Kirsch, Mitzenmacher, Wieder, 2008)：使用 stash（小辅助存储），将插入最坏情况降低到 \(O(\log n)\)
布谷鸟图
将结构看作二部图：左顶点集 \(L\) 和右顶点集 \(R\)，各大小 \(m\)，每个元素 \(x\) 对应边 \((h_1(x), h_2(x))\)
\(S\) 被成功存储 \(\Leftrightarrow\) 每个连通分量最多一个环
性质
- 查找和删除：最坏 2 次访问（可并行化）
- 插入：摊还常数时间
- 合理的内存利用率
- 无动态内存分配
布隆过滤器
给定集合 \(S = \{x_1, \ldots, x_n\}\)，全域 \(U\)，回答查询 “\(y \in S\)？”
特点：常数时间、小空间、但有假阳性
工作原理
\(m\) 位数组 \(B\)，全初始化为 0
插入：对每个 \(x_j \in S\)，用 \(k\) 个哈希函数 \(H_1, \ldots, H_k\)，将 \(B[H_i(x_j)]\) 设为 1
查询：检查 \(H_1(y), \ldots, H_k(y)\) 对应位是否全为 1 - 任何一位为 0：\(y\) 肯定不在 \(S\) 中（无假阴性） - 全为 1：\(y\) 可能在 \(S\) 中（可能假阳性）
假阳性率分析
\(p = (1 - \frac{1}{m})^{kn} \approx e^{-\frac{kn}{m}}\)（某一位仍为 0 的概率）
假阳性概率：
\[ f = (1 - p)^k \approx (1 - e^{-\frac{kn}{m}})^k \]
最优哈希函数个数
令 \(f\) 对 \(k\) 求导并令其为 0：\(k^* = \frac{m}{n} \ln 2\)
此时 \(f^* = (\frac{1}{2})^k = (0.6185)^{\frac{m}{n}}\)
示例：\(\frac{m}{n} = 8\)（每元素 8 位），\(k^* \approx 5.45\)，取 \(k = 5\) 或 \(6\)，假阳性率约 \(2\%\)
应用
分布式系统中的 Web 缓存：每个缓存节点维护存储 URL 的布隆过滤器，节点间交换过滤器，查找 URL 时先检查过滤器
Count-Min Sketch
数据流中频率估计的概率数据结构
结构：\(t \times k\) 二维数组 \(C\)，\(t\) 个独立哈希函数，\(k = \frac{1}{\varepsilon}\)，\(t = \log(\frac{1}{\delta})\)
处理 \((j, c)\)：
1 | for i ← 1 to t |
查询元素 \(a\) 的频率：\(\hat{f}_a = \min_{i=1}^{t} C[i][h_i(a)]\)
分析
点击查看详细分析
设随机变量 \(X_i = C[i][h_i(a)] - f_a\)（第 \(i\) 行的误差）
定义 \(Y_{i,j} = \mathbf{1}[h_i(a) = h_i(j)]\)（\(j \neq a\)）
\[X_i = \sum_{j \neq a} f_j \cdot Y_{i,j}\]
由 2-通用性，\(E[Y_{i,j}] = 1/k\)
\[ E[X_i] = \sum_{j \neq a} f_j / k = \frac{\|f\|_1 - f_a}{k} \leq \frac{\|f\|_1}{k} \]
由 Markov 不等式：
\[ \Pr\{X_i \geq \varepsilon \|f\|_1\} \leq \frac{E[X_i]}{\varepsilon \|f\|_1} \leq \frac{1}{\varepsilon k} = \frac{1}{2} \]
取所有 \(t\) 行最小值：
\[ \Pr\left\{\min_i X_i \geq \varepsilon \|f\|_1\right\} \leq \left(\frac{1}{2}\right)^t = \delta \]
以至少 \(1 - \delta\) 的概率：\(f_a \leq \hat{f}_a \leq f_a + \varepsilon \|f\|_1\)
总空间 \(O(\frac{1}{\varepsilon} \log \frac{1}{\delta})\) 个计数器
附录
k-独立哈希
- 2-通用：足以保证链接法 \(O(1+\alpha)\) 期望查找
- 5-通用：足以保证 Cuckoo 哈希 \(O(1)\) 期望插入
- 完全独立：最强保证，但存储本身需 \(\Omega(n)\) 空间
Tabulation Hashing 虽只是 3-独立的，但对很多应用表现与完全独立一样好（Patrascu-Thorup, 2012）
装载因子的经验法则
- 链接法：\(\alpha \leq 1\)（Java HashMap 默认 \(0.75\) 时 rehash）
- 线性探测：\(\alpha \leq 0.5\) 到 \(0.75\)
- 布谷鸟哈希：\(\alpha \leq 0.5\)