|
|
##[$AcWing$ $840$. 模拟散列表](https://www.acwing.com/problem/content/842/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
维护一个集合，支持如下几种操作：
|
|
|
|
|
|
`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$
|
|
|
|
|
|
**输入样例：**
|
|
|
```cpp {.line-numbers}
|
|
|
5
|
|
|
I 1
|
|
|
I 2
|
|
|
I 3
|
|
|
Q 2
|
|
|
Q 5
|
|
|
```
|
|
|
**输出样例：**
|
|
|
```cpp {.line-numbers}
|
|
|
Yes
|
|
|
No
|
|
|
```
|
|
|
|
|
|
### 二、什么是散列表
|
|
|
|
|
|
又称 **哈希表**，将一个比较大的值域映射到一个小的范围，比如$0\sim 10^9$,映射到$0 \sim 10^5$范围内。原因是原来的值域是比较稀疏的，稠密的。
|
|
|
|
|
|
类似于离散化，**离散化保序**，而**哈希表不保序**。离散化是一种极其特殊的$Hash$方式。
|
|
|
|
|
|
一般的操作有:
|
|
|
* 插入
|
|
|
* 查找
|
|
|
* 删除（一般不用）
|
|
|
|
|
|
### 二、拉链法
|
|
|
```c++
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 100003; //这个数字是根据FindGreaterPrime.cpp获取到的
|
|
|
|
|
|
//槽
|
|
|
int h[N];
|
|
|
|
|
|
//拉链法
|
|
|
int e[N], ne[N], idx;
|
|
|
|
|
|
//单链表插入
|
|
|
void insert(int x) {
|
|
|
//如果x是负数，那么x%N就是一个负数，我们不想要一个负数，就加上一个N，
|
|
|
//然后再模N就行了。
|
|
|
int k = (x % N + N) % N;
|
|
|
//头插法
|
|
|
//1、添加一个新数据
|
|
|
//2、原来k的头接到新增加数据idx的后面
|
|
|
//3、把idx设置为k的头
|
|
|
//4、idx++方便下一次插入
|
|
|
e[idx] = x, ne[idx] = h[k], h[k] = idx++;
|
|
|
}
|
|
|
|
|
|
//查询操作
|
|
|
bool find(int x) {
|
|
|
//同样的Hash函数
|
|
|
int k = (x % N + N) % N;
|
|
|
//查找链表，看看有没有x
|
|
|
for (int i = h[k]; i != -1; i = ne[i])
|
|
|
if (e[i] == x) return true;
|
|
|
return false;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//优化输入
|
|
|
ios::sync_with_stdio(false);
|
|
|
int n;
|
|
|
cin >> n;
|
|
|
|
|
|
//批量设置h数组内容为-1,清空槽，这是链表终点的初始值
|
|
|
memset(h, -1, sizeof h);
|
|
|
|
|
|
while (n--) {
|
|
|
string op;
|
|
|
int x;
|
|
|
cin >> op >> x;
|
|
|
//插入x
|
|
|
if (op == "I") insert(x);
|
|
|
else {
|
|
|
//检查是不是存在
|
|
|
if (find(x)) puts("Yes");
|
|
|
else puts("No");
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 三、开放寻址法
|
|
|
```c++
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
//如果题目说是100000,那就需要找一个两倍大一点的质数
|
|
|
//这个数字是根据FindGreaterPrime.cpp获取到的
|
|
|
const int N = 200003;
|
|
|
|
|
|
//正无穷
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
//因为题目的数据范围是1e9,而0x3f3f3f3f大于1e9，所以可以用来做特殊值判断
|
|
|
|
|
|
//开放寻址法
|
|
|
int h[N];
|
|
|
|
|
|
//核心操作
|
|
|
//找坑位：有两种方式会停止下来，一是找到了这个值，二是找到了坑位，用时再注意分辩
|
|
|
//如果存在，返回x存储的位置
|
|
|
//如果不存在，返回x应该存储的位置
|
|
|
//如果返回的位置上真实的值==x就是找到了，!=x就是找不到
|
|
|
int find(int x) {
|
|
|
int k = (x % N + N) % N;
|
|
|
while (h[k] != INF && h[k] != x) {
|
|
|
k++;
|
|
|
if (k == N) k = 0;//如果找到了最后一个位置，那么就回到0
|
|
|
}
|
|
|
return k;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//输入优化
|
|
|
ios::sync_with_stdio(false);
|
|
|
|
|
|
int n;
|
|
|
cin >> n;
|
|
|
//全部初始化为正无穷，判断是不是使用过此位置
|
|
|
memset(h, 0x3f, sizeof h);
|
|
|
|
|
|
while (n--) {
|
|
|
string op;
|
|
|
int x;
|
|
|
cin >> op >> x;
|
|
|
int k = find(x);
|
|
|
if (op == "I")h[k] = x;
|
|
|
else {
|
|
|
if (h[k] != INF) puts("Yes");
|
|
|
else puts("No");
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
### 四、找出大于$n$的第一个质数
|
|
|
```c++
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
//判断一个数是不是质数
|
|
|
bool isPrime(int n) {
|
|
|
if (n < 2) return false;
|
|
|
for (int i = 2; i <= n / i; i++)
|
|
|
if (n % i == 0) return false;
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
for (int i = 100000;; i++) {
|
|
|
if (isPrime(i)) {
|
|
|
cout << i << endl;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
