1、 什么是哈希
哈希算法是：通过哈希函数将字符串、较大的数等转换为能够用变量表示的或者是直接能作为数组下标的数，通过哈希算法转换到的值，称之为哈希值。哈希值可以实现快速查找 和匹配。
比如：用数组下标计数法，统计一个字符串中，每种字母出现的次数就是一个简单的哈希，将每个字母都映射为了对应的ascii码。
2、 如何构造哈希
原理：将字符串中的每一个字母都看作是一个数字(例：从a-z,视为1-26)；将字符串视为是一个b进制的数。(注意，不能映射为0,因为如果a为0, 那么a、aa、aaa的值将都为0)
比如：可以将字符串s=”abcd”视为26进制的整数，则可以计算出： hash(s)=1*263+2*262+3*261+4*260。 如果字符串很长，h(s) 很容易超出 long long 的范 畴，为防止溢出，我们取一个固定的值 h 用 hash(s)%h，使得结果在long long范围内。
选取两个合适的互质常数b和h (b<h)，其中h要尽可能的大一点，为了降低冲突 (不同字符串计算到同一个哈希值) 的概率。
一般来说：b取131或13331, h取264，最终产生的哈希值的冲突的概率极低。
假设字符串C=c1c2c3…cm,定义哈希函数：
H(C) = (c1 * bm-1 + c2 * bm-2 + … + cm * b0) mod h。在实际计算中不用 mod h，因为264是unsigned long long范围内，H采用unsigned long long的类型，那么数据溢出就相当于 mod h 了。
3、 滚动哈希优化
如果针对一个很长的字符串，判断其中两个长度为len的子串是否相同，如果釆用 O(len)的时间复杂度计算出对应的子串hash,那和直接取出子串比较的时间复杂度并无差异，因此我们需要使用滚动哈希优化的技巧，可以在0(1)的时间复杂度下取出子串的hash 值。
(1) 滚动计算到前缀哈希h(k)
设：h(k)为字符串 C 前 k 个字符构成的子串的哈希值，(先不考虑取模)：
h(k+1)= h(k)*b+ck+1；
类比 10 进制理解该公式，比如 10 进制的12345,取出前3个数是123，如果要取前 4 个数，可以使用：123 * 10 (进制)+ 4(ck+1) = 1234 的方法来取出。
(2) 利用前缀哈希H(k)计算区间哈希值
设：
H(R) = c1*bR-1 + … + CL-1*bR-L-1+CL*bR-L + … + cr*b0
H(L-1) = ci*bL-2 + … + CL-I * b0
H(L,R) = H(R) – H(L-l) * bR-L+1
因此，求L~R之间的哈希值： H(R) – H(L-l) * bR-L+1
由上述公式可知，只需要预处理出bm，就可以在0(1)的时间内求得任意子串的哈希值。
(3) 时间复杂度
综上，如果在一个长度为n的字符串中，任意取长度为m的子串进行匹配，时间复杂度 为 O(n+m)。
本章节的下一个知识点：哈希表原理