字符串哈希和碰撞概率

· · 个人记录

计算字符串哈希

字符串哈希就是一种进制哈希、多项式哈希。

一般来说，模数会选择一个很大的质数，进制的基数会选择一个小于模数的跟字符集差不多大小的质数。

双哈希带质数模数（快速计算子串哈希值）

const int B[] = {131, 233}, MOD[] = {(int)1e9 + 7, 998244353};

struct Hash {
  vector<int> h[2], b[2];
  void init(const string &s) {
    for (int x : {0, 1}) {
      h[x].assign(s.size() + 1, 0);
      b[x].assign(s.size() + 1, 0);
    }
    b[0][0] = b[1][0] = 1;
    for (int i = 0; i < s.size(); i++) {
      for (int x : {0, 1}) {
        h[x][i + 1] = (1ll * h[x][i] * B[x] + s[i]) % MOD[x];
        b[x][i + 1] = 1ll * b[x][i] * B[x] % MOD[x];
      }
    }
  }
  pair<int, int> get_hash(int l, int r) {
    int res[2];
    for (int x : {0, 1}) {
      res[x] = ((h[x][r] - 1ll * b[x][r - l + 1] * h[x][l - 1]) % MOD[x] + MOD[x]) % MOD[x];
    }
    return {res[0], res[1]};
  }
} T;

计算字符串哈希值

int str_hash(string s) 
{
    int res = 0,base = 13331,mod = 1000000009;
    for(int i = 0;s[i];++i) res = (res * base + s[i]) % mod;
    return res;
}

单哈希带质数模数（快速计算子串哈希值）

struct Hash
{
    int base = 13331,mod = 1000000009;
    vector<int> h,p;
    void init_hash(string s) {
        h.assign(s.length() + 1,0);
        p.assign(s.length() + 1,0);

        p[0] = 1;
        for(int i = 0;s[i];++i) {
            p[i + 1] = (p[i] * base) % mod;
            h[i + 1] = (h[i] * base + s[i]) mod;
        }
    }
    int get_hash(int l,int r) {
        return ((h[r] - h[l - 1] * p[r - l + 1]) % mod + mod) % mod;
    }
};

单 Hash 自然溢出法（可快速计算子串）（不推荐使用，CF 题目是会卡该算法的）

struct Hash
{
    int base = 13331;
    vector<int> h,p;
    void init_hash(string s) {
        h.assign(s.length() + 1,0);
        p.assign(s.length() + 1,0);

        p[0] = 1;
        for(int i = 0;s[i];++i) {
            p[i + 1] = p[i] * base;
            h[i + 1] = h[i] * base + s[i];
        }
    }
    int get_hash(int l,int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
};

碰撞概率

参考：

  1. http://rng-58.blogspot.com/2017/02/hashing-and-probability-of-collision.html
  2. https://xglight.netlify.app/posts/951dcf71/

简单来说，多项式哈希在使用质数模数 M 的情况下，两个不同的字符串碰撞（拥有相同哈希值）的概率为 \frac{n}{M}，其中 n 为较长的字符串的长度。例如，当两个字符串长度至多为 10^4，你选择的质数模数为 10^9 + 7 时，碰撞的概率大概为 10^{-4}。

但是请注意：

  1. 进行 m 次长度至多为 n 的不同字符串的哈希值比较，碰撞的概率为 \frac{mn}{M}。
  2. 给定 m 个长度至多为 n 的不同字符串，其中有两个字符串碰撞的概率高达 \frac{C_m^2 \times n}{M}。

舍去若干过程的推导（参考链接 2），在实战中对于上述两种情况写双哈希、三哈希，产生碰撞的概率会很低。