浅谈字符串Hash
本篇随笔讲解Hash（散列表）的一个重要应用：字符串Hash。
关于Hash
Hash是一种数据结构，叫做Hash表（哈希表），也叫散列表。关于Hash的实现，其实与离散化颇为类似。就是把若干的复杂的信息映射到一个比较容易维护的值域去。具体的实现方式是散列函数，即Hash函数，其原理是对于一个数据，选取一个关键键值(k)，那么这个数据在Hash表中的位置就是(f(k))。那么这个对应关系（(f())）就是哈希函数。
哈希冲突
因为我们只是定义了一个(f())作为哈希函数，并没有定义这个(f())到底是什么样的函数。所以显然地，可能会出现一个函数(f(k))，使得两个不同的(k(k_1 ot=k_2))而出现函数值相等的情况(f(k_1)=f(k_2))（比如二次函数）。这种情况被称作哈希冲突。导致答案错误。
关于字符串Hash
字符串哈希就是在字符串上进行哈希。字符串哈希的用处是快速判断两个字符串是否相等。
一个简单的思想：将一个字符串转化为一个整数，这样，只需要比较整数相不相等就可以判断这个串是否重复出现过（不考虑哈希冲突）。
但是这个思想不考虑哈希冲突，不代表我们实现的时候也肯定不会出现哈希冲突。那么，我们当然希望我们哈希的东西（哈希映射，散列函数）是一个单射。
那么，我们用什么方法来避免哈希冲突呢？
自然溢出
给定一个字符串(S=s_1s_2s_3cdots s_n)，我们规定：(f(x)=x-'a'+1).
那么，自然溢出的哈希公式可以如此这么表示：
注意，这里的哈希数组是(unsigned\, long\, long)范围的，所以可以通过自然溢出而自动取模(2^{64}-1)。
单Hash法
单Hash法的哈希公式可以这么表示：
显然，(mod)越小越容易冲突，所以我们把(p,mod)都尽量取大即可。
这种方法仍然存在哈希冲突的概率，只不过特别低。实际运用的时候可以使用这种方法。除非你RP低到一定境界，否则不会被卡掉。
例如：
(p=13,mod=101)，对(abc)进行如上所示的(hash)。
(hash[0]=1)（从0开始计算）
(hash[1]=15)
(hash[2]=97)
那么97就是(abc)的hash值。
双hash法
hash一遍可能还会出现冲突，那我hash两遍。这就是双Hash法。
开一个二元组，用两个不同的(mod)来分别(Hash)，得到的两个结果存进二元组，作为哈希的结果。
同理，你还可以开一个结构体，多哈希几遍（强迫症患者）（滑稽.jpg）
子串Hash
字符串子串是个常见的问题，变式很多。
但是，显然的是，如果我们求出了一个大串的hash,就能以(O(1))的时间求解其子串的哈希值。
来让我们解释一下这个“显然”的含义：
(hash[1]=s1)
(hash[2]=s1∗p+s2)
(hash[3]=s1∗p2+s2∗p+s3)
(hash[4]=s1∗p3+s2∗p2+s3∗p+s4)
(hash[5]=s1∗p4+s2∗p3+s3∗p2+s4∗p+s5)
现在展示的是1-5的哈希。
如果我们要求s3s4的哈希，容易得出（根据哈希公式）：(s_3 imes p+s_4)。我们把(hash[4],hash[2])进行消元处理的话，就能将结果中带有(s_1,s_2)的系数消掉，而这个操作只需要乘上(p^2)即可。
那么：
那么我们处理出通项公式：
取模的时候为了防止减法运算出现负数，还要做如下处理：
这就完事了。