【C++】哈希表的实现（unordered_map和unordered_set的底层）

文章目录

前言

        前面我们学习了红黑树，红黑树就是map和set的底层，本篇文章带来的是unordered_map和unordered_set的底层，也就是哈希表。本节重点讲解哈希表的实现。

一、unordered_set和unordered_map介绍

简介：

• unordered_set和unordered_map是在C++11中才引入的，早年C++库中只有set和map，也就是已经有Key和Key:Value这两种查找的数据结构了并且效率不差，后来因为前两者的查找效率很高，因此就将其引入C++库。
• 因为set和map这种Key和Key:Value结构已经存在，所以新set和新map取名就在前面加上了unordered，这个单词的意思是无序的。暗示了unorder_set和unorder_map存储的数据是无序的，这点就和set、map存储的数据有序不一样了。

1.unordered_set

• unordered_set的声明如下，Key就是unordered_set底层关键字的类型：
• 
• unordered_set默认要求Key支持转换为整形，如果不支持或者想按自己的需求走可以自行实现支持将Key转成整形的仿函数传给第二个模板参数Hash。
• unordered_set默认要求Key支持比较相等，如果不支持或者想按自己的需求走可以自行实现支持将Key比较相等的仿函数传给第三个模板参数Pred。
• unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第四个参数Alloc。
• 一般情况下，我们都不需要传后三个模板参数。

2.unordered_set和set的使用差异

• 查看文档我们会发现unordered_set的支持增删查且跟set的使用⼀模⼀样，关于使用我们这里就不再赘述和演示了，可参考前面文章：
• 
• unordered_set和set的第一个差异是对key的要求不同，set要求Key支持小于比较，而unordered_set要求Key支持转成整形且支持等于比较，要理解unordered_set的这个两点要求得后续我们结合下文哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。可以参考unordered_set的Hash、Pred参数和set的Compare参数:
• 
• unordered_set和set的第二个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set 是单向迭代器，其次set底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以set迭代器遍历是有序+去重。而unordered_set底层是哈希表，迭代器遍历是无序+去重。
• unordered_set和set的第三个差异是性能的差异，整体而言大多数场景下，unordered_set的增删查改更快⼀些，因为红黑树增删查改效率是 O(log n)，而哈希表增删查平均效率是 O(1)，其实，实际上，O(log n) 和 O(1) 在数据量不是特别大的时候差别不是很大，因为就是10亿个数据也就是2的30次方，对于log n也就是查找30次，但总体上，O(1)还是要更优一点。具体可以参考下面的代码演示：

unordered_set和set的效率对比：

#include <iostream>
#include <unordered_set>
#include <set>
using namespace std;

void test()
{
	const int N = 1000000;//测试数据个数
	srand((unsigned int)time(0));

	set<int> s;
	unordered_set<int> us;

	//测插入数据时间
	vector<int> v;
	v.reserve(N);
	for (int i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

	int begin1 = clock();
	for (auto& e : v)
	{
		s.insert(e);
	}
	int end1 = clock();

	int begin2 = clock();
	for (auto& e : v)
	{
		us.insert(e);
	}
	int end2 = clock();

	cout << "set insert: " << end1 - begin1 << "（毫秒）" << endl;
	cout << "unordered_set insert: " << end2 - begin2 << "（毫秒）" << endl << endl;

	//测查找个数和时间
	int begin3 = clock();
	int m1 = 0;
	for (auto& e : v)
	{
		auto ret = s.find(e);
		if (ret != s.end())
		{
			++m1;
		}
	}
	int end3 = clock();

	int begin4 = clock();
	int m2 = 0;
	for (auto& e : v)
	{
		auto ret = us.find(e);
		if (ret != us.end())
		{
			++m2;
		}
	}
	int end4 = clock();

	cout << "set find: " << end3 - begin3 << "（毫秒）" << "->" << m1 << "（个数）" << endl;
	cout << "unordered_set find: " << end4 - begin4 << "（毫秒）" << "->" << m2 << "（个数）" << endl << endl;

	//测删除数据时间
	int begin5 = clock();
	for (auto& e : v)
	{
		s.erase(e);
	}
	int end5 = clock();

	int begin6 = clock();
	for (auto& e : v)
	{
		us.erase(e);
	}
	int end6 = clock();

	cout << "set erase: " << end5 - begin5 << "（毫秒）" << endl;
	cout << "unordered_set erase: " << end6 - begin6 << "（毫秒）" << endl;
}

int main()
{
	test();
	return 0;
}

测试结果（Release x64）:

• 很明显，在增删查的效率上，unordered_set是更优于set的。

3.unordered_map

• unordered_map声明如下，参数的Key和T决定map的K:V类型
• 
• unordered_map也默认要求Key支持转换为整形，如果不支持或者想按自己的需求走可以自行实现支持将Key转成整形的仿函数传给第二个模板参数Hash。
• unordered_map也默认要求Key支持比较相等，如果不支持或者想按自己的需求走可以自行实现支持将Key比较相等的仿函数传给第三个模板参数Pred。
• unordered_map底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第四个参数Alloc。
• 一般情况下，我们都不需要传后三个模板参数。

3.unordered_map和map的使用差异

• 查看文档我们会发现unordered_map的支持增删查改且跟map的使用一模一样，关于使用我们这里就不再赘述和演示了，可参考主页map的使用文章。
• 
• unordered_map和map的第一个差异是对key的要求不同，map要求Key支持小于比较，而unordered_map要求Key支持转成整形且支持等于比较，要理解unordered_map的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。比如参考两者的Hash、Pred参数和Compare参数：
• 
• unordered_map和map的第⼆个差异是迭代器的差异，map的iterator是双向迭代器， unordered_map是单向迭代器，其次map底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以map迭代器遍历是Key有序+去重。而unordered_map底层是哈希表，迭代器遍历是 Key无序+去重。
• unordered_map和map的第三个差异是性能的差异，整体而言大多数场景下，unordered_map的增删查改更快⼀些，因为红黑树增删查改效率是 O(logN) ，而哈希表增删查平均效率是O(1) ， 具体可以参看下面代码的演示的对比差异。

unordered_map和map增删查效率对比：

#include <iostream>
#include <unordered_map>
#include <map>
using namespace std;

void test()
{
	const int N = 1000000;
	srand((unsigned int)time(0));

	vector<int> v;
	v.reserve(N);
	for (int i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

	map<int, int> m;
	unordered_map<int, int> um;

	int begin1 = clock();
	for (auto& e : v)
	{
		m.insert({ e,e });
	}
	int end1 = clock();

	int begin2 = clock();
	for (auto& e : v)
	{
		um.insert({ e,e });
	}
	int end2 = clock();

	cout << "map insert: " << end1 - begin1 << "（毫秒）" << endl;
	cout << "unordered_map insert: " << end2 - begin2 << "（毫秒）" << endl << endl;

	int begin3 = clock();
	int m1 = 0;
	for (auto& e : v)
	{
		auto ret = m.find(e);
		if (ret != m.end())
		{
			++m1;
		}
	}
	int end3 = clock();

	int begin4 = clock();
	int m2 = 0;
	for (auto& e : v)
	{
		auto ret = um.find(e);
		if (ret != um.end())
		{
			++m2;
		}
	}
	int end4 = clock();

	cout << "map find: " << end3 - begin3 << "（毫秒）" << "->" << m1 << "（个数）" << endl;
	cout << "unordered_map find: " << end4 - begin4 << "（毫秒）" << "->" << m2 << "（个数）" << endl << endl;

	int begin5 = clock();
	for (auto& e : v)
	{
		m.erase(e);
	}
	int end5 = clock();

	int begin6 = clock();
	for (auto& e : v)
	{
		um.erase(e);
	}
	int end6 = clock();

	cout << "map erase: " << end5 - begin5 << "（毫秒）" << endl;
	cout << "unordered_map erase: " << end6 - begin6 << "（毫秒）" << endl << endl;
}

int main()
{
	test();
	return 0;
}

测试结果（Release x64）：

• 在插入效率上，unordered_map和map差不多，但是查找和删除上，明显unordered_map更优。

• 关于unordered_set,unordered_map和set,map最后再说一点。
• 前面不是提到set和map底层是红黑树吗，所以set和map的数据是有序和去重的，而unordered_set和unordered_map底层是哈希表（桶），所以unordered_set和unordered_map的数据是无序和去重的。

代码演示：

#include <iostream>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
using namespace std;

void test()
{
	set<int> s1({ 5,2,6,3,4,8,1,9,7 });
	map<int, int>m1;
	m1.insert({ 5,5 });
	m1.insert({ 2,2 });
	m1.insert({ 1,1 });
	m1.insert({ 4,4 });
	m1.insert({ 3,3 });

	for (auto e : s1)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : m1)
	{
		cout << e.first << ":" << e.second << " ";
	}
	cout << endl << endl;

	unordered_set<int> s2({ 5,2,6,3,4,8,1,9,7 });
	unordered_map<int, int>m2;
	m2.insert({ 5,5 });
	m2.insert({ 2,2 });
	m2.insert({ 1,1 });
	m2.insert({ 4,4 });
	m2.insert({ 3,3 });

	for (auto e : s2)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : m2)
	{
		cout << e.first << ":" << e.second << " ";
	}
	cout << endl;
}

int main()
{
	test();
	return 0;
}

运行结果：

• 综合上面性能测试以及unordered_set,unordered_map和set,map接口得相似性，所以我们大多数情况下，一般是使用unordered_set或者unordered_map即可。除非你有数据排序的需要或其他特殊需求。

二、哈希表的介绍

1.哈希概念

• 哈希(hash)又称散列，是一种组织数据的方式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建立⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进行快速查找。

2.直接定址法

• 直接定值法是最简单的一种哈希，可以让我们初步了解什么是哈希。
• 该方法其实我们很早就使用过，比如下面这道题：

题目链接：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

题解：

class Solution {
public:
	int firstUniqChar(string s)
	{
        //先开辟26个空间（26个字母）
		int count[26] = { 0 };

		//将每个字母减去a映射到数组中
		for (auto e : s)
		{
			count[e - 'a']++;
		}

        //通过映射关系，遍历数组找到最前面的单个字母即可
		for (size_t i = 0; i < s.size(); i++)
		{
			if (count[s[i] - 'a'] == 1)
			{
				return i;
			}
		}

		return -1;
	}
};

• 上面这题也可以看成是计数排序，将每个字母减去a，从而映射到0-25的空间上，每个位置对应一个字母，比如字母a，其减去a映射的位置就是数组count[0]，以此类推，不仅可以计数，也能排序。
• 将 字母-'a' 来计算字母的映射位置的函数，可以看成一种哈希函数，因为方法比较直接，计算出来的位置比较绝对，所以称为直接定址法。
• 直接定址法优点：当关键字的范围比较集中时，直接定址法就是非常简单高效的方法，比如一组关键字都在[0,99]之间， 那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置的下标。再比如⼀组关键字值都在 [a,z]的小写字母，那么我们开⼀个26个数的数组，每个关键字acsii码-a = ascii码就是存储位置的下标。 也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。

3.哈希冲突

• 直接定址法的缺点也非常明显，当关键字的范围比较分散时，就很浪费内存甚至内存不够用。假设我们只有数据范围是[0,9999]的N个值，我们要映射到一个M个空间的数组中(一般情况下M>=N)，那么 就要借助哈希函数(hashfunction)hf，关键字key被放到数组的h(key)位置，这里要注意的是h(key)计算出的值必须在[0,M)之间。
• 这里存在的一个问题就是，两个不同的key可能会映射到同⼀个位置去，这种问题我们叫做哈希冲突， 或者哈希碰撞。理想情况是找出一个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的， 所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的方案。

补充：

• 简单点说，哈希就是将N个值通过哈希函数，映射到M个空间内。哈希函数下面会讲到，常见点的哈希函数就是取模，做 % 运算得到的结果映射到M空间中的某一个位置上，哈希冲突就是2个及以上的数据进行取模后映射的位置相同，哈希冲突尽量避免但是无法消除，如遇到需要进一步确认映射位置解决哈希冲突，这一步也叫线性探测。
• 将关键字转为整数：这里有一个点需要注意，我们将关键字映射到数组中位置，一般是整数好做映射计算，比如取模运算，如果不是整数，我们要想办法转换成整数。这就是unordered_set和unordered_map的模板中，Hash参数的意义，Hash就是将非整形数据通过某种计算转为整形的仿函数。具体细节在下文实现哈希表中会详细介绍。
• 总的来说，直接定址法有着巨大的缺陷，所以哈希一般不考虑直接定址法，具体的哈希函数参考下文。

4.哈希函数

• 冲突虽不可避免，但是我们可以设计出优秀的哈希函数来减少冲突。
• 一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个方向去考量设计。
• 以下是介绍几种常见的哈希函数，其实最主要的就是第一种：

 （1）除留余数法（除法散列法）*

• 除法散列法也叫做除留余数法，顾名思义，假设哈希表的大小为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。
• 当使用除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等。如果是 ，那么key% 本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就冲突了。如： {63 , 31}看起来没有关联的值，如果M是16，也就是，那么计算出的哈希值都是15，因为63的⼆ 进制后8位是00111111，31的⼆进制后8位是00011111。如果是  ，就更明显了，保留的都是 10进值的后x位，如：{112,12312}，如果M是100，也就是 ，那么计算出的哈希值都是12。
• 关于除数是，那么只要后X位相同取模后余数就相同，这个一眼就能看出来很容易理解。关于除数是，这个可以看以下解释：简单点说，只要二进制中后X位相同，前面都可以被K * 抵消，后X位就是余数。
• 因此，当使用除法散列法时，建议M取不太接近2的整数次幂的一个质数(素数)。
• 需要说明的是，实践中也是八仙过海，各显神通，Java的HashMap采用除法散列法时就是2的整数次幂做哈希表的大小M，这样玩的话，就不用取模，而可以直接位运算，相对而言位运算比模更高效一些。但是他不是单纯的去取模，比如M是2^16次方，本质是取后16位，那么用key’= key>>16，然后把key和key'异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围 内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀⼀些即可。所以我们上面建议M取不太接近2的整数次幂的一个质数的理论是大多数数据结构书籍中写的理论，但是实践中， 灵活运用，抓住本质，而不能死读书。（了解）
• 那么C++中具体是这么设计除数的呢，其实就是使用一张质数表，具体我们在下文中讲解：

（2）乘法散列法（了解）

• 乘法散列法对哈希表大小M没有要求，他的大思路第一步：用关键字K乘上常数A(0<A<0)，并抽取出k*A的小数部分。第二步：后再用M乘以k*A的小数部分，再向下取整。
• ，其中floor表示对表达式进行向下取整，，这里最重要的是A的值应该如何设定，Knuth认为：（黄金分割点）比较好。
• 乘法散列法对哈希表大小M是没有要求的，假设M为1024，key为1234，A=0.6180339887,A*key = 762.6539420558，取小数部分为0.6539420558, M×((A×key)%1.0)=0.6539420558*1024= 669.6366651392，那么h(1234)=669。
• 乘法散列法用的比较少，但也是一种思路。

（3）全域散列法（了解）

• 如果存在⼀个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集， 比如，让所有关键字全部落入同一个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决方法自然是见招拆招，给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。
• ，P需要选一个足够大的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了一个P*(P-1)组全域散列函数组。假设P=17，M=6，a=3，b=4，则。
• 需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数使用，后续增删查改都固定使用这个散列函数，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数， 查找又是另一个散列函数，就会导致找不到插入的key了。
• 简单点说，会随机生成一个哈希函数，因为随机，所以连设计者都不知道具体的哈希函数，因此就不容易被恶意攻击，在安全性方面有一定作用。本质来说还是除留余数法，只不过在除数上做到一定随机性。

（4）关于其他哈希函数

• 其他哈希函数可参考：《殷人昆 数据结构：用面向对象方法与C++语言描述（第二版）》和《[数据结构(C语言版)].严蔚敏_吴伟民》等教材型书籍。
• 其中讲解的哈希函数包括但不限于：平方取中法、折叠法、随机数法、数学分析法等。大家感兴趣可以前去学习。

5.负载因子

• 我们知道哈希表也是要存储数据的，既然存储数据就避免不了扩容的问题，因此负载因子就是决定是否需要扩容的判断依据。这一点具体体现在下文的代码实现中，我们先了解知道。
• 假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子 = （也就是N 和 M 的比值），负载因子有些地方也翻译为载荷因子/装载因子等，他的英文为loadfactor。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；
• 一般情况下，比值等于0.7时就需要扩容了，因为比值过大，可用空间越小，哈希冲突的概率就越大，对性能的影响也就越大。

查看负载因子接口：

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

int main()
{
	unordered_map<int, int> m1;
	m1.insert({ 1,1 });
	m1.insert({ 54,54 });
	cout << m1.load_factor() << endl;//查看当前负载因子大小
	m1.insert({ 2,2 });
	cout << m1.load_factor() << endl;

	cout << m1.max_load_factor() << endl;//查看最大负载因子值

	return 0;
}

运行结果：

• unordered_set同理。

三、哈希冲突的解决方法

• 因为哈希冲突无法避免，那么就需要解决方法，主要的解决方法有两种：

1. 开放定址发
2. 链地址法（哈希桶）

• 这两种方法后续代码中都会进行实现

1.开放定址法

• 在开放定址法中所有的元素都放到哈希表里，当一个关键字key用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储，开放定址法中负载因子一定是小于1的，所以不存在没有位置的可能。这里的规则有三种：线性探测、二次探测、双重探测。
• （注意：以下方法中，M表示容量，h是哈希函数，hc是探测函数）

（1）线性探测

• 线性探测是我们后续代码中解决哈希冲突的方法，比较常见。具体规则：从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。因为哈希因子的存在，所以不存在没位置的情况。
• 
• 见上图，假如 h(19) 和 h(30) 计算的映射位置冲突，则 h(30)依次向后探测，直到找到一个空位置即可。这里面具体的计算公式参考下一点：
• ，这是哈希函数中的除留余数法，计算映射位置的公式。如果 hash0 位置冲突了，则线性探测公式为：，因为负载因子小于1， 则最多探测M-1次，一定能找到一个存储key的位置，如果继续冲突则i++。
• 下面演示：{19,30,5,36,13,20,21,12} 这⼀组值映射到M=11的表中的位置。
• 
• 解释：上图中，19,30哈希都等于8，发生哈希冲突，19先来就在位置8，30则在后一位9。因为9位置被30占住了，所以哈希等于9的20就继续顺延到10的位置。21同理。
• 线性探测的比较简单且容易实现，但缺点也明显（如上），线性探测的问题：假设 hash0 位置连续冲突，hash0，hash1， hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位置，这种现象叫做群集/堆积。下面的二次探测可以一定程度改善这个问题。

 （2）二次探测

• 从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置；具体公式如下：
• 哈希函数：，hash0位置冲突了，则二次探测公式为：，i = {1,2,3,...,2/M}。如果继续冲突则i++。
• 二次探测当时，当hashi<0时，需要hashi+=M，避免越界。
• 上面二次探测公式中是加减 i 的平方，一般按照先加 i 的平方，再减 i 的平方的顺序。当减 i 的平方等于负数时，就是上一条中需要加上M避免越界。
• 下面演示，{19,30,52,63,11,22}这一组值，映射到M=11的表中。
• 
• 解释：首先19先占据位置8，30通过二次探测加上i=1的平方计算最后在位置9。52则是因为9的位置被占，根据先加后减，因此52是减去i=1的平方最后在位置7。63也是哈希冲突，此时i=1的位置都被占了，因此i=2，加上i=2的平方再取模，计算的位置就是1了。11没啥说的，注意22，22因为1的位置被占，所以减去i=1的平方，因为0-1=-1<0越界了，此时需要 + M，M=11加上就是10，取模后22就在位置10了。
• 二次探测利用 i 平方的落差，使得堆积不容易发生，但难免有些极端情况会导致堆积。

（3）双重散列

• 第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟key相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为址。
• 双重散列从名字上就能看出，它是会进行两次哈希函数计算的，它的一般公式如下：
• 哈希函数依旧是除留余数法：，hash0位置冲突了，则双重探测公式为：，i = {1,2,3,...,M}，其中h2是第二个哈希函数。如果继续冲突则i++。
• 双重散列的要求：，关于h2这里有两种简单的取值方法：1. 当M为2整数幂时，h2(key)从[0，M-1]任选一个奇数；2. 当M为质数时，，也就是第二个哈希函数。
• 保证h2(key)和M互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群，若最大公约数，那么所能寻址的位置的个数为 M / P < M，使得对于⼀个关键字来说无法充分利用整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12， 那么所能寻址的位置为{1,4,7,10}，寻址个数为 12/gcd(12,3) = 4。
• 下面演示 {19,30,52,74}这⼀组值映射到M=11的表中，设
• 
• 解释：h1(19) = 8，h1(30) = 8，h1(52) = 8，h1(74) = 8，也就是这一组值都是冲突的，首先19占据位置8，30的位置：hc(30,1) = (8+1*(30 % 10+1)) % 11 = 9，52的位置：hc(52,1) = (8+1*(52 % 10 +1)) % 11 = 0，hc(74,1) = (8+1*(74 % 10+1)) % 11 = 2。
• 双重散列利用第二个哈希函数，使得堆积发生的概率更低。

2.链地址法

• 链地址法解决哈希冲突是我们重点掌握的办法。
• 链地址法与开放定址法最大的不同就是：在开放定址法中，如果遇到冲突就占据另一个位置，因为会占据另一个位置，所以冲突概率会越来越大，而在链地址法中，每一个位置都能存下多个值，就不存在发生冲突去占据其他位置的情况。

解决冲突的思路：

• 开放定址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。

思路演示：

• 下面演示 {19,30,5,36,13,20,21,12,24,96} 这一组值映射到M=11的表中：
• 
• 很明显，链地址法解决哈希冲突的方法就是将冲突值串在一起形成一个链表，也可以看成一个个桶（哈希桶）。

关于链地址法的扩容：

• 开放定址法负载因子必须小于1，链地址法的负载因子就没有限制了，可以大于1。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；stl中 unordered_xxx 的最大负载因子基本控制在1，大于1就扩容，我们下面实现也使用这个方式。

关于极端场景：

• 如果极端场景下，某个桶特别长怎么办？其实我们可以考虑使用全域散列法，这样就不容易被针对 了。但是假设不是被针对了，用了全域散列法，但是偶然情况下，某个桶很长，查找效率很低怎么办？这里在Java8的HashMap中当桶的长度超过一定阀值时就把链表转换成红黑树。一般情况下， 不断扩容，单个桶很长的场景还是比较少的，下面我们实现就不搞这么复杂了，这个解决极端场景的思路，了解⼀下。

四、两种哈希表代码实现

1. 开放定址法
2. 链地址法

（哈希函数都默认选择除留余数法）

1.开放定址法：

在开放定址法实现前需要补充一个知识点：

• 我们假设下面这个场景（线性探测中的例图）：哈希函数是除留余数法，解决冲突是线性探测
• 
• 以上是已经插好值的哈希表，现在有什么问题呢？当我们删除19，此时可以直接删除8位置上的值，但是当我们继续删除30时，由于删除值也是按照除留余数法进行查找，此时由于8位置上的19已经被删除了，所以8位置上为空，为空就无法确认30是否存在。假如19没被删除，我们查到8位置不为空并且不为30时，可以继续进行线性探测进一步查找。
• 问题总结：直接删除哈希表中的一个值，可能会引起后续无法查到相同哈希值的其他数据或者被哈希冲突影响位置的数据。
• 解决方法：为每一个哈希表中的位置设定一个状态，这些状态有：EXIST（存在）、EMPTY（为空）、DELETE（删除）。这三种状态前两个很好理解，有值就设定存在，没值就默认为空，而删除则是删除一个值后将其位置标记为DELETE，这样做就是在查找一个值时，如果遇见删除标记，则表示需要进一步使用线性探测等方式查找。

（1）基本框架

#pragma once
#include <vector>
#include <algorithm>
using namespace std;

//开放定址法的命名空间
namespace open_address
{
	//定义状态标志
	enum State
	{
		EXIST,//存在
		EMPTY,//为空
		DELETE //删除
	};

	//定义哈希数据
	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	//定义哈希表
	template<class K, class V>
	class HashTable
	{
	public:

	private:
		vector<HashData<K, V>> _tables;//底层数据结构使用vector
		size_t _n = 0;//表中存储数据个数
	};
}

框架简介： 

• State 枚举结构用来定义哈希表中数据的三种状态。
• HashData 类定义哈希表中数据类型。底层数据默认为pair类型，因此模板参数都需要有K,V。每个数据都有一个状态值，默认为 EMPTY（空）。
• HashTable 类就是哈希表本体了，底层数据结构选择vector，vector用来存储管理连续性空间是很高效和方便的。vector中存放的数据就是 HashData。
• n 用来记录哈希表中有效值个数，方便负载因子计算，用于扩容判断。

（2）Insert 框架

//插入
bool Insert(const pair<K, V>& kv)
{
	//扩容
	if ((double)_n / (double)_tables.size() > 0.7)
	{
		//...
	}

	//哈希函数：除留余数法
	size_t hash0 = kv.first % _tables.size();
	size_t hashi = hash0;
	size_t i = 1;

	//冲突探测（线性探测）
	while (_tables[hashi]._state == EXIST)
	{
		hashi = (hash0 + i) % _tables.size();
		++i;
	}

	//插入
	_tables[hashi]._kv = kv;
	_tables[hashi]._state = EXIST;
	++_n;

	return true;
}

• 我们先不看扩容，先了解值是具体怎么插入的。
• 首先使用除留余数法计算出插入值的映射位置hash0，然后hashi用于接下来的线性探测使用。注意取模的除数都是 _tables.size() 而不是 tables.capacity()，这是因为capacity()的返回值是vector的容量大小，而我们因为对除数有质数的要求，因此这里使用capacity是一个坑，size()返回的是质数有效空间，稍后我们实现构造时会有初始空间大小。
• 如果hashi位置的状态为EMPTY或者DELETE就可以直接插入，而只有当状态值为EXIST时才需要进行线性探测进一步确认映射位置，线性探测的公式参考：
• 直到线性探测找到的位置为EMPTY或者DELETE时才停止循环。
• 最后插入需要注意的就是改变状态指为EXIST，另外_n需要++。

（3）Insert 扩容和构造函数实现

• 结合前面内容，我们知道无论是哈希函数，还是探测函数，为了减少哈希冲突的概率，我们除数需要满足质数的性质。那么怎么获取这些质数呢？
• 诶，下面这个接口就能满足我们的需求：

__stl_next_prime 接口：

//获取下一个质数
inline unsigned long __stl_next_prime(unsigned long n)
{
	static const int __stl_num_primes = 28;//定义质数列表大小
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
		53,         97,         193,       389,       769,
		1543,       3079,       6151,      12289,     24593,
		49157,      98317,      196613,    393241,    786433,
		1572869,    3145739,    6291469,   12582917,  25165843,
		50331653,   100663319,  201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};

	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);//返回大于等于n的质数

	return pos == last ? *(last - 1) : *pos;
}

• 首先参数n是我们需要的空间大小。
• __stl_num_primes 是数组大小，__stl_prime_list[__stl_num_primes]是我们创建的质数数组，里面存储的都是质数。这两个变量都设置为 static 静态变量，因为这两被访问的频率很高，设置为静态能提高效率。
• first 是数组的头指针，last 是数组的尾指针，lower_bound是库函数，返回迭代区间内大于等于n的数的指针，并将其存储在 pos。这样 *pos 就是我们需要的空间大小。
• 但是，数组中的最后一个值是过大的，所以如果pos是最后一个值则需要后退一步。

哈希表的构造函数：

//构造
HashTable()
{
	_tables.resize(__stl_next_prime(0));
}

• 只需要将 vector 的size通过resize接口设置成质数数组中的最小值即可。其中的数据 HashData 的状态值都默认为空(EMPTY)，这些都算是有效空间。除数不使用capacity就体现在这里，因为扩容的特殊性,capacity实际大小并不能精准的被我们控制，因此除数使用size。

insert 的扩容实现：

//插入
bool Insert(const pair<K, V>& kv)
{
	//扩容
	if ((double)_n / (double)_tables.size() > 0.7)//计算负载因子,大于0.7就扩容
	{
		//创建一个新哈希表，重新建立映射
		HashTable<K, V> newHT;
		newHT._tables.resize(__stl_next_prime((unsigned long)(_tables.size() + 1)));

		//利用已有的Insert进行开放定址和冲突探测
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i]._state == EXIST)
			{
				newHT.Insert(_tables[i]._kv);
			}
		}

		//交换
		_tables.swap(newHT._tables);
	}

	//哈希函数：除留余数法
	size_t hash0 = kv.first % _tables.size();
	size_t hashi = hash0;
	size_t i = 1;

	//冲突探测（线性探测）
	while (_tables[hashi]._state == EXIST)
	{
		hashi = (hash0 + i) % _tables.size();
		++i;
	}

	//插入
	_tables[hashi]._kv = kv;
	_tables[hashi]._state = EXIST;
	++_n;

	return true;
}

• 说到扩容的数据调整，这是因为扩容导致size()大小变化，因此旧哈希表中的数据都需要重新映射。新size大小依旧由__stl_next_prime接口获取，参数传递旧size+1即可，因为会返回下一个质数。
• 这里的扩容代码实现的很巧妙，我们不是新建一个vector，而是直接新建一个哈希表newHT。这里直接复用已经实现的insert代码进行插入。因为新空间的负载因此肯定小于0.7，所以不会再进一步扩容导致递归。
• 这里的复用很巧妙的节省了代码量，减少重复代码，newHT插入完成后，将其底层vector与原哈希表底层vector进行swap交换即可。newHT出了扩容的作用域就会自行析构。

（4）Find 和 Erase 接口实现

Find:

//查找
HashData<K, V>* Find(const K& key)
{
	//哈希函数：除留余数法
	size_t hash0 = hash(key) % _tables.size();
	size_t hashi = hash0;
	size_t i = 1;

	while (_tables[hashi]._state != EMPTY)
	{
		if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
		{
			return &_tables[hashi];//找到了
		}

		//线性探测
		hashi = (hash0 + i) % _tables.size();
		++i;
	}

	return nullptr;//找不到
}

• Find实现并不复杂，先使用哈希函数找到映射位置hash0，再判断对应位置是否为空，不为空则进入循环，循环中使用线性探测进行查找，因为hash0的位置还没有判断，因此++i放在线性探测后面，当且仅当hashi的位置标记为存在EXIST并且对于值为key时，查找成功返回对应指针，反之，hashi位置为空则说明找不到，返回空指针。
• 注意，查找成功的条件中，必须有判断标记是否为存在，具体原因我们先看Erase的实现：

Erase:

//删除
bool Erase(const K& key)
{
	HashData<K, V>* ret = Find(key);
	if (ret == nullptr)
	{
		return false;
	}
	else
	{
		ret->_state = DELETE;//伪删除
		--_n;
		return true;
	}
}

• Erase 的实现非常简单，先查找需删除的值Key，只要Key不为空，就只需要将其状态标记为删除，然后--_n即可。
• 这是典型的伪删除法，因为是伪删除，原数据并没有真正清除，所以前面Find查找值时需要进一步确认其状态标记是否为EXIST。

Insert补充：

//插入
bool Insert(const pair<K, V>& kv)
{
	//不允许冗余
	if (Find(kv.first))
	{
		return false;
	}

    //...省略

}

• 因为我们实现的哈希表是不支持冗余值的，所以插入值如果已经存在就返回false。

（5）仿函数实现

• 前面提到过，哈希表要求：1.数据Key支持转换为整形的；2.数据Key支持==比较。
• 要求Key支持转换为整形是因为取模运算，要求Key支持相等比较是因为Find接口中查找数据的需要。所以这些要求我们结合底层来看是很好理解的。
• 详细思路：当key是string/Date等类型时，key不能取模，那么我们需要给HashTable增加⼀个仿函数，这个仿函数支持把key转换成⼀个可以取模的整形，如果key可以转换为整形并且不容易冲突，那么这个仿函数就用默认参数即可，如果这个Key不能转换为整形，我们就需要自己实现⼀个仿函数传给这个参数，实现这个仿函数的要求就是尽量key的每值都参与到计算中，让不同的key转换出的整形值不同。string 做哈希表的key非常常见，所以我们可以考虑把string特化一下。

仿函数的实现：

//定义默认仿函数（即一些实数数据）
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

//string版的特化仿函数
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash += e;
			hash *= 131;
		}

		return hash;
	}
};

//定义哈希表，将实现的仿函数作为默认参数传给模板参数Hash
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
    //获取下一个质数
    //省略...	

public:
    //构造
	//省略...

	//插入
	bool Insert(const pair<K, V>& kv)
	{
        //省略...		

		//哈希函数：除留余数法
		Hash hash;//实例化仿函数类
		size_t hash0 = hash(kv.first) % _tables.size();//将key的first数据进行转换

		//省略...
	}

	//查找
	HashData<K, V>* Find(const K& key)
	{
		//哈希函数：除留余数法
		Hash hash;
		size_t hash0 = hash(key) % _tables.size();
		
        //省略...
	}

	//删除
	//省略...

private:
	vector<HashData<K, V>> _tables;
	size_t _n = 0;
};

1. 首先实现默认的仿函数，是因为作为模板参数，我们需要统一格式，一律使用Hash转换数据类型，包括整形、浮点型等这类常见数学数据，这类数据我们之间强制转换为size_t即可。
2. 然后是特化的仿函数，也就是string，为什么要特化，因为我们平时使用unordered_map/unordered_set时，传递string模板参数后我们就可以直接使用，不需要进一步传递string类的对应仿函数，原因就是stl已经实现了string的特化仿函数，所以我们这里实现string的仿函数时也使用模板的特化。关于特化可以参考主页文章，简单点说特化可以让编译器根据数据类型自动选择生成对应的仿函数。
3. 然后重点就是特化的仿函数HashFunc<string>的实现过程，这里转换为整形采用的是BKDR哈希算法，它的核心思路就是在字符串转整形时每个字符的每一次运算都乘以一个素数P，P一般取131即可。为了确保字符串中的每一个字符都参与运算并且降低哈希冲突，所以我们依次相加每个字符的ASCII码值，如果只是相加每个字符的ASCII码值，那么就会出现拥有相同字符但是顺序不同的字符串，转换为整形后数值相同，这样大大增加了哈希冲突的概率已经不利于Find接口准确查找数据。因此这里BKDR哈希算法就是在每一次相加字符后，进行一次乘等运算，这样计算字符相同但是只要顺序不同的字符串时，那么计算的结果就一定不同。
4. 最后加入Hash转换只有两个地方会受到影响，一个是inset中的哈希函数，一个是Find中的哈希函数。

（6）完整代码

#pragma once
#include <vector>
#include <algorithm>
using namespace std;

//开放定址法的命名空间
namespace open_address
{
	//定义状态标志
	enum State
	{
		EXIST,//存在
		EMPTY,//为空
		DELETE //删除
	};

	//定义哈希数据
	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	//定义默认仿函数（即一些实数数据）
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;//强转为无符号整形即可
		}
	};

	//string版的特化仿函数
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash += e;
				hash *= 131;
			}

			return hash;
		}
	};

	//定义哈希表
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		//获取下一个质数
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			static const int __stl_num_primes = 28;//定义质数列表大小
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
				53,         97,         193,       389,       769,
				1543,       3079,       6151,      12289,     24593,
				49157,      98317,      196613,    393241,    786433,
				1572869,    3145739,    6291469,   12582917,  25165843,
				50331653,   100663319,  201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			const unsigned long* first = __stl_prime_list;
			const unsigned long* last = __stl_prime_list + __stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);//返回大于等于n的质数

			return pos == last ? *(last - 1) : *pos;
		}

	public:
		//构造
		HashTable()
		{
			_tables.resize(__stl_next_prime(0));
		}

		//插入
		bool Insert(const pair<K, V>& kv)
		{
			//不允许冗余
			if (Find(kv.first))
			{
				return false;
			}

			//扩容
			if ((double)_n / (double)_tables.size() > 0.7)//计算负载因子,大于0.7就扩容
			{
				//创建一个新哈希表，重新建立映射
				HashTable<K, V> newHT;
				newHT._tables.resize(__stl_next_prime((unsigned long)(_tables.size() + 1)));

				//利用已有的Insert进行开放定址和冲突探测
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					if (_tables[i]._state == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}

				//交换
				_tables.swap(newHT._tables);
			}

			//哈希函数：除留余数法
			Hash hash;
			size_t hash0 = hash(kv.first) % _tables.size();
			size_t hashi = hash0;
			size_t i = 1;

			//冲突探测（线性探测）
			while (_tables[hashi]._state == EXIST)
			{
				hashi = (hash0 + i) % _tables.size();
				++i;
			}

			//插入
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;

			return true;
		}

		//查找
		HashData<K, V>* Find(const K& key)
		{
			//哈希函数：除留余数法
			Hash hash;
			size_t hash0 = hash(key) % _tables.size();
			size_t hashi = hash0;
			size_t i = 1;

			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];//找到了
				}

				//线性探测
				hashi = (hash0 + i) % _tables.size();
				++i;
			}

			return nullptr;//找不到
		}

		//删除
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				ret->_state = DELETE;//伪删除
				--_n;
				return true;
			}
		}

	private:
		vector<HashData<K, V>> _tables;//底层数据结构使用vector
		size_t _n = 0;//表中存储数据个数
	};
}

简单运行测试：

#include <iostream>
#include "HashTable.h"
using namespace std;

int main()
{
	open_address::HashTable<int, int> h1;
	h1.Insert({ 1,1 });
	h1.Insert({ 54,54 });//这两值会产生哈希冲突
	cout << h1.Find(1) << endl;
	cout << h1.Find(54) << endl;

	h1.Erase(1);//删除{1,1}只要对{54,54}没影响就说明删除没问题
	cout << h1.Find(1) << endl;
	cout << h1.Find(54) << endl;

	return 0;
}

运行结果：

• 观察前后地址变化，1的删除没有影响54的地址，可以说明程序无明显问题
• 如果想观察详细的存储信息，可在调试的监视窗口查看。

2.链地址法：

（1）基本框架

//链地址法的命名空间
namespace hash_bucket
{
	//定义哈希数据节点
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			, _next(nullptr)
		{}
	};

	//定义默认仿函数
	template<class K>
	struct HashFunc
	{
		
	};

	//string版的特化仿函数
	template<>
	struct HashFunc<string>
	{
		
	};

	//定义哈希表
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		
	private:
		vector<Node*> _tables;//指针数组
		size_t _n = 0;//有效数据个数
	};
}

• 因为链地址法解决哈希冲突是将冲突值串起来，形成一个链表（单链表），所以链地址法中就不需要定义每个值的状态，但因为需要用到链表，所以HashNode中除了记录数据_kv，还需要记录当前映射位置的下一个节点_next。
• 有了开放定址法的经验，这里就先把仿函数的框架搭出来，这里仿函数的作用和开放地址法是一样的，都是将数据转为可以进行取模计算的整形。
• 哈希表的大框架和开放定址法一样，这里先加上第三个模板参数。

（2）Insert实现，构造函数实现

框架：

//插入
bool Insert(const pair<K, V>& kv)
{
	Hash hs;
	//扩容
	if (_n == _tables.size())
	{

	}

	//除留余数法计算映射位置
	size_t hashi = hs(kv.first) % _tables.size();
	Node* newnode = new Node(kv);//创建新节点

	//头插到哈希桶
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;

	return true;
}

• 先说基本的插入，先计算映射位置hashi，并创建新节点newnode，然后需要注意的是，链地址法中链表的插入是采用头插的方式，对于单链表来说，头插也是最简单的插入方法，我们先将newnode的下一个节点指针指向当前映射位置的链表头节点，然后将链表的头节点位置改为newnode，最后++_n即可。

扩容实现：

	//获取下一个质数
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		static const int __stl_num_primes = 28;//定义质数列表大小
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			53,         97,         193,       389,       769,
			1543,       3079,       6151,      12289,     24593,
			49157,      98317,      196613,    393241,    786433,
			1572869,    3145739,    6291469,   12582917,  25165843,
			50331653,   100663319,  201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};

		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);//返回大于等于n的质数

		return pos == last ? *(last - 1) : *pos;
	}
public:
	//构造
	HashTable()
	{
		_tables.resize(__stl_next_prime(0), nullptr);
	}

	//插入
	bool Insert(const pair<K, V>& kv)
	{
		Hash hs;
		//扩容
		if (_n == _tables.size())
		{
			size_t newSize = __stl_next_prime((unsigned long)(_tables.size() + 1));//新空间大小
			vector<Node*> newTables(newSize, nullptr);//新空间

			//遍历旧表，把旧把数据重新装到新表
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				Node* cur = _tables[i];

				//循环遍历桶
				while (cur)
				{
					Node* next = cur->_next;//先保存一份下一个节点

					//计算新位置
					size_t hashi = hs(cur->_kv.first) % newSize;
					//将cur头插到新表
					cur->_next = newTables[hashi];
					newTables[hashi] = cur;

					cur = next;//接着遍历当前桶（如果还有节点）
				}

				_tables[i] = nullptr;//将旧表置空
			}

			_tables.swap(newTables);//交换
		}

		//除留余数法计算映射位置
		size_t hashi = hs(kv.first) % _tables.size();
		Node* newnode = new Node(kv);//创建新节点

		//头插到哈希桶
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
		++_n;

		return true;
	}

• 首先，我们依旧需要用到__stl_next_prime函数获取下一个质数。
• 然后构造函数，使用vector的resize接口初始化基础空间，大小为第一个质数，然后将其中每个链表初始化为nullptr。
• 接着是关键的insert扩容，前面提到过，链地址法中，负载因子可以大于1，但我们还是将负载因子设定为1，也就是当_n == _tables.size()时进行扩容操作。
• 扩容过程：依旧先计算新空间大小newSize，但与开放定址法不同的是，开放定址法是新建一个哈希表，复用insert然后swap交换，为什么链地址法不行呢，关键就是其中的链表，因为如果将旧链表复制拷贝一份再插入，最后再删掉，这样效率会很低而且链表的析构很麻烦。这里我们采用的方法是：将旧链表中的数据摘下来放到新链表中。我们新建一个vector就行，循环遍历旧表，外循环遍历vector中的每个链表，内循环遍历每个链表具体内容并进行拷贝操作，首先cur先初始化为链表的头节点_tables[i]，然后需要next先保存一份cur的下一个节点，方便单链表遍历，接着计算cur对应值的新映射位置hashi，再将其头插到新vector，注意虽然这样会导致新链表中的数据会颠倒，但是不影响查找。然后每遍历完一个旧链表，我们需将其设置为空，断开其与节点的联系，最后全部转移完成，就使用swap交换新旧表中的vector即可，空vector会随着扩容结束自动析构。

（3）Find

//查找
Node* Find(const K& key)
{
	Hash hs;
	size_t hashi = hs(key) % _tables.size();
	Node* cur = _tables[hashi];

	//遍历桶查找
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return nullptr;
}

• 查找就很简单了，先计算映射位置，然后遍历对应的哈希桶即可。
• 实现Find后，insert就可以补充一个条件，避免冗余值插入：

//插入
bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
		return false;

    //省略...
}

（4）Erase

//删除
bool Erase(const K& key)
{
	Hash hs;
	size_t hashi = hs(key) % _tables.size();//先计算映射位置
	Node* prev = nullptr;//用于记录cur的上一个节点
	Node* cur = _tables[hashi];

	while (cur)
	{
		if (cur->_kv.first == key)
		{
			//头删
			if (prev == nullptr)
			{
				_tables[hashi] = cur->_next;
			}
			else//不是头删
			{
				prev->_next = cur->_next;
			}

            //删除cur
			delete cur;
			--_n;
			return true;
		}

		//如果没找到，继续遍历下一个节点
		prev = cur;
		cur = cur->_next;
	}

	return false;
}

• 这里删除需要注意一下，因为是单链表元素的删除，因此要考虑删除节点对上一个节点的影响。
• 这里定义一个prev用于记录cur的上一个节点，cur遍历哈希桶，当我们找到对应节点时，需要先判断是不是链表的第一个节点，如果prev==nullptr，那么就是，此时需要更改头结点为cur的下一个节点，在删除cur，如果不是头删，则需要将prev指向的节点的_next指针更改为cur的下一个节点，然后再删除cur。记得--_n。如果没找到，则继续遍历下个节点。

（5）析构函数

//析构
~HashTable()
{
	for (size_t i = 0; i < _tables.size(); ++i)
	{
		Node* cur = _tables[i];
		while (cur)
		{
			Node* next = cur->_next;
			delete cur;
			cur = next;
		}
		_tables[i] = nullptr;
	}
}

• 因为涉及自己实现的单链表，所以需要自己实现析构，析构就是遍历释放每一个节点。
• 当然，假如你想实现一个纯粹的这样的哈希表，那么可以使用直接使用 list 容器，也就是将vector中的指针元素用list替代，那么就不用写析构，我们这里自己控制实现单链表是方便后续进一步封装使用。

（6）仿函数

//定义默认仿函数
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

//string版的特化仿函数
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash += e;
			hash *= 131;
		}

		return hash;
	}
};

• 这里仿函数和上面开放定址法一样，就不再赘述了。

（6）完整代码

#pragma once
#include <vector>
#include <algorithm>
using namespace std;

//链地址法的命名空间
namespace hash_bucket
{
	//定义哈希数据节点
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			, _next(nullptr)
		{}
	};

	//定义默认仿函数
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	//string版的特化仿函数
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash += e;
				hash *= 131;
			}

			return hash;
		}
	};

	//定义哈希表
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;

		//获取下一个质数
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			static const int __stl_num_primes = 28;//定义质数列表大小
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
				53,         97,         193,       389,       769,
				1543,       3079,       6151,      12289,     24593,
				49157,      98317,      196613,    393241,    786433,
				1572869,    3145739,    6291469,   12582917,  25165843,
				50331653,   100663319,  201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			const unsigned long* first = __stl_prime_list;
			const unsigned long* last = __stl_prime_list + __stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);//返回大于等于n的质数

			return pos == last ? *(last - 1) : *pos;
		}
	public:
		//构造
		HashTable()
		{
			_tables.resize(__stl_next_prime(0), nullptr);
		}

		//析构
		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		//插入
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			Hash hs;
			//扩容
			if (_n == _tables.size())
			{
				size_t newSize = __stl_next_prime((unsigned long)(_tables.size() + 1));//新空间大小
				vector<Node*> newTables(newSize, nullptr);//新空间

				//遍历旧表，把旧把数据重新装到新表
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];

					//循环遍历桶
					while (cur)
					{
						Node* next = cur->_next;//先保存一份下一个节点

						//计算新位置
						size_t hashi = hs(cur->_kv.first) % newSize;
						//将cur头插到新表
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;//接着遍历当前桶（如果还有节点）
					}

					_tables[i] = nullptr;//将旧表置空
				}

				_tables.swap(newTables);//交换
			}

			//除留余数法计算映射位置
			size_t hashi = hs(kv.first) % _tables.size();
			Node* newnode = new Node(kv);//创建新节点

			//头插到哈希桶
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return true;
		}

		//查找
		Node* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];

			//遍历桶查找
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}

		//删除
		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();//先计算映射位置
			Node* prev = nullptr;//用于记录cur的上一个节点
			Node* cur = _tables[hashi];

			while (cur)
			{
				if (cur->_kv.first == key)
				{
					//头删
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else//不是头删
					{
						prev->_next = cur->_next;
					}

					//删除cur
					delete cur;
					--_n;
					return true;
				}

				//没找到，继续遍历下一个节点
				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<Node*> _tables;//指针数组
		size_t _n = 0;//有效数据个数
	};
}

测试：

#include <iostream>
#include "HashTable.h"
using namespace std;

int main()
{
	hash_bucket::HashTable<int, int> h1;
	h1.Insert({ 1,1 });
	h1.Insert({ 54,54 });//这两值会产生哈希冲突
	cout << h1.Find(1) << endl;
	cout << h1.Find(54) << endl;

	h1.Erase(1);//删除{1,1}只要对{54,54}没影响就说明删除没问题
	cout << h1.Find(1) << endl;
	cout << h1.Find(54) << endl;

	return 0;
}

运行结果：

• 总体上来说，链地址法是比开放定址法更优的，因为它不存在抢占位置的情况，即便在一些极端情况下，比如数据全挂在某一个串上时，此时也有解决方法，比如前面提到的将链表转换为一棵红黑树，那么查找效率就不会很低。

总结

以上就是本文的全部内容了，感谢支持！