拉链法

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1E5 + 10;
const int MOD = 100003;
int h[N], e[N], ne[N], idx;
void insert(int x){
    int t = ((x % MOD) + MOD) % MOD;
    e[idx] = x;
    ne[idx] = h[t];
    h[t] = idx ++ ;
}
bool query(int x){
    int t = ((x % MOD) + MOD) % MOD;
    for(int i = h[t]; i != -1; i = ne[i]){
        if(e[i] == x)   return true;
    }
    return false;
}
int main(){
    int n;  cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 0; i < n; i ++ ){
        string op;  
        int x;  cin >> op >> x;
        if(op[0] == 'I')    insert(x);
        else    cout << (query(x) ? "Yes" : "No") << endl;
    }
    return 0;
}

开放寻址法

#include <iostream>
#include <cstring>
#include <cstdio>
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 n;  scanf("%d", &n);
    memset(h, null, sizeof h);
    while(n -- ){
        char op[5];
        int num;    scanf("%s%d", op, &num);
        int k = find(num);
        if(op[0] == 'I')    h[k] = num;
        else    cout << (h[k] == null ? "No" : "Yes") << endl;
    }
    return 0;
}