# AcWing 840. Simulated hash table (two methods to solve hash conflict --- open addressing method and chain address method)

Title Description:

Maintain a collection and support the following operations:

1. I x, insert a number {X;
2. Q x, ask whether the number ＾ x ＾ has appeared in the set;

Now you need to perform N # operations and output the corresponding results for each query operation.

Input / output format:

input

The first line contains the integer N, which indicates the number of operations.

Next, N ， lines, each line contains an operation instruction, and the operation instruction is one of ， I x, Q x ，.

output

For each query instruction Q x, output a query result. If Q x \\\\\\\\\.

One line for each result.

Input and output examples:

input

5
I 1
I 2
I 3
Q 2
Q 5

output

Yes
No

Topic analysis:

Hash table (also known as hash table) is a data structure accessed directly according to the key value. This is Baidu's definition of hash table. In fact, the main purpose of hash table is to map a discrete point in a large range to a small range (is it a bit like discretization? But discretization needs to maintain order, but hash table does not). So how to map? We take the form of module here, that is, the larger data range% the smaller data range, so as to ensure that the result does not exceed the smaller data range. Of course, the addresses of different points may conflict during mapping (the same result can be obtained by modulo). Here, we can take two ways to solve hash conflict ---------- open addressing method and chain address method.

Let's first introduce the open addressing method. Its main idea is that if the current address has been occupied (hash conflict occurs), continue to look down for the subscript until the address (subscript) has not been occupied before. Here, we define a find function to return the subscript of the number x in the hash table. In find, first use t = (x% N + n)% N, which is to convert the remainder into a positive number considering that x is a negative number. At the same time, we need a ruler to judge whether the current subscript has been used. For example, define null = 0x3f3f3f3f (greater than the left and right ends of a wide range of intervals), and initialize h to 0x3f3f3f3f. So, if h[t]= Null indicates that it has been occupied, then t + + goes to find the next address. Of course, if the number x has been saved in the hash table before, there is no need to address it. In particular, if t == N, we reach the array boundary, let t = 0, and then look for it from the beginning. See the following code for the open addressing method.

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N = 2e6 + 7, null = 0x3f3f3f3f;
int h[N];//The length of the array is generally 2-3 times of the upper limit of the number.
int find(int x) {//The find function is used to find the mapped address
int t = (x % N + N) % N;//Combine the modulo of positive and negative numbers
while (h[t] != null && h[t] != x) {//If h[t] is not equal to null and h[t] is not mapped to the number x, it indicates that the position of T has been used by other numbers before
t ++ ;                        // Look for the next address
if (t == N) t = 0;//If t reaches the boundary of the interval, search from 0
}
return t;
}
int main() {
memset(h, 0x3f, sizeof(h));//memset is initialized by bytes. There are four bytes in int. initializing to 0x3f means initializing each byte to 0x3f, so each int is 0x3f3f3f3f.
int n;
cin >> n;
while (n -- ) {
char op;
int x;
cin >> op >> x;
if (op == 'I') h[find(x)] = x;
else {
if (h[find(x)] == null) cout << "No" << endl;
else cout << "Yes" << endl;
}
}
return 0;
}
```

```#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5 + 7;
int h[N], e[N], ne[N], cur;//cur indicates the node subscript that has been used currently
void insert(int x) {
int t = (x % N + N) % N;
ne[cur] = h[k];
h[k] = cur ++ ;
}
bool find(int x) {
int t = (x % N + N) % N;//The ne field at the end of the linked list is defined as 1
for (int i = h[k]; i != -1; i = ne[i]) {
if (e[i] == x) {
return true;
}
}
return false;
}
int main() {
int n;
cin >> n;
memset(h, -1, sizeof(h));
while (n -- ) {
char op;
int x;
cin >> op >> x;
if (op == 'I') insert(x);
else  cout << (find(x) ? "Yes" : "No") << endl;
}
return 0;
} ```

-------------------------------------------------------------------------------

Here we give the templates of two methods

``` open addressing
int h[N];

// If x is in the hash table, the subscript of X is returned; If x is not in the hash table, return the position where x should be inserted
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;
}```

``` Zipper method
int h[N], e[N], ne[N], idx;

// Inserts a number into the hash table
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}

// Query whether a number exists in the hash table
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;

return false;
}
```