字符串散列

metaphysis

2023-07-10 21:08:29

Personal

字符串散列（string hash，又称字符串哈希）是指在字符串和数值之间建立对应关系，相当于为字符串创建“指纹”。存在非常多的散列算法，下面介绍通过模运算实现的一种简易散列算法。

给定一个字符串 S=s_1s_2 \dots s_n，选定一个基数 base 和模数 mod （编程竞赛中，一般选择小于 2^{32} 的较大素数），令 h[i] 表示前 i 个字符所对应的数值，且令 h[0]=0，可以按照如下方法将此字符串转换为一个整数：

h[i]=h[i-1]*base+s_i

由于 h[i] 可能很大而不便于表示，在应用中一般是将其值对 mod 取模，即：

h[i]=(h[i-1]*base+s_i)\%mod

const int MAXN = 1000100;
const int BASE = 16777213, MOD = 2147483647;

long long h[MAXN], b[MAXN];

int getHash(string &s) {
    h[0] = 0;
    int n = (int)s.length();
    for (int i = 1; i <= n; i++) h[i] = (h[i - 1] * BASE + s[i - 1]) % MOD;
    return h[n];
}

当两个不同的字符串依据上述方法转换得到的散列值相同时，称之为冲突（collide），为了尽量减少冲突出现的概率，可以使用两组（甚至多组）基数和模数，得到两个不同的散列值，将之配对来表示字符串的映射值，这样冲突的概率非常小。

有时并不需要获取整个字符串的散列值，而只需获取字符串某一部分的散列值，那么可以通过类似于前缀和的技巧来获取。观察确定字符串散列值的过程：

\begin{aligned} h[0] &= 0 \\ h[1] &= s_1 \\ h[2] &= s_1 * base^1 + s_2 \\ h[3] &= s_1 * base^2 + s_2 * base^1 + s_3 \\ h[4] &= s_1 * base^3 + s_2 * base^2 + s_3 * base^1 + s_4 \\ h[5] &= s_1 * base^4 + s_2 * base^3 + s_3 * base^2 + s_4 * base^1 + s_5 \\ \dots &= \dots \\ h[n] &= s_1 * base^{n-1} + s_2 * base^{n-2} + \dots + s_1 * base^1 + s_n \\ \end {aligned}

如果需要计算子串 s_3s_4 的散列值，易知其散列值为：

s_3*base+s_4=h[4]-h[2]*base^2

适当扩展可得，若要计算子串 s_l \dots s_r 的散列值，可以使用等式：

h[s_{l \dots r}]=h[r]-h[l-1]*base^{r-l+1}

来予以确定。

// 获取字符串中序号区间为[L，R]的子串的散列值，字符串的序号从0开始计数。
int prepared = 0;
int getHash(string &s, int L, int R) {
    if (!prepared) {
        h[0] = 0, b[0] = 1;
        int n = (int)s.length();
        for (int i = 1; i <= n; i++) {
            h[i] = (h[i - 1] * BASE + s[i - 1]) % MOD;
            b[i] = b[i - 1] * BASE % MOD;
        }
        prepared = 1;
    }
    return (h[R + 1] - h[L] * b[R - L + 1] % MOD + MOD) % MOD;
}