一个字符串的hash值:

•现在我们希望找到一个hash函数,使得每一个字符串都能够映射到一个整数上
•比如hash[i]=(hash[i-1]*p+idx(s[i]))%mod
•字符串:abc,bbc,aba,aadaabac
•字符串下标从0开始
•先把a映射为1,b映射为2,c->3,d->4,即idx(a)=1, idx(b)=2, idx(c)=3,idx(d)=4;
•好!开始对字符串进行hash

假设我们取p=13 ,mod=101

先把abc映射为一个整数

hash[0]=1,表示 a 映射为1

hash[1]=(hash[0]*p+idx(b))%mod=15,表示 ab 映射为 15

hash[2]=(hash[1]*p+idx(c))%mod=97

这样,我们就把 abc 映射为 97 这个数字了。

•用同样的方法,我们可以把bbc,aba,aadaabac都映射到一个整数
•用同样的hash函数,得到如下结果
• abc  ->  97
• bbc  ->  64
• aba  ->  95
• aadaabac  ->  35
•那么,我们发现,这是一个字符串到整数的映射
•这样子,我们就可以记录下每个字符串对应的整数,当下一次出现了一个已经出现的字符串时,查询整数是否出现过,就可以知道 字符串是否重复出现。
•现在要判断两个字符串是否一致,怎么办呢?直接用它们的hash值判断即可,若hash值一致,则认为字符串一致;若hash值不一致,则认为是不同的字符串。
•我们要判断两个字符串是否一致,没有那么麻烦,直接先判断长度是否一致,然后再判断每个对应的字符是否一致即可。
•但,如果要判断多个字符串里有多少个不同的字符串,怎么办呢?
•两两字符串都进行比较?时间复杂度太高
•把每个字符串hash成一个整数,然后把所有整数进行一个去重操作,即可知道答案了。
当遇到冲突时,我们可以想办法调整p和mod,使得冲突概率减小之又小。我们一般认为p和mod一般取素数,p取一个较大的素数即可(6位到8位),mod取一个大素数,比如1e9+7,或者1e9+9。
 
如何求一个子串的hash值?
•在之前,我们求出了hash[i],表示第i个前缀的hash值。现在怎么求出每个子串的

hash值呢?

•我们看下hash的公式:
• hash[i]=(hash[i-1]*p+idx(s[i]))%mod
•这表示第 i 个前缀的hash值,是一个hash的前缀和。
•hash[i]=(hash[i-1]*p+idx(s[i]))%p;
•那么,我要求S[l…r]这个子串的hash值
• hash[l..r]=(hash[r]-hash[l-1]*(p^(r-1+1)))%mod(假设字符串下标从1开始)
•但注意下取模时候的问题!
•hash[l..r]=(hash[r]-hash[l-1]*(p^(r-1+1)))%mod
• hash[l..r]是不是可能有负数?
•怎么办呢?当得到的hash[l..r]<0的时候,hash[l..r]+=mod,就好啦。
•这样就可以保证每个子串的hash值在[0, mod-1]的范围内,准确地用hash值来处理字符串
 
常用的几个字符串hash法
•1. unsigned long long hash[N];
     hash[i]=hash[i-1]*p(自动取模)
解释:

unsigned long long hash[N];

定义一个unsigned long long类型的变量,它的范围是在[0, 2^64) 内,这就相当于,当数超不过2^64-1后,它会溢出!这就相当于一个数模2^64的过程。

那么hash函数可以理解为:

hash[i]=(hash[i-1]*p)%(2^64)

P取一个大素数,一般习惯取1e9+7或1e9+9

安全指数:三星(所以并不是很安全)

•2. hash[i]=(hash[i-1]*p+idx(s[i]))%mod
解释:

这个之前已经提到过了。

hash[i]=(hash[i-1]*p+idx(s[i]))%mod

p取一个6到8位的素数,mod取一个大素数,一般取1e9+7或1e9+9
安全指数:四星 (还可以)
 
•3. 双hash

hash1[i]=(hash1[i-1]*p+idx(s[i]))%mod1

hash2[i]=(hash2[i-1]*p+idx(s[i]))%mod2

pair<hash1,hash2>表示一个字符串!

解释:

double hash
即取两个mod值,mod1和mod2

hash1[i]=(hash1[i-1]*p+idx(s[i]))%mod1

hash2[i]=(hash2[i-1]*p+idx(s[i]))%mod2

mod1一般取1e9+7,mod2一般取1e9+9为什么这么取?

1000000007和1000000009是一对孪生素数,取它们,冲突的概率极低!

安全指数:五星!(非常稳!)
 
小结:
•可以这么说,hash某种程度上就是乱搞,把hash函数弄的越没有规律越好,使得冲突的概率小到 大部分数据都卡不掉。
•如果你开心,你想triple hash,ultra hash,rampage hash… 都没有问题!

但请注意,hash的维度越高,耗时越高,耗内存越大!一般情况下,single hash可以被hack掉,但double hash极难被hack掉, 用double hash足以解决问题

根据hash函数去求得一段区间的的 hash 值

#include <cstdio>
#include <cstring>
using namespace std;
#define ll unsigned long long
const ll maxn = 1e6+; char s1[maxn], s2[maxn];
ll p = ;
ll hash[maxn]; ll pp[maxn];
void init() {
pp[] = ;
for(int i = ; i <= ; i++) {
pp[i] = pp[i-]*p;
}
} int main() {
scanf("%s%s", s1, s2);
ll len1 = strlen(s1);
ll len2 = strlen(s2);
init(); ll hash_1 = ;
for(ll i = ; i < len1; i++){
hash_1 = hash_1*p+(s1[i]-'a');
}
printf("hash_1 = %llu\n",hash_1); for(ll i = ; i < len2; i++){
hash[i] = hash[i-]*p+(s2[i]-'a');
printf("+++ i = %llu -> %llu\n", i, hash[i]);
}
ll ans = hash[]-hash[]*pp[];
printf("%llu \n", ans);
return ;
}
/*
qwe
rasqwe
*/

最新文章

  1. iOS 使用EZAudio库生成wav出错的情况
  2. Something Wrong or Something Right
  3. css 之盒子模型
  4. Windows下JNI执行步骤
  5. linux 硬盘相关命令学习
  6. SQL Server R2 2008中的SQL Server Management Studio 阻止保存要求重新创建表的更改问题的设置方法
  7. NOIP2009 靶形数独
  8. numpy+scipy+matlotlib+scikit-learn的安装及问题解决
  9. shell if语句
  10. sqlite 数据库打开失败
  11. 《转》前端性能优化----yahoo前端性能团队总结的35条黄金定律
  12. TreeView无刷新获取text及value
  13. Android L下载
  14. JQuery&amp;原生js ——实现剪刀石头布小游戏
  15. SSM中的Mybatis的操作
  16. ORACLE DB体系结构
  17. 【 python】输出随机的字符或数字
  18. RETE算法介绍
  19. CVE-2010-2883
  20. 初识powershell、nuget powershell 调试

热门文章

  1. QDUOJ 分辣条-01背包恰好装满情况
  2. thinkphp5.0 页面缓存
  3. Unity2D研究院之自动生成动画、AnimationController、Prefab(一)
  4. bzoj 1901: Zju2112 Dynamic Rankings【整体二分+树状数组||主席树+树状数组】
  5. 用BeautifulSoup简单爬取BOSS直聘网岗位
  6. web项目数据存入mysql数据库中文乱码问题
  7. [BZOJ3128]a+b Problem
  8. struts2的@Result annotation 如何添加params,并且在页面取值
  9. python入门之数据类型之列表、元组、字典
  10. Idea 2017注册码