字符串Hash

发表于 更新于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 4 分钟

多项式Hash

思想

将字符串看作是某个进制($Base$)下的数字串

$H(S)=H(S[1,|S|-1])\times Base+S[|S|]$
$=S[1]\times Base^{|S|-1}+S[2]\times Base^{|S|-2}+\cdots +S[|S|]\times Base^{0}$
例：字符集$\sum =\lbrace a,b,\cdots,o\rbrace$,字符串就可看作$16$进制数字串
其中$a$对应$1$，$b$对应$2$，$\cdots$，$o$对应$15$
若$|S|=adenoo$，有$H(S)=145EFF_{(16)}=1335039_{(10)}$

优缺点

优点：不考虑计算机对整形变量的值域限制，在数学上，对于多项式哈希，字符串和$Hash$值一一对应，一定不会发生$Hash$冲突
缺点：产生的数字很可能过大爆$i64$

多项式取模Hash(模哈)

思想

选择一个模数$M$，解决多项式$Hash$的缺点，增加冲突率，减小值域
$H(S)=(S[1]\times Base^{|S|-1}+S[2]\times Base^{|S|-2}+\cdots +S[|S|]\times Base^{0})\% M$

优缺点

优点：值域缩小，方便了计算机的存储
缺点：增加$Hash$冲突可能性

模哈的冲突概率

当$H(S)\neq H(T)$但$H(S)\% M=H(T)\% M$时我们称发生了模哈冲突
模运算可以看作是一个均匀随机散列，即每个$H(S)$会被随机映射成$[0,M-1]$内的整数
原来无限的值域被压缩成了一个有限值域，根据鸽巢原理，冲突一定存在
不妨先回顾一下生日问题：
$n$个人，一年$365$天，存在有人同天生日的概率
若$n\gt 365$，根据鸽巢原理，一定有人生日相同
若$n\leq 365$，则没有人生日相同的概率为$\frac{A(365,n)}{365^n}$
当$n=23$时，上述结果约为$0.5$，即有$0.5$的概率有人生日相同
将$365$看作$M$，$n$看作随机检验次数
可以认为随机检验次数超过$\sqrt{Mod}$时，就会有较大概率发生错误
因此模哈中使用的$M$最好超过$Hash$检验次数的平方

Hash模数

根据前面对冲突概率的分析，优秀的$Hash$模数应该尽量大
因此一个策略是用$ULL$保存$Hash$值，使$Hash$值自然溢出，相当于对$2^{64}$取模，但这很容易构造$Hash$冲突($BZOJ3097$)
优秀的$Hash$模数还应该是一个质数，因为选一个大合数作模数相当于选了很多小模数
回顾$Hash$冲突的定义，当$H(S)\% M=H(T)\% M$而$H(S)\neq H(T)$时称哈希发生冲突
其中$H(S)\% M=H(T)\% M$又可以写成$(H(S)-H(T))\% M=0$
若$M=6$，$(H(S)-H(T))\% 6=0$蕴含了$(H(S)-H(T))\% 2=0$和$(H(S)-H(T))\% 3=0$
因此，如果选了一个因子很多的合数，$Hash$冲突的概率会翻非常多倍

实际策略

单模：选取$10^9$到$10^{10}$范围的大质数作为$Hash$模数。但也有广为人知的方法构造冲突
双模(甚至多模)：进行多次不同质数的单模哈希，有效降低冲突概率。在不泄露模数的前提下，没有已知方法可以构造冲突

快速计算子串$Hash$

$H(S[l,r])=(S[l]\times Base^{r-l}+S[l+1]\times Base^{r-l-1}+\cdots +S[r]\times Base^{0})\% M$
令$F(i)=H(Prefix(i))$
$F(l-1)=(S[1]\times Base^{l-2}+S[2]\times Base^{l-3}+\cdots +S[l-1]\times Base^{0})\% M$
$F(r)=(S[1]\times Base^{r-1}+S[2]\times Base^{r-2}+\cdots +S[r]\times Base^{0})\% M$
有$H(S[l,r])=(F(r)-(F(l-1)\times Base^{r-l+1}\% M)+M)\% M$
直观上可以这样想，有一个数字串$12345$，我要提取出子串$345$，是通过$12345-12\times 1000$做到的
因此我们预处理出每一个前缀的$Hash$即可

单模哈模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using ULL = unsigned long long;
const int N = 1e6 + 10;
struct Hash
{
    ULL Base, Mod;
    ULL pow[N];
    ULL f[N];
    std::string str;
    Hash(ULL Base, ULL Mod, std::string s) : Base(Base), Mod(Mod), str("?" + s)
    {
        int n = str.size() - 1;
        pow[0] = 1;
        for (int i = 1; i <= n; ++i)
            pow[i] = pow[i - 1] * Base % Mod;
        for (int i = 1; i <= n; ++i)
            f[i] = (f[i - 1] * Base % Mod + str[i]) % Mod; 
    }
    ULL getHash(int l, int r)
    {
        return (f[r] - f[l - 1] * pow[r - l + 1] % Mod + Mod) % Mod;
    }
};