拉链法

// #include <iostream>
// #include <algorithm>
// #include <cstring>

// using namespace std;
// const int N = 1e5 + 10;
// int n;
// int h[N];
// int e[N], ne[N], idx;

// void insert(int x)
// {
//     int k = (x % N + N) % N;//如果x是负数， x % N 可能为负数
//     e[idx] = x;
//     ne[idx] = h[k];
//     h[k] = idx;
//     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()
// {
//     cin >> n;
//     memset(h, -1, sizeof h);

//     while(n --)
//     {
//         char op;
//         cin >> op;
//         int x;
//         cin >> x;

//         if(op == 'I')
//         {
//             insert(x);
//         }
//         else 
//         {
//             if(find(x))  cout << "Yes" << endl;
//             else cout << "No" << endl;      
//         }
//     }
//     return 0;
// }

###开放寻址法

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 200003, null = 0x3f3f3f3f;
int h[N];

int find(int x)//如果x在哈希表中存在，返回在表中的位置，若不存在返回应该存放的位置
{
    int k = ((x % N) + N) % N;//目的是让余数变成正数
    while(h[k] != null && h[k] != x)
    {
        k ++;
        if(k == N) k = 0;//如果已经看到了最后一个坑位，返回第一个坑位找
    }

    return k;// k 的两种含义，x的位置或者x应该存放的位置
}

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

    while(n -- )
    {
        char op;
        int x;
        cin >> op >> x;
        if(op == 'I')
        {
            int k = find(x);
            h[k] = x;
        }
        else
        {
            if(h[find(x)] != null) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    return 0;
}