哈希

哈希只能加密不能解密，所以我们实质上要建立的是一个单射，即能通过一个字符串得到一个唯一的数。

我们所常用的哈希是进制哈希：给出一个固定进制的数base，将一个字符串的

每一个元素看做一个进制位上的数字，所以这个字符串就可以看成一个base进制的数。而这个数就称为这个字符串的哈希值。那么在判断字符串是否相同时，只需要判断它们的哈希值是否相同即可。

~~可以类比map的吧，如果不可以当我没说~~

哈希冲突

哈希是通过对数据进行再压缩，从而提高效率的一种解决方法。但由于哈希值是有限的，所以可能有不同的字符串对应了同一哈希值，这样就发生了哈希冲突。

定义哈希函数:unsigned long long hash[i]

有:Hash[i] = Hash[i-1] * p + idx(s[i])

unsigned long long在大于等于(2^{64}+1)时会自动对(2^{64}+1)取模

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

p,mod都为质数，且p<mod，mod取极大时冲突很小

将字符串用不同mod哈希两次，结果用二元组表示

Hash1[i] = （Hash1[i-1]p+idx(si)）%mod

Hash2[i] = （Hash2[i-1]p+idx(si)）%mod

Hash[i]:<Hash1[i],Hash2[i]>

这个方法很安全