字符串哈希

定义

我们定义一个把字符串映射到整数的函数 $f$ ，这个 $f$ 称为是 Hash 函数。

我们希望这个函数 $f$ 可以方便地帮我们判断两个字符串是否相等。

Hash 的思想

Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。

这里的「值域较小」在不同情况下意义不同。

在 哈希表 中，值域需要小到能够接受线性的空间与时间复杂度。

在字符串哈希中，值域需要小到能够快速比较（ $10^9$ 、$10^{18}$ 都是可以快速比较的）。

同时，为了降低哈希冲突率，值域也不能太小。

性质

具体来说，哈希函数最重要的性质可以概括为下面两条：

1. 在 Hash 函数值不一样的时候，两个字符串一定不一样；
2. 在 Hash 函数值一样的时候，两个字符串不一定一样（但有大概率一样，且我们当然希望它们总是一样的）。

Hash 函数值一样时原字符串却不一样的现象我们成为哈希碰撞。

解释

我们需要关注的是什么？

时间复杂度和 Hash 的准确率。

通常我们采用的是多项式 Hash 的方法，对于一个长度为 $l$ 的字符串 $s$ 来说，我们可以这样定义多项式 Hash 函数： $f(s) = \sum _{i = 1} ^{l} s[i] \times b^{l - i}\ (mod\ \ M)$ 。例如，对于字符串 $xyz$ ，其哈希函数值为 $xb^2 + yb + z$ 。

特别要说明的是，也有很多人使用的是另一种 Hash 函数的定义，即 $f(s) = \sum _{i = 1} ^{l} s[i] \times b^{i - 1}\ (mod\ \ M)$ ，这种定义下，同样的字符串 $xyz$ 的哈希值就变为了 $x + yb + zb^2$ 了。

显然，上面这两种哈希函数的定义函数都是可行的，但二者在之后会讲到的计算子串哈希值时所用的计算式是不同的，因此千万注意 不要弄混了这两种不同的 Hash 方式。

由于前者的 Hash 定义计算更简便、使用人数更多、且可以类比为一个 $b$ 进制数来帮助理解，所以本文下面所将要讨论的都是使用 $f(s) = \sum _{i = 1} ^{l} s[i] \times b^NaN\ (mod\ \ M)$ 来定义的 Hash 函数。

下面讲一下如何选择 $M$ 和计算哈希碰撞的概率。

这里 $M$ 需要选择一个素数（至少要比最大的字符要大）， $b$ 可以任意选择。

如果我们用未知数 $x$ 替代 $b$ ，那么 $f(s)$ 实际上是多项式环 $\Z_M[x]$ 上的一个多项式。考虑两个不同的字符串 $s,t$ ，有 $f(s) = f(t)$ 。我们记 $h(x) = f(s) - f(t) = \sum _{i = 1} ^{l} (s[i] - t[i]) x^{l - i}\ (mod\ M)$ ，其中 $l = max(|s|, |t|)$ 。可以发现 $h(x)$ 是一个 $l - 1$ 阶的非零多项式。

如果 $s$ 与 $t$ 在 $x = b$ 的情况下哈希碰撞，则 $b$ 是 $h(x)$ 的一个根。由于 $h(x)$ 在 $\Z_M$ 是一个域（等价于 $M$ 是一个素数，这也是为什么 $M$ 要选择素数的原因）的时候，最多有 $l - 1$ 个根，如果我们保证 $b$ 是从 $[0, M)$ 之间均匀随机选取的，那么 $f(s)$ 与 $f(t)$ 碰撞的概率可以估计为 $\frac{l - 1}{M}$ 。简单验算一下，可以发现如果两个字符串长度都是 $1$ 的时候，哈希碰撞的概率为 $\frac{l - 1}{M} = 0$ ，此时不可能发生碰撞。

Hash 的分析与改进

错误率

若进行 $n$ 次比较，每次错误率 $\frac{1}{M}$ ，那么总错误率是 $1 - (1 - \frac{1}{M})^n$ 。在随机数据下，若 $M = 10^9 + 7$ ，$n = 10^9$ ，错误率约为 $\frac{1}{1000}$ ，并不是能够完全忽略不计的。

所以，进行字符串哈希时，经常会对两个大质数分别取模，这样的话哈希函数的值域就能扩大到两者之积，错误率就非常小了。

多次询问子串哈希

单次计算一个字符串的哈希值复杂度是 $O(n)$ ，其中 $n$ 为串长，与暴力匹配没有区别，如果需要多次询问一个字符串的子串的哈希值，每次重新计算效率非常低下。

一般采取的方法是对整个字符串先预处理出每个前缀的哈希值，将哈希值看成一个 $b$ 进制的数对 $M$ 取模的结果，这样的话每次就能快速求出子串的哈希了：

令 $f_i(s)$ 表示 $f(s[1..i])$ ，即原串长度为 $i$ 的前缀的哈希值，那么按照定义有 $f_i(s) = s[1] \cdot b^{i - 1} + s[2] \cdot b^{i - 2} + \dots + s[i - 1] \cdot b + s[i]$

现在，我们想要用类似前缀和的方式快速求出 $f(s[l..r])$ ，按照定义有字符串 $s[l..r]$ 的哈希值为 $f(s[l..r]) = s[l] \cdot b^{r - l} + s[l + 1] \cdot b^{r - l - 1} + \dots + s[r - 1] \cdot b + s[r]$

对比观察上述两个式子，我们发现 $f(s[l..r]) = f_r(s) - f_{l - 1}(s) \times b^{r - l + 1}$ 成立（可以手动代入验证一下），因此我们用这个式子就可以快速得到子串的哈希值。其中 $b^{r - l + 1}$ 可以 $O(n)$ 的预处理出来然后 $O(1)$ 地回答每次询问（当然也可以快速幂 $O(log\ n)$ 的回答每次询问）。

模板

const int L = 2e6 + 5;
const int HASH_CNT = 2;

int hashBase[HASH_CNT] = {29, 31}; // {13331, 23333}
int hashMod[HASH_CNT] = {int(1e9 + 9), 998244353}; // {1e9 + 7, 1e9 + 9}

struct StringWithHash {
  char s[L];
  int ls;
  int hsh[HASH_CNT][L];
  int pwMod[HASH_CNT][L];

  void init() {  // 初始化
    ls = 0;
    for (int i = 0; i < HASH_CNT; ++i) {
      hsh[i][0] = 0;
      pwMod[i][0] = 1;
    }
  }

  StringWithHash() { init(); }

  void extend(char c) {
    s[++ls] = c;                          // 记录字符数和每一个字符
    for (int i = 0; i < HASH_CNT; ++i) {  // 双哈希的预处理
      pwMod[i][ls] =
          1ll * pwMod[i][ls - 1] * hashBase[i] % hashMod[i];  // 得到b^ls
      hsh[i][ls] = (1ll * hsh[i][ls - 1] * hashBase[i] + c) % hashMod[i];
    }
  }

  vector<int> getHash(int l, int r) {  // 得到哈希值
    vector<int> res(HASH_CNT, 0);
    for (int i = 0; i < HASH_CNT; ++i) {
      int t =
          (hsh[i][r] - 1ll * hsh[i][l - 1] * pwMod[i][r - l + 1]) % hashMod[i];
      t = (t + hashMod[i]) % hashMod[i];
      res[i] = t;
    }
    return res;
  }
};