哈希表
作用：类似离散化，将值域较大的一些数映射进较小的范围中，并快速查询是否存在
一般可以用取模运算来映射，取模时最好取质数
注意：c++取模时会出现负数，所以取模后加上$mod$再次取模即可
若重复，解决方法：
- 拉链法：利用链表存储重复元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
using namespace std;
const int N=100003;
int n;
int h[N],ne[N],e[N];
int cnt;
void insert(int x){
e[++cnt]=x;
x=(x%N+N)%N;
ne[cnt]=h[x];
h[x]=cnt;
}
bool find(int x){
int t=(x%N+N)%N;
for(int i=h[t];i;i=ne[i]){
if(e[i]==x)return 1;
}
return 0;
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
char op[2];
cin >> op;
int tmp;
cin >> tmp;
if(op[0]=='I'){
insert(tmp);
}
else{
if(find(tmp))cout << "Yes\n";
else cout << "No\n";
}
}
return 0;
}
|
开放寻址法
遇到冲突时向后遍历第一个空的地方插入。
为了减小向后查找的次数，数组一般开两倍大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
using namespace std;
const int N=200003,INF=0x3f3f3f3f;
int n,Hash[N];
int find(int x){
int t=(x%N+N)%N;
while(Hash[t]!=INF){
if(Hash[t]==x)return t;
t++;
if(t==n)t=0;
}
return t;
}
void insert(int x){
Hash[find(x)]=x;
}
int main(){
memset(Hash,0x3f,sizeof Hash);
cin >> n;
for(int i=1;i<=n;i++){
char op[2];
cin >> op;
int x;
cin >> x;
if(op[0]=='I'){
insert(x);
}
else{
if(Hash[find(x)]==x)cout << "Yes\n";
else cout << "No\n";
}
}
return 0;
}
|
应用：字符串哈希
作用：快速判断两个字符串是否相同
字符串前缀哈希法：
先处理字符串前缀的哈希值$h$：
$$
h[i]=\sum_{\mathclap{1\le i\le n}} (str_i-‘A’) %Q
$$
然后可以通过$h$数组求出字符串任意的子串哈希值
$$
hash(L,R)=(h[R]-h[L-1]\times P^{R-L+1})%Q
$$
此后，比较两个字符串是否相等就可以比较两个字符串的哈希值是否相等。
注意：因为部分数值到达了$2^{64}$,因此需要unsigned long long
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+5,P=131;
int n,m;
string s;
ull h[N];
ull p[N];
int get(char ch){
if(ch>='0'&&ch<='9')return ch-'0'+1;
if(ch>='a'&&ch<='z')return ch-'a'+11;
if(ch>='A'&&ch<='Z')return ch-'A'+37;
}
ull Hash(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main(){
cin >> n >> m;
cin >> s;
p[0]=1;
for(int i=1;i<=n;i++){
p[i]=p[i-1]*P;
h[i]=h[i-1]*P+get(s[i-1]);
}
for(int i=1;i<=m;i++){
int l1,r1,l2,r2;
cin >> l1 >> r1 >> l2 >> r2;
if(Hash(l1,r1)==Hash(l2,r2))cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
|
