Hash表

哈希表存储结构（开放寻址法，拉链法）字符串哈希方式（添加、查找h(x)）

常见从0~10^9映射到0~10^5就要对10^5取mod（取模一般要质数最好）但是可能会有冲突

1.拉链法：O(1)，每个节点拉一条链增加数

#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=(x%N+N)%N;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!=-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--){char op[2];int x;cin>>op>>x;if(op[0]=='I')insert(x);else {if(find(x))cout<<"Yes"<<endl;else cout<<"No"<<endl;}}return 0;
}

2.开放寻址法：开放寻（厕）法

#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;
}
int main(){int n;cin>>n;memset(h,0x3f,sizeof(h));while(n--){char op[2];int x;cin>>op>>x;int k=find(x);if(op[0]=='I')h[k]=x;else {if(k)cout<<"Yes"<<endl;else cout<<"No"<<endl;}}return 0;
}

字符串前缀哈希方式：映射成从1开始取p=131   13331  2^64三个

#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int N=100010,P=131;//进制 
int n,m;
char str[N];
ull h[N],p[N];//h[i]表示前i个数的哈希值,p用于存储p的多少次方 
ull get(int l,int 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[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))cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}