在ACM中一般只会用到一种名为“BKDR Hash”的字符串Hash算法。它的主要思路是选取恰当的进制，可以把字符串中的字符看成一个大数字中的每一位数字。关于进制的选择实际上非常自由，大于所有字符对应的数字的最大值即可，比如一个字符集是a到z的题目，选择27、233、19260817都是可以的。一般使用李煜东前辈的给出的值——131或13331，此时冲突概率极低。
字符串Hash的实现
跟二进制的算法是一样的。比如对于一个字符串s,p为选取的进制数，使用哈希数组hash[i]保存前缀:一般设Hash[0]=0。
H
a
s
h
[
i
]
=
s
[
1
]
?
p
i
?
1
+
s
[
i
]
?
p
i
?
2
+
s
[
i
]
?
p
i
?
3
.
.
.
.
+
s
[
i
]
Hash[i]=s[1]*p^{i-1}+s[i]*p^{i-2}+s[i]*p^{i-3}....+s[i]
Hash[i]=s[1]?pi?1+s[i]?pi?2+s[i]?pi?3....+s[i]
由此区间[l,r]的哈希值为Hash(l,r)=Hash[r]-Hash[l-1]*
p
r
?
l
+
1
p^{r-l+1}
pr?l+1。
哈希函数中存在指数级，所以一般都需要%MOD，我们一般取MOD=2^64，即用unsigned long long类型保存哈希值，让其自然溢出就好，因为此类型是不会出现负数的（无符号位）。
为了方便使用我们一般预处理出p的i次方的值存到bin数组中,我们一般用bin数组打表而不是用快速幂，因为快速幂可能超时。
#define ull unsigned long long
const ull mod = 1<<64;
int p=131;
for(int i = 1; i <= n; ++i)
{
hash[i] = hash[i - 1] * P + str[i] - 'a' + 1;
}
ull getsub(int l, int r)
{
return hash[r] - hash[l - 1] * bin[r - l + 1];
}
注意
两个元素若全等，其哈希值必定也相等；但哈希值相等，两个元素未必全等（哈希值相等是两个元素全等的必要不充分条件）。
即Hash是尽量使冲突概率趋近于0，（尽量的满足其充分性）。
此外，字符串每种元素的值都要至少从1开始，不能从0开始。比如说小写字母，如果从0开始，即a=0，b=1，…，z=25，那么b和ab的哈希值会相同，这时候就会发生冲突，但从1开始就没这种问题了。