第十一讲 开放寻址哈希
哈希的冲突解决方法：上一讲使用的是链表法。本节重点是开放地址法：发生冲突时，通过某种规则在表内寻找另一个空槽位。
线性探查法：
映射函数为 \(h(k, i) = (h'(k) + i) \mod m\)。\(h'(k)\) 是原始哈希函数得到的位置，\(i\) 是探测次数。
最大缺陷是一次聚集。
- 若表中存在聚集（一段连续占用的空间），任何哈希到这段空间及其开头前一个位置的键都会延长此聚集，聚集越长，下一次插入落在该区域概率就越高，由于这种正反馈，长簇会迅速形成。
- 聚集的大小通常为 \(\Theta(\log n)\)，意味着查找和插入的最坏情况或平均情况的性能会随着 \(n\) 的增加而显著下降。
平方探查法：
\(h(k, i) = (h'(k) + c_1 i + c_2 i^2) \mod m\)。
相比于线性探查法改进：有效缓解了“一次聚集”问题——即使两个键的初始位置靠得很近，它们的探测路径也会迅速分叉。
-
二次聚集：如果两个键的初始哈希值 \(h'(k)\) 相同，它们生成的探测序列仍然是完全一样的。虽然比线性探测好，但仍未达到随机探测的理想状态。且二次探测的数学性质比线性探测复杂得多。 Kuszmaul 和 Xi 的最新研究指出：在装载因子 \(\alpha \le 0.089\)时，插入时间为 \(O(1)\)。
-
猜想：只要 \(\alpha \le 1 - \epsilon\)，插入时间应该是 \(O(1/\epsilon)\)。学术界仍在试图证明二次探测在表较满时的严格性能界限。
| 特性 | 线性探测 | 平方探测 |
|---|---|---|
| 探测步长 | 固定为 1 | 随 \(i^2\) 增加 |
| 主要问题 | 一次聚集 | 二次聚集（较轻） |
| CPU 缓存 | 非常友好 | 较差（跳跃性大） |
| 表满时的表现 | 性能急剧下降 | 甚至可能找不到空位 |
双重哈希（Double hashing）
\(h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m\)
解决了线性探测和二次探测的聚集问题，步长由 \(h_2(k)\) 决定。
当\(h_2(k)\)与\(m\)互质时，\(h(k,i)\)可以遍历到所有的槽位。
- 随机性：起始点由 \(h_1(k)\) 决定，探测序列的“节奏”由 \(h_2(k)\) 决定，使得整个序列在宏观上看起来非常接近随机排列。
理想化假设：\(h(k, i)\) 会产生 \([m]\) 空间的一个随机排列。即假设每次探测都是独立且等概率地落在尚未检查过的槽位中。
失败查找次数：claim:在装载因子为 \(\alpha\) 时，不成功查找的预期探测次数 \(\mathbb{E}[X] \le \frac{1}{1-\alpha}\)。
- 事件 \(A_i\)：第 \(i\) 次探测撞到了一个已被占用的槽位。
-
条件概率：如果你已经连续撞到了 \(i-1\) 个占用的槽位，那么在剩余的 \(m-(i-1)\) 个位置中，还有 \(n-(i-1)\) 个是被占用的。因此： $\(\Pr[A_i |A_1A_2\cdots A_{i-1}] = \frac{n-i+1}{m-i+1} \le \frac{n}{m} = \alpha\)$
-
累积概率：需要探测至少 \(i\) 次，意味着前 \(i-1\) 次全都发生了碰撞。其概率 \(\Pr[X \ge i]=\Pr[A_1]\cdot\Pr[A_2|A_1]\cdots\Pr[A_{i-1}|A_1A_2\cdots A_{i-2}] \le \alpha^{i-1}\)
- 对于只取非负整数值的随机变量，\(E[X] = \sum_{i=1}^{\infty} \Pr[X \ge i]\)。 $\(\mathbb{E}[X] \le 1 + \alpha + \alpha^2 + \dots = \frac{1}{1-\alpha}\)$
成功查找次数：成功查找一个键 \(k\) 所需探测次数等于当初插入该键时所进行的探测次数。如果一个键是表中第 \(i+1\) 个被插入的，那么插入它时的装载因子是 \(i/m\)。利用之前所计算的失败平均查找次数，找到空缺并插入该键的预期探测次数是 \(\frac{1}{1 - i/m} = \frac{m}{m-i}\)
对表中现有的 \(n\) 个键取探测次数平均值：\(\frac{1}{n} \sum_{i=0}^{n-1} \frac{m}{m-i}\)。 $\(\text{Average} \le \frac{1}{\alpha} \int_{m-n}^{m} \frac{1}{x} dx\)$ 得$\(\mathbb{E}[X] \le \frac{1}{\alpha} \ln \frac{1}{1-\alpha}\)$
成功查找总是比不成功查找快。 双重哈希在理论上达到了“均匀散列”的巅峰，它彻底消除了一次和二次聚集。虽然计算两个哈希函数比线性探测多了一点 CPU 开销，但它极大地减少了探测次数，是处理大规模内存哈希表时的首选方案之一。
开放寻址法的优势：无需新内存分派，高度连续的，利好cache的性能；劣势：对哈希函数高度敏感，存在聚集问题，当装载因子靠近1时性能很差。