关键

理解两种哈希表的实现方法：
1拉链法：
纵向存储
2开放寻址法：
横向存储

二者本质都是利用映射的方法 利用空间省时间

算法1 拉链法

参考文献

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;
const int N = 100003;
int n;
int h[N],e[N],ne[N],idx;  //把每一个h[k]看成一个表头，链式存储，类似邻接表

void insert(int x){
    int k = (x % N + N) % N; //k为哈希值 并且防止取模得到负数

    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++;
}

void query(int x){
    int k = (x % N + N) % N;
    int flag = 0;
    for(int i = h[k]; i != -1; i = ne[i]){
        if(e[i] == x) flag = 1;
    }
    if(flag == 1) printf("Yes\n");
    else printf("No\n");
}

int main(){
    int n;
    memset(h,-1,sizeof h);
    cin >> n;
    while(n --){
        char op[2];
        scanf("%s",op);
        if(op[0] == 'I'){
            int x;
            cin >> x;
            insert(x); 
        }
        else if(op[0] == 'Q'){
            int x;
            cin >> x;
            query(x);
        }
    }
    return 0;
}

算法2 开放地址法

参考文献 关于0x3f

https://blog.csdn.net/tcherry/article/details/37606277

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;
const int N = 200003, null = 0x3f3f3f3f; 
int n;
int h[N];

int query(int x){
    int k = (x % N + N) % N;
    while(h[k] != null && h[k] != x){
        k ++;
        if(k == N){
            k = 0;
        }
    }
    return k;
}

int main(){
    int n;
    memset(h,0x3f,sizeof h);
    cin >> n;
    while(n --){
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(op[0] == 'I'){
            h[query(x)] = x;
        }
        else if(op[0] == 'Q'){
            if(h[query(x)] == null){
                printf("No\n");
            }
            else{
                printf("Yes\n");
            }
        }
    }
    return 0;
}

总结

个人感觉拉链法的思路更易懂。。。