一、哈希的整体思想
最简单的哈希表其实就是数组，从数组中取出一个数的时间复杂度是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;
}