在计算机科学和算法竞赛中，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}}$$

注意: 实际字符串数量有效上限 $M$ 是 $\min(\text{字符串总种类数}, \text{模数 } M)$。

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}$，错误率直接降到微乎其微的级别。

下面通过两道题目，构造数据卡掉 Hash

例1. P12198 Hash Killer II

【题意简化】进制 Hash 下，$MOD=10^9+7$， 请构造一个长度为 $n$ 的小写字母字符串，使得在这个字符串中，至少有两个不同的长度为 $l$ 的连续子串，它们的哈希值在 $\pmod{10^9+7}$ 下完全相同。(字符串不同，Hash 值相同)

【分析】要卡掉大模数 Hash , 要满足两个条件: 1. 子串种类数要大于 $mod$ ; 2. Hash 冲突概率 $1-e^{-\frac{N^2}{2M}}$ 足够高。

由于是小写字母，那么 $26^l > 10^9+7$，那么 $l > 6$ , 取 $l=7$ ;

$l$ 也不适宜取得过大 ， 长度为 $n$ 的字符串，子串数量是 $n-l$ ， $l$ 过大，子串数量减少。

当 $n=10^5,l=7$ 的情况下，$mod=10^9+7$, Hash 冲突的概率是 $1-e^{-\frac{N^2}{2M}}\approx 99.33\%$

【参考代码】点击

例2. P12197 Hash Killer I

【题意简化】进制 Hash 情况下，unsigned long long 自然溢出，即 $mod=2^{64}$ ,请构造一个长度为 $n$ 的小写字母字符串，使得在这个字符串中，至少有两个不同的长度为 $l$ 的连续子串，它们的哈希值在 $\pmod{2^{64}}$ 下完全相同。(字符串不同，Hash 值相同)

【题意简化】此时模数很大，就不能随机构造。分类讨论，可以构造数据卡掉 ull 。

1. 当 $p$ 为偶数，那么对于子串 Hash 值计算如下:

   $f(S)=S_{n-1}*p^{n-1}+\dots+S_0 \pmod{2^{64}}$

   $p$ 是偶数，当 $n-1\ge 64$ , $S_{n-1}*p^{n-1} \equiv 0 \pmod{2^{64}}$

只需要构造 $aaa \dots a$ 和 $baa \dots a$ 长度大于 64 ,字符串对应的 hash 值就相等。

2. $p$ 为奇数, 构造 经典 Thue-Morse 序列卡法

设 $!s$ 表示将字符串 $s$ 中的所有字符进行某种对称翻转（例如 'a' 变成 'b'，'b' 变成 'a'）。

我们通过以下递推式不断拼接字符串：

$s_1 = \text{"a"}$

$s_2 = s_1 + !s_1 = \text{"ab"}$

$s_3 = s_2 + !s_2 = \text{"abba"}$

$s_4 = s_3 + !s_3 = \text{"baab"}$

$\dots$

$s_i = s_{i-1} + !s_{i-1}$

字符串 $s_i$ 的 hash 值为 $H_i$ ，$!s_i$ 的 hash 值为 $h_i$ , 可以推导如下式子:

其中 $s_i$ 和 $!s_i$ 长度是 $2^{i-1}$ ,由 $s_i = s_{i-1} + !s_{i-1}$ 和 $!s_i = !s_{i-1} + s_{i-1}$ 得到:

$H_i=H_{i-1}*p^{2^{i-1}}+h_{i-1}$ , $h_i=h_{i-1}*p^{2^{i-1}}+H_{i-1}$

两式相减，得到

$$H_i-h_i=(H_{i-1}-h_{i-1})*(p^{2^{i-1}}-1)$$

迭代 $H_{i-1}-h_{i-1}=(H_{i-2}-h_{i-2})*(p^{2^{i-2}}-1)$ , 不断迭代可以得到

$H_i-h_i=(H_{i-2}-h_{i-2})*(p^{2^{i-2}}-1)*\cdots*(p^{2^{i-1}}-1)$

$\cdots$

$H_i-h_i=(H_{1}-h_{1})*(p^{2^{0}}-1)*(p^{2^{1}}-1)*\cdots *(p^{2^{i-1}}-1)$

由平方差公式可得 $p^{2^{i-1}}-1=(p^{2^{i-2}}+1)*(p^{2^{i-2}}-1)$ ,迭代下去:

$p^{2^{i-1}}-1=(p^{2^{i-2}}+1)*(p^{2^{i-2}}-1)=(p^{2^{i-2}}+1)*(p^{2^{i-3}}+1)*(p^{2^{i-4}}+1)*\dots*(p^{2^{0}}+1)*(p^{2^{0}}-1)$

也就得到: $2^i | (p^{2^{i-1}}-1)$

那么

$2^{i-1} | (p^{2^{i-2}}-1)$

$\dots$

$2^{1} | (p^{2^{0}}-1)$

即 $2*2^2*\dots*2^i | (H_i-h_i)$

简化后得到 $2^{\frac{i(i+1)}{2}} | (H_i-h_i)$

也就是当 $\frac{i(i+1)}{2} \ge 64$ , $2^{64} | (H_i-h_i)$ , 即 $H_i \equiv h_i \pmod {2^{64}}$, 此时 $i \ge 11$.

对于 Thue-Morse 构造方式，已经就包含了 $p$ 为偶数的情况 $s_i=s_{i-1}+!s_{i-1}=s_{i-2}+!s_{i-2}+!s_{i-2}+s_{i-2}$,请自行分析。

综上，需要构造出 Thue-Morse 就可以。

【参考代码】点击

通过以上两道题，说明 双 hash 的巨大优势

---

学习完毕

{{ select(1) }}

• YES
• NO