`算法知识` 字符串哈希
catalog
- 经验谈
- 映射从1开始
- 字符串的哈希冲突
- 代码模板
- 字符串哈希
经验谈
映射从1开始
假如是从0开始映射, 则abc 和 bc, 他们的对应的P进制是: (0) (1) (2) 和 (1) (2)
如果采用(前高位)的哈希顺序, 则他们对应的10进制值都是: (1 * P + 2), 就冲突了;
其原因在于: 两者的长度不同; 如果长度相同, 不会出现: 前导零的情况;
一般, 最好都从(1)开始映射
字符串的哈希冲突
由于字符串哈希, 不像整数哈希是有探测法(即整数哈希 不会出现哈希冲突, 探测法解决了这点)
而字符串哈希没有探测法, 因此, 字符串哈希是会发生冲突的; 假如他发生冲突, 目前是没有解决办法的!
只能去尝试更换: 字符串哈希的取模值: 将(默认的1e9+7) 改为: (1e9 + 21)
代码模板
字符串哈希
原理: 两个不同的P进制数, 他对应的十进制数, 是不同的;
假如P = 26, 两个P进制数: (a1) (a2) (a3) 和 (b1) (b2) (b3)
如果存在: ai != bi, 那么其对应的10进制数, 即(a1 * P^2 + a2 * P + a3)是不同的
这就像是, 假如P为熟悉的十进制, 那么(012) 和 (022)是不同的;
因此, 对于一个P进制数(也可以看做是一个P进制字符串), 他所对应的十进制数, 就称为他的(哈希值)
基于此, 假如一个字符串有P个不同的字符, 则对应一个P进制, 每个字符映射到[0, P)之中
由于其对应的十进制数, 会爆出LL, 需要使用取模操作;