拉链法

#include<bits/stdc++.h>
using namespace std;
const int N=100003;//本题数据范围是1e5，所以开一个N=大于1e5的第一个素数就可以了
//素数可以最大的避免冲突的概率
int h[N],e[N],ne[N],idx;
void insert(int x)
{
    int k=(x%N+N)%N;
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx++;
}
bool query(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;
}
int main()
{
    memset(h,-1,sizeof h);
    int n;
    cin>>n;
    while(n--)
    {
        char x;
        int a;
        cin>>x>>a;
        if(x=='I')
        {
            insert(a);
        }
        else
        {
            if(query(a))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

开放寻址法

这个方法你可能有疑问，为什么开放寻址法能比一个一个找要快呢？因为按照经验，素数本身就可以最大的避免冲突，然后我们只需要在（x%N+N）%N的位置往后两三个之内就可以找得到我们要找的数了

#include<bits/stdc++.h>
using namespace std;
const int N=200003;//开放寻址法避免冲突的方法就是多开点坑位，挤了就往下一个坑位去，所以我们就用一个
//比要存的数据量的两倍还要多的一个素数来作为槽就可以了。
//素数可以最大的避免冲突的概率
int h[N];
int null=0x4f4f4f4f;//规定空指针为 null 0x3f3f3f3f
int find(int x)
{
    int k=(x%N+N)%N;
    while(h[k]!=null&&h[k]!=x)
    {
        k++;//会一直走到空位或x待着的位置
        if(k>N)
            k=0;
    }
    return k;//如果这个位置是空的, 则返回的是他应该存储的位置
}
int main()
{
    memset(h,0x4f,sizeof h);//memset比for一个一个定义的要快一点几倍,把h全部定义为0x4f4f4f4f,大概1.3e9
    //这里因为我们要一个数据范围之外的数来表示空，所以我们需要一个比1e9大的常数作为null
    int n;
    cin>>n;
    while(n--)
    {
        char x;
        int a;
        cin>>x>>a;
        if(x=='I')h[find(a)]=a;
        else
        {
            if(h[find(a)]==a)cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}