字符串哈希
字符串哈希就是将一个字符串映射为P进制的整数.
- 将一个字符串映射成一个P进制整数
对于一个长度为n的字符串s,这样定义一个Hash函数:\(h(s)=\sum_{i=1}^{n}s[i] \times p^{n-i}(mod M)\)
例如,字符串,abc,其哈希值为\(ap^2 + bp^1 + c\) - 如果两个字符串不一样,哈希值却一样,这种现象称为哈希碰撞
- 解决哈希碰撞的方法:
巧妙地设置P和M的值,保证P与M互质.
P通常取质数131或者13331
M通常取大整数\(2^{64}\),把哈希函数值的数据类型定义为UUL(unsigned long long),超过则自动移除,等价于取模