这里个大家用数组来模拟哈希表
法一:拉链法
法二:开放寻址法
/* * Project: 11_哈希表 * File Created:Sunday, January 17th 2021, 2:11:23 pm * Author: Bug-Free * Problem:AcWing 840. 模拟散列表 拉链法 */ #include#include 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#include using namespace std; //开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了 const int N = 2e5 + 3; //大于数据范围的第一个质数 const int null = 0x3f3f3f3f; //规定空指针为 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 n; int main() { cin >> n; memset(h, 0x3f, sizeof h); //规定空指针为 0x3f3f3f3f while (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; }