$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

笔记：
哈希表的作用：把庞大复杂的数据映射到较小的范围。
$h(x)$可以把数据进行映射，成为哈希函数。
我们可以这么考虑：

1. $h(x)=x$ $mod$ $10^5$。
2. 对于冲突的处理：
   • 若干不同的数倍映射成相同的数，称为冲突。
   • 对于冲突，我们有两种处理方法。
   • 根据处理方法的不同，分为拉链法和开放寻址法。
     1. 拉链法
        • 设$h(11)=3$，$h(23)=3$，这就是一种冲突。
        • 我们可以设一个数组$h$，也就是哈希的结果。
        • 对于每一个结果，建立一个链表。
        • 把映射为$k$的所有数$x$都放在$h[k]$这个链表里。
     2. 开放寻址法
        • 设$h(x)=k$。
        • 也就是$x$的哈希值为$k$。
        • 如果在$hash[k]$的位置已经有元素，持续往后遍历直到找到$x$（询问）或为空（插入）为止。
        • 注意开放寻址法一般会把数组开到数据范围的$2$~$3$倍，能提高效率。

代码：

拉链法：

#include <bits/stdc++.h>
using namespace std;
const int N = 100003;
int h[N], e[N], ne[N], idx;
void insert(int x) {
    int k = (x % N + N) % N;
    e[idx] = x; ne[idx] = h[k], h[k] = idx++;
}
bool find(int x) {
    int k = (x % N + N) % N;
    for (int i = h[k]; ~i; i = ne[i]) {
        if (e[i] == x) return 1;
    }
    return 0;
}
int main() {
    int n; scanf("%d", &n);
    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, null = 0x3f3f3f3f;
int h[N];
int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x) {
        k++;
        if (k == N) k = 0;
    }
    return k;
}
int main() {
    int n; scanf("%d", &n);
    memset(h, 0x3f, sizeof h);
    while (n--) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        int k = find(x);
        if (*op == 'I') h[k] = x;
        else {
            if (h[k] != null) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}