C++之哈希

发布于：2025-04-21 ⋅ 阅读:(23) ⋅ 点赞:(0)

目录

一、unordered_set

1.1、unordered_set的介绍

1.2、unordered_set和set的使用差异

二、unordered_map

2.1、unordered_map和map的差异

2.2、unordered_multimap/unordered_multiset 

三、哈希表

3.1、哈希概念

3.1.1、直接定地址法

3.1.2、哈希冲突

3.1.3、负载因子

3.1.4、将关键字转为整数

3.1.5、哈希函数

3.1.5.1、除法散列法/除留余数法

3.1.5.2、乘法散列法（了解）

3.1.5.3、全域散列法（了解）

3.1.6、如何处理哈希冲突

3.1.6.1、开放定址法

3.1.6.2、链地址法

3.2、代码实现

3.2.1、公共部分

3.2.2、开放定址法

3.2.2、链地址法

一、unordered_set

1.1、unordered_set的介绍

unordered_set的声明如下，Key就是unordered_set底层关键字的类型。

  • unordered_set默认要求Key⽀持转换为整形，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现支持将Key转成整形的仿函数传给第⼆个模板参数。
  • unordered_set默认要求Key⽀持⽐较相等，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持将Key⽐较相等的仿函数传给第三个模板参数。
  • unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第四个参数。
  • ⼀般情况下，我们都不需要传后三个模板参数。

unordered_set底层是⽤哈希桶实现，增删查平均效率是O(1)，迭代器遍历不再有序，为了跟set 区分，所以取名unordered_set。

注意：前⾯部分我们已经学习了set容器的使⽤，set和unordered_set的功能⾼度相似，只是底层结构不 同，有⼀些性能和使⽤的差异，这⾥我们只讲他们的差异部分。

1.2、unordered_set和set的使用差异

unordered_set文档：unordered_set - C++ Reference

查看⽂档我们会发现unordered_set⽀持的增删查改跟set的使⽤⼀模⼀样，关于使⽤我们这⾥就不再赘述和演示了。

unordered_set和set的第⼀个差异是对key的要求不同，set要求Key⽀持⼩于⽐较，unordered_set要求Key⽀持转成整形且⽀持等于⽐较，要理解unordered_set的这两点要求需要后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

unordered_set和set的第⼆个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set 是单向迭代器，其次set底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以set迭代器遍历是有序+去重。⽽unordered_set底层是哈希表，迭代器遍历是⽆序+去重。

unordered_set和set的第三个差异是性能的差异，整体⽽⾔⼤多数场景下，unordered_set的增删 查改更快⼀些，因为红⿊树增删查改效率是O(logN)，⽽哈希表增删查平均效率是O(1) ，具体可以参看下⾯代码演示的对⽐差异。

#include<unordered_set>
#include<unordered_map>
#include<set>
#include<iostream>

using namespace std;

int test_set()
{
	const size_t N = 100000;
	unordered_set<int> us;
	set<int> s;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; ++i)
	{
		//v.push_back(rand()); // N⽐较⼤时，重复值⽐较多 
		v.push_back(rand() + i); // 重复值相对少 
		//v.push_back(i); // 没有重复，有序 
	}

	size_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	size_t end1 = clock();
	cout << "set insert:" << end1 - begin1 << endl;
	size_t begin2 = clock();
	us.reserve(N);
	for (auto e : v)
	{
		us.insert(e);
	}
	size_t end2 = clock();
	cout << "unordered_set insert:" << end2 - begin2 << endl;
	int m1 = 0;
	size_t begin3 = clock();
	for (auto e : v)
	{
		auto ret = s.find(e);
		if (ret != s.end())
		{
			++m1;
		}
	}
	size_t end3 = clock();
	cout << "set find:" << end3 - begin3 << "->" << m1 << endl;
	int m2 = 0;
	size_t begin4 = clock();
	for (auto e : v)
	{
		auto ret = us.find(e);
		if (ret != us.end())
		{
			++m2;
		}
	}
	size_t end4 = clock();
	cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;
	cout << "插入数据个数：" << s.size() << endl;
	cout << "插入数据个数：" << us.size() << endl << endl;
	size_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end5 = clock();
	cout << "set erase:" << end5 - begin5 << endl;
	size_t begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	size_t end6 = clock();
	cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
	return 0;
}

int main()
{
	test_set();

	return 0;
}

代码效果：

从上面代码中可以看到unordered_set的效率是要比set的效率要高的。

二、unordered_map

2.1、unordered_map和map的差异

unordered_map声明如下图：

unordered_map文档：unordered_map - C++ Reference

查看⽂档我们会发现unordered_map⽀持的增删查改跟map的使⽤⼀模⼀样，关于使⽤我们这⾥就不再赘述和演⽰了。

  • unordered_map和map的第⼀个差异是对key的要求不同，map要求Key⽀持⼩于⽐较，⽽ unordered_map要求Key⽀持转成整形且⽀持等于⽐较，要理解unordered_map的这两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。
  • unordered_map和map的第⼆个差异是迭代器的差异，map的iterator是双向迭代器，而unordered_map是单向迭代器，其次map底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有 序的，所以map迭代器遍历是Key有序+去重。⽽unordered_map底层是哈希表，迭代器遍历是 Key⽆序+去重。
  • unordered_map和map的第三个差异是性能的差异，整体⽽⾔⼤多数场景下，unordered_map的增删查改更快⼀些，因为红⿊树增删查改效率是O(logN)，⽽哈希表增删查平均效率是O(1) ， 具体和unordered_set那里类似，这里就不演示了。

2.2、unordered_multimap/unordered_multiset 

unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似，⽀持Key冗余。

unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个⽅⾯的差异， key的要求的差异，iterator及遍历顺序的差异，性能的差异。

三、哈希表

3.1、哈希概念

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

3.1.1、直接定地址法

当关键字的范围⽐较集中时，直接定址法就是⾮常简单⾼效的⽅法，⽐如⼀组关键字都在[0,99]之间， 那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置的下标。再⽐如⼀组关键字值都在 [a,z]的⼩写字⺟，那么我们开⼀个26个数的数组，每个关键字acsii码减去 a 的 ascii码就是存储位置的下标。 也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置。不过直接定地址法也存在缺陷。

3.1.2、哈希冲突

直接定址法的缺点⾮常明显，当关键字的范围⽐较分散时，数据的存储就会相对分散，就很浪费内存甚⾄内存不够⽤。假设我们只有数据范围是[0,9999]的N个值，在不浪费空间的情况下，我们要映射到⼀个M个空间的数组中(⼀般情况下M >=N)，那么就要借助哈希函数(hash function)hf，计算出关键字key被放到数组的h(key)位置，这⾥要注意的是h(key)计算出的值必须在[0, M)之间。

借助哈希函数存在的⼀个问题就是，两个不同的key可能会映射到同⼀个位置去，这种问题我们叫做哈希冲突， 或者哈希碰撞。理想情况是找出⼀个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的， 所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的⽅案。

3.1.3、负载因子

假设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，那么 负载因子 = N/M，负载因⼦有些地⽅也翻译为载荷因⼦/装载因⼦等，他的英⽂为load factor。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低。

3.1.4、将关键字转为整数

我们将关键字映射到数组中位置，⼀般是整数好做映射计算，如果不是整数，我们要想办法转换成整数。所以下⾯哈希函数部分我们讨论时，如果关键字不是整数，那么我们讨论的Key是关键字转换成的整数。

3.1.5、哈希函数

3.1.5.1、除法散列法/除留余数法

除法散列法也叫做除留余数法，顾名思义，假设哈希表的⼤⼩为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。

当使⽤除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等。如果是2^{x}，那么 key % 2^{x} 本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就冲突了。如： {63,31}看起来没有关联的值，如果M是16，也就是2^{4} ，那么计算出的哈希值都是15，因为63的⼆ 进制后8位是00111111，31的⼆进制后8位是00011111。如果是10^{x} ，就更明显了，保留的都是 10进值的后x位，如：{112,12312}，如果M是100，也就是10^{2}，那么计算出的哈希值都是12。

当使⽤除法散列法时，建议M取不太接近2的整数次幂的⼀个质数(素数)。

3.1.5.2、乘法散列法（了解）

乘法散列法对哈希表⼤⼩ M 没有要求，他的⼤思路第⼀步：⽤关键字 K 乘上常数A (0 < A < 1)，并抽出 K*A 的小数部分。第二部：再用 M 乘以 K*A 的小数部分，在向下取整。

h(key) = floor(M × ((A × key)%1.0))，其中 floor 表⽰对表达式进⾏下取整，A∈(0,1)，这⾥最重要的是A的值应该如何设定，Knuth认为 A = ( \sqrt{5} − 1)/2 = 0.6180339887.... (⻩⾦分割点]) ⽐较好。

乘法散列法对哈希表⼤⼩ M 是没有要求的，假设 M 为1024，key为1234，A = 0.6180339887， A*key  = 762.6539420558，取小数部分为0.6539420558，M*((A*key)%1.0) = 669.6366651.392  ，那么h(1234) = 669。

3.1.5.3、全域散列法（了解）

如果存在⼀个恶意的对⼿，他针对我们提供的散列函数，特意构造出⼀个发⽣严重冲突的数据集， ⽐如，让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定 的，就可以实现此攻击。解决⽅法⾃然是⻅招拆招，给散列函数增加随机性，攻击者就⽆法找出确 定可以导致最坏情况的数据。这种⽅法叫做全域散列。

h_{ab}(key) = ((a × key + b)%P )%M，P需要选⼀个⾜够⼤的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了⼀个P*(P-1)组全域散列函数组。 假设P=17，M=6，a=3，b=4,则h_{34} (8) = ((3*8+4)%17)%6=5。

需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使⽤，后续增删查 改都固定使⽤这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插⼊是⼀个散列函数， 查找⼜是另⼀个散列函数，就会导致找不到插⼊的key了。

3.1.6、如何处理哈希冲突

实践中哈希表⼀般还是选择除法散列法作为哈希函数，当然哈希表⽆论选择什么哈希函数也避免不了冲突，那么插⼊数据时，如何解决冲突呢？主要有两种⽅法，开放定址法和链地址法。

3.1.6.1、开放定址法

在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于1的。这⾥的规则有三种：线性探测、⼆次探测、双重探测。

线性探测：

从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛ 到哈希表尾，则回绕到哈希表头的位置。

h(key) = hash0 =  key % M，hash0位置冲突了，则线性探测公式为：

hc(key,i) = hashi = (hash0 + i) % M， i  =  {1, 2, 3, ..., M − 1}，因为负载因⼦⼩于1， 则最多探测M-1次，⼀定能找到⼀个存储key的位置。

线性探测⽐较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1， hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位 置，这种现象叫做群集/堆积。下⾯的⼆次探测可以⼀定程度改善这个问题。

下⾯演⽰ {19,30,5,36,13,20,21,12} 等这⼀组值映射到M=11的表中。

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) = 10，h(12) = 1

二次探测：

从发⽣冲突的位置开始，依次左右按⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为 ⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表 尾的位置；

h(key) = hash0 =  key % M，hash0位置冲突了，则⼆次探测公式为：

hc(key,i) = hashi = (hash0 ± i^{2} ) % M， i  =  {1, 2, 3, ..., M/2 }

⼆次探测当 hashi = (hash0 − i^{2} )%M 时，当 hashi < 0 时，需要hashi += M

下⾯演⽰ {19,30,52,63,11,22} 等这⼀组值映射到M=11的表中。

经过计算：h(19) = 8, h(30) = 8, h(52) = 8, h(63) = 8, h(11) = 0, h(22) = 0

双重散列（了解）：

第⼀个哈希函数计算出的值发⽣冲突，使⽤第⼆个哈希函数计算出⼀个跟key相关的偏移量值，不 断往后探测，直到寻找到下⼀个没有存储数据的位置为⽌。

h_{1}(key) = hash0 =  key % M，hash0位置冲突了，则双重探测公式为：

h_{c}(key,i) = hashi = (hash0 +  i ∗ h_{2}(key)) % M， i  =  {1, 2, 3, ..., M}

要求h_{2}(key) < M且h_{2}(key)和M互为质数，有两种简单的取值⽅法：1、当M为2整数幂时，h_{2}(key)

从[0，M-1]任选⼀个奇数；2、当M为质数时h_{2}(key)  =  key % (M − 1)  +  1

保证 h_{2}(key)与M互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群，若最⼤公约数 p = gcd(M, h1(key)) > 1，那么所能寻址的位置的个数为 M/P < M ，使得对于⼀个关键字来说⽆法充分利⽤整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表⼤⼩为12， 那么所能寻址的位置为{1,4,7,10}，寻址个数为 12/gcd(12, 3) = 4

下⾯演⽰ {19,30,52,74} 等这⼀组值映射到M=11的表中，设 h_{2}(key)  =  key%10 + 1

开放定址法在实践中，不如下⾯讲的链地址法，因为开放定址法解决冲突不管使⽤哪种⽅法，占⽤的都是哈希表中的空间，始终存在互相影响的问题。所以开放定址法，后面我们只简单实现线性探测方法。

开放定址法的哈希表结构注意点：

哈希表结构中需要给每个存储值的位置加⼀个状态标识，否则删除⼀些值以后，会影响后⾯冲突的值的查找。如下图，我们删除30，会导致查找20失败，当我们给每个位置加⼀个状态标识{EXIST,EMPTY,DELETE} 删除30就可以不⽤删除值，⽽是把状态改为 DELETE，那么查找20 时是遇到EMPTY才能，就可以找到20。

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) = 10，h(12) = 1

扩容问题：

这⾥我们哈希表负载因⼦控制在0.7，当负载因⼦到0.7以后我们就需要扩容了，我们还是按照2倍扩容，但是同时我们要保持哈希表⼤⼩是⼀个质数，第⼀个是质数，2倍后就不是质数了。那么如何解决呢，⼀种⽅案是sgi版本的哈希表使⽤的⽅法，给了⼀个近似2倍的质数表，每次去质数表获取扩容后的⼤⼩。

Key不能取模的问题：

当key是string/Date等类型时，key不能取模，那么我们需要给HashTable增加⼀个仿函数，这个仿函数⽀持把key转换成⼀个可以取模的整形，如果key可以转换为整形并且不容易冲突，那么这个仿函数就⽤默认的即可，如果这个Key不能转换为整形，我们就需要⾃⼰实现⼀个仿函数传入，实现这个仿函数的要求就是尽量key的每值都参与到计算中，让不同的key转换出的整形值不同。string 做哈希表的key⾮常常⻅，所以我们可以考虑把string特化⼀下。

3.1.6.2、链地址法

解决冲突的思路：

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

下⾯演⽰ {19,30,5,36,13,20,21,12,24,96} 等这⼀组值映射到M=11的表中。

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) = 10，h(12) = 1,h(24) = 2,h(96) = 88

扩容：

开放定址法负载因⼦必须⼩于1，链地址法的负载因⼦就没有限制了，可以⼤于1。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低；stl中unordered_map/set的最⼤负载因⼦基本控制在1，⼤于1就扩容，我们下⾯实现也使⽤这个⽅式。

极端场景：

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

3.2、代码实现

3.2.1、公共部分

template<class K>
struct HashFunc //将非整形数据转换为整形
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

//string不支持强转，但又比较常见作为Key
//所以直接特化一个版本出来
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t hashi = 0;
		for (auto e : s)
		{
			hashi *= 31;
			hashi += e;
		}

		return hashi;
	}
};

3.2.2、开放定址法

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 Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

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

			//负载因子 == 0.7  扩容
			if (_n * 10 / _tables.size() > 7)
			{
				//vector<HashData<K, V>> newTables(_tables.size() * 2);
				遍历旧表，将所有数据重新映射到新表
				......还需要重新写一遍插入逻辑，麻烦
				//_tables.swap(newTables);

				HashTable<K, V, Hash> newHT;
				newHT._tables.resize(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._state == EXIST)
					{
						newHT.Insert(_tables[i]._kv); //复用插入数据的逻辑
					}
				}
				_tables.swap(newHT._tables);
			}

			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state != DELETE
					&& _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}
				++hashi;
				hashi %= _tables.size();
			}

			return nullptr;
		}

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

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0; //当前有效数据个数
	};

	void TestHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 11,21,4,14,24,15,9 };
		for (auto e : a)
		{
			ht.Insert({ e,e });
		}

		ht.Insert({ 19,19 });
		ht.Insert({ 19,190 });
		ht.Insert({ 19,1900 });
		ht.Insert({ 39,1900 });

		//cout << ht.Find(24) << endl;
		//ht.Erase(4);
		//cout << ht.Find(24) << endl;
		//cout << ht.Find(4) << endl;
	}

	//不特化情况下可以自己写一个合适的传入
	//一般自己定义的自定义类型需要自己写
	struct StringHashFunc
	{
		size_t operator()(const string& s)
		{
			size_t hashi = 0;
			for (auto e : s)
			{
				hashi *= 31;
				hashi += e;
			}

			return hashi;
		}
	};

	void TestHT2()
	{
		HashTable<string, string> ht;
		ht.Insert({ "sort", "排序" });
		ht.Insert({ "left", "左边" });

		//string s1("sort");
		//string s2("sort");

		cout << StringHashFunc()("bacd") << endl;
		cout << StringHashFunc()("abcd") << endl;
		cout << StringHashFunc()("aadd") << endl;
	}
}

3.2.2、链地址法

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, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		typedef HashNode<K, V> Node;

		HashTable()
		{
			_tables.resize(10, 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)
		{
			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();

			//负载因子==1  扩容
			if (_n == _tables.size())
			{
				// 需要新建节点和释放旧节点，效率较低
				//	HashTable<K, V, Hash> newHT;
				//	for (size_t i = 0; i < _tables.size(); i++)
				//	{
				//		Node* cur = _tables[i];
				//		while (cur)
				//		{
				//			newHT.Insert(cur->_kv);
				//			cur = cur->_next;
				//		}
				//	}

				//	_tables.swap(newHT._tables);

				vector<Node*> newtables(_tables.size() * 2, 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) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}

					//节点都挪到新表上了，旧表置空
					_tables[i] = nullptr;
				}

				_tables.swap(newtables);
			}

			//头插
			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;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		//这样写也可以，但是后面封装迭代器有点麻烦
		//vector<list<pair<K, V>>> _tables;  // 指针数组

		vector<Node*> _tables; //指针数组
		size_t _n; //表中存储数据个数

		//优化，当数据量小的时候用链表，当数据量大的时候用红黑树
		//union list_map  //用联合体可以进一步节省空间
		// {
		//	 list<pair<K, V>> _lt;
		//	 map<K, V> _m;
		// } 
		//struct Bucket
		//{
		//  list_map _lm
		//	size_t _bucketsize;   // >8 map  <=8 list
		//};
		//vector<Bucket> _tables;
	};

	void TestHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 11,21,4,14,24,15,9,19,29,39 };
		for (auto e : a)
		{
			ht.Insert({ e,e });
		}

		ht.Insert({ -6, 6 });

		for (auto e : a)
		{
			ht.Erase(e);
		}
	}

	void TestHT2()
	{
		HashTable<string, string> ht;
		ht.Insert({ "sort", "排序" });
		ht.Insert({ "left", "左边" });
	}
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布