hash是什么

哈希用来将很大范围的数（比如[10^-9, 109]），映射到一块较小的区间内。比如对于109，我们想让它映射到[0, 105]这块区间（也可以理解为数组）内，可以直接对109进行取余（10^9 % 10^5），然后根据余数确定该数在区间内的落点。这里的取余操作就叫做hash，取余也是常见的一种hash算法。

我们使用hash就是为了节约空间，如果内存大小无限，我们直接选择开一块2 * 10^9的数据存放数据即可，但是这块内存可能有很多空闲区域。实际中内存是有限的，我们需要尽可能的将大范围的数缩小范围，聚集在一起。哈希本身是一种特殊的离散化。

对于hash表来说，查找插入和删除的效率是O(1)，这是一个期望值（平均值），指的是在hash算法不会导致出现过多冲突的情况下的时间复杂度。最坏情况下是O(n)。

拉链法

既然缩小范围，那么数据量过大时，必然取余会有相同的结果，那此时再根据余数确定落点就会产生冲突。由此产生了两种解决方式：拉链法和开放寻址法。

拉链法其实就是在出现冲突的点位，延伸出一条链表，来存储相同余数的原数据。该链上所有的数hash的结果都是相同的，在查找具有重复hash值的数时，就需要遍历一下该链表，看看有无目标数据。

实际上我们会使用平衡树代替拉链，来减少冲突时的寻找时间。

开放寻址法

开放寻址法其实就是向后寻找位置，当hash结果出现冲突，如果右边的点位是空闲的，那么就继续向后寻找，直到有空闲点位。只要是hash完了发现数组的该位置已经被占，那就向后找，直到有空地。在整体上看该数组，每一小段区间内hash结果是相同的，也可能不同小区间的hash结果也相同，这取决于插入顺序。

具体实现

参考例题：活动 - AcWing

拉链法：

#include<iostream>
#include<cstring>

using namespace std;

const int N = 100003;
int h[N], e[N], ne[N], idx; 

// 求比1e5大的第一个质数，数学结果显示，对质数取余的hash冲突概率最小
// void getN() {
//     for (int i = 100000; ; i ++) {
//         bool flag = false;
//         for (int j = 2; j * j <= i; j ++ ) {
//             if (i % j != 0) {
//                 flag = true;
//             } else {
//                 flag = false;
//                 break;
//             }
//         }
//         if (flag) {
//             cout << i;
//             break;
//         }
//     }
// }

void insert(int x) {
    int k = ((x % N) + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++;
}

void find(int x) {
    int k = ((x % N) + N) % N;
    for (int i = h[k]; i != - 1; i = ne[i]) {
        if (e[i] == x) {
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}

int main() {
    
    // 初始化h[N]为-1
    memset(h, -1, sizeof h);
    
    int n;
    scanf("%d", &n);
    
    while (n -- ) {
        char op[2]; int x;
        scanf("%s%d", op, &x);
        if (op[0] == 'I') {
            insert(x);
        } else {
            find(x);
        }
    }
    
    return 0;
}

开放寻址法：

#include<iostream>
#include<cstring>

using namespace std;

const int N = 100003, null = 0x3f3f3f3f;
int h[N];

void insert(int x) {
    int k = ((x % N) + N) % N;
    while(h[k] != null) {
        k ++;
        if (k == N) k = 0;
    }
    h[k] = x;
}

void find(int x) {
    int k = ((x % N) + N) % N;
    while (h[k] != null) {
        if (h[k] == x) {
            cout << "Yes" << endl;
            return;
        } else {
            k ++;
        }
        if (k == N) k = 0;
    }
    cout << "No" << endl;
}

int main() {
    
    // 初始化h[N]为比10^9大的数，表示该位置没被命中过
    // 关于0x3f的用法详见：https://www.cnblogs.com/handsomecui/p/4723949.html
    memset(h, 0x3f, sizeof h);
    
    int n;
    scanf("%d", &n);
    
    while (n -- ) {
        char op[2]; int x;
        scanf("%s%d", op, &x);
        if (op[0] == 'I') {
            insert(x);
        } else {
            find(x);
        }
    }
    
    return 0;
}