拉链法

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N=1e5+3;
int h[N],ne[N],e[N],idx;//h[k]是映射的结果，e[]存储元素 ne[]存储下个地址，idx是指当前移动到哪里了
void insert(int x)
{
    int k=(x%N+N)%N;//+N为了正数
    e[idx]=x;//存下当前值
    ne[idx]=h[k];//指向的下个位置
    h[k]=idx++;
}
int find(int x)
{
    int k=(x%N+N)%N;
    for(int i=h[k];i!=-1;i=ne[i])//链表中寻找
        if(e[i]==x) return 1;
    return 0;
}
int main ()
{
    int n,x;
    cin>>n;
    memset (h,-1,sizeof h);//初始化
    while(n--)
    {
        string op;
        cin>>op>>x;
        if(op=="I") insert(x);
        else if(op=="Q") 
        {
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

开放寻址法

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=2e5+3,null=0x3f3f3f3f;
int h[N];
int find(int x)
{
    int k=(x%N+N)%N;//+N确保正数
    while(h[k]!=null&&h[k]!=x)//有的话，就往下一个找
    {
        k++;
        if(k==N) k=0;
    }
    return k;
}
int main ()
{
    int n,x;
    scanf("%d",&n);
    memset(h,0x3f,sizeof h);//给数组初始化为 0x3f
    while(n--)
    {
        char op[3];
        scanf("%s%d",op,&x);
        int k=find(x);
        if(op[0]=='I') h[k]=x;
        else if(op[0]=='Q'){
            if(h[k]!=null) puts("Yes");
            else puts("No");
        }
    }
}