通用哈希 | Codeboy's Blog

形式陈述

设键域为 $U$ ，槽集合为 $[m]=\{0,\ldots,m-1\}$ 。函数族 $\mathcal H\subseteq[ m]^U$ 称为 universal，若对任意不同键 $x,y\in U$ ，按指定分布随机选择 $h\in\mathcal H$ 时都有

\Pr_{h\sim\mathcal H}[h(x)=h(y)]\le\frac1m.

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

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

h_{a,b}(x)=((ax+b)\bmod p)\bmod m, \qquad a\in\{1,\ldots,p-1\},\ b\in\{0,\ldots,p-1\}.

均匀抽取 $(a,b)$ 得到 universal 族。对预先固定的 $n$ 个键，链地址哈希表中某个固定键的期望碰撞数至多 $(n-1)/m$ ，故在负载因子 $\alpha=n/m$ 受常数控制时，查询的期望成本为 $O(1+\alpha)$ 。

直觉

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

随机化解决的是可预测冲突：固定函数总可能遇到专门构造的坏键集；从受控函数族抽样后，攻击者若不知道选择结果，就不能让所有候选函数同时产生同样的聚集。性质是关于函数族和抽样分布的，不是某一个已选函数“永不碰撞”。

例子与边界

取素数 $p=7$ 、槽数 $m=5$ ，函数 $h_{3,1}(x)=((3x+1)\bmod7)\bmod5$ 会让某些键碰撞；例如 $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}\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.

形式陈述 ​

反向链接

形式陈述