哈希表通常被描述成“均摊 O(1)O(1)”的数据结构。这个说法在日常编程里很好用但它暗含了一个前提输入没有系统性地撞向同一批桶。只要这个前提失效哈希表就会从一个轻快的工具变成一条很长的链表或者一段反复探测的泥潭。当输入可能很坏或者你无法相信输入分布时怎样用随机化把坏运气挡在门外。确定性哈希的脆弱之处考虑一个最普通的链地址哈希表。表有 mm 个桶插入 nn 个键负载因子是 αn/mαn/m。如果每个键都像独立随机地落入桶中那么某个桶的期望长度大约是 αα查询一个键的代价也接近 O(1α)O(1α)。问题在于如果程序里的哈希函数通常是确定的。给定同一个键永远得到同一个桶。于是对某个固定哈希函数 hh完全可能存在一批键 x1,x2,…,xnx1​,x2​,…,xn​满足h(x1)h(x2)⋯h(xn)h(x1​)h(x2​)⋯h(xn​)这时链地址哈希表的一次查询可能退化到 O(n)O(n)如果插入过程中还需要查重整体可能接近 O(n2)O(n2)。开放寻址也没有逃过这个问题只是坏情况从“链很长”变成了“探测序列很长”。很多时候这不是理论洁癖。在线评测、Web 服务、日志聚合、编译器符号表都会遇到“输入不是你以为的随机输入”的场景。攻击者不需要破解你的整个程序只要能构造大量哈希冲突就可能让一个看起来线性的接口拖垮。问题不是哈希表不快而是一个公开且固定的哈希函数可能把坏输入变成坏复杂度。一个直接想法是“换一个更好的哈希函数”。但只要函数是固定且公开的理论上仍然可以为它构造坏输入。随机化的关键不是寻找某个永远不会坏的函数而是在程序运行时从一族函数里随机选一个。更准确地说哈希表不再只使用一个 hh而是有一个函数族 HH。程序启动或表创建时随机选出 h∈Hh∈H之后这个表一直使用它。这样一来输入可以是固定的、甚至可以是恶意构造的但是攻击者不知道本次运行选中了哪个 hh。虽然这个 hh 对应的坏情况仍然存在只是它不再能稳定命中。我们把确定性保证换成了概率保证。这和排序里的随机快速排序很像。如果我能看到某人写的快排如果选择 pivot我就总能找到一个序列让他选出最坏 pivot 退化复杂度但如果 pivot 是真正随机选的那么对于任意固定输入期望时间仍然是 O(nlog⁡n)O(nlogn)。从“均匀哈希”到“通用哈希”如果抛开计算机实现回到数学最理想的模型是有一个完全随机独立的映射函数。每个键都被完全独立、均匀地映射到 mm 个桶之一。这个模型很干净但真正实现一个“完全随机函数”代价极高因为它等价于为每个可能的键保存一份随机映射。工程和理论中更常用的是通用哈希。一个哈希函数族 HH 被称为通用的通常指对于任意两个不同的键 x≠yxy随机选 h∈Hh∈H 后有Pr⁡h∈H[h(x)h(y)]≤1mh∈HPr​[h(x)h(y)]≤m1​这个定义只关心两两冲突概率。它没有要求所有键完全独立也没有要求每个桶的分布在所有细节上都完美。好处是实现成本低很多而且已经足够推导哈希表的期望复杂度。设表里已有键集合 SS查询键 xx。对每个 y∈S,y≠xy∈S,yx定义指示变量Iy{1,h(x)h(y)0,h(x)≠h(y)Iy​{1,0,​h(x)h(y)h(x)h(y)​和 xx 冲突的键数量是 Cx∑y∈S,y≠xIyCx​∑y∈S,yx​Iy​。由期望线性性可得E[Cx]∑y∈S,y≠xE[Iy]∑y∈S,y≠xPr⁡[h(x)h(y)]≤n−1mE[Cx​]y∈S,yx∑​E[Iy​]y∈S,yx∑​Pr[h(x)h(y)]≤mn−1​也就是 E[Cx]≤αE[Cx​]≤α。链地址哈希表中一次查询的期望代价就是 O(1α)O(1α)。这个推导并没有证明“每个桶都很短”。它证明的是对于一个固定查询期望遇到的冲突数量不大。某次运行仍然可能出现很长的桶只是概率被控制住了。如果你需要的是强尾界或最坏情况保证还要引入更强的独立性、再哈希策略或者换成确定性平衡结构。一个经典构造模素数的线性哈希假设键可以看作 0,1,…,p−10,1,…,p−1 中的整数其中 pp 是素数。可以随机选 a,ba,b其中 a∈1,…,p−1a∈1,…,p−1b∈0,…,p−1b∈0,…,p−1定义ha,b(x)(axb)modpha,b​(x)(axb)modp如果桶数也是 pp这个函数族在素数域上有很好的两两独立性质。直觉上看对于不同的 xx 和 yy方程组axb≡u(modp),ayb≡v(modp)axb≡u(modp),ayb≡v(modp)在 x≠yxy 时有唯一解因为 x−yx−y 在模 pp 意义下存在逆元。这意味着两个不同键的哈希值不会被某种固定关系强行绑在一起。现实中桶数通常不是素数而是 2k2k 或某个动态扩容后的容量。把上面的结果直接再对 mm 取模会引入一点偏差。很多程序里这点偏差可以接受但如果你在写的是严肃的哈希表库就需要更仔细地处理映射到桶的过程比如使用乘法缩放、拒绝采样或直接选择更贴合机器字长的哈希方案。机器上的随机化乘法、移位和混合在实际代码里取模素数不一定便宜尤其是在热路径上。现代哈希表常常偏好容量为 2k2k这样桶下标可以通过位运算得到。问题是如果直接取低 kk 位很多整数键会表现得很差。例如连续偶数的最低位永远是 00按低位分桶会让一半桶空着。更常见的做法是先把键“打散”再取高位或低位。一个简化的乘法哈希形式是ha(x)⌊(axmod2w)2w−k⌋ha​(x)⌊2w−k(axmod2w)​⌋这里 ww 是机器字长表大小是 m2km2kaa 通常取随机奇数。表达式的含义是先让乘法在 ww 位整数上自然溢出再取结果的高 kk 位作为桶下标。取高位是有原因的乘法的低位往往保留了输入低位的某些规律而高位通常混合得更充分。很多语言标准库的hashint并不一定做强混合。有些实现里整数的哈希值就是它自己。对普通业务数据这未必有问题但在在线评测或对抗输入下就很脆弱。C 里常见的防御写法是给unordered_map配一个带随机种子的混合函数#include bits/stdc.husing 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);