字符串Hash

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

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

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

我们规定
$$index(x)=x{-}^{\prime }{a}^{\prime }+1$$
说白了就是x是第几个字母

基本Hash公式为

$$hash[i]=hash[i-1]\ast p+index(s[i])$$

自然溢出法

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

单Hash方法

然后我们有hash公式
$$hash[i]=(hash[i-1])\ast 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两次，将这两个结果用一个二元组表示，构建成一个
$$<hash1[n],hash[2]>\to 字符串$$
的理想单射

利用两个mod即可
$$hash1[i]=(hash1[i])\ast p+index(s[i])\%mod1$$

$$hash2[i]=(hash2[i])\ast p+index(s[i])\%mod2$$

如何获取子串的Hash

$$设有一字符串s，len(s)=5，设S_i为第i个字符$$

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

$$如果我们要求字串S_4{S}_5的hash值。$$
不难得出
$$hash[4,5]=s_4\ast p+s_5$$
由上列可知
$$hash[5]=s1\ast p^4+s_2\ast p^3+s_3\ast p^2+s_4\ast p+s_5$$

$$hash[3]=s1\ast p^2+s_2\ast p+s_3$$

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

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

得到求字串hash值的公式为
$$hash[l,r]=((hash[r]-hash[l-1]\ast p^{r-l+1})\%mod+mod)\%mod$$

如何选取素数

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

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

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

得到求字串hash值的公式为
$$hash[l,r]=((hash[r]-hash[l-1]\ast p^{r-l+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