AcWing 840. 模拟散列表（模板）

题目链接：点击这里


（1）拉链法

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

using namespace std;
const int N = 100003;       //大于100000的第一个质数

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

（2）开放寻址法

数组要开题目数据范围的 $2 \sim 3$2∼3 倍

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

using namespace std;
const int N = 200003;       //大于200000的第一个质数
const int null = 0x3f3f3f3f;
int h[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
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, 0x3f, sizeof(h));
    
    while(n--)
    {
        char op[2];
        int x;
        
        scanf("%s%d", op, &x);
        
        int k = find(x);
        if(*op=='I')
        {
            h[k] = x;
        }
        else if(*op=='Q')
        {
            if(h[k] != null)   puts("Yes");
            else    puts("No");
        }
    }
    
    return 0;
}