2-choice hashing（双选哈希）的哈希碰撞率计算方法

常规哈希碰撞率 #

常规哈希函数的碰撞率可以通过数学推导或者暴力枚举计算得出，参考计算逻辑见下图：

从计算结果能看出来，32位长度的常规哈希碰撞概率是比较高的。

双选哈希（2-choice hashing）变体碰撞概率计算 #

你使用的两个独立哈希函数生成哈希键的变体方案，碰撞概率可以按以下逻辑计算，前提是两个哈希函数完全独立、输出值均匀分布：

• 先明确参数：设哈希位长为n，对应总哈希空间大小N = 2^n（比如32位哈希对应N=2^32，约42.9亿），总共要存入m个元素。
• 先对照单哈希的碰撞概率：单哈希场景下m个元素至少出现一次碰撞的概率符合生日悖论公式，当m远小于N时近似为P单 = 1 - e^(-m²/(2N))，这也是32位单哈希碰撞率偏高的原因。
• 双选哈希的碰撞触发条件比单哈希严格很多：插入新元素时会算出两个哈希值，只有当新元素的两个哈希值，刚好和某个已存入元素的两个哈希值完全匹配（不考虑顺序）时，才会发生键碰撞。
  • 单对元素（一个新元素+一个已存元素）的碰撞概率为2/N²：新元素的第一个哈希匹配旧元素两个哈希中任意一个，第二个哈希匹配旧元素剩下的那个，总共有2种匹配组合。
  • 当m远小于N时，m个元素至少出现一次碰撞的概率可以近似为：P双选 ≈ 1 - e^(-m²/N²)

拿32位哈希做个直观对比：插入10万元素时，单哈希的碰撞概率约为69%，而双选哈希的碰撞概率仅约为百万分之0.5，抗碰撞能力提升了6个数量级，降碰撞效果非常明显。

• 工程实现注意：上面的理论值是基于两个哈希完全独立的前提，如果两个哈希函数存在输出相关性，实际碰撞概率会比理论值高，建议选用不同种子的非加密哈希（比如MurmurHash、XXHash）做双哈希计算，避免哈希关联带来的碰撞率抬升。

内容的提问来源于stack exchange，提问作者Frei Zhang