开放寻址法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
    int k = (x % N + N) % N;

    while (h[k] != null && h[k] != x) 
    {
        k++;
        if (k == N) k = 0;
    }

    return k;
}

int main()
{

    int T;
    cin >> T;

    memset(h, 0x3f, sizeof h);

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

        int k = find(x);

        if (op[0] == 'I') h[k] = x; 
        else puts(h[k] == x ? "Yes" : "No");
    }

    return 0;
}

拉链法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100003;

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 find(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()
{
    int T;
    cin >> T;

    memset(h, -1, sizeof h);

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

        if (op[0] == 'I') insert(x);
        else puts(find(x)? "Yes" : "No");
    }

    return 0;
}