哈希表是一种非常带劲的存储方法，它将一定个数内的数据以一种降低数据规模的方式存储着，哈希表的主要操作就是添加数据和查找数据，当然你也可以用标记来标记数据是否被删除（实际上，它只是被你标记删除了，并未被实际删除并释放内存）

上模板题让我们直观感受下：
Acwing840 传送门 ： https://www.acwing.com/problem/content/842/

这题就让我们实现了哈希表的存储和查找：

比较好用的两种方法： 拉链法和 开放寻址法

1.拉链法

一个节点上存储着 取模后位置相同的数据，由于存储位置相同，为避免矛盾，采用拉链法将其以拉链形式展开存储

首先创建存储位置的数组，这个数组的每个元素作为拉链的头结点，即每个元素都作为一个单链表的头结点，之后按照数据的模后存储位置存储单链表的数据即可

如图所示：

觉得图的大小不合适的同学可以右击打开图片链接

2. 开放寻址法

为了避免查找时的寻找次数过多，一般数组大小为题目所给数据范围的2~3倍，且数组大小尽量设置为质数减少冲突。

主要思路就是如果数据取模后的位置未被占用，那么就直接将该数据存储着该位置，如果已被占用，则往后寻找直至找到一个未被占用的位置。

这里直接上代码：

Acwing840

#include<stdio.h>
#include<string.h>

const int null = 0x3f3f3f3f;
const int N = 200003; //开为题目数据范围的2倍

int h[N]; //存储的值


void init(){
    memset(h, 0x3f, sizeof(h));
}

//插入值和查找值只需一个函数
int find(int x){
    int k = ((x % N) + N) % N;
    while(h[k] != null && h[k] != x){ //当这个位置被占用了，且x未被存储
        k++;
        if(k == N) k = 0; //如果到了最后一个位置，就返回初位置再开始寻找
    }
    return k;
}

int main(){

    init();

    int n;
    scanf("%d", &n);

    while(n--){
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        if(op[0] == 'I'){            
            int k = find(x);
            h[k] = x;
        }   

        else if(op[0] == 'Q'){
            if(h[find(x)] == null) puts("No"); 
            else puts("Yes");
        }
    }

    return 0;
}