【题目来源】
840. 模拟散列表 - AcWing题库
【题目描述】
维护一个集合，支持如下几种操作：
（1）I x，插入一个数x；
（2）Q x，询问数x是否在集合中出现过；
现在要进行N次操作，对于每个询问操作输出对应的结果。
【输入】
第一行包含整数N，表示操作数量。
接下来N行，每行包含一个操作指令，操作指令为I x，Q x中的一种。
【输出】
对于每个询问指令Q x，输出一个询问结果，如果x在集合中出现过，则输出 Yes， 否则输出No。每个结果占一行。
【输入样例】
5
I 1
I 2
I 3
Q 2
Q 5
【输出样例】
Yes
No
【解题思路】
【算法标签】
《AcWing 840 模拟散列表》 #哈希表#
【代码详解】
// 拉链法
#include <bits/stdc++.h>
using namespace std;const int N = 100003; // 哈希表的大小，一个质数int h[N]; // 哈希表，h[k]存储哈希值为k的链表的头指针
int e[N]; // 存储实际插入的值
int ne[N]; // 存储下一个节点的索引
int idx; // 当前可用的节点索引// 向哈希表中插入一个数x
void insert(int x)
{// 计算哈希值，处理负数int k = (x % N + N) % N;// 头插法：将新节点插入到链表头部e[idx] = x; // 存储值ne[idx] = h[k]; // 新节点指向原来的头节点h[k] = idx; // 更新头节点为新节点idx++; // 移动到下一个可用位置
}// 在哈希表中查找数x是否存在
bool find(int x)
{// 计算哈希值，处理负数int k = (x % N + N) % N;// 遍历哈希值为k的链表for (int i = h[k]; i != -1; i = ne[i]){// 如果找到相同的值，返回trueif (e[i] == x){return true;}}// 没有找到，返回falsereturn false;
}int main()
{int n; // 操作次数scanf("%d", &n);// 初始化哈希表，所有链表的头指针设为-1（表示空链表）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;
}
// 开放寻址法
#include <bits/stdc++.h>
using namespace std;const int N = 200003; // 哈希表的大小，一般取质数，且至少是数据量的2倍
const int null = 0x3f3f3f3f; // 特殊值，表示该位置为空
int h[N]; // 哈希表数组// 查找函数：找到x应该插入的位置，或者x当前所在的位置
int find(int x)
{// 计算哈希值，处理负数int k = (x % N + N) % N;// 线性探测：当当前位置不为空且不是要找的值时，继续查找while (h[k] != null && h[k] != x){k++; // 移动到下一个位置if (k == N) // 如果到达数组末尾{k = 0; // 回到数组开头}}// 返回找到的位置// 如果x存在，返回x的位置// 如果x不存在，返回应该插入的空位置return k;
}int main()
{int n; // 操作次数scanf("%d", &n);// 初始化哈希表，将所有位置设为空// 0x3f3f3f3f是一个很大的数，通常不会作为有效值memset(h, 0x3f, sizeof(h));while (n--){char op[2]; // 操作类型int x; // 操作的值scanf("%s%d", op, &x);// 找到x应该插入的位置，或者x当前所在的位置int k = find(x);if (*op == 'I') // 插入操作{h[k] = x; // 在找到的位置插入x}else // 查询操作{// 如果h[k]不是空值，说明x存在if (h[k] != null){puts("Yes");}else{puts("No");}}}return 0;
}
【运行结果】
5
I 1
I 2
I 3
Q 2
Yes
Q 5
No