题目描述
维护一个集合,支持如下几种操作:
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
哈希表是把复杂的数据结构映射到0~n的一种数据结构。
例如插入数据范围是1e-9~1e9,查询操作和输出范围为1e5;(一般很少删除操作,如果删除就是另开一个数组,用用bool变量打一个标记。)
x mod 10e5 属于范围(0,1e5);
冲突;把两个不一样的数映射到同一个数上。
处理冲突的方法有两种:
拉链法
开放寻址法
算法1
拉链法
开一个一维数组储存所有的哈希值,在每个槽拉一条单链表储存映射在这个位置上的所有数。
x mod N
N要取成质数,而且要离二的整次幂尽可能远,这样冲突概率最小。
质数是因为取成N等差数列时可以回避冲突。(这部分参考CSDM作者NeyoShinado)
首先来说假如关键字是随机分布的,那么无所谓一定要模质数。但在实际中往往关键字有某种规律,例如大量的等差数列,那么公差和模数不互质的时候发生碰撞的概率会变大,而用质数就可以很大程度上回避这个问题。
考虑模是合数的情况:假设N = kn, M = km, N和M存在最大公因数k,此时可以将N % M = r转化为公式N = Mq + r,即kn = kmq + r。其中q是商,r是余数。“表面上”r的取值范围是{0, 1, 2, …, M-1}(忽视了只有N与M最大公因数为1时,才能取整个余数集合R的定理),一片和谐。但是可以对公式进行稍微的变换,n = mq + (r/k),由于n和mq都是整数,则(r/k)也是整数。此时我们看一看到(r/k)的取值范围是{0, 1, 2, …, m} = {0, 1, 2, …, M/k}。恢复到原式,也是就r的“实际”取值范围是{0, k, 2k, 3k, …, m*k},缩小了k倍。
可以明显看出,在模和关键字有公因数的情况下,模后取值范围减少,冲突概率增加,尤其是关键字是等差数列。而模为质数就不会出现这种情况。
离二的整次幂尽可能远是因为防止取模时高位被截断,因为二进制数据对2的k次方取模相当于只要这个数的后k位,高位被截断后,取模的冲突概率就会大。
因为范围是(1e-9~1e9),为了取模为正数
int t = (x % N + N) % N;
插入操作和单链表里头结点的一样,把h[k],看成头结点,往下拉链(如果理解不了idx和和h[k]的关系,可以去看单链表)。
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 3;
int 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 ++;
}
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;
scanf("%d", &n);
memset(h, -1, sizeof h);
while (n --)
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') insert(x);
else
{
if (find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
算法2
开放寻址法
可以想成蹲坑法。
对于冲突,只开一个一维数组,要开到1e5的2到三倍确保不会撞车。
插入:首先取模找到位置k,然后一个个坑位找下去,有人就去下一个,直到找到空坑位就蹲下。
查找:从第k个坑位开始找,如果没人,那他不在;如果有人,打开看看是不是他,这时候如果是他,他就在,如果不是他,他就不在。
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 3, null = 0x3f3f3f3f;
int h[N];
int find(int x)
{
int t = (x % N + N) % N;
while(h[t] != null && h[t] != x)
{
t ++;
if(t == N) t = 0;//如果没位置它就会死循环
}
return t;
}
int main()
{
int n;
scanf("%d", &n);
memset(h, 0x3f, sizeof h);
while(n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') h[find(x)] = x;
else
{
if(h[find(x)] == null) printf("No\n");
else printf("Yes\n");
}
}
return 0;
}