哈希

数字哈希

用于单点修改及数字查询，期望复杂度均摊O(n)，核心在于建一个链表结构，将读入数据取模一个较大值并以此值作为链表行，存储行头，相临值编号及编号对应值，在查询时直接访问行即可，模板：

#include<bits/stdc++.h>
using namespace std;
const int N = 100005,M = 99991;
int hd[M],nxt[N],val[N],idx = 1,a,n;
char s[2];
void add(int x){
int cnt = (x%M+M)%M;
val[idx] = x;
nxt[idx] = hd[cnt];
hd[cnt] = idx;
}
bool query(int x){
int cnt = (x%M+M)%M;
for(int i = hd[cnt];i;i = nxt[i]){
if(val[i] == x) return true;
}
return false;
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%s",s);
if(s[0] == 'I'){
scanf("%d",&a);
add(a);
}else{
scanf("%d",&a);
if(query(a)) printf("Yes\n");
else printf("No\n");
}
idx++;
}
return 0;
}

字符串哈希

用于解决字符串的匹配及查询问题，衍生用法可查询循环节（不过KMP可以更简单地实现此效果）。时间复杂度O(m+n)，方法核心在于将字符串按位转化为一个数字，类似于十进制转二进制，再将该值进行匹配

 如图即为匹配成功

该值基本具有唯一性（其余情况出现概率极小，所以可以放心用），由于该值较大且确保为正数，我们可以使用unsigned long long进行储存，代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 1000005,P = 131;
int t,ans,l1,l2;
ull hs1[N],hs2[N],p[N];
char s1[10005],s2[1000005];
int main(){
scanf("%d",&t);
p[0] = 1;
for(int i = 1;i <= N;i++) p[i] = p[i-1]*P;//预处理p数组
for(int i = 1;i <= t;i++){
ans = 0;
cin >> (s1+1) >> (s2+1);
l1 = strlen(s1+1);
l2 = strlen(s2+1);
for(int i = 1;i <= l1;i++) hs1[i] = hs1[i-1]*P+s1[i];
for(int i = 1;i <= l2;i++) hs2[i] = hs2[i-1]*P+s2[i];
for(int i = l1;i <= l2;i++) if(hs1[l1] == hs2[i]-hs2[i-l1]*p[l1]) ans++;//匹配过程
printf("%d\n",ans);
}
return 0;
}