字符串哈希_解题技巧

发表于 2023-11-10 分类于解题技巧阅读次数： Waline：本文字数： 1.8k 阅读时长 ≈ 6 分钟

定义

能将一个字符串$s$映射为整数的函数$ f $，我们可以将其称作为Hash函数，即： \[ f\left( s \right) \longrightarrow \text{数字} \] 如此一来，就能方便我们比较两个字符串是否相等。

下面介绍的方法在算法界称为Rabin-Karp算法，简称RK

性质

在 Hash 函数值不一样的时候，两个字符串一定不一样
在 Hash 函数值一样的时候，两个字符串不一定一样

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

实现

令$h$为哈希数组，字符串起始下标为1（计算机内是0起始），$h[i]$记录下标$[1...i]$字串的哈希值；$l$为字符串长度，$P$为质数

有哈希数组公式如下。在没有特别注解的情况下默认都是用它： \[ h\left[ i \right] =h\left[ i-1 \right] \times P+idx\left( s\left[ i \right] \right) \]

\[ i\in \left[ 1,l \right] \]

一般$idx$函数定义如下：

idx(x) = x - 'a' + 1

但没必要，一般直接用字符的ASCII码，即int(s[i])替代即可

以字符串xyz举例：

h[0] = 0

h[1] = h[0] * P + s[1] = x

h[2] = h[1] * P + s[2] = x*P + y

h[3] = h[2] * P + s[3] = xP² + y P + z

显然，哈希数组公式是将字符串作为了$P$进制的数来描述，那么可以用数学语言进行归纳： \[ f\left( s \right) =\sum{\begin{array}{c} l\\ i=1\\ \end{array}s\left[ i \right] \times P^{l-i}}\left( mod\,\,M \right) \]

另一种哈希数组公式描述如下。其中$p$数组保存$P$的幂次，即$p[i]$保存$P^{i}$的结果： \[ p\left[ i \right] =p\left[ i-1 \right] \times P \]

\[ h[i]=idx(s[i])\times p[i-1]+h[i-1] \]

用数学语言归纳的话就是这样： \[ f\left( s \right) =\sum{\begin{array}{c} l\\ i=1\\ \end{array}s\left[ i \right] \times P^{i-1}\left( mod\,\,M \right)} \] 结果如下：

p[0] = 1, h[0] = 0

p[1] = P, h[1] = s[1] * p[0] + h[0] = x

p[2] = P², h[2] = s[2] * p[1] + h[1] = x + y*P

p[3] = P³, h[3] = s[3] * p[2] + h[2] = x + y*P + z*P²

故而用第一种公式处理源字符串得到的哈希值，等于用第二种公式处理源字符串的翻转

即： \[ f_{\text{第一种}}\left( abc \right) =f_{\text{第二种}}\left( cba \right) \]

下面解答一些疑问，默认为第一种公式

为什么取模？

对$M$取模是因为幂次运算过于巨无霸，必须要手动控制精度确保不会溢出

M是质数，为什么？

哈希表中的数列冲突分布间隔，受模的因子数量影响；同样的随机数列，模的因子越多，冲突的可能性就越大

所以要减少冲突，肯定希望模的因子最少，而因子最少的就是质数了

详细证明可参见链接

M一般取什么值？

一般在算法界，我们喜欢取1e9+7和1e9+9

这俩是$2^{30}$范围内比较好记的超大质数，好处在哪？

所有模过之后的数进行加法操作不会溢出int范围

\[ a,b<2^{30}, a+b<2^{31} \]

所有模过之后的数进行乘法操作不会溢出long long范围 \[ a\times b<2^{60} \]

详细讨论可参见链接

P一般取什么值？

我个人喜欢131和13331，$P$一定要小于$M$（不然取模的意义在哪呢）

有一个在线判断质数的网址，可以记一个你喜欢的质数（笑）

求子串的哈希值？

令$f_i\left( s \right)$表示$f\left( s\left[ 1...i \right] \right)$，即下标1到$i$的字串哈希值

我们需要求下标$[l..r]$的字串哈希值就是： \[ f\left( s\left[ l...r \right] \right) =s\left[ l \right] \times P^{r-l}+s\left[ l+1 \right] \times P^{r-l-1}+...+s\left[ r-1 \right] \times P+s\left[ r \right] \] 观察下方两个式子

$f_l\left( s \right)$是下标1到$l$的字串哈希值，$f_r\left( s \right)$是下标1到$r$的字串哈希值，$l$<$r$ \[ f_l\left( s \right) =s\left[ 1 \right] \times P^{l-1}+s\left[ 2 \right] \times P^{l-2}+...+s\left[ l-1 \right] \times P+s\left[ l \right] \]

\[ f_r\left( s \right) =s\left[ 1 \right] \times P^{r-1}+s\left[ 2 \right] \times P^{r-2}+...+s\left[ r-1 \right] \times P+s\left[ r \right] \]

列出下标1到$l-1$的字串哈希值 \[ f_{l-1}\left( s \right) =s\left[ 1 \right] \times P^{l-2}+s\left[ 2 \right] \times P^{l-3}+...+s\left[ l-2 \right] \times P+s\left[ l-1 \right] \] 如果再乘$P^{r-l+1}$ \[ P^{r-l+1}\times f_{l-1}\left( s \right) =s\left[ 1 \right] \times P^{r-1}+s\left[ 2 \right] \times P^{l-2}+...+s\left[ l-2 \right] \times P^{r-l+2}+s\left[ l-1 \right] \times P^{r-l+1} \] 你会惊奇地发现，任何一个字串的哈希值都能通过这个等式以$O(1)$的时间复杂度算出 \[ f\left( s\left[ l...r \right] \right) =f_r\left( s \right) -f_{l-1}\left( s \right) \times P^{r-l+1} \] 如果用哈希公式来表达，那就是 \[ h\left[ l...r \right] =h\left[ r \right] -h\left[ l-1 \right] \times P^{r-l+1} \] 大质数$P$的幂次用上面提到的$p$数组记录，即$p[i]$等于$P$的$i$次幂 \[ h\left[ l...r \right] =h\left[ r \right] -h\left[ l-1 \right] \times p\left[ r-l+1 \right] \] 方才说过，为了防止溢出，我们会对$M$进行取模 \[ h\left[ l...r \right] =\left( h\left[ r \right] -h\left[ l-1 \right] \times p\left[ r-l+1 \right] \right) \%M \] 表达式结果有可能是负数。编程语言是允许对负数取模的（事实上被模数和模数都允许为负数），但负数会带来很多不确定...

（也没人喜欢负数吧，笑）

所以还需作以下处理得到最终的字串哈希表达式： \[ h\left[ l...r \right] =\left( \left( h\left[ r \right] -h\left[ l-1 \right] \times p\left[ r-l+1 \right] \right) \%M+M \right) \%M \]

取模的Trick

上面的各种七七八八取模操作会相当影响编程...

可喜的是，在实际编程中可以令$h$与$p$这种存储超大质数的数组类型设定为unsigned long long，这样一旦溢出会自动取模$2^{64}$

所以你只需要这样：

typedef unsigned long long ull;
//s为字符串，P取了131，M就是2^64
const int P = 131, N = s.length() + 1;
ull h[N], p[N], h_r[N];
p[0]=1,h[0]=0,h_r[0]=0;
//h数组使用的第一种公式
//h_r数组使用的第二种公式
for(int i = 1; i < N; i++ ){
    //编程中还需使用s[i-1]，因为计算机内部数组下标还是0开头
    h[i] = h[i-1] * P + s[i-1];
    p[i] = p[i-1] * P;
    h_r[i] = s[i-1] * p[i-1] + h_r[i-1];
	...
}
...

双哈希

字面意思，用两个不同的质数进行两次取模，结果用一对数$<h_1[i],h_2[i]>$来代表字符串的哈希值

（但说实话，我刷题还没遇到过必须用双哈希解决冲突的....没有对冲突率如此严苛） \[ h_1\left[ i \right] =h_1\left[ i-1 \right] \times P+idx\left( s\left[ i \right] \right) \left( mod\,\,M_1 \right) \]

\[ h_2\left[ i \right] =h_2\left[ i-1 \right] \times P+idx\left( s\left[ i \right] \right) \left( mod\,\,M_2 \right) \]