AcWing 840. 模拟散列表 - 哈希表
原题链接
简单
作者:
Im_OK
,
2023-11-14 11:26:15
,
所有人可见
,
阅读 54
两种方式
- 根据处理冲突的方式进行划分为两种方式
- 开放寻址法 开一个操作数 2~3倍的数组进行储存,可以视为平躺着的单链表
- 拉链法 在一般情况下链的长度可以看成长度、那么查找的时间复杂度为O(1)
用途
- 把一个较大的操作值域空间映射到一个较小的区域 比如(0~10^5)
- 一般只有添加和查找两种操作,没有删除操作
- 如果需要删除操作:通过开一个标记数组,例如布尔数组进行标记是否被删除。
注意事项:
- 哈希函数:
mod a
a尽量取成质数和尽量离2^n远
思考
- 因为一共n^5的操作数,理想情况下每个哈希表槽里都有一个元素。有正数和负数的情况下不用担心冲突。
- 因为一共n^5的操作数,所以一个长度为n^5的数组就够了,idx也不会越界
- 开放寻址法:关键操作:find()函数
拉链法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100003;
int h[N]; //哈希表
int e[N], ne[N], indx;//每个节点的链表
void insert(int x){
int k = (x % N + N) % N; // 令负数的余数也为正数
//相当于在链表头插入元素,h[k]等同于head指针
e[indx] = x;
ne[indx] = h[k];
h[k] = indx ++;
}
bool query(int x){
int k = (x % N + N) % N;
int a = h[k];
while(a != -1){
if(e[a] == x) return true;
a = ne[a];
}
return false;
}
int main(){
int m;
cin >> m;
memset(h, -1, sizeof h);
char op[2];
int x;
while(m--){
scanf("%s%d", &op, &x);
if(op[0] == 'I') insert(x);
else printf("%s\n", query(x) ? "Yes" : "No");
}
}
开放寻址法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f; //两倍的操作数, null可以认为int的正无穷
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; //说明k原来是N-1已经走到了末尾。需要循环到头进行find
}
return k;
}
int main(){
int m;
cin >> m;
memset(h, 0x3f, sizeof h); //按字节赋值全部元素赋值为0x3f3f3f3f
char op[2];
int x;
while(m--){
scanf("%s%d", op, &x);
int k = find(x);
if(op[0] == 'I') h[k] = x ; //不考虑重复元素,因为只有查询操作
else printf("%s\n", h[k] != null ? "Yes" : "No");
}
//寻找大于某个数的第一个质数,开数组的时候需要。
// for(int i = ;;i++){
// bool flag = true;
// for(int j = 2; j*j < i; j++){
// if(i % j == 0) {
// flag = false;
// break;
// }
// }
// if(flag) {
// cout << i;
// break;
// }
// }
}