简介

字符串哈希 $\mathrm{getHash}()$ 能够将字符串转化成整数，并保证：不同字符串对应不同整数。该整数称为哈希值。

判断两个字符串是否相等，就只要判断它们的哈希值是否相等。

INFO

不局限于字符串，任何序列都可以通过字符串哈希映射成一个数值。

原理

假设所有字符串中只包含小写字符 $a\cdots z$。以字符串 $\mathtt{\text{fantasy}}$ 为例：

1. 将 $a\cdots z$ 替换为数字 $1\cdots 26$，得到一个数列；

$$\mathtt{\text{fantasy}}\to \{6,1,14,20,1,19,25\}$$

2. 将该数列看作一个 $27$ 进制数（逢 $27$ 进一）。

$$\mathrm{getHash}(\mathtt{\text{fantasy}})=6\cdot {27}^6+1\cdot {27}^5+14\cdot {27}^4+\cdots +25\cdot {27}^0$$

按此方法设计的哈希函数，可保证不同字符串的哈希值必不同。

WARNING

字符串长度过长时，哈希值会超出 long long 的范围。

滚动哈希

为解决一般哈希函数适用范围有限的问题，采用滚动哈希。

选取两个合适的质数 $b$ 和 $p$，将字符串看作 $b$ 进制数（$b>$ 字符种数）。例如

$$\mathrm{getHash}(\mathtt{\text{fantasy}})=(6\cdot b^6+1\cdot b^5+14\cdot b^4+\cdots +25\cdot b^0)modp$$

按此方法设计的哈希函数，不同字符串的哈希值相同的概率很小，且哈希值不会超出 long long 的范围。时间复杂度为 $O(n)$。

typedef long long LL;
const LL b = 29, p = 10000019;

// 返回 str 的哈希值
LL getHash(string str) {
    LL h = 0;
    for (int i = 0; i < str.size(); i ++)
        h = (h * b + str[i] - 'a') % p;
    return h;
}

哈希冲突

使用 滚动哈希 时，有概率会使不同字符串的哈希值相同。该现象称为 哈希冲突。

一种降低哈希冲突概率的可靠方法是双哈希：使用两组不同的质数 $\{b_1,p_1\},\{b_2,p_2\}$，分别计算哈希值。只有两个字符串的哈希值分别相同，才认为字符串相同。

typedef long long LL;
const LL b_1 = 29, p_1 = 10000019;
const LL b_2 = 31, p_2 = 10000079;

LL getHash_1(string str) {
    LL h = 0;
    for (int i = 0; i < str.size(); i ++)
        h = (h * b_1 + str[i] - 'a') % p_1;
    return h;
}

LL getHash_2(string str) {
    LL h = 0;
    for (int i = 0; i < str.size(); i ++)
        h = (h * b_2 + str[i] - 'a') % p_2;
    return h;
}

// 比较 s1 和 s2 的哈希值是否相同
bool cmp(string s1, string s2) {
    return getHash_1(s1) == getHash_1(s2)
        && getHash_2(s1) == getHash_2(s2);
}