哈希表的主要内容是两大块：
- 介绍哈希表这个存储结构
- 介绍一个字符串哈希的方式
哈希的存储也有两种方式
- 开放寻址法
- 拉链法
存储
在说存储之前，先说一下哈希表的主要作用
作用就是把一个比较庞大的值域，映射到一个比较小的区域内，一般是映射到从$0-n$，$n$一般就比较小，$10^5, 10^6$这个等级的（这不离散化么）。
一般就是把 $0-10^9$ 这些数映射成 $0-10^5$ 这个范围内
可以看一道例题：模拟散列表
他要支持两种操作，一种是在集合内插入一个整数x，另一种是查找整数x在不在集合内
操作的个数不超过 $10^5$，日常照顾抓哇童鞋（滑稽）
我们可以写个函数，叫做哈希函数，作用是输入一个 $x(-10^9 \le x \le 10^9)$，把它映射到一个在 $(0, 10^5)$ 范围内得数。
那这样还有几个问题
- 哈希函数怎么写
其实直接用那个数 $mod 10^5$ 就行 - 有可能会有冲突
$10^9$级别上的数，被映射到 $10^5$ 那个级别上，当然会有冲突。
先扯点别的：哈希和离散化到底有啥区别呢
可以说，离散化是一种极其特殊的哈希。
离散化是要保序的，但哈希不用。
这就去抛弃离散化（doge）
回到正题，解决冲突的方式有两种，就是开头那两种
第一种：拉链法
拉链法就是开一个一维数组，存储所有的哈希值。
处理冲突的方法就是，每次把 $x$ 映射到某一个数的时候，比如把11映射到3，就把3那个槽下面拉一条链，存上11，然后如果还有一个数映射到3那么就将它接到11的下面。
哈希表是一个期望函数，意思就是可以把每一条链的长度都看成一个常数，这样哈希表的时间复杂度就接近于 $O(1)$，非常快。
而在算法题里，一般是不会删除某一个数的，应该只有插入和删除。
插入很简单，就求一下 $h(x)$ ，也就是哈希函数，然后再栓到那条链上就可以了，这个链就是当初学的单链表。
查找也很简单，就看一下 $x$ 在哪个槽里，然后遍历那个链表看看有没有就可以了。
至于删除，倒不用真的删掉，就开一个bool数组，存每一个点有没有被删就行。
最后有一点，就是取模时尽量取质数，这个是有讲究的，详见这个(从网上随便搜的)。
代码：
哈希中写开放寻址法和拉链法的人数差不多多
const int N = 1e5 + 3; 大于100000的第一个质数
int h[N]/*首先要先开一个槽*/, e[N], ne[N], idx/*然后是单链表*/;
插入操作：
void insert(int x){
int k = (x % N + N) % N; // k就是哈希值，这一串就是让它的余数变成正数
// 需要将那个点插到h[k]上。
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
// 参考单链表的头插法
}
查询操作：
bool find(int x){
int k = (x % N + N) % N; // 见上
for (int i = h[k]; ~i; i = ne[i]){
if (e[i] == x)
return true;
} // 遍历整条链
return false;
}
这就是哈希表中的拉链法。
第二种：开放寻址法
y总喜欢用的方法。
开放寻址法只需要一个一维数组，不过要开到题目标准的两到三倍。
跟上厕所差不多（yの奇妙比喻），$x$ 的哈希值如果为 $k$（如果人要到这个坑位上厕所），那先看看有没有一个值也映射到了 $k$（看看这个坑位有没有人），如果有值映射到了 $k$（这个坑位有人），就往后找一个位置（就往后找一个坑），一直找到位置为空了为止（一样），把 $x$ 放进去（上厕所）。
插入就是求一下$h(x)$，然后一直往后找到空的位置给他安上。
查找，求$h(x)$，然后往后遍历， 如果遍历到空的坑位了还没找到那就是没有了。
至于删除，跟拉链法差不多。
代码：
const int N = 2e5 + 3/*得开两倍*/, null = 0x3f3f3f3f/*提前存一个空指针*/;
int h[N]; // 开一个厕所
开放寻址法和拉链法是不同的，开放寻址法主要是一个 $find$ 函数。
他主要求的是：
- 如果x在表中存在的话，就返回x的位置。
- 如果x在表中不存在，就返回应该存储的位置
int find(int x){
int k = (x % N + N) % N; // 见上
// 要提前把厕所里面的数都设成空指针，代表坑里没有人
while (h[k] != null && k[k] != x){
k++;
if (k == N)
k = 0;
}
return k;
}
让 $k$ 是 $find(x)$。
如果是插入，就让 $h_k \gets x$;
最后判断如果 $h_k = null$ , 就说明这个值不存在，否则就是存在
这就是哈希表中的开放寻址法。
哈希表就结束了，简单总结一下
- 开放寻址法就是如果坑里有人就往后找坑。
- 拉链法就是如果坑里有人，
就拉他头上，就一起双排甚至多排，就在门口排队。
字符串哈希
学 $kmp$ 学的蒙蒙叨叨的，而用字符串哈希就能完美的解决这个问题，这就去放弃kmp。
字符串哈希其实是个比较特殊的哈希方法，叫做“字符串前缀哈希法”。
那他到底是什么意思呢？
假设有一个字符串 $str = \texttt{gwcakakioi}$ ($gwc$ 是俺的名字)
先预处理每个前缀的哈希
比如：
$h_1 = \texttt{g}$的哈希值
$h_2 = \texttt{gw}$的哈希值
$\vdots$
$h_{10} = \texttt{gwcakakioi}$的哈希值
注意 $h_0 = \varnothing$，因为前零个数的哈希值就是空。
那么哈希值怎么定义呢？
我们可以把每个字符串前缀看成一个$p$进制的数。
比如拿 $h_3$ 来说吧，$h_3$是 $\texttt{gwc}$。
假设 $p$ 是26，把 $a, b, \ldots, z$ 看成 $1, 2, \ldots, 26$
$$\begin{aligned} \texttt{gwc} &= (7 23 3)_p \\ &= 7 \times p^2 + 23 \times p^1 + 3 \times p^0 \end{aligned}$$
但要是这样的话数可能会比较大，所以就要模一个较小的数$N$，最后就是这样：
$$(7 \times p^2 \bmod N + 23 \times p^1 \bmod N + 3 \times p^0 \bmod N) \bmod N$$
好长，这就是最后哈希的结果，这样我们就能将一个字符串映射到 $0 \sim N - 1$之间的一个数了。
这里要注意几个点
- 不要把字母映射成零，因为这样就可能出现多个字符串等于一个数的情况（指未取模前）
- 当然取模后是有冲突的对吧，我们家顶自己 $rp$ 等于 LONG_LONG_MAX 不用去管冲突，我们让$\begin{cases} p = 131 \operatorname{or} 13331 \\ N = 2^{64} \end{cases}$，这样就有 99.99% 的概率没有冲突，
当然 99.99% 是我瞎说的。
额，说了半天，好处是什么呢，好处就是我们可以通过之前求得前缀哈希值以及某种公式，把字符串中所有子串的哈希值都算出来。
根据前缀和（应该是吧）等等BLABLABLA公式可以推出 $h_{l \sim r} = h_r - h_{l-1} \times p^{r-l+1}$，至于为什么我也没看懂，知道就行。
它的作用可以通过一道题表现出来： 字符串哈希。
如果两个子串的哈希值相同，就说明它俩相同，否则就说明它俩不相同。
上代码：
const int N = 1e5 + 5, P = 131;
int n, m;
string str;
unsigned long long h[N], p[N];
-----------准备工作-----------
p[0] = 1;
for (int i = 1; i <= n; i++){
p[i] = p[i-1] * P; // 先把所有P的多少次方处理了
h[i] = h[i-1] * P + str[i]; // h表示前缀哈希值；
}
while (m--){
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (get(l1, r1) == get(l2, r2)) printf("Yes\n"); // get表示求哈希值
else printf("No\n");
}
