哈希函数

简介 #

哈希函数 $getHash()$ 能够将字符串转化成整数，并保证字符串不同，对应的整数也不同.该整数称为哈希值.这样，判断两个字符串是否相等，就只要判断它们的哈希值是否相等.

原理 #

假设所有字符串中只包含小写字符 $a\sim z$.以字符串 fantasy 为例：

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

$$fantasy→\{6,1,14,20,1,19,25\}$$

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

$$getHash(fantasy)=6\cdot 27^6+1\cdot 27^5+14\cdot 27^4+\cdots+25\cdot 27^0$$

按此方法设计的哈希函数，可保证不同字符串的哈希值必不同.但字符串长度过长时，哈希值会超出 long long 的范围.

滚动哈希 #

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

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

$getHash(fantasy)=(6\cdot b^6+1\cdot b^5+14\cdot b^4+\cdots+25\cdot b^0)\%p$

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

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

LL getHash(string str) { // 返回 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;
}

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