哈希碰撞概率计算

假如取值空间为 $d$，取值范围为 $n$，可得均不碰撞的概率为：

$$\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 – \overline{p}(n)$$

根据泰勒公式，指数函数 $e^x$ 可以展开成多项式

$$e^x = \sum_{k=1}^\infty \frac{x^k}{k!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \cdots$$

当 $ x \to 0$ 时，

$$e^x \approx 1 + x $$

代入$-\dfrac{1}{d}$可得：

$$e^{-\frac{1}{d}} \approx 1 -\frac{1}{d}$$

代入$p(n)$ 可得：

$$p(n,d) \approx 1 – e^{ – \frac{n(n – 1)}{2d}}$$

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