【算法漫笔002】浅谈字符串HASH
字符串Hash 将字符串映射为一个固定范围的整数（也就是哈希值），该映射是单向的，即从字符串计算哈希值很容易，但从哈希值反推原字符串在计算上不可行。
构造哈希函数
哈希函数，即将字符串映射为哈希值的函数。理论上只要是能将字符串转化为哈希值的函数都可以被称为哈希函数。
首先给一个极其容易想到的哈希函数，我们将字符串中的每一个字符的 ASCII 码值相加得到哈希值，如下：
但是这样的哈希函数会有一个严重的问题：哈希冲突。
哈希冲突
首先我们要知道，字符串 Hash 的意义是什么、作用又是什么。普通的字符串操作多数为 O(N)O(N)O(N) 级别的（此处及后文中的 NNN 为字符串的长度），而整数的操作大多为 O(1)O(1)O(1)。
拿一个直观的例子，给你一个长串 SSS，反复询问 Sl1…r1S_{l1 \dots r1}Sl1…r1 和 Sl2…r2S_{l2 \dots r2}Sl2…r2 是否一样。如果是直接截取子串并逐字符比较的话，每一次计算的时间复杂度自然为子串长度。而如果使用哈希去预处理，其预处理后每次比较的时间复杂度为常数级。
但这不代表字符串Hash是万能的，如果两个不同字符串的哈希值相同，程序自然会认为两个字符串相等，在很多情况下就会出现错误，我们称这样的问题为哈希冲突。上文中提到的哈希函数的冲突率极高，仅就长度为 555 的小写字母字符串而言，可能的哈希值只有约 126126126 种，而字符串总数约为 265=118826^5=1188265=1188 万种，冲突率显然十分高。
进制哈希
一种常见的避免哈希冲突的方式是使用 Base Hash，即进制哈希（又称滚动哈希）。其核心思想是：将字符串看作一个 BBB 进制数，每一位字符的 ASCII 码作为该位上的数字，然后对这个 BBB 进制数取模，得到最终的哈希值。BBB 的值通常为 131,1331131,1331131,1331[1] 等。
相比于简单的 ASCII 码求和，进制哈希保留了字符的位置信息，哈希冲突概率大幅降低。
双模数优化
即使是用进制哈希，其哈希结果的数量也取决于 MODMODMOD 的大小，如果题目当中给出的 NNN 很大，就算使用进制哈希，冲突的概率也并不低。所以说，我们做两个进制哈希函数，其 BASEBASEBASE 值和 MODMODMOD 值都不同，程序在检查两个字符串是否相同时会同时调用这两个函数，如果两个哈希函数返回的值都相同，那么程序才认为两个字符串是相同的，冲突概率再次大大降低[2]。
前缀哈希
显然，这样的哈希函数时间复杂度为 O(N)O(N)O(N)，并不高效。然而在大多数题目中，我们需要频繁查询的是同一个字符串的不同子串。此时我们可以通过前缀哈希来预处理，实现 O(1)O(1)O(1) 获取任意子串的哈希值。下文就是一个典型的 进制哈希+前缀哈希+双模数优化 的模板。
哈希可解决的问题
哈希几乎可以解决任何字符串问题。例如：
* 字符串匹配问题，计算模式串的哈希值，在原串中滑动窗口比较，O(N)O(N)O(N) 完成匹配（KMP 的另一种实现方式）
* 最长回文子串问题，正反各算一遍哈希，配合二分，O(NlogN)O(N \log N)O(NlogN) 求解，虽然马拉车可以在 O(N)O(N)O(N) 时间复杂度下解决，之后可能会讲到。
* 最长公共前缀（LCP）：二分 + 哈希，O(logN)O(\log N)O(logN) 查询两个后缀的 LCP，exKMP 也能够实现
* 字符串去重：将所有字符串映射为哈希值存入 unordered_set 中实现去重。
致谢&注释
感谢 StackEdit软件，欢迎大家去使用这个免费的 Markdown 编辑软件。它不仅可以在线使用，还可以下载使用。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 这些值均为质数，经验表明冲突率较低。 ↩︎
2. 双哈希的碰撞概率约为 1MOD1×MOD2\frac 1 {MOD1 \times MOD2}MOD1×MOD21 ，实际使用中几乎可以忽略。 ↩︎
