字符串Hash

字符串Hash可以通俗的理解为,把一个字符串转换为一个整数

最后构造成理想状态下的一个整数→字符串的单射。所以问题就是如何构造Hash函数,使他成为一个单射。

有几种方法,分别是自然溢出方法,单Hash方法和双Hash方法。

我们规定
i n d e x ( x ) = x − ′ a ′ + 1 index(x)=x-'a'+1 index(x)=xa+1
说白了就是x是第几个字母

基本Hash公式为

h a s h [ i ] = h a s h [ i − 1 ] ∗ p + i n d e x ( s [ i ] ) hash[i]=hash[i−1]∗p+index(s[i]) hash[i]=hash[i1]p+index(s[i])

自然溢出法

简单来说就是利用unsigned long long的自然溢出对
2 64 取 模 2^{64}取模 264

单Hash方法

然后我们有hash公式
h a s h [ i ] = ( h a s h [ i − 1 ] ) ∗ p + i n d e x ( s [ i ] ) % m o d hash[i]=(hash[i−1])∗p+index(s[i]) \% mod hash[i]=(hash[i1])p+index(s[i])%mod

其中p和mod均为质数,且有p<mod

对于此种Hash方法,将p和mod尽量取大即可,这种情况下,冲突的概率是很低的。

例如有字符串"abc"

若取p=13,mod=103,对abc进行hash则有

hash[0]=1

hash[1]=(hash[0]*13+2)%103=15

hash[2]=(hash[1]*13+3)%103=95

此时,串“abc”的hash值为95

为什么要选素数

因为对于取模运算,非素数不能用遍集合里全部元素。

比如我们取12这个合数,我们不难发现,12%它的因子{1,2,3,4,6,12}均为0,对于取模运算,非素数不能用遍集合里全部元素。所以选取合数造成哈希冲突的概率会大大增加。

例如

N=12, g=4, f(g,x)=g*x mod N

4*1 mod N = 4

4*2 mod N = 8

4*3 mod N = 0

4*4 mod N = 4

4*5 mod N = 8

4*6 mod N = 0

4*7 mod N = 4

4*8 mod N = 8

4*9 mod N = 0

4*10 mod N = 4

4*11 mod N = 8

而如果N=13 g=4, f(g,x)=g*x mod N,则

4*1 mod N = 4

4*2 mod N = 8

4*3 mod N = 12

4*4 mod N = 3

4*5 mod N = 7

4*6 mod N = 11

4*7 mod N = 2

4*8 mod N = 6

4*9 mod N = 10

4*10 mod N = 1

4*11 mod N = 5

4*12 mod N = 9

可以直观的看出冲突概率的变化

双Hash方法

将一个字符串用不同的mod hash两次,将这两个结果用一个二元组表示,构建成一个
< h a s h 1 [ n ] , h a s h [ 2 ] > → 字 符 串 <hash1[n],hash[2]>→字符串 <hash1[n],hash[2]>
的理想单射

利用两个mod即可
h a s h 1 [ i ] = ( h a s h 1 [ i ] ) ∗ p + i n d e x ( s [ i ] ) % m o d 1 hash1[i]=(hash1[i])*p+index(s[i])\%mod1 hash1[i]=(hash1[i])p+index(s[i])%mod1

h a s h 2 [ i ] = ( h a s h 2 [ i ] ) ∗ p + i n d e x ( s [ i ] ) % m o d 2 hash2[i]=(hash2[i])*p+index(s[i])\%mod2 hash2[i]=(hash2[i])p+index(s[i])%mod2

如何获取子串的Hash

设 有 一 字 符 串 s , l e n ( s ) = 5 , 设 S i 为 第 i 个 字 符 设有一字符串s,len(s)=5,设S_i为第i个字符 slen(s)=5Sii

我们根据定义不难得出[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KjGPlFlD-1584246002264)(C:\Users\刘伟强\AppData\Roaming\Typora\typora-user-images\image-20200314104453546.png)]

如 果 我 们 要 求 字 串 S 4 S 5 的 h a s h 值 。 如果我们要求字串S_4S_5的hash值。 S4S5hash
不难得出
h a s h [ 4 , 5 ] = s 4 ∗ p + s 5 hash[4,5]=s_4*p+s_5 hash[4,5]=s4p+s5
由上列可知
h a s h [ 5 ] = s 1 ∗ p 4 + s 2 ∗ p 3 + s 3 ∗ p 2 + s 4 ∗ p + s 5 hash[5]=s1*p^4+s_2*p^3+s_3*p^2+s_4*p+s_5 hash[5]=s1p4+s2p3+s3p2+s4p+s5

h a s h [ 3 ] = s 1 ∗ p 2 + s 2 ∗ p + s 3 hash[3]=s1*p^2+s_2*p+s_3 hash[3]=s1p2+s2p+s3

由此可知我们只需要想办法消去hash[5]中S_4之前的部分即可

联立可得
h a s h [ 4 , 5 ] = h a s h [ 5 ] − h a s h [ 3 ] ∗ p 5 − 4 + 1 hash[4,5]=hash[5]-hash[3]*p^{5-4+1} hash[4,5]=hash[5]hash[3]p54+1
抽象可得
h a s h [ l , r ] = h a s h [ r ] − h a s h [ l − 1 ] ∗ p r − l + 1 hash[l,r]=hash[r]-hash[l-1]*p^{r-l+1} hash[l,r]=hash[r]hash[l1]prl+1
注意要每次取模,并且做减法时有可能会出现负数,所以我们对其+mod后再取余做出修正

得到求字串hash值的公式为
h a s h [ l , r ] = ( ( h a s h [ r ] − h a s h [ l − 1 ] ∗ p r − l + 1 ) % m o d + m o d ) % m o d hash[l,r]=((hash[r]-hash[l-1]*p^{r-l+1})\%mod+mod)\%mod hash[l,r]=((hash[r]hash[l1]prl+1)%mod+mod)%mod

如何选取素数

像1e9+7,1e9+9的一些素数,出题人一般会专门卡一下

下面这个网站有可供选择的素数,可以自行查阅

我们对其+mod后再取余做出修正

得到求字串hash值的公式为
h a s h [ l , r ] = ( ( h a s h [ r ] − h a s h [ l − 1 ] ∗ p r − l + 1 ) % m o d + m o d ) % m o d hash[l,r]=((hash[r]-hash[l-1]*p^{r-l+1})\%mod+mod)\%mod hash[l,r]=((hash[r]hash[l1]prl+1)%mod+mod)%mod

如何选取素数

像1e9+7,1e9+9的一些素数,出题人一般会专门卡一下

下面这个网站有可供选择的素数,可以自行查阅

http://planetmath.org/goodhashtableprimes

在pengwill97大大的https://blog.csdn.net/pengwill97/article/details/80879387基础上做了一点点自己的理解和扩充

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/pengwill97/article/details/80879387