把坏运气关在门外：哈希的随机化之路

哈希表通常被描述成“均摊 $O(1)$”的数据结构。这个说法在日常编程里很好用，但它暗含了一个前提：输入没有系统性地撞向同一批桶。只要这个前提失效，哈希表就会从一个轻快的工具变成一条很长的链表，或者一段反复探测的泥潭。

当输入可能很坏，或者你无法相信输入分布时，怎样用随机化把坏运气挡在门外。

确定性哈希的脆弱之处

考虑一个最普通的链地址哈希表。表有 $m$ 个桶，插入 $n$ 个键，负载因子是 $\alpha = n / m$。如果每个键都像独立随机地落入桶中，那么某个桶的期望长度大约是 $\alpha$，查询一个键的代价也接近 $O(1 + \alpha)$。

问题在于，如果程序里的哈希函数通常是确定的。给定同一个键，永远得到同一个桶。于是对某个固定哈希函数 $h$，完全可能存在一批键 $x_1, x_2, \dots, x_n$，满足：

$$h(x_1) = h(x_2) = \cdots = h(x_n)$$

这时链地址哈希表的一次查询可能退化到 $O(n)$，如果插入过程中还需要查重，整体可能接近 $O(n^2)$。开放寻址也没有逃过这个问题，只是坏情况从“链很长”变成了“探测序列很长”。

很多时候这不是理论洁癖。在线评测、Web 服务、日志聚合、编译器符号表，都会遇到“输入不是你以为的随机输入”的场景。攻击者不需要破解你的整个程序，只要能构造大量哈希冲突，就可能让一个看起来线性的接口拖垮。

问题不是哈希表不快，而是：一个公开且固定的哈希函数，可能把坏输入变成坏复杂度。

一个直接想法是“换一个更好的哈希函数”。但只要函数是固定且公开的，理论上仍然可以为它构造坏输入。随机化的关键不是寻找某个永远不会坏的函数，而是在程序运行时从一族函数里随机选一个。

更准确地说，哈希表不再只使用一个 $h$，而是有一个函数族 $\mathcal{H}$。程序启动或表创建时，随机选出 $h \in \mathcal{H}$，之后这个表一直使用它。

这样一来，输入可以是固定的、甚至可以是恶意构造的，但是攻击者不知道本次运行选中了哪个 $h$。虽然这个 $h$ 对应的坏情况仍然存在，只是它不再能稳定命中。我们把确定性保证换成了概率保证。

这和排序里的随机快速排序很像。如果我能看到某人写的快排如果选择 pivot，我就总能找到一个序列让他选出最坏 pivot 退化复杂度；但如果 pivot 是真正随机选的，那么对于任意固定输入，期望时间仍然是 $O(n \log n)$。

从“均匀哈希”到“通用哈希”

如果抛开计算机实现回到数学，最理想的模型是有一个"完全随机独立的映射函数"。每个键都被完全独立、均匀地映射到 $m$ 个桶之一。这个模型很干净，但真正实现一个“完全随机函数”代价极高，因为它等价于为每个可能的键保存一份随机映射。

工程和理论中更常用的是通用哈希。一个哈希函数族 $\mathcal{H}$ 被称为通用的，通常指对于任意两个不同的键 $x \ne y$，随机选 $h \in \mathcal{H}$ 后，有：

$$\Pr_{h \in \mathcal{H}}[h(x) = h(y)] \le \frac{1}{m}$$

这个定义只关心两两冲突概率。它没有要求所有键完全独立，也没有要求每个桶的分布在所有细节上都完美。好处是实现成本低很多，而且已经足够推导哈希表的期望复杂度。

设表里已有键集合 $S$，查询键 $x$。对每个 $y \in S, y \ne x$，定义指示变量：

$$I_y = \begin{cases} 1, & h(x) = h(y) \\ 0, & h(x) \ne h(y) \end{cases}$$

和 $x$ 冲突的键数量是 $C_x = \sum_{y \in S, y \ne x} I_y$。由期望线性性可得：

$$\mathbb{E}[C_x] = \sum_{y \in S, y \ne x} \mathbb{E}[I_y] = \sum_{y \in S, y \ne x} \Pr[h(x) = h(y)] \le \frac{n - 1}{m}$$

也就是 $\mathbb{E}[C_x] \le \alpha$。链地址哈希表中，一次查询的期望代价就是 $O(1 + \alpha)$。

这个推导并没有证明“每个桶都很短”。它证明的是，对于一个固定查询，期望遇到的冲突数量不大。某次运行仍然可能出现很长的桶，只是概率被控制住了。如果你需要的是强尾界或最坏情况保证，还要引入更强的独立性、再哈希策略，或者换成确定性平衡结构。

一个经典构造：模素数的线性哈希

假设键可以看作 ${0, 1, \dots, p-1}$ 中的整数，其中 $p$ 是素数。可以随机选 $a, b$，其中 $a \in {1, \dots, p-1}$，$b \in {0, \dots, p-1}$，定义：

$$h_{a,b}(x) = (a x + b) \bmod p$$

如果桶数也是 $p$，这个函数族在素数域上有很好的两两独立性质。直觉上看，对于不同的 $x$ 和 $y$，方程组

$$a x + b \equiv u \pmod p,\quad a y + b \equiv v \pmod p$$

在 $x \ne y$ 时有唯一解，因为 $x-y$ 在模 $p$ 意义下存在逆元。这意味着两个不同键的哈希值不会被某种固定关系强行绑在一起。

现实中桶数通常不是素数，而是 $2^k$ 或某个动态扩容后的容量。把上面的结果直接再对 $m$ 取模，会引入一点偏差。很多程序里这点偏差可以接受，但如果你在写的是严肃的哈希表库，就需要更仔细地处理映射到桶的过程，比如使用乘法缩放、拒绝采样，或直接选择更贴合机器字长的哈希方案。

机器上的随机化：乘法、移位和混合

在实际代码里，取模素数不一定便宜，尤其是在热路径上。现代哈希表常常偏好容量为 $2^k$，这样桶下标可以通过位运算得到。问题是，如果直接取低 $k$ 位，很多整数键会表现得很差。例如连续偶数的最低位永远是 $0$，按低位分桶会让一半桶空着。

更常见的做法是先把键“打散”，再取高位或低位。一个简化的乘法哈希形式是：

$$h_a(x) = \left\lfloor \frac{(a x \bmod 2^w)}{2^{w-k}} \right\rfloor$$

这里 $w$ 是机器字长，表大小是 $m = 2^k$，$a$ 通常取随机奇数。表达式的含义是：先让乘法在 $w$ 位整数上自然溢出，再取结果的高 $k$ 位作为桶下标。取高位是有原因的；乘法的低位往往保留了输入低位的某些规律，而高位通常混合得更充分。

很多语言标准库的 hash 并不一定做强混合。有些实现里，整数的哈希值就是它自己。对普通业务数据这未必有问题，但在在线评测或对抗输入下就很脆弱。C++ 里常见的防御写法是给 unordered_map 配一个带随机种子的混合函数：

#include 
using namespace std;
 
struct CustomHash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t seed =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + seed);
    }
};
 
unordered_map<uint64_t, int, CustomHash> mp;

这段代码不应该被神化。splitmix64 是一个很好的非密码学混合函数，但它不是密码学哈希，也不提供严格的通用哈希证明。它的价值在于：固定输入很难稳定命中某次运行的桶分布，尤其能避开很多针对标准整数哈希构造的冲突数据。

有两个实现细节容易踩坑。第一，随机种子应该在哈希器生命周期里保持稳定，不能每次调用 operator() 都重新随机，否则同一个键会找不到原来的位置。第二，混合函数的输出位要尽量都可用，因为底层容器可能只取低若干位，也可能使用取模，不同实现并不完全一致。

期望保证和高概率

通用哈希常常给出漂亮的期望复杂度，但程序员真正关心的有时是尾部风险：某一次请求能不能卡住，某一次构建会不会炸掉。

只知道 $\mathbb{E}[C_x] \le \alpha$，可以用 Markov 不等式得到：

$$\Pr[C_x \ge t] \le \frac{\alpha}{t}$$

这说明冲突数特别大的概率会下降，但下降得不算快。如果希望得到更强的界，比如最大桶长以高概率不太大，通常需要更强的随机性假设，接近“每个键独立均匀落桶”的模型。经典 balls into bins 结果告诉我们，当 $n$ 个键独立均匀放入 $n$ 个桶时，最大桶长大约是 $\frac{\log n}{\log \log n}$ 量级，而不是常数。

这并不意味着哈希表不可靠。它只是提醒我们：均摊 $O(1)$、期望 $O(1)$、高概率 $O(1)$、最坏情况 $O(1)$ 是不同层次的承诺。很多标准哈希表只承诺平均或均摊表现；如果你在写需要硬实时延迟的系统，单靠普通随机哈希并不够。

一些实现会在桶过长时触发再哈希，重新抽一个种子，把所有元素搬到新表里。这个策略的思路是，如果当前随机选择碰到了坏分布，就重抽一次。对于固定输入，多次失败的概率会快速下降。代价也很直接：再哈希会带来一次 $O(n)$ 的停顿，内存占用和实现复杂度也会上升。

拓展

写一个实际可用的哈希表，随机化通常只是其中一层。负载因子控制决定了平均桶长；扩容策略决定了均摊成本；冲突解决方式决定了缓存局部性；哈希函数决定了输入模式如何映射到桶；随机种子则让固定坏输入不容易稳定复现坏分布。

链地址法对删除友好，桶过长时还可以把链表替换成树。开放寻址缓存友好，但对负载因子更敏感，删除和探测策略也更复杂。随机化不能替你解决这些设计问题，它只是减少“某个固定哈希函数被输入拿捏”的概率。

可以把哈希随机化看成一道门。门外仍然有坏运气：碰撞会发生，长桶会出现，再哈希会停顿，非密码学哈希也可能被更强的攻击绕过。但只要种子没有被提前知道，攻击者就不能轻易把一份输入稳定地变成你的最坏情况。

哈希表之所以好用，不是因为碰撞不存在，而是因为我们愿意把碰撞的风险管理起来。确定性哈希把风险固定在代码里；随机化哈希把风险推回概率空间。对程序员来说，这往往就是从“偶尔会被构造数据打穿”到“可以放心放在真实输入前面”的差别。