两种哈希的简单总结
普通哈希
例题：模拟散列表
哈希的基本思想是通过y=f(x)把一个很大的定义域映射到一个较小的值域中去，因为%的特性会导致多对一（哈希冲突），以下为两种不同的解决哈希冲突的办法。
拉链法：在拉链法中，在每个哈希后的序号k下拉一条链表（像邻接表），模数N应该取大于或等于数据范围的第一个素数
void hash_insert(int x){
int k=(x%N+N)%N;
e[++idx]=x; nxt[idx]=h[k]; h[k]=idx;
}
bool hash_quiz(int x){
int k=(x%N+N)%N;
bool flag=0;
for(int i=h[k];i;i=nxt[i]){
if(e[i]==x){
flag=1;
break;
}
}
if(flag)return 1;
else return 0;
}
idx=0;
memset(h,0,sizeof(h));
此处idx从0开始，从1开始其实都没有问题，只需改动部分语句即可
开放寻址法（使用找厕所思维）：N应该取大于等于数据范围的两到三倍的第一个素数
int hash_get(int x){
int k=(x%N+N)%N;
while(h[k]!=null&&h[k]!=x){
k++;
if(k==N)k=0;
}
return k;
}
int k=hash_get(x);
if(s[0]=='I')h[k]=x;
else if(s[0]=='Q'){
if(h[k]==null)printf("No\n");
else printf("Yes\n");
}
注意hash_get中while条件的写法：
- 当此位置为空，：对于插入则可以插入该位置，对于查询则不存在该值（h[k]==null）
- 当此位置为x：对于插入则已存在无需插入，对于查询则找到了该值
字符串前缀哈希
例题：字符串哈希（字符串前缀哈希法
字符串哈希是先通过p进制把一个字符串转化为特定的数字，再通过取模把这个数字映射到较小的值上，存储到前缀哈希串上，再通过前缀哈希串来对字符串进行快速的比对。
1.对于哈希冲突：尽人事（使用经数学验证的模数和素数），听天命（看RP高不高）。
2.好数：p的值取131和13331，MOD取1<<64。在取模运算中，因为MOD=1<<64如果开成ull则可以避免溢出的问题(溢出即导致前缀哈希值大于1<<64，即原来取模为1的数放到1<<64+1取存储了，因为取模后的值一定小于1<<64，所以ull刚好可以解决冲突)。
3.映射的细节：不要映射成0，如果'A'对应0会导致”A”和”AA”的值一致(如果直接用asc码就不用想那么多)。
4.背公式：h[l,r]=h[r]-h[l-1]*index[r-l+1]。公式自己手推一遍就会很清晰。
const int N=100005,p=131;
ull h[N],idx[N];
ull str_hash(int l,int r){//计算哈希
return h[r]-h[l-1]*idx[r-l+1];
}
//前缀表和高次幂表
idx[0]=1;
for(int i=1;i<=n;i++){
idx[i]=idx[i-1]*p;
h[i]=h[i-1]*p+s[i];
}
int l1,r1,l2,r2;//处理询问
while(m--){
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(str_hash(l1,r1)==str_hash(l2,r2))printf("Yes\n");
else printf("No\n");
}