定义
字符串哈希
将一个字符串映射到整数。这时可以通过判断整数是否相等来判断字符串是否相等，从而降低了时间复杂度。
方法
多项式哈希
对于一个字符串，哈希值的计算公式为：
其中：
- (Base)： 通常取一个大于字符集大小的质数。常用：, , 。
- (Mod)： 为了减少冲突，通常取一个大质数。常用：, 。
技巧
快速获取任意子串的哈希值
先考虑字符串前个字符构成的子串，设长度为0的字符串哈希为0，对于前个字符，可以发现前个字符都要多乘一个，然后加上第个字符，即：
0 & if~~i = 0 \\ (h[i-1] \cdot P + s[i]) \pmod M & if~~i>0 \end{cases}$$ 然后再考虑对于长度为$i$的字符串$S$去掉前$j$个构成的子串，可以发现保留的字符需要的$P$的数量不变，而前$j$个字符再乘$i - j$个$P$刚刚好就是前$i$个字符的值，即：$$Hash(S[l..r]) = (h[r] - h[l-1] \cdot P^{r-l+1}) \pmod M$$