一、哈希的整体思想

最简单的哈希表其实就是数组，从数组中取出一个数的时间复杂度是O(1)的。但是数组下标类型是整型的，万一我的下标类型不是整型了该怎么办呢？比如说字符串型，典型的就是我想查找某个单词存不存在。还有些更复杂的数据类型，比如自定义的类型。那么问题就来了，如何满足任意数据类型的索引需求呢？最简单直接的想法，其实就是先对任意数据类型与整型的数组下标做一个映射，往后就又回到数组取数的环节了。这种映射是一种高维空间到低维空间的映射。低维空间是有限的，而高维空间的变化情况要复杂得多。如果采用一个萝卜一个坑的思想，必然会产生重复占位，这就是哈希冲突。当我们在设计哈希表的时候一定要考虑到哈希冲突。为什么说哈希表的设计感极强，其实就在于，解决哈希冲突的方法是多种多样的。还有一个问题，哈希表装满了怎么办？有一个概念叫做装填因子（=存储元素数/哈希表size大小）一般来说，装填因子达到0.75的情况下，意味着哈希表可能要进行扩容了。

布隆过滤器

好了，说回布隆过滤器，传统哈希表有一个缺点，就是存储空间与元素数量有关，在大数据的场景下，经常需要判重操作。如果用一张哈希表存，数据量可能过于庞大。而布隆过滤器，可以实现存储空间与元素数量无关。它是通过几组不同的哈希函数，映射到不同的数组下标，然后在对应位置的数组上标记为1，默认是0，如果这些位置上的数组值一旦只要出现一个0，那么都可以直接判断出，该元素不存在，但是如果全为1，也不能说明它就一定存在哈希表中，只能说明它大概率存在。布隆过滤器经常应用于大数据和信息安全相关的场景中。

二、哈希冲突解决办法

1、开放地址法

思想：如果7的位置发生冲突了，那就试一试8，8也不行，那就试一试9，依次往后“探测”，直到找到空位。（线性探测法）
注意：往后探测位置的计算规则是很灵活的，这里只是举了最简单的线性探测法。

平方探测法也有两种，可以简要看看找找区别，做题的时候格外注意，到底是哪一种：
第一种：7->8->12->21->37 (a[i+1] = a[i] + i^2)
第二种：7->8->11->16->23 (a[i+1] = a[0] + i^2)
值得注意的是，第二种只需要判断 i 从0-Msize-1 即可，因为(key+Msize*Msize)%Msize代表搜索回到了原地，这时可以认为无法搜索到这个数字

2、再哈希法

思想：比方说可以设计三种不同的哈希函数，如果第一种冲突了，就试试第二种，第二种也冲突了就试试第三种，依次类推。
注意：这种方法治标不治本，一般配合其他的哈希冲突解决方法使用。

3、建立公共溢出区

思想：另外建立一个公共溢出区，我想找的元素哈希表中找不到，就去公共溢出区再找找，其实就是用另外一种数据结构来维护，比方说红黑树。

4、链式地址法(拉链法)

思想：把哈希表的每一个坑看成链表的头节点。如果两个元素都想占用这个坑，直接在该坑上往后形成一个链表即可。

三、哈希表代码实现：

#include<iostream>
#include<vector>
using namespace std;

// 开放寻址法
class HashTable {
public:
    HashTable(int n = 100) : data(n), flag(n), cnt(0) {} 
    void insert(string s) {
        int ind = hash_func(s) % data.size(); // 计算哈希值
        recalc_ind(ind, s); // 冲突处理
        if (!flag[ind]) {
            data[ind] = s;
            flag[ind] = true;
            cnt++;
            if (cnt * 100 > data.size() * 75) {
                expand();
            }
        }
    }
    bool find(string s) {
        int ind = hash_func(s) % data.size(); // 计算哈希值
        recalc_ind(ind, s); // 冲突处理
        return flag[ind];
    }
private:
    int cnt; // 记录有多少元素
    vector<string> data;
    vector<bool> flag; // 记录相应位置是否存数据

    void expand() {
        int n = data.size() * 2;
        HashTable h(n);
        for (int i = 0; i < data.size(); i++) { // 看似很高的时间复杂度，其实分摊到每一个元素，扩容所造成的时间复杂度是O(1)的。
            if (flag[i] == false) continue;
            h.insert(data[i]);
        }
        *this = h;
        return ;
    }
    int hash_func(string &s) {
        int seed = 131, hash = 0;
        for (int i = 0; s[i]; i++) {
            hash = hash * seed + s[i];
        }
        return hash & 0x7fffffff; // 最高位是0，最后肯定是一个正数
    }
    void recalc_ind(int &ind, string s) {
        int t = 1;
        while (flag[ind] && data[ind] != s) {
            ind += t * t;
            t += 1;
            ind %= data.size();
        }
        return ;
    }

};


// 公共溢出区法：
class HashTable {
public:
    HashTable(int n = 100) : flag(n), data(n), cnt(0) {}
    void insert(string s) {
        int ind = hash_func(s) % data.size(); // 计算哈希值
        recalc_ind(ind, s); // 冲突处理
        if (flag[ind] == false) {
            data[ind] = s;
            flag[ind] = true;
            cnt += 1;
            if (cnt * 100 > data.size() * 75) {
                expand();
            }
        } else if (data[ind] != s) {
            buff.insert(s);
        }
        return ;
    }
    bool find(string s) {
        int ind = hash_func(s) % data.size(); // 计算哈希值
        recalc_ind(ind, s); // 冲突处理
        if (flag[ind] == false) return false;
        if (data[ind] == s) return true;
        return buff.find(s) != buff.end();
    }

private:
    int cnt;
    vector<string> data;
    vector<bool> flag;
    set<string> buff;
    
    void expand() {
        int n = data.size() * 2;
        HashTable h(n);
        for (int i = 0; i < data.size(); i++) {
            if (flag[i] == false) continue;
            h.insert(data[i]);
        }
        for (auto x : buff) {
            h.insert(x);
        }
        *this = h;
        return ;
    }
    int hash_func(string &s) {
        int seed = 131, hash = 0;
        for (int i = 0; s[i]; i++) {
            hash = hash * seed + s[i];
        }
        return hash & 0x7fffffff;
    }
    void recalc_ind(int &ind, string &s) {
        return ;
    }
};

// 拉链法
class Node {
public :
    Node(string data = "", Node *next = nullptr) : data(), next(nullptr) {}
    string data;
    Node *next;
    void insert(Node *node) {
        node->next = this->next;
        this->next = node;
        return ;
    }
};

class HashTable {
public:
    HashTable(int n = 100) : data(n), cnt(0) {}
    void insert(string s) {
        int ind = hash_func(s) % data.size(); // 计算哈希值
        recalc_ind(ind, s); // 冲突处理
        Node *p = &data[ind];
        while (p->next && p->next->data != s) p = p->next;
        if (p->next == nullptr) {
            p->insert(new Node(s));
            cnt += 1;
            if (cnt > data.size() * 3) expand();
        }
        return ;
    }
    bool find(string s) {
        int ind = hash_func(s) % data.size(); // 计算哈希值
        recalc_ind(ind, s); // 冲突处理
        Node *p = data[ind].next;
        while (p && p->data != s) p = p->next;
        return p != nullptr;
    }

private:
    int cnt;
    vector<Node> data;
    
    void expand() {
        int n = data.size() * 2;
        HashTable h(n);
        for (int i = 0; i < data.size(); i++) {
            Node *p = data[i].next;
            while (p) {
                h.insert(p->data);
                p = p->next;
            }
        }
        *this = h;
        return ;
    }
    int hash_func(string &s) {
        int seed = 131, hash = 0;
        for (int i = 0; s[i]; i++) {
            hash = hash * seed + s[i];
        }
        return hash & 0x7fffffff;
    }
    void recalc_ind(int &ind, string &s) {
        return ;
    }
};


int main() {
    int op;
    string s;
    HashTable h;
    while (cin >> op >> s) {
        switch (op) {
            case 1: h.insert(s); break;
            case 2: cout << "find " << s << " : " << h.find(s) << endl; break;
        }
    }

    return 0;
}

看到这里，不妨来一道PAT的题目练练手吧，PAT题目链接：https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805343236767744
题解代码：

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
#define MAX_N 20000

int Msize, n, m;
int a[MAX_N + 5], flag[MAX_N + 5];
int cnt;

bool insert(int s) {
    if (cnt == Msize) return false;
    for (int t = 0; t < Msize; t++) {
        int ind = (s + t * t) % Msize;
        if (!flag[ind]) {
            a[ind] = s;
            flag[ind] = 1;
            cnt++;
            return true;
        }
    }
    return false;
}
bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2, I = sqrt(x); i <= I; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
int main() {
    // 初始化
    int x;
    scanf("%d%d%d",&Msize, &n, &m);
    while (!is_prime(Msize)) Msize++;

    // 插入部分
    for (int i = 0 ; i < n; i++) {
        scanf("%d", &x);
        bool insert_status = insert(x);
        if (!insert_status) printf("%d cannot be inserted.\n", x);
    }

    // 查找部分
    int ans = 0;
    for (int i = 0; i < m; i++) {
        scanf("%d", &x);
        int t;
        for (t = 0; t <= Msize; t++) {
            ans += 1;
            int ind = (x + t * t) % Msize;
            if (a[ind] == x || flag[ind] == 0) break;
        }
    }
    printf("%.1f\n", ans * 1.0 / m);

    return 0;
}