通用哈希

形式陈述 ​

设键域为 $U$，槽集合为 $[m]=\{0,\dots ,m-1\}$。函数族 $\mathcal{H}\subseteq [m{]}^U$ 称为 universal，若对任意不同键 $x,y\in U$，按指定分布公理库概率分布Probability distribution · Law定义在可测空间上的概率测度；随机变量的律是由推前得到的一类分布。随机选择 $h\in \mathcal{H}$ 时都有

$${\text{Pr}}_{h\sim \mathcal{H}}[h(x)=h(y)]\le \frac{1}{m}.$$

若对任意 $a,b\in [m]$ 还满足 $\text{Pr}[h(x)=a\wedge h(y)=b]=1/m^2$，则哈希值是 pairwise independent；这是比只控制碰撞概率更强的条件，不能把两个术语当作同义词。

一个标准构造令 $U\subseteq \{0,\dots ,p-1\}$，其中 $p$ 为素数，并取

$$h_{a,b}(x)=((ax+b)modp)modm,a\in \{1,\dots ,p-1\},b\in \{0,\dots ,p-1\}.$$

均匀抽取 $(a,b)$ 得到 universal 族。对预先固定的 $n$ 个键，链地址哈希表公理库哈希表Hash table用哈希函数把键映射到桶并处理冲突的字典结构。中某个固定键的期望碰撞数至多 $(n-1)/m$，故在负载因子 $\alpha =n/m$ 受常数控制时，查询的期望成本为 $O(1+\alpha )$。

直觉 ​

通用哈希不假设输入键“自然随机”，而把随机性放到建表时选择的函数上。键集可以是最坏情况，只要它在随机种子选定前已经固定，任意一对键都难以稳定地被整个函数族送进同一槽。分析因此针对算法自己的随机选择，而不是把现实数据分布理想化。

随机化公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。解决的是可预测冲突：固定函数总可能遇到专门构造的坏键集；从受控函数族抽样后，攻击者若不知道选择结果，就不能让所有候选函数同时产生同样的聚集。性质是关于函数族和抽样分布的，不是某一个已选函数“永不碰撞”。

例子与边界 ​

取素数 $p=7$、槽数 $m=5$，函数 $h_{3,1}(x)=((3x+1)mod7)mod5$ 会让某些键碰撞；例如 $h_{3,1}(0)=1$、$h_{3,1}(4)=1$。这不违反 universal 性，因为定义控制的是随机选择 $(a,b)$ 后固定键对的碰撞概率，并不要求每个族成员都是无碰撞函数。

对集合 $S$ 中固定键 $x$，令 $I_y$ 表示 $y\ne x$ 与 $x$ 碰撞。线性期望给出

$$\mathbb{E}\left[\sum _{y\in S\setminus \{x\}}{I}_y\right]=\sum _{y\ne x}\text{Pr}[h(y)=h(x)]\le \frac{n-1}{m},$$

该推导不要求所有 $I_y$ 相互独立。它解释了 universal 条件为何足以支撑链地址法的单键期望界，也说明 pairwise independence 在这里不是必需前提。

若攻击者先观察已选函数或种子，再自适应提交碰撞键，标准“固定键集”分析便可能失效；服务端哈希防洪需要隐藏随机密钥、定期重播种或使用更强的伪随机构造。通用哈希也不是密码学抗碰撞：后者要求计算上难以找到碰撞，面对的是已知函数，安全目标完全不同。

推论与应用 ​

通用哈希给字典、静态完美哈希和随机化负载均衡提供可证明的输入无关期望界。它把“平均 $O(1)$”从含糊的数据均匀假设改写成明确概率空间：固定键集、随机函数、对函数选择取期望。选择函数族时还需计算哈希本身的成本；一个统计性质良好却求值昂贵的族，不会自动得到快速实现。

更强的 $k$-wise independence、tabulation hashing 与 keyed hashing 分别服务于浓缩界、工程速度和对手模型。使用哪一种，应由证明实际需要的独立性阶数和威胁模型决定，而不是把“随机哈希”当成单一保证。

参考资料

• J. Lawrence Carter and Mark N. Wegman, “Universal Classes of Hash Functions,” Journal of Computer and System Sciences 18(2), 1979, pp. 143–154.
• Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, §11.3, universal hashing.