题目描述

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

“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

需要散列化的数据特征：数据涉及范围远大于数据个数

求N:第一个大于i的质数的方法

#include<bits/stdc++.h>
using namespace std;

int main()
{
    for(int i=100000;;i++)
    {
        bool flag=true;
        for(int j=2;j*j<=i;j++)
        {
            if(i%j==0)
            {
                flag=false;
                break;
            }
        }
        if(flag)
        {
            cout<<i;
            break;
        }
    }
    return 0;
}

算法1

拉链法

N：质数，且距离二的整次方很远
拉链法：将数据值通过N映射到散列表的下标值，如果该位置重复，则向下延伸散列表
idx的用处： 连接一个结构体的数据域和指针域
能够通过第几个插入的数找到该数的值

#include<bits/stdc++.h>
using namespace std;
const int N=100003;
int h[N],e[N],ne[N],idx;
//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;
    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;
    cin>>n;
    memset(h,-1,sizeof(h));
    while(n--)
    {
        string op;
        int x;
        cin>>op>>x;
        if(op=="I")insert(x);
        else{
            if(find(x))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
} 

算法2

开放寻址法

N：质数，数据个数的二倍
开放寻址法：先将数据域初始化为0x3f，即数据值达不到的值
find函数从下标k开始向后找，若找不到则返回该插入的位置

#include<bits/stdc++.h>
using namespace std;
const int N=200003,null=0x3f3f3f3f;
int h[N];
int find(int x)
{
    int t=(x%N+N)%N;
    while(h[t]!=null&&h[t]!=x)//该位置已经有数且改值不是x，则继续遍历
    {
        t++;
        if(t==N)t=0;
    }
    return t;
}
int main()
{

    int n;
    cin>>n;
    memset(h,0x3f,sizeof(h));
    while(n--)
    {
        string op;
        int x;
        cin>>op>>x;
        if(op=="I")
        {
            h[find(x)]=x;
        }
        else
        {
            if(h[find(x)]!=null)
            cout<<"Yes"<<endl;
            else
            cout<<"No"<<endl;
        }
    }
    return 0;
}