题目描述

模拟散列表

哈希函数：使得从-10^9~10^9中任取一个数映射到0~10^5中

算法1

(拉链法)

由一个一维数组和于其中每个数对应的单链表组成

利用单链表，而单链表中存储的是自变量x;因为定义域的范围比值域大得多，所以会有多对一的情况

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=100003;
int h[N],e[N],ne[N],idx;
void insert(int x)
{
    int k=(x%N+N)%N; //构建的哈希函数（因为在c++中负数的余数是负数，所以要在取模后+N）
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx++;
}
bool find(int x)
{
    int k=(x%N+N)%N;

    //原哈希表中的槽（一维数组）存储的因变量相当于单链表的头节点
    //h[k]就指的是第一个节点的下标,ne[i]指的是i的下一个坐标,当i指向空节点时结束(值为-1)
    for(int i=h[k];i!=-1;i=ne[i])
    {
        if(e[i]==x)return true;
    }
    return false;
}
int main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof(h));       //将原来的单链表全部初始化为-1，作为循环终止的判定条件
    while(n--)
    {
        char op[2];             //字符串输入，在用scanf时可以自动忽略其中的空格等，比较方便
        int x;
        scanf("%s%d",op,&x);
        if(*op=='I')insert(x);
        else 
        {
            if(find(x))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

算法2

(开放寻址法)

开放寻址法中只需要一个一维数组，h[k]k表示因变量，h[k]的值表示自变量

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=200003,null=0x3f3f3f3f; //无穷大的值且不超过32-bit
int h[N];           //开放寻址法中只需要有一个一维数组来存放自变量

int find(int x)
{
    int k=(x%N+N)%N;         //x的位置
    while(h[k]!=null&&h[k]!=x)
    {
        k++;
        if(k==N)k=0;      k已经将当前位置及以后查找完，将k赋值为1，从头开始循环
    }
    return k;
}
int main()
{
    int n;
    cin>>n;
    memset(h,0x3f,sizeof(h));       //将h一维数组中所有值初始化为无穷大
    while(n--)
    {
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        int k=find(x);
        if(*op=='I')h[k]=x;      //插入，将因变量为k时的自变量插入
        else 
        {
            if(h[k]!=null)cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}