AcWing840.模拟散列表
[题目描述]
维护一个集合，支持如下几种操作：
- “I x”，插入一个数x；
- “Q x”，询问数x是否在集合中出现过；
现在要进行N次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数N，表示操作数量。
接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。
[输出格式]
对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。
每个结果占一行。
[数据范围]
1≤N≤105
−109≤x≤109
[输入样例]：
5
I 1
I 2
I 3
Q 2
Q 5
[输出样例]：
Yes
No
（一）暴力二分，遍历一遍，一种普通的方法。
（二）如果操作数很小，我们可以开个桶来计数。相似地，map数组却能开一个无限制的空间。
#include<bits/stdc++.h>
using namespace std;
map<int,bool>mapp;
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
char s;
long long x;
cin>>s;
scanf("%lld",&x);
if(s=='I')
{
mapp[x]=1;
}
else
{
if(mapp[x]==1)puts("Yes");
else puts("No");
}
}
return 0;
}
（三）哈希表 一种投影的思想
我们要在一个长度为n的随机整数序列A中统计一个数是否出现，可以直接建立一个数组计数（建立一个大小等于值域的数组进行映射和统计，就是简单的Hash思想）。
设计Hash函数为ha（x）=（x mod p）+1，其中p较大。就能把A分成p类。把A[i]定位到h[ha(x)]的链表，然后查找数所在的链表是否包含该数即可，每次操作时间复杂度期望为O(1)，整个算法复杂度优化到O(n)。
#include<bits/stdc++.h>
using namespace std;
const int mod=100010,N=100005;
int h[mod+5],to[N],nex[N],cnt;
void add(int x)
{
int u=(x%mod+mod)%mod; //注意x可能为负数 ，所以u不能直接为x对mod取模
to[++cnt]=x; //在h[u]中加点连边
nex[cnt]=h[u];
h[u]=cnt;
}
bool find(int x)
{
int u=(x%mod+mod)%mod;
for(int i=h[u];i;i=nex[i])
if(to[i]==x)return 1;
return 0;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
char s;
long long x;
cin>>s;
scanf("%lld",&x);
if(s=='I') add(x);
else
{
bool b=find(x);
if(b==1)puts("Yes");
else puts("No");
}
}
return 0;
}