22. 散列表

原题链接

• 开放寻址法(常用)

//开大于题中给定空间2倍大的质数

填表：如果当前坑位有人，就继续往后面的坑位找，如果当前坑位没人，说明该数值在hash表中不存在，如果到N了，就把k重新置为0

返回的k的含义：如果x在哈希表中的话，k就是我们x的下标，如果x不在hash表中的话，k就是x在hash表中应该存储的位置

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
const int N=200003;
const int INF=0x3f3f3f3f;
int h[N];
int Find(int x)
{
    int k=(x%N+N)%N;
    while(h[k]!=INF&&h[k]!=x)
    {
        k++;
        if(k==N) k=0;
    }
    return k;
}
int main()
{
    int n;
    scanf("%d",&n);
    memset(h,0x3f,sizeof(h));
    for(int i=0;i<n;i++)
    {
        char s[5];
        int x;
        scanf("%s%d",s,&x);
        int k=Find(x);
        if(s[0]=='I') h[k]=x;
        else if(s[0]=='Q')
        {
            if(h[k]!=INF)
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }
    return 0;
}

• 拉链法

//开比题中所给空间大一倍的质数

当产生冲突的时候，每个数值都可以存下来，存在一条链子中

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
const int N=100003;
int ne[N],e[N],idx,h[N];
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;i=ne[i])
    {
        if(e[i]==x)
            return true;
    }
    return false;
}
int main()
{
    int n;
    scanf("%d",&n);
    memset(h,-1,sizeof(h));
    for(int i=0;i<n;i++)
    {
        char s[5];
        int x;
        scanf("%s%d",s,&x);
        if(s[0]=='I')
            Insert(x);
        else if(s[0]=='Q')
        {
            if(Find(x))
            cout<<"Yes"<<endl;
            else
            cout<<"No"<<endl;
        }
    }
    return 0;
}