开放寻址法

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

using namespace std;

const int N = 2e5+3, null = 0x3f3f3f3f;     //N一般取大于数据范围两三倍的第一个质数
int h[N];   //哈希表

//开放寻址法
int find(int x)
{
    int t = (x % N + N) % N;    //负数求余后还是负数，这样保证t一定为正数
    while ( h[t] != null && h[t] != x )     //寻找坑位，如果当前位置已经有数，就往后找
    {
        t ++;           
        if ( t == N ) t = 0;    //找到头儿之后重新开始
    }
    return t;       //返回应该存放的位置
}

int main()
{
    memset(h, 0x3f, sizeof h);
    int T;
    cin >> T;
    while ( T -- )
    {
        char op[2];
        int x;
        cin >> op >> x;
        if ( op[0] == 'I' ) h[find(x)] = x;
        else
        {
            if ( h[find(x)] == null ) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

拉链法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5+10;

int h[N], e[N], ne[N], idx;

void add(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] )    //遍历以k为余数的链表
        if ( e[i] == x ) return true;           //如果找到x，返回true
    return false;       //说明没找到
}

int main()
{
    int T;
    cin >> T;
    memset(h, -1, sizeof h);    //一定记得初始化
    while ( T -- )
    {
        char op[2];
        int x;
        cin >> op >> x;
        if ( op[0] == 'I' ) add(x);
        else
        {
            if ( !find(x) ) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}