一、拉链法

一般将质数取成10003(大于10000的第一个质数)
拉链法即领接表，每次将取模获得的位置$t$当做一个领接表中的头结点，将这个值挂到这个$t$头结点的链上

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+3;
int h[N], e[N], ne[N], idx;

void insert(int x)
{
    int t = (x % N + N) % N;  // 获取取模值
    e[idx] = x, ne[idx] = h[t], h[t] = idx ++;  // 将x这个值挂到取模值结点的下面
}
int find(int x)
{
    int t = (x % N + N) % N;  // 获取取模值
    for (int i = h[t]; ~i; i = ne[i])  // 遍历取模值结点下面挂的链表，检查是否有x
        if (e[i] == x) return true;
    return false;
}

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

        if (*op == 'I') insert(x);
        else
        {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

二、开放寻址法

开放寻址法经验上一般将数组开到数据范围的2~3倍
开放寻址法的思想类似《上厕所》，每次取模获得位置$t$，如果位置$t$已经有数了，那么就一直往后找第一个有空位的位置，如果到数组末尾还没有空位就重新从0开始找

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+3, INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], idx;
int find(int x)
{
    int t = (x % N + N) % N;  // 获取取模后的位置
    // 如果是查找x，当h[t]=x的时候就会退出，如果是添加x，那么就会返回第一个空位置添加x
    while (h[t] != INF && 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)] == INF) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

三、字符串哈希