维护一个集合，支持如下几种操作：
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, 2*k, 3*k, …, m*k}，缩小了k倍。可以明显看出，在模和关键字有公因数的情况下，模后取值范围减少，冲突概率增加，尤其是关键字是等差数列。而模为质数就不会出现这种情况。//
离二的整次幂尽可能远是因为防止取模时高位被截断，因为二进制数据对2的k次方取模相当于只要这个数的后k位，高位被截断后，取模的冲突概率就会大。
因为范围是（1e-9~1e9),为了取模为正数
int t = (x % N + N) % N;
插入操作和单链表里头结点的一样，把h[k]，看成头结点，往下拉链（如果理解不了idx和和h[k]的关系，可以去看单链表）。
#include#include 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个坑位开始找，如果没人，那他不在；如果有人，打开看看是不是他，这时候如果是他，他就在，如果不是他，他就不在。
#include#include 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("Non"); else printf("Yesn"); } } return 0; }
