哈希 散列 Hash
对于2个字符串，希望计算出Hash值
如果Hash值相同，那么字符串相同
如果Hash值不同，那么字符串不同
如果能做到的话，相当于字符串和Hash值一一映射，做不到
如果Hash值不同，那么字符串一定不同
如果Hash值相同，那么字符串尽量相同
如果字符串不同，且Hash相同，就说明Hash碰撞，这个不好，会导致错误，我们需要降低这个发生的概率
假设Hash值是随机的，Hash值的范围是 p = 4294967296 或者 1000000007 大概几十亿
比较两个不同的字符串，Hash值不同的概率是 1 - 1/p
比较两个不同的字符串，Hash值相同的概率是 1/p
如果比较n次不同的字符串，每一组Hash值都不同的概率 (1 - 1/p) ^ n
如果比较n次不同的字符串，存在一组Hash值相同的概率 1 - (1 - 1/p) ^ n
注意到 (1 - 1 / n) ^ n = e ^ -1
只有当 n 和 p 差不多大的时候，这个概率才比较大
所以说，如果目标是比较两个字符串是否相等，直接比较Hash值是没问题的
%2的次幂是可能被卡掉，所以不能使用自然溢出
abbabaabbaababba
baababbaabbabaab
如果选择自然溢出
那么一定存在两个不同的长度为 2048 的字符串，hash值相同
是否存在长度更短的，看运气
底数 b
模数 自然溢出的话是 2**64
如果手动取模的话，需要处理负数，模多少，范围就是多少
s是原字符串
h[i]是前i个字符的hash值
可以通过两个前缀的hash值相减，得到一个子串的hash值
h[0] = 0
h[1] = s[0]
h[2] = s[0] * b + s[1]
h[3] = s[0] * b * b + s[1] * b + s[2]
h[4] = (s[0] * b * b * b + s[1] * b * b + s[2] * b + s[3]) % p
h[i + 1] = h[i] * b + s[i]
希望知道 s[1] s[2] 这个子串的hash值
(h[3] - h[1] * b * b) % p = (s[1] * b + s[2]) % p
单模数Hash会在
输入一个长度为n的字符串，问有多少个长度为m的子串
做法：生成所有n-m+1个子串的hash值，去重，看有多少个不同的
如果自然溢出，会出错
如果模 int 范围的质数，对大约 十万个数字 做去重，会出错
一定要注意比较n对字符串出错的概率
和对n个不同的字符串hash值去重出错的概率
所以最稳妥的方法是双模数hash，底数随机，是最稳妥的方法，即使出数据的人看到了你的程序，也没有办法造出反例
h1[4] = (s[0] * b1 * b1 * b1 + s[1] * b1 * b1 + s[2] * b1 + s[3]) % p1
h2[4] = (s[0] * b2 * b2 * b2 + s[1] * b2 * b2 + s[2] * b2 + s[3]) % p2
参考题目