【算法笔记】Hash

本文主要是介绍【算法笔记】Hash，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

字符串 Hash

骗大分的好东西，当你记不住 AC自动机之类的东西的时候可以用（

我们知道，当某些题的值域达到 \(10^9\) 的时候，我们需要离散化，把这些整数都映射到一个更小的范围里面，这实际上就是一种类似的 Hash 思想。

那么，我们有没有办法把一个字符串映射成一个唯一的数，方便操作呢？

当然有，这就是大名鼎鼎的字符串 Hash 算法。

我们考虑取两个整数 \(base\) 和 \(mod\)。

把一个任意的字符串当作 \(base\) 进制的一个数，给字符集里面的每一个字符分配一个数值方便操作。

比如我们令 \(a=1,b=2,c=3...z=26\) ，那么字符串 \(S=\{abcy\}\) 就是 \(base=26\) 进制数 \((123\overline{25})_{26}\)

然后我们在 \(base\) 进制下对 \(S\) 代表的这个数进行对 \(mod\) 取模的操作。

这就是这个字符串的 Hash 值 \(\text{Hash}(S)\)。

举个例子，当你对于字符串 \(S=\{abc\}\) 进行 Hash 的时候，我们取 \(base=13,mod=101\) ，令 \(index(a)=1,index(b)=2,index(c)=3\)。

那么 \(\text{Hash}[0]=1\) ,表示字符串 \(S\) 的前缀 \(S[0,0]\) 的 Hash 值为 \(1\)。

\(\text{Hash}[1]=(\text{Hash}[0]\times base+index(b)) \ \text{mod} \ mod=15\)，表示 \(S\) 的前缀 \(S[0,1]\) 的 Hash 值是 \(15\)。

同理 \(\text{Hash}[2]=(\text{Hash}[1]\times base + index(c))\ \text{mod} \ mod=97\) ，表示 \(S\) 的前缀 \(S[0,2]\) 的 Hash 值是 \(97\) 。

那么字符串 \(S\) 的 Hash 值就是 \(97\)。

你发现我们这里都是在求前缀的 Hash 值，有没有办法求字串的 Hash 值，然后方便匹配呢？

有，对于 \(S[l,r]\),他的 Hash 值是:

\((\text{Hash}[r]-\text{Hash}[l-1]\times base^{r-l+1}) \ \text{mod} \ mod\)。

（字符串下标从 \(1\) 开始）

你也可以把 \(S[1,r]\) 当作两个字符串 \(P+Q\) , \(S[1,l-1]\) 当作 \(P\) ，那么这实际上就是在求 \(Q\) 的 Hash 值。

然后注意一下负数的情况即可。

那么，只要两个字符串的 Hash 值是相等的，那么我们就认为这两个字符串是相等的。

但是，这很明显是有问题的，当两个本来不相同的字符串 \(S_1,S_2\) 进行 Hash 的时候，万一他们两个字符串的 Hash 值刚好相等怎么办，这不就冲突了吗？

办法是有的，我们可以调 \(base\) 和 \(mod\) 的值。

你发现，当 \(mod\) 为质数，并且比较大的时候，你的可能的 Hash 值就更不容易冲突。

还有另外一种更狠的方法：双 Hash。

我们给每个字符串两个意义下的 Hash 值，也就是把每一个字符串表示为一个 \(\text{pair}:<\text{Hash}_1(S),\text{Hash}_2(S)>\)

当且仅当两个字符串分别的两个 \(\text{Hash}\) 值都完全一样的时候，我们才认为两个字符串是相等的。

并且，我们使用一组极大的孪生素数作为两个意义下的模数 ：\(10^9+7,10^9+9\)。

这样的话，冲突的概率基本为 \(0\) ！

当然，当 Hash 的维度增加的时候，空间消耗也会增加，而且这样的双 Hash 实际上已经非常非常难卡了，所以我们使用双 Hash 已经完全保险了。

练习题：https://www.luogu.com.cn/problem/P3370

Hash 表

咕

这篇关于【算法笔记】Hash的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！