数据结构哈希表

这里个大家用数组来模拟哈希表

法一：拉链法

法二：开放寻址法

/** Project: 11_哈希表* File Created:Sunday, January 17th 2021, 2:11:23 pm* Author: Bug-Free* Problem:AcWing 840. 模拟散列表 拉链法*/
#include <cstring>
#include <iostream>using namespace std;const int N = 1e5 + 3;  // 取大于1e5的第一个质数，取质数冲突的概率最小 可以百度//* 开一个槽 h
int h[N], e[N], ne[N], idx;  //邻接表void insert(int x) {// c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx++;
}bool find(int x) {//用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数int k = (x % N + N) % N;for (int i = h[k]; i != -1; i = ne[i]) {if (e[i] == x) {return true;}}return false;
}int n;int main() {cin >> n;memset(h, -1, sizeof h);  //将槽先清空 空指针一般用 -1 来表示while (n--) {string op;int x;cin >> op >> x;if (op == "I") {insert(x);} else {if (find(x)) {puts("Yes");} else {puts("No");}}}return 0;
}

/** Project: 11_哈希表* File Created:Sunday, January 17th 2021, 4:39:01 pm* Author: Bug-Free* Problem:AcWing 840. 模拟散列表  开放寻址法*/
#include <cstring>
#include <iostream>using namespace std;//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 2e5 + 3;        //大于数据范围的第一个质数
const int null = 0x3f3f3f3f;  //规定空指针为 null 0x3f3f3f3fint 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 n;int main() {cin >> n;memset(h, 0x3f, sizeof h);  //规定空指针为 0x3f3f3f3fwhile (n--) {string op;int x;cin >> op >> x;if (op == "I") {h[find(x)] = x;} else {if (h[find(x)] == null) {puts("No");} else {puts("Yes");}}}return 0;
}