字符串哈希

Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。

我们定义一个把字符串映射到整数的函数 ，这个 称为是 Hash 函数。
我们希望这个函数 可以方便地帮我们判断两个字符串是否相等。
具体来说，哈希函数最重要的性质可以概括为下面两条：

1. 在 Hash 函数值不一样的时候，两个字符串一定不一样；
2. 在 Hash 函数值一样的时候，两个字符串不一定一样（但有大概率一样，且我们当然希望它们总是一样的）。

Hash 函数值一样时原字符串却不一样的现象我们成为哈希碰撞。

通常我们采用的是多项式 Hash 的方法，对于一个长度为 的字符串 来说，我们可以这样定义多项式 Hash 函数：。例如，对于字符串 ，其哈希函数值为 。