此处 Hash 指​字符串哈希，只用来判断两个字符串是否相同。

字符串哈希，一般使用多项式哈希，将字符串 $s$ 映射到整数 $\sum s_i\times bas{e}^i$ 上。

单哈：

​将字符串 $s$ 映射到整数 $\sum s_i\times bas{e}^{i}modp$ 上。

​在把不同字符串的哈希值近似看作独立、均匀分布于 $[0,p)$ 的前提下，对 $q$ 个不同字符串计算哈希，其中至少出现一对碰撞的概率近似为

$$1-\exp (-\frac{q(q-1)}{2p}).$$

这里描述的是 $q$ 个哈希值中“任意一对”发生碰撞的概率，不是达到 $\sqrt{p}$ 次后每次比较都有一半概率冲突。单独比较一对不同字符串时，误判概率近似为 $1/p$；上述整体碰撞概率约为 $1/2$ 时，$q\approx \sqrt{2p\ln 2}\approx 1.177\sqrt{p}$。

​例如，对于大小约为 $2^{32}$ 的哈希空间，生日界的数量级为 $\sqrt{2^{32}}=2^{16}=65536$；此时出现任意碰撞的概率约为 $1-e^{-1/2}\approx 39.3\mathrm{\%}$，而不是 $50\mathrm{\%}$。实际使用 int 模数时应将具体的 $p$ 代入公式。若选取接近 long long 上界的模数，两个余数相乘可能超过 long long，需要使用 __int128 或其他安全的模乘方法。

自然溢出：

​自然溢出是指使用 unsigned long long 进行运算，结果会自动对 $2^{64}$ 取模。若仍采用独立均匀的随机模型，$q=2^{32}=4294967296$ 个哈希值中出现任意碰撞的概率约为 $1-e^{-1/2}\approx 39.3\mathrm{\%}$；概率达到约 $50\mathrm{\%}$ 时需要 $q\approx \sqrt{2\ln 2}\cdot 2^{32}$。这种写法不需要 __int128，并且运算速度较快。

但是由于模数的特殊性，非常容易构造哈希冲突。

双哈：

​将字符串 $s$ 映射到两个模数下的哈希值组成的二元组。

​若两个哈希使用相同的底数和字符映射，先在整数上定义同一个多项式 $H(s)$，再分别计算 $H(s)mod{p}_1$ 和 $H(s)mod{p}_2$，并且 $p_1,p_2$ 互质，则根据中国剩余定理，这一对余数与 $H(s)mod(p_1{p}_2)$ 一一对应。此时双哈碰撞等价于两个字符串的整数多项式之差能被 $p_1{p}_2=\mathrm{lcm}(p_1,p_2)$ 整除。

​若两个哈希使用不同底数或不同字符映射，它们不再是同一个整数多项式在不同模数下的余数，因此不能使用上述 CRT 等价关系。只有在把两个哈希近似看作相互独立且均匀分布时，才能估计一对不同字符串同时碰撞的概率约为 $1/(p_1{p}_2)$，而 $q$ 个哈希值中出现任意双哈碰撞的概率近似为

$$1-\exp (-\frac{q(q-1)}{2p_1{p}_2}).$$

​双哈只能显著降低随机数据下的碰撞概率，不能保证完全无碰撞；面对可能刻意构造的数据，还需要随机化底数、模数或字符映射。

​最简单的随机化方式是为每个字符随机映射一个权值，而不是固定使用 $s_i$；也可以在哈希开始前随机选取合适的底数和模数。

点击展开代码

const int Base[4] = {3333, 13331, 131, 13331},
          mod[4] = {1610612741, 1061067769, (int)1e9 + 7, (int)1e9 + 9};
int m1 = 0, m2 = 1;
void init(int n) {
    base[0][0] = base[0][1] = 1;
    for (int i = 1; i <= n; i++) {
        base[i][0] = 1ll * base[i - 1][0] * Base[m1] % mod[m1];
        base[i][1] = 1ll * base[i - 1][1] * Base[m2] % mod[m2];
    }
}
void init(int a[], int n) {
    for (int i = 1; i <= n; i++) {
        sum[i][0] = (1ll * sum[i - 1][0] * Base[m1] + a[i]) % mod[m1];
        sum[i][1] = (1ll * sum[i - 1][1] * Base[m2] + a[i]) % mod[m2];
    }
}
u64 sum_hash(int l, int r) {
    int now = (sum[r][0] - 1ll * sum[l - 1][0] * base[r - l + 1][0]) % mod[m1];
    int cur = (sum[r][1] - 1ll * sum[l - 1][1] * base[r - l + 1][1]) % mod[m2];
    if (now < 0) // 注意负数不能 u64
        now += mod[m1];
    if (cur < 0)
        cur += mod[m2];
    return (1ull * now) << 32 | cur;
}

注：因为 pair<int,int> 是两个 int，若要使用 map 储存字符串的哈希值，将 pair<int,int> 压成 long long 后比较哈希值的常数会更小。