python/TangDou/AcWing/Hash/840.md

##AcWing 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

二、什么是散列表

又称 哈希表，将一个比较大的值域映射到一个小的范围，比如0\sim 10^9,映射到0 \sim 10^5范围内。原因是原来的值域是比较稀疏的，稠密的。

类似于离散化，离散化保序，而哈希表不保序。离散化是一种极其特殊的Hash方式。

一般的操作有:

• 插入
• 查找
• 删除（一般不用）

二、拉链法

#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;
}

三、开放寻址法

#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的第一个质数

#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;
}