哈希表
哈希表是一种非常优雅实用的数据结构,把庞大复杂的数据映射到较小的范围。
使得查找、插入和删除操作可以在平均情况下提供接近常量的时间复杂度,即O(1)。
若干不同的数倍映射成相同的数,称为哈希冲突。
对于哈希冲突我们有两种方法来处理,如下
1.拉链法(可以用链表或者vector实现)
用vector:(洛谷深入浅出yyds)
#include <bits/stdc++.h>
using namespace std;
const int mod = 233333;
vector<int> h[mod + 2];
inline void insert(int x) {
int f = 0;
for (int i = 0; i < h[(x % mod + mod) % mod].size(); i++) {
if (h[(x % mod + mod) % mod][i] == x) {
f = 1;
break;
}
}
if (!f) h[(x % mod + mod) % mod].push_back(x);
}
inline void find(int x) {
for (int i = 0; i < h[(x % mod + mod) % mod].size(); i++) {
if (h[(x % mod + mod) % mod][i] == x) {
cout << "Yes\n";
return;
}
}
cout << "No\n";
}
int main() {
ios::sync_with_stdio(0),cin.tie(0);
int n;
cin >> n;
while (n--) {
char op;
int x;
cin >> op >> x;
if (op == 'I') insert(x);
else find(x);
}
return 0;
}
用数组模拟链表:(y总)
#include <bits/stdc++.h>
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; i = ne[i]) {
if (e[i] == x) return 1;
}
return 0;
}
int main() {
int n; scanf("%d", &n);
memset(h, -1, sizeof h);
while (n--) {
char op[2]; int x;
scanf("%s%d", op, &x);
if (*op == 'I') insert(x);
else {
if (find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
2.开放寻址法(个人不太爱爱用这个,要开数组2-3倍,提高效率)
#include <cstring>
#include <iostream>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
int h[N];
int find(int x){
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x){
t ++ ;
if (t == N) t = 0;
}
return t;
}
int main(){
memset(h, 0x3f, sizeof h);
int n;scanf("%d", &n);
while (n -- ){
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') h[find(x)] = x;
else{
if (h[find(x)] == null) puts("No");
else puts("Yes");
}
}
return 0;
}
字符串哈希
将字符串当成P进制来处理,然后再使用哈希函数
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N=100010,base=131;
int n,m;
char str[N];
ULL h[N],p[N];
//获取字串哈希值
ULL get(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",str);
p[0]=1;
for(int i=0;str[i];i++){
h[i+1]=h[i]*base+str[i]; // 计算前缀哈希值
p[i+1]=p[i]*base; // 更新幂次
}
while(m--){
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if (get(l1,r1)==get(l2,r2)) puts("Yes");
else puts("No");
}
return 0;
}