题面：
维护一个集合，支持如下几种操作：
I x，插入一个整数 \(x\)；Q x，询问整数 \(x\) 是否在集合中出现过现在要进行 \(N\) 次操作，对于每个询问操作输出对应的结果。
哈希表[1]
基本概念
哈希表也叫散列表，通过将键映射到索引位置（在关键字和位置之间建立对应关系）来实现高效的查找操作。
记作 \(Loc(i)=Hash(key_i)\) 。
时间复杂度：\(O(1)\)
无论哈希表中有多少条数据，其插入和查找操作的时间复杂度都恒定。
因为哈希表的查找速度非常快，所以在很多程序中都有使用哈希表，例如拼音检查器。
基本思想：转换思想，通过哈希函数将非int的键或者关键字转换成int数组下标。
注意：并不是每个元素都需要通过哈希函数来将其转换成数组下标，有些可以直接作为数组的下标。
缺点：基于数组，空间效率较低，扩容成本较高；
当哈希表被填满时，会造成比较严重的性能下降。
索引存储和散列存储的区别：散列存储多了 \(hash\) 函数运算的过程，用于节省空间。
举例：用哈希表来存放班级里面学生信息
利用学号作为关键字时，因为数据类型为int，可以同时作为数据下标，不需要通过哈希函数进行转化；
但如果需要将姓名作为关键字，就需要哈希函数完成键值的重映射。
常见的哈希函数[2]
构造准则：简单、均匀、冲突最小
构造哈希函数的目标是使得到的 \(n\) 个元素的哈希地址尽可能均匀地分布在 \(m\) 个连续内存单元地址上，同时使计算过程尽可能简单以达到尽可能高的时间效率[3]。
1. 线性定址法
直接取关键字的某个线性函数作为存储地址：\(Hash(key)=a×key+b\)
其中 \(a\) 和 \(b\) 为常数，这种哈希函数叫做自身函数。当 \(a=1\)，\(b=0\) 时，\(H(key)=key\)
优点：直接定址所得地址集合和关键字集合的大小相同；对于不同的关键字不会产生冲突。
缺点：空间效率低，占用连续地址空间，需要提前确定关键字的取值范围，且不能太大。
举例：有一个从1岁到100岁的人口统计表，其中，年龄作为关键字，哈希函数取其自身，即哈希函数为 \(H(key)= key\)。这样，若要询问25岁的人有多少，则只要查表中地址为25的桶即可。
2. 除留余数法
将关键字对某一小于散列表长度的数 \(p\) (\(p<a.length\)) 取余的结果作为存储地址：\(Hash(key)=key\%p\)
最简单，也最常用。不仅可以对关键字直接取模，也可在对关键字进行折迭、平方取中等运算之后取模。
对 \(p\) 的选择很重要，一般情况下选 \(p\) 为质数或不包含小于 \(20\) 的质因素的合数。
3. 数字分析法
取某关键字的某几位组合成哈希地址。
假设已经知道哈希表中所有的关键字值，而且关键字值都是数字；
所选的位应当是：各种符号在该位上出现的频率大致相同。
举例：有1000个记录，关键字为10位十进制整数\(x_1、x_2…x_{10}\)，如哈希表长度为2000。
假设经过分析，各关键字中 \(x_3\)、\(x_5\) 和 \(x_7\) 的取值分布近似随机，则可取哈希函数为：\(h(key)=h(x_1、x_2…x_{10})=x_3x_5x_7\)。
例如，\(h(3778597189)=757\)，\(h(9166372560)=632\)。
4. 平方取中法
对关键字取平方，然后将得到结果的中间几位作为存储地址；
当无法确定关键字中哪几位分布较均匀时，先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。
特点：通过平方扩大差别，另外，中间几位与关键字中的每一位都相关，故不同关键字会以较高的概率产生不同的、均匀的哈希地址。
5. 折叠法
将关键字自左到右分成位数相等的几部分，最后一部分可以短些；
然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
适用于：每一位上各符号出现概率大致相同的情况。
举例：根据国际标准图书编号（ISBN）建立一个哈希表。
如一个国际标准图书编号 \(0-442-20586-4\) 的哈希地址为：
- 移位法：将各部分的最后一位对齐相加；
使用移位叠加 \(5864 +4220+04 =1 0088\)，故\(H(0-442-20586-4)= 0088\)（将分割后的每一部分的最低位对齐）。 - 间界叠加法：从一端向另一端沿分割界来回折叠后,最后一位对齐相加。
使用边界叠加法叠加 \(5864 +0224+04 =6092\)，故\(H(0-442-20586-4)= 6092\)（从一端向另一端沿分割界来回叠加）。
6. 随机数法
取关键字的随机函数值为它的哈希地址，即 \(H(key) = random (key)\)，
其中 \(random\) 为伪随机函数。
适用于：关键字长度不等
哈希冲突与处理方法
哈希冲突：元素关键字不同，但具有相同哈希地址，键值不再一一对应。
一般来说，哈希冲突很难避免。为了解决这个问题，需要找到新的尚未被占用的地址来存储该元素。
拉链法
将所有的冲突元素用单链表连接起来，每个链表对应一个单元；
此时，每个单元存储的不再是元素本身，而是相应单链表的头指针。
思路类似于：邻接表
基于取模法的哈希函数：(x % N + N) % N
通常情况下，我们希望哈希函数的输出值处于 \([0,N-1]\) 的范围内，其中 \(N\) 是哈希表的大小。
而转换前的键值范围例如 \([10^{-9},10^9]\)，可能存在负数。
为了解决这个问题，可以利用取模运算的性质：如果 \(a\) 和 \(b\) 都是整数，且 \(a\) 除以 \(b\) 得到的商为 \(q\)，余数为 \(r\)，则有 \(a = q * b + r\)。根据这个性质，我们可以将负数的取模运算转化为一个正数的取模运算。
单链表的建立：AcWing 826. 单链表 - 蒟蒻爬行中
此处插入操作选用头插法，链表头指针即存储在哈希表中。
#include<bits/stdc++.h>
using namespace std;
const int N = 100003; //从100000开始的第一个素数
int n, x;
int h[N], e[N], ne[N], idx;
/* 构建哈希函数：取模法 */
int hashF(int x) {
return (x % N + N) % N; //索引值
}
/* 拉链法的插入操作 */
void insert(int x) {
int k = hashF(x);
e[idx] = x; //数据数组
ne[idx] = h[k]; //指针数组
h[k] = idx++; //哈希数组
}
/* 拉链法的查找操作 */
bool find(int x) {
int k = hashF(x);
//先找到索引值，再从该单元链表头开始查找
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}
int main()
{
cin >> n;
memset(h, -1, sizeof h); //空指针一般用-1表示
while (n--) {
char op;
cin >> op >> x;
if (op == 'I') insert(x);
else cout << (find(x) ? "Yes\n" : "No\n");
}
}