模拟散列表

题目

维护一个集合，支持如下几种操作：

“I x”，插入一个数x；
“Q x”，询问数x是否在集合中出现过；

现在要进行N次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数N，表示操作数量。接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。
输出格式
对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。
每个结果占一行。
数据范围

1≤N≤10^5
−10 ^ 9≤x≤10 ^ 9

输入样例：
5
I 1
I 2
I 3
Q 2
Q 5
输出样例：
Yes
No

分析

这个题有很多方式可以做，可以用哈希，也可以用c++的STL

哈希

开放寻址法

首先数组要开到题目要求的两倍，并且还要是一个质数，因为题目中的数据范围是-10 ^ 9到10 ^9次方，所以，可以找一个不是这个区间的数字作为标记，代表这个位置上没有存放数字，这里用的是0x3f3f3f3f。

#include<iostream>
#include<cstring>
using namespace std;
int aa[200003];
const int mod=200003;
const int off=0x3f3f3f3f;
int find(int a)
{  //x表示a如果没有冲突的话应该存在那个位置上
    int x=(a%mod+mod)%mod;  //x可能是负数，取模之后还是负数
    while(aa[x]!=off&&aa[x]!=a)
    {  //如果这个位置上不等于off(表示这个位置上已经有数字了)并且这个数字不是a
        x++;  //就去寻找下一个位置
        if(x==mod) x=0;
    }
    return x;
}  //如果数组中已经有a就返回a所在的数组下标，如果没有就返回a应该在那个位置上
int main()
{
    int n;
    cin>>n;
    memset(aa,0x3f,sizeof aa);
    while(n--)
    {
       string s;int a;
       cin>>s>>a;
       if(s=="I") aa[find(a)]=a;
       else if(s=="Q")
       {
           if(aa[find(a)]==a) cout<<"Yes"<<endl;
           else cout<<"No"<<endl;
       }
    }
    return 0;
}

拉链法

拉链法就是在数组每个位置上延申出一条链，有点类似于存图时用的邻接表

#include<iostream>
#include<cstring>
using namespace std;
const int N=100003;
int h[N],e[N],ne[N],idx;

void add(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 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(h,-1,sizeof h);
    int n;
    cin>>n;
    while(n--)
    {
        string s;int a;
        cin>>s>>a;
        if(s=="I") add(a);
        else if(s=="Q")
        {
            if(find(a)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

c++ STL

这个题如果用STL的话，可以用set，map。这些都是可以做出来的

#include<iostream>
#include<cstring>
#include<set>
using namespace std;
set<int> st;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;int a;
        cin>>s>>a;
        if(s=="I") st.insert(a);
        else if(s=="Q") 
        {
            if(st.count(a)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}