专栏文章

9.27 字符串哈希-Hash

KKoei
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minq85id
此快照首次捕获于
2025/12/02 06:34
3 个月前
此快照最后确认于
2025/12/02 06:34
3 个月前
查看原文

字符串哈希

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

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

性质：

  1. Hash值不一样时，两字符串一定不一样
  2. Hash值一样时，两字符串不一定一样
对于Hash值相同而字符串不同的情况我们称其为Hash冲突

计算Hash值

使用进制Hash，将字符串看作一个p进制的数Hash(s)pHash(s)_p
对于每一个字符串的前i位字符只需要在前i-1位字符的基础上乘p加上当前第i位字符即可
Hashi=Hashi−1×p+siHash_i=Hash_{i-1}\times p+s_i

解决Hash冲突

注意到Hash冲突会使程序出现错误以致于无法拿到满分，那么我们需要避免Hash冲突，使Hash冲突的概率尽可能降低
那么如何降低Hash冲突的给概率呢？ 注意到有很多种方法

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

单模数Hash就是求出的值仅对一个数取模得到的值作Hash值
至于Hash值在取模前怎么算呢？
其实很简单，你把它当转换进制就行了
hashi=(hashi−1∗p+si) mod MODhash_i=(hash_{i-1}*p+s_i)\bmod MOD
及把其当作一个p进制的数储存

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

顾名思义，多模数Hash就是使用多个模数和不同的进制对Hash值进行计算
hash1i=(hash1i−1∗p1+si) mod MOD1hash2i=(hash2i−1∗p2+si) mod MOD2hash1_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对 2642^{64} 取模一个意思 (就是如此神奇
公式的话把取模删了就行了
hashi=hashi−1∗p+sihash_i=hash_{i-1}*p+s_i
当然如果在使用单模数的同时加上自然溢出就变成了双模数Hash

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...