专栏文章

字符串哈希和碰撞概率

bbeyoursven
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipaag0l
此快照首次捕获于
2025/12/03 08:43
3 个月前
此快照最后确认于
2025/12/03 08:43
3 个月前
查看原文

计算字符串哈希

字符串哈希就是一种进制哈希、多项式哈希。
一般来说，模数会选择一个很大的质数，进制的基数会选择一个小于模数的跟字符集差不多大小的质数。
双哈希带质数模数（快速计算子串哈希值）
CPP
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;
计算字符串哈希值
CPP
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;
}
单哈希带质数模数（快速计算子串哈希值）
CPP
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 题目是会卡该算法的）
CPP
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/
简单来说，多项式哈希在使用质数模数 MM 的情况下，两个不同的字符串碰撞（拥有相同哈希值）的概率为 nM\frac{n}{M}，其中 nn 为较长的字符串的长度。例如，当两个字符串长度至多为 10410^4，你选择的质数模数为 109+710^9 + 7 时，碰撞的概率大概为 10−410^{-4}。
但是请注意：
  1. 进行 mm 次长度至多为 nn 的不同字符串的哈希值比较，碰撞的概率为 mnM\frac{mn}{M}。
  2. 给定 mm 个长度至多为 nn 的不同字符串，其中有两个字符串碰撞的概率高达 Cm2×nM\frac{C_m^2 \times n}{M}。
舍去若干过程的推导（参考链接 2），在实战中对于上述两种情况写双哈希、三哈希，产生碰撞的概率会很低。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...