在计算机科学和算法竞赛中，Hash 的错误率分析（通常指哈希冲突率分析）指的是：评估不同的输入（如不同的字符串）通过哈希函数计算后，意外得到相同哈希值的概率。

简单来说，就是算一算“你的哈希算法有多大 概率 会翻车”。

在 OI Wiki 字符串哈希 中，这一节的核心目的就是通过数学公式告诉你：为什么看起来很大的模数（比如 $10^9$），在面对几万个字符串时依然极其容易发生冲突。

---

核心幕后推手：生日悖论 (Birthday Paradox)

很多人直觉上认为：如果我的哈希值取值空间有 $M = 10^9$ 那么大，我只放入 $N = 10^5$ 个字符串，坑位远多于萝卜，怎么可能会撞？

但现实是残酷的。这就像在一个 23 人的房间里，两个人生日相同的概率就已经超过了 50%，而不是直觉上的 $\frac{23}{365}$。因为冲突关注的是两两配对组合。

1. 数学公式推导

假设你要计算 $N$ 个字符串的哈希值，哈希值的总空间（模数，所有可能出现的字符串的数量）为 $M$。 哈希完全不冲突的概率为：

$$\overline{P}(N, M) = 1 \cdot \left(1 - \frac{1}{M}\right) \cdot \left(1 - \frac{2}{M}\right) \cdots \left(1 - \frac{N-1}{M}\right)$$

利用泰勒展开式 $e^x \approx 1 + x$（当 $x$ 极小时）进行近似化简，可以得到哈希发生冲突（错误）的概率公式：

$$P(N, M) \approx 1 - e^{-\frac{N(N-1)}{2M}} \approx 1 - e^{-\frac{N^2}{2M}}$$

2. 这个公式告诉我们什么？

注意看指数部分：$\frac{N^2}{2M}$。这意味着错误率不是随着 $N$ 线性增长的，而是随着 $N$ 的平方 ($N^2$) 级数爆炸增长！

📌 关键结论 当你的数据量 $N$ 达到 $\sqrt{M}$ 级别时，哈希冲突的概率就会发生质变，急剧飙升。

---

来看一个惨痛的实例

在单哈希中，大家很喜欢用 $M = 10^9+7$ 或 $10^9+9$ 作为模数。

• 如果你有 $N = 10^5$ 个串，$\sqrt{M} \approx 31622$。此时 $N$ 已经远超 $\sqrt{M}$。
• 带入公式计算，$P \approx 1 - e^{-\frac{10^{10}}{2 \times 10^9}} = 1 - e^{-5} \approx 99.33\%$。

也就是说，仅仅 $10^5$ 个数据，单哈希的错误率就已经高达 99.33%。在评测机成百上千的数据点轰炸下，必然会 WA（Wrong Answer）。

---

如何解决这种高错误率？

既然分析出了错误率的原因，解决办法也就显而易见了：

1. 增大值域空间 $M$：使用 unsigned long long 自然溢出，相当于把 $M$ 扩大到 $2^{64} \approx 1.8 \times 10^{19}$。此时 $\sqrt{M} \approx 4 \times 10^9$，对抗 $10^5$ 级别的数据绰绰有余（但要注意，自然溢出容易被特定的数据恶意卡掉）。
2. 多值 Hash（双哈希）：同时用两个不同的质数作为模数（比如 $M_1 = 10^9+7, M_2 = 10^9+9$）算两次哈希。只有两个哈希值都相等才算相等。这时总空间变成了 $M_1 \times M_2 \approx 10^{18}$，错误率直接降到微乎其微的级别。

---

学习完毕

{{ select(1) }}

• YES
• NO