本文首要叙述哈希表的实现及存储办法，存储办法包括敞开寻址法和拉链法；其次叙述字符串的哈希办法。
作用是把一个巨大的空间映射到一个小的空间内，哈希即将一个数x映射到某一个规模之内，但是不免会有两个数或多个数经过映射函数h(x)后，映射的成果相同，则咱们需要处理冲突。
哈希表的运用一般是增加和查找。
哈希表的存储结构
哈希表的存储办法首要包括拉链法和敞开寻址法。
首要思路
- 拉链法：拉链法的运用办法十分相似于链表，即在遇到冲突的时候，将映射成果相同的x，在同一个方位向下拉链，即构成链表的结构，来实现处理冲突。
- 敞开寻址法：而敞开寻址法则是在遇到冲突之后，在这个冲突点持续向下一个方位寻找，直到找到x应该在的方位，即空位。敞开寻址法的数组长度一般取到x数量的2-3倍。
例题
AcWing 840. 模仿散列表
保护一个调集，支持如下几种操作：
-
I x，刺进一个数xx； -
Q x，问询数xx是否在调集中呈现过； 现在要进行NN次操作，关于每个问询操作输出对应的成果。
输入格局
榜首行包括整数NN，表明操作数量。
接下来NN行，每行包括一个操作指令，操作指令为I x，Q x中的一种。
输出格局
关于每个问询指令Q x，输出一个问询成果，假如xx在调集中呈现过，则输出Yes，不然输出No。
每个成果占一行。
数据规模
1≤N≤105,1≤N≤105
−109≤x≤109−109≤x≤109
输入样例：
5
I 1
I 2
I 3
Q 2
Q 5
输出样例：
Yes
No
解题代码：
本次题解首要从两个方向出发，一个是拉链法一个是敞开寻址法。
/*
* @Author: IndexYang
* @Date: 2022-02-10 14:48:02
* @Last Modified by: IndexYang
* @Last Modified time: 2022-02-10 21:10:55
*/
/************拉链法************/
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100003;
int h[N],e[N],ne[N],idx;
void insert(int x){
//将原数字映射到这个区间之内
int k = abs(x % N);
//运用拉链法将冲突的数连起来（链表）
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}
bool find(int x){
//运用哈希表查找，相似链表的操作
int k = abs(x % N);
for(int i = h[k];i != -1;i = ne[i]){
if(e[i] == x) return true;
}
return false;
}
int main(){
int n;
cin>>n;
//重置内存
memset(h,-1,sizeof h);
while(n--){
string s;
int x;
cin>>s>>x;
if(s == "I") insert(x);
else if(s == "Q"){
if(find(x)) puts("Yes");
else puts("No");
}
}
system("pause");
return 0;
}
/*
* @Author: IndexYang
* @Date: 2022-02-10 14:48:02
* @Last Modified by: IndexYang
* @Last Modified time: 2022-02-10 21:10:55
*/
/************敞开寻址法************/
#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003,null = 0x3f3f3f3f;
int h[N];
int find(int x){
int k = (x % N + N) % N;
while(h[k] != null && h[k] != x){
k++;
if(k == N) k=0;//假如查到头了，则回到榜首个
}
return k; //回来x应该在的方位
}
int main(){
int n;
cin>>n;
memset(h,0x3f,sizeof h);
while(n--){
string s;
int x;
cin>>s>>x;
int k = find(x);
if(s == "I") h[k] = x;
else if(s == "Q"){
if(h[k] != null) puts("Yes");
else puts("No");
}
}
return 0;
}
字符串的哈希办法
首要思路
这儿首要叙述的是字符串的前缀哈希办法，即当一个str="abcdef"时，使得h[1]=”a”的哈希值，h[2]=”ab”的哈希值……,h[x]=前x个字符的哈希值，之后运用前缀哈希算出一切字串的哈希值。
算法过程
- 怎么求哈希值
- “a b c d”是一个p进制的数。
abcd=(1234)p=(1∗p3+2∗p2+3∗p1+4∗p0)modQa b c d = (1 2 3 4)_p = (1*p^3 + 2*p^2 + 3*p^1 + 4*p^0) mod Q 即可将某一个字符串映射到0~Q-1这个区间内了。
- 在字符串的哈希中，不需要考虑冲突的状况，则咱们需要取必定的p和Q值，这儿p=131或13331，且Q=2^64时，不必考虑冲突的状况。
- 运用前缀哈希求出一切字段的哈希值
- 只用 h[l-1] 和 h[r] 即可算出从 l~r 的哈希值。
则l到r段的哈希值为 h[l,r]=h[r]−h[l−1]∗pl−r+1h[l,r] = h[r] – h[l-1]*p^{l-r+1}
- 运用p求出一切前缀的哈希： h[i]=h[i−1]∗p+str[i]h[i] = h[i-1]*p + str[i]，这儿的str[i]即为第i个字符的ASCII值。
例题
AcWing 841. 字符串哈希
给定一个长度为nn的字符串，再给定mm个问询，每个问询包括四个整数l1,r1,l2,r2l1,r1,l2,r2，请你判别[l1,r1][l1,r1]和[l2,r2][l2,r2]这两个区间所包括的字符串子串是否完全相同。
字符串中只包括大小写英文字母和数字。
输入格局
榜首行包括整数nn和mm，表明字符串长度和问询次数。
第二行包括一个长度为nn的字符串，字符串中只包括大小写英文字母和数字。
接下来mm行，每行包括四个整数l1,r1,l2,r2l1,r1,l2,r2，表明一次问询所触及的两个区间。
留意，字符串的方位从11开始编号。
输出格局
关于每个问询输出一个成果，假如两个字符串子串完全相同则输出Yes，不然输出No。
每个成果占一行。
数据规模
1≤n,m≤1051≤n,m≤105
输入样例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例：
Yes
No
Yes
解题代码：
/*
* @Author: IndexYang
* @Date: 2022-02-10 22:03:16
* @Last Modified by: IndexYang
* @Last Modified time: 2022-02-10 22:20:18
*/
#include<iostream>
#include<cstring>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010,P = 131; //这儿P取131为经验值，可以使得不必考虑冲突的状况
int n,m;
char str[N]; //str这儿是输入的字符串，一起运用ASCII值
ULL h[N],p[N]; //h为前n个字母的哈希值，p为上述大P的n次幂
ULL get(int l,int r){
//这儿是求l-r区间内的哈希值
return h[r] - h[l-1] * p[r-l+1];
}
int main(){
cin>>n>>m>>str+1;
p[0]=1;
for(int i=1;i<=n;i++){
//求P的n次幂和前n个字符的哈希值
p[i] = p[i-1] * P;
h[i] = h[i-1] * P + str[i];
}
while(m--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(get(l1,r1) == get(l2,r2)) puts("Yes");
else puts("No");
}
return 0;
}
