哈希碰撞概率计算
文章转载自我自己的小破站，欢迎大佬们进来瞧一瞧
数学推导
假如取值空间为 d d d，取值范围为 n n n，可得均不碰撞的概率为：
p ‾ ( n ) = 1 ⋅ ( 1 − 1 d ) ⋅ ( 1 − 2 d ) ⋯ ( 1 − n − 1 d ) \overline{p}(n) = 1 \cdot \Big(1 - \frac{1}{d}\Big) \cdot \Big(1 - \frac{2}{d}\Big) \cdots \Big(1 - \frac{n-1}{d}\Big) p(n)=1⋅(1−d1)⋅(1−d2)⋯(1−dn−1)
推导可得，存在碰撞的概率为：
p ( n ) = 1 − p ‾ ( n ) p(n) = 1 - \overline{p}(n) p(n)=1−p(n)
根据泰勒公式，指数函数 e x e^x ex 可以展开成多项式
e x = ∑ k = 1 ∞ x k k ! = 1 + x + x 2 2 + x 3 6 + ⋯ e^x = \sum_{k=1}^\infty \frac{x^k}{k!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \cdots ex=k=1∑∞k!xk=1+x+2x2+6x3+⋯
当 $ x \to 0$ 时，
e x ≈ 1 + x e^x \approx 1 + x ex≈1+x
代入 − 1 d -\dfrac{1}{d} −d1可得：
e − 1 d ≈ 1 − 1 d e^{-\frac{1}{d}} \approx 1 -\frac{1}{d} e−d1≈1−d1
代入 p ( n ) p(n) p(n) 可得：
p ( n , d ) ≈ 1 − e − n ( n − 1 ) 2 d p(n,d) \approx 1 - e^{ - \frac{n(n - 1)}{2d}} p(n,d)≈1−e−2dn(n−1)
代码实现
const calculate = (d, n) => {
const exponent = (-n * (n - 1)) / (2 * d)
return 1 - Math.E ** exponent;
}
模拟场景
如果使用时间戳作为输入生成哈希值，发生哈希碰撞的概率是多少？
// qps = 1
calculate(1000, 1); // 0
// qps = 38
calculate(1000, 38); // 0.5049022197190565
// qps = 50
calculate(1000, 50); // 0.7062422996764672
参考文献
[1] http://ruanyifeng.com/blog/2018/09/hash-collision-and-birthday-attack.html