通用哈希

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

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

取素数 $p=7$、槽数 $m=5$，函数 $h_{3,1}(x)=((3x+1)mod7)mod5$ 会让某些键碰撞；例如 $h_{3,1}(0)=1$、$h_{3,1}(4)=1$。把函数族的全部 $6\times 7=42$ 个参数对都考虑进来，固定键对 $(0,4)$ 的模 $7$ 输出遍历 $42$ 个互异有序对。其中最终碰撞的只有 $(0,5),(5,0),(1,6),(6,1)$ 四对，概率为 $4/42=2/21<1/5$。定义控制的正是这个比例，并不要求每个族成员无碰撞。

对集合 $S$ 中固定键 $x$，令 $I_y$ 表示 $y\ne x$ 与 $x$ 碰撞。期望的线性性理路期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分，概括加权平均与总体质量平衡。给出

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

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

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

剩余哈希引理理路剩余哈希引理Leftover hash lemma · LHL二通用哈希把弱随机源压缩为公开种子和经典旁信息后仍接近均匀的输出，误差由平均条件最小熵控制；条件化与 Jensen 不等式给出证明，三比特例子精确算出联合距离。把同一碰撞概率条件用于随机性提取：当种子独立于弱源与经典旁信息的联合变量时，平均条件最小熵控制输出与公开种子、旁信息联合接近独立均匀的距离。这里使用统计碰撞界，不要求把函数族升级为密码学抗碰撞假设。

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