9.27 字符串哈希-Hash

· · 算法·理论

字符串哈希

用处：通过Hash函数快速地判断两个字符串是否相等

Hash思想：将字符串映射入更小、更方便比较的范围中

性质：

  1. Hash值不一样时，两字符串一定不一样
  2. Hash值一样时，两字符串不一定一样

对于Hash值相同而字符串不同的情况我们称其为Hash冲突

计算Hash值

使用进制Hash，将字符串看作一个p进制的数Hash(s)_p

对于每一个字符串的前i位字符只需要在前i-1位字符的基础上乘p加上当前第i位字符即可

Hash_i=Hash_{i-1}\times p+s_i

解决Hash冲突

注意到Hash冲突会使程序出现错误以致于无法拿到满分，那么我们需要避免Hash冲突，使Hash冲突的概率尽可能降低

那么如何降低Hash冲突的给概率呢？ 注意到有很多种方法

1.单模数Hash(被卡概率较高)

单模数Hash就是求出的值仅对一个数取模得到的值作Hash值

至于Hash值在取模前怎么算呢？

其实很简单，你把它当转换进制就行了

hash_i=(hash_{i-1}*p+s_i)\bmod MOD

及把其当作一个p进制的数储存

2.多模数Hash(被卡概率低)

顾名思义，多模数Hash就是使用多个模数和不同的进制对Hash值进行计算

hash1_i=(hash1_{i-1}*p1+s_i)\bmod MOD1\\ hash2_i=(hash2_{i-1}*p2+s_i)\bmod MOD2

3.自然溢出(常使用)

自然溢出需要使用 unsigned long long ，因为使用普通 long long 有符号位的存在使Hash值在溢出时改变符号位变成负数

自然溢出与单模数Hash对 2^{64} 取模一个意思 (就是如此神奇

公式的话把取模删了就行了

hash_i=hash_{i-1}*p+s_i

当然如果在使用单模数的同时加上自然溢出就变成了双模数Hash