我们常用的字符串 Hash 形如：
\[f(s) = \sum_{i = 1}^{n} s_i \times b^{n - i} \bmod p \]但是经常有人写出不正确的 Hash。举例说明，以下 Hash 是不正确的：
- 自然溢出 Hash。
- 固定底数和模数，模数是 \(2^{64}\) 级别的 Hash。
- 固定底数和模数，模数数 \(2^{32}\) 级别的双 Hash。
具体的 Hack 方法见 CF 上的一篇文章。
还有一种正确性存疑的 Hash：
- 固定模数，随机底数，但是模数减 \(1\) 有大量小质因数的 Hash。
下面给出一种正确的 Hash：
固定模数，随机底数，模数在 \(2^{32}\) 级别，且模数减 \(1\) 的 \(1 \over 2\) 是质数的双 Hash。
这样做为什么对呢？考虑两个等长字符串 \(s,t\)，\(f(s) = f(t)\) 相当于这样一件事情成立：
\[\sum_{i = 1}^n (s_i - t_i) \times b^{n - i} \equiv 0 \pmod p \]这是一个关于 \(b\) 的至多 \(n - 1\) 次非零多项式。因为 \(p\) 是质数，所以该多项式在 \(\mathbb{F}_M\) 域上的根至多有 \(n - 1\) 个，因此 Hash 碰撞的概率不超过 \({n - 1} \over p\)。双 Hash 即可保证正确性。
那为什么 \(p - 1\) 不能有很多小质因数呢？因为如果 \(b\) 模 \(p\) 的阶很小，那么高次项会自动取模，那么我们可以直接构造出一个零多项式，因此正确性是无法保证的。不过，如果 \(p - 1 = 2q\)，那么 \(b\) 模 \(p\) 的阶只能是 \(1, 2, q, 2q\)。\(q\) 和 \(2q\) 已经足够大（远大于 \(n\)），而阶为 \(1\) 的只有 \(1\)，阶为 \(2\) 的只有 \(p - 1\)，因此我们令 \(b\) 在 \([2, p - 2]\) 中均匀随机即可。
不过合适的 \(p\) 确实不好找。这里讲一组好记的：\(10^9 + 7\) 和 \(10^9 + 787\)。
标签：Hash,2q,多项式,杂谈,底数,模数,字符串 From： https://www.cnblogs.com/ClHg2/p/17964195