转载 字符串hash
转载自:http://www.cnblogs.com/jiu0821/p/4554352.html
求一个字符串的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 这个数字了。
hash值呢?
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
安全指数:三星(所以并不是很安全)
这个之前已经提到过了。
hash[i]=(hash[i-1]*p+idx(s[i]))%mod
hash1[i]=(hash1[i-1]*p+idx(s[i]))%mod1
hash2[i]=(hash2[i-1]*p+idx(s[i]))%mod2
pair<hash1,hash2>表示一个字符串!
解释:
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的维度越高,耗时越高,耗内存越大!一般情况下,single hash可以被hack掉,但double hash极难被hack掉, 用double hash足以解决问题
最新文章
- 对copy、mutableCopy理解
- Ant 命令行编译Android项目
- 【AngularJS】—— 5 表单
- 零零碎碎写的shell脚本(二):一键修改网络配置信息脚本
- CUBRID学习笔记 7 ms常见错误
- c规范(1)
- Xcode7中添加3DTouch
- LINQ里的Distinct()
- Hadoop源码解析之: TextInputFormat如何处理跨split的行
- 在阿里云上布置git server
- NTSC色域(CIE1931)计算公式
- Cloud9vue&;vux上传github小步骤
- nodejs版本管理工具NVM(Node Version Mene)
- SDWebImage 加载一些大的图片的时候导致程序崩溃
- 软件工程_9th weeks
- The Salt Master has cached the public key报错解决办法
- Stacking调参总结
- Apollo 配置详细步骤(Windows环境)
- Cookie、Session 和 Token区别
- 【CF799E】Aquarium decoration 线段树
热门文章
- spring cloud config搭建说明例子(二)-添加eureka
- spring 简单实现BeanFactory(转)
- [Usaco2018 Feb]Snow Boots
- ACM_四数之和
- 用Movie显示gif(2)GifView
- TimeOut Error :因为远程服务器关闭导致mnist数据集不能通过input_data下载下来
- 用Python利用pyFirmata控制Arduino实现Blink
- 5步上手体验kettle快捷调度方式
- GDB 学习
- 【sqli-labs】 对于less34 less36的宽字节注入的一点深入