模拟散列表

拉链法

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100003;//N的值为质数，而且离2的幂越远越好，这样不容易冲突
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 ++;
}

int 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()
{
    memset(h, -1, sizeof h);
    int n;
    cin >> n;
    while(n --)
    {
        char op[2];
        int x;
        cin >> op >> x;
        if(*op == 'I')insert(x);
        else {
            if(find(x))puts("Yes");
            else puts("No");
        }
    }
}

开放寻址法

#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003, nu = 0x3f3f3f3f;//N一般是题目给的2~5倍。
int h[N];
int find(int x)
{
    int k = (x % N + N) % N;
    while(h[k] != nu && h[k] != x)
    {
        k ++;
        if(k == N)k = 0;
    }
    return k;
}
int main()
{
    int n;
    memset(h, 0x3f, sizeof h);
    cin >> n;
   
    while(n --)
    {
        char op[2];
        int x;
        cin >> op >> x;
        int k = find(x);
        if(*op == 'I')
        {
            h[k] = x;
        }
        else if(*op == 'Q'){
            if(h[k] == nu)puts("No");
            
            else puts("Yes");
        }
    }
}