Pit Filling Simulated Hash Table

Title:

The map can also be done. The main thing is to learn how to implement the hash table. In the past March and April, I was crazy to fill the pits to prepare for the test, but I chose Luogu and B station. Now it seems that acwing is better because there are videos.

Zip code

The zipper method is 1-N, and then there is a linked list for each i. It feels very easy to understand. Let's go to the code.

#include #include using namespace std;const int N = 1e5 + 3; // Take the first prime number greater than 1e5, the probability of taking the prime number conflict is the smallest, you can Baidu//* open a slot hint h[N], e[N], ne[N], idx; //adjacency listvoid insert(int x) {// If it is a negative number in c++, its modulo is also negative, so adding N and then %N must be a positive numberint k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx++;}bool find(int x) {//Use the same Hash function above to map x to a number between 0-1e5int 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); //Empty the slot first. The null pointer is generally represented by -1while (n--) {string op;int x;cin >> op >> x;if (op == "I") {insert(x);} else {if (find(x)) {puts("Yes");} else {puts("No");}}}return 0;}

Open Addressing:

#include #include using namespace std;//The open addressing method generally opens 2~3 times the data range, so there is a high probability that there will be no conflictconst int N = 2e5 + 3; //The first prime number greater than the data rangeconst int null = 0x3f3f3f3f; //Specify the null pointer as 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; //If this location is empty, it returns the location where it should be stored}int n;int main() {cin >> n;memset(h, 0x3f, sizeof h); //Specify the null pointer as 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;}