(资料图片仅供参考)
一、哈希的整体思想
最简单的哈希表其实就是数组，从数组中取出一个数的时间复杂度是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#includeusing 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 data; vector 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 data; vector flag; set 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 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#include#includeusing namespace std;#define MAX_N 20000int 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;} 
