840. 模拟散列表
维护一个集合，支持如下几种操作：
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 输出样例： Yes No
闭散列方法（开放寻址法）:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
int n;
int h[N];
int find(int x) //开发寻址法查找
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x) //不为空且值相等
t = (t + 1) % N;
return t;//找不到x值,最终落在未赋值的null = 0x3f3f3f3f
}
int main()
{
memset(h, 0x3f, sizeof h);//开发寻址法，初始最大值，null定义为0x3f3f3f3f
scanf("%d", &n);
while (n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x); //'*'取字符串单个字符(bushi)，直接op打出全部内容
if (*op == 'I') h[find(x)] = x;//find找到位置且赋值
else
{
if (h[find(x)] == null) puts("No");
else puts("Yes");
}
}
return 0;
}
开散列方法（拉链法）:
数组模拟链表+find函数-->insert函数 int t = (x % N + N) % N ; //负数整数都转化成为正数【c++取模负数仍为负数】
深度解析数组模拟链表： e数组存放每个idx下标值， ne数组存放每个下标指向的下一个下标，add中指向 h数组仅存放最后添加的节点下标【当做每个下标为链表的初始起点】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200003;//除余法需要先找离N最大范围最近的质数【试除法，口算也行】
int n;
int h[N], e[N], ne[N], idx;
bool find(int x)//查找t=x的hash值映射的h[t]单链表是否存在x
{
int t = (x % N + N) % N;//除余法
for (int i = h[t]; ~i; i = ne[i])//遍历映射hash值t所在h[t]是否存在x，~i等效 i != -1
if (e[i] == x)
return true;
return false;
}
void add(int a,int b )//链表头插法 : 添加一条边 a->b
{
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}
void insert(int x)
{
if(find(x)) return ;
int t = (x % N + N) % N ; //负数整数都转化成为正数【c++取模负数仍为负数】
add(t,x);
}
int main()
{
memset(h , -1 , sizeof h);//二进制全为1 ，遍历邻接表 i = h[t]; ~i 按位取反二进制每位全部为0
scanf("%d",&n);
while(n --)
{
char op[2];
int x;
scanf("%s%d",op,&x);
if(*op == 'I' ) insert(x);//*取字符串单个字符(bushi)，直接op打出全部内容
else
{
if(find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}