哈希表又称散列表 在c++中 unordered_map 便是哈希表的应用实现 可以做到查找元素近乎o(1)的时间复杂度 常用的方法有 拉链法 开放寻执法
哈希表的使用存在着哈希冲突 即不同的值映射到了同一个位置 可想像成一个人拥有着两个手机号 但是一个是废弃的 两个手机号都指向了同一个人
为减少哈希冲突 对数据取模的时候 最好选择质数 可以降低哈希冲突 实现如下：

拉链法：

//模拟哈希表 拉链法：单链表的使用 开放寻址法： 将范围相应的扩大一部分找临近位置
//存在哈希冲突 为减少冲突 找要求范围的质数
#include<iostream>
using namespace std;
const int N=1e5+3;
int q[N],e[N],ne[N]; //单链表一样配置
int idx=1;
//哈希表映射 将一个大范围的数据映射到一个较小的空间内
void insert(int x)
{
    int k=(x%N+N)%N; //c++中的模仍是负数 这是将负数的模也能正确的映射
    e[idx]=x,ne[idx]=q[k],q[k]=idx++;
}

bool find(int x)
{
    int k=(x%N+N)%N;
    for(int i=q[k];i!=0;i=ne[i])
    if(e[i]==x)
    return true;
    return false;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char op[2];
        int x;
        cin>>op>>x;
        if(*op=='I') insert(x);
        else
        if(find(x)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

开放寻址法:

把映射的大小适当放大两杯或者三倍 当找到这个位置后如果已经被占用则看下一个位置是否被占用

#include <cstring>
#include <iostream>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int 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;
}

int main()
{
    memset(h, 0x3f, sizeof h);

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

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}