Title Link: Click to view
Title Description:
Maintain a collection and support the following operations:
- I x, insert a number {X;
- 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;
}
Next, we introduce the chain address method. Different from the open addressing method, in case of hash conflict, we no longer continue to address down, but connect a linked list outside the node, and each node in the linked list has the same address after taking the module. The operation is basically the same as that of ordinary single linked list. When connecting the linked list, we use the head insertion method, but here we regard h[k] as the head node of the linked list. See the following code for chain address method.
#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;
e[cur] = x;//Head interpolation method regards h[k] as the head node of a single linked list
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;
}