字符串哈希

1. 定义

一个把字符串映射到整数的函数\(f\)，这个\(f\)被称为哈希函数；

这个函数的作用：希望可以判断两个字符是否相等；

1.1 Hash的思想

核心思想在于：

如何将一个字符串映射到一个值域较小、方便比较的范围？

大范围映射到小范围：

对一个大数进行取模，例如一个大的质数

注意：

1. 在字符串哈希中，值域需要小到能够快速比较， 例如\(10^ {18}\) 或者 \(10^ 9\) 都是可以快速比较的）

哈希性质：

1. 若Hash值不一样，那么两个字符串一定不相等；
2. 若Hash值一样，那两个字符串不一定相等，当时大概率一样；

将 Hash 函数值一样但原字符串不一样的现象称为哈希碰撞。

1.2 Hash的计算和改进

哈希需要关注的有时间复杂度和Hash的准确率

对于一个长度为L的字符串s来说，可以这样定义Hash的表达式如下:

即对于字符串s = "xyz"来说，如下计算

其中哈希值计算公式为: \(f(s) = xb^2 + yb + z\),可以理解为一个P进制的计算;

经验选择:

1. \(M = 2^{64}\), 即 unsigned long long 类型的最大取值范围;
2. \(b = 131\)或者 \(b = 13131\)

1.3 自己的常用实现

具体例子： 字符串S为\(X_1X_2X_3...X_n\)，把字符串变成一个P进制数字，具体方法如下：

为了方便计算P[N]，可以提前计算好每个值，如下：

typedef unsigned long long ULL;
const int N = 1E5+7;
const int p = 131;

ULL P[N], s[N];

void init() {
    P[1] = 1;
    
    for (int i = 2; i <= N; i++)
        P[i] = P[i-1] * p;
}

求一个字符串的哈希值就相当于求前缀和，求一个字符串的子串哈希值就相当于求部分和;
前缀和公式：

区间和公式：

字符串中求子串的哈希的区间和公式的理解：

ABCDEF 和 ABC的前三个字符串一样，那么子串DEF的哈希值计算可以理解为ABC的哈希值 * P^2变成ABC000，则俩式做减法即可得DEF的哈希值

代码的简单实现如下：

unsigned long long getHash(int l ,int r) {
    return h[r] - h[l-1] * P[r-l+1];
}

2. 代码实现

2.1 暴力版本:

#include <iostream>
#include <cstring>

typedef unsigned long long ULL;

const int N = 1E5+7;//  字符串最大长度
const int b = 131;
const int M = 1E9+7;

ULL getHash(const string &s) {
    ULL res = 0;
    for (int i = 0; i < s.size(); i++) {
        res = (s[i] +  res * b) % M; // 这里如果越界了,即等于 Mod 2^64
    }
    
    return res;
}

2.2 字符串前缀和哈希

typedef unsigned long long ULL;
const int N = 1E5+7;
const int p = 131;

ULL P[N], s[N];

void init(int n) {
    P[0] = 1;
    
    for (int i = 0; i < n; i++)
        P[i+1] = P[i] * p;
        h[i+1] = h[i] * p + s[i];
}

unsigned long long getHash(int l ,int r) {
    return h[r] - h[l-1] * P[r-l+1];
}

参考文档