哈希表最大的作用是快速查找，在上一篇文章中（【数据结构】【哈希】哈希表的概念和算法实现）也给出了哈希表插入和查找一个字符的实现方法。
那么如果是多个字符（即字符串），我们该如何处理？比如让你判断两个文件内容是否相同？如果共有10000个字符，一个一个去比较的话，若前9999个都一样，最后一个不一样，那么这种比较方法是相当低效的。
按照之前哈希的思路，我们只需要将这个字符串通过哈希函数find(x)得到其哈希值，与用同样的方法得到的另一个字符串的哈希值相比较，如果相等就说明两个字符串相同，如果不相等就说明两个字符串不相同。这样的方法效率会大大提升，因为只需计算一次，所以将时间复杂度由O(n)降到O(1)。
因此我们引入字符串前缀哈希法，这个方法常常用于字符串的快速匹配（即判断两个字符串是否相等）。有很多字符串的问题不仅可以用之前提到的kmp算法（【数据结构】KMP算法详解），也可以用哈希处理。
1 哈希函数的设计
对形如x1x2x3…xn-1xn的字符串，其哈希值 = 字符串的ascii码 × p的次方，即：
比如字符串"ABCD"，假设 1 - 4 分别对应 A - D的ascii码，则其哈希值 = 1 * P3 + 2 * P2 + 3 * P1 + 4，为了避免该哈希值过大，我们往往对其取模即：哈希值 mod Q。
其实字符串哈希最核心的一点就是，将字符串看成一个P进制的数，哈希的过程就是将P进制的数转换成十进制的数。
2 处理冲突的方式
为了避免冲突，我们有如下经验之谈：
- 字符的映射值不能为0，多少都无所谓，这里选择ascii码
- P = 131 或 13331
- Q = 264
怎么样是不是很玄学
3 子串的匹配
对两个完整字符串的匹配我们可以采用以上方法，但是如果实现取字符串的两个子串匹配，每取一次就计算一次哈希值的时间复杂度也会到O(n)。最好的方法就是预处理求前缀和，把时间复杂度降低为O(1)。
当得到前缀和数组后，每次对[l, r]区间字符串的访问就可以直接得到其哈希值了。
对应的两个公式分别是：
- 预处理：h[i] = h[i - 1] * P + str[i]
- 每次查询[l, r]：h[r] - h[l - 1] * Pr-l+1
注：为什么不是 h[r] - h[l-1] 而是 h[r] - h[l - 1] * pr-l+1？理由如下：
给定字符串ABCDE，想知道ABC和DE，那么看成P进制的数之后，DE = ABCDE - ABC00（其中：ABC00 = ABC * p2），而不是ABCDE - ABC。
4 总代码
我们只需要掌握3中的两个公式，就可以写出代码了。
注意两点：
- P = 131 或 13331，为了便于计算Pr-l+1，我们可以在设置p[N]数组存放P的次方值，在预处理h[N]的同时预处理p[N]。
- 这里用到了
unsigned long long，没必要取模了，因为这个变量类型就是64位的，如果超过的话自带mod 264功能。
题目链接：841. 字符串哈希
题目代码：
#include<iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
char str[N];
ULL h[N]; // 字符串前缀和
ULL p[N]; // P的多少次方的值
ULL get_hash(int l, int r){
return h[r] - h[l - 1] * p[r - l + 1];
}
int main(){
int n, m;
scanf("%d%d%s", &n, &m, str + 1); // 优雅式写法
p[0] = 1;
// 预处理h[N], p[N]
for(int i = 1; i <= n; i ++){
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + str[i]; // 保证字符的映射值不是0就可以，多少都无所谓，这里用的是ascii码
}
// m次查询
while(m --){
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if(get_hash(l1, r1) == get_hash(l2, r2)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
题外话：
注意一个写法，字符串的位置从1开始编号，所以我们从h[1]开始存储字符串，y总用到了一个非常优雅的方法来读取：
char str[N];
scanf("%s", str + 1);
y总对字符串的接收总能让我意外，还有之前为了避免读入空格和换行，比如"D 5"这种，y总的读取方法是：
char op[2];
int x;
scanf("%s%d", op, &x);
if(*op == 'D') /**/
else /**/
5 参考
[1] C语言数据类型占用字节大小