c++-第18节-哈希-创新互联

1.unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 $log_{2}^{N}$ ，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，这里只对unordered_map和unordered_set进行介绍，unordered_multimap和unordered_multiset学生可查看文档介绍。

1.1.unordered_set 1.1.1.unordered_set的介绍

unordered_set类的文档介绍：unordered_set - C++ Reference (cplusplus.com)
成都创新互联公司服务项目包括邗江网站建设、邗江网站制作、邗江网页制作以及邗江网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，邗江网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到邗江省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
注：
1. unordered_set是存储key值的关联式容器。 2. 在unordered_set中，key值用于惟一地标识元素。 3. 在内部,unordered_set没有对key按照任何特定的顺序排序, 为了能在常数范围内找到key，unordered_set将相同哈希值的key放在相同的桶中。 4. unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低。 5. 它的迭代器是前向迭代器。

1.1.2.unordered_set的使用

此处只简单演示unordered_set与set的不同，其他接口与set相同，可参考set。
（1）set中的迭代器是双向迭代器，因此set中有begin、end、rbegin、rend函数。unordered_set中的迭代器是单向迭代器，因此unordered_set中有begin、end函数而没有rbegin、rend函数。
（2）set遍历访问的数据是有序的，unordered_set遍历访问的数据是无序的。
（3）set底层是红黑树，其搜索效率为 $O(log_{2}^{N})$ ，unordered_set底层是哈希，其搜索效率为O(1)，如下面代码所示
注：rand函数产生的随机数其实是有限制的，c语言rand函数有一个RAND_MAX，其大只能产生三万多个随机数，因此如果上面的n值很大时，重复的数据是很多的，打印出来的size值（不重复的值）远小于n值。如果想让随机数变得更多可以如下图所示，给rand函数+循环变量i。

1.2.unordered_map 1.2.1.unordered_map的介绍

unordered_map类的文档介绍： unordered_map - C++ Reference (cplusplus.com) 注： 1. unordered_map是存储键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。 2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。 3. 在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。 4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。 5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问 value。 6. 它的迭代器是前向迭代器。

1.2.2.unordered_map的使用

此处只简单演示unordered_map与map的不同，其他接口与map相同，可参考map。
（1）map中的迭代器是双向迭代器，因此map中有begin、end、rbegin、rend函数。unordered_map中的迭代器是单向迭代器，因此unordered_map中有begin、end函数而没有rbegin、rend函数。
（2）map遍历访问的数据是有序的，unordered_map遍历访问的数据是无序的。
（3）map底层是红黑树，其搜索效率为 $O(log_{2}^{N})$ ，unordered_map底层是哈希，其搜索效率为O(1)。

1.3.unordered_multiset和unordered_multimap

unordered_multiset和multiset用法及功能基本相同，unordered_multimap和multimap用法及功能基本相同，下面讲解unordered_multiset、unordered_multimap和multiset、multimap的不同：
（1）multiset、multimap中的迭代器是双向迭代器，因此multiset、multimap中有begin、end、rbegin、rend函数。unordered_multiset、unordered_multimap中的迭代器是单向迭代器，因此unordered_multiset、unordered_multimap中有begin、end函数而没有rbegin、rend函数。
（2）multiset、multimap遍历访问的数据是有序的，unordered_multiset、unordered_multimap遍历访问的数据是无序的。
（3）multiset、multimap底层是红黑树，其搜索效率为 $O(log_{2}^{N})$ ，unordered_multiset、unordered_multimap底层是哈希，其搜索效率为O(1)。

2.底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

2.1.哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度为 $log_{2}^{N}$ ，时间复杂度为 $O(log_{2}^{N})$ ，搜索的效率取决于搜索过程中元素的比较次数。理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。当向该结构中： $\bullet$ 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
$\bullet$ 搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置
取元素比较，若关键码相等，则搜索成功。该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表) 例如：数据集合{1，7，6，4，5，9}；哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？

2.2.哈希冲突

对于两个数据元素的关键字ki和kj(i!=j)，有ki!= kj，但有：Hash(ki)==Hash(kj)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。发生哈希冲突该如何处理呢？

2.3.哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。哈希函数设计原则： $\bullet$ 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间 $\bullet$ 哈希函数计算出来的地址能均匀分布在整个空间中 $\bullet$ 哈希函数应该比较简单

常见哈希函数： 1.直接定址法(常用) 取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况面试题： 387. 字符串中的第一个唯一字符 - 力扣（LeetCode） 2.除留余数法(常用) 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key%p(p<=m),将关键码转换成哈希地址 3.平方取中法(了解) 假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况 4.折叠法(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况 5.随机数法(了解) 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中 random为随机数函数。通常应用于关键字长度不等时采用此法 6.数学分析法(了解) 设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

2.4.哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

2.4.1.闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个”空位置中去。那如何寻找下一个空位置呢？有线性探测和二次探测两种方法。

1. 线性探测比如2.1中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。线性探测找下一个空位置的方法为：Hi= (H0+i)%m 或者 Hi=(H0-i)%m，其中：i = 1,2,3…，H0是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置，m是表的大小。插入： $\bullet$ 通过哈希函数获取待插入元素在哈希表中的位置 $\bullet$ 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素线性探测优点：实现非常简单线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢？使用二次探测可以缓解。

2. 二次探测线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题。二次探测：从发生冲突的位置开始，跳跃向后探测，直到寻找到下一个空位置为止。二次探测找下一个空位置的方法为：Hi= (H0+i^2)%m 或者 Hi=(H0-i^2)%m，其中：i = 1,2,3…，H0是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置，m是表的大小。插入： $\bullet$ 通过哈希函数获取待插入元素在哈希表中的位置 $\bullet$ 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用二次探测找到下一个空位置，插入新元素二次探测的优缺点：二次探测相对线性探测而言减轻了产生数据的“堆积”，但是其本质还是让不同的关键码占据了本属于其他关键码的位置，这样哈希冲突越多，搜索效率还是会降低。

基于线性探测和二次探测的哈希表代码实现 HashTable.h文件：
#pragma once
#includenamespace CloseHash
{
	enum State
	{
		EMPTY,
		EXITS,
		DELETE
	};

	templatestruct HashData
	{
		pair_kv;
		State _state = EMPTY;
	};

	templatestruct DefaultHash
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	template<>struct DefaultHash{
		size_t operator()(const string& key)
		{
			// BKDR
			size_t hash = 0;
			for (auto ch : key)
			{
				hash = hash * 131 + ch;
			}

			return hash;
		}
	};

	template>class HashTable
	{
		typedef HashDataData;
	public:
		bool Insert(const pair& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}

			// 负载因子到0.7及以上，就扩容
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				// 扩容以后，需要重新映射
				HashTablenewHT;
				newHT._tables.resize(newSize);
				// 遍历旧表，插入newHT
				for (auto& e : _tables)
				{
					if (e._state == EXITS)
					{
						newHT.Insert(e._kv);
					}
				}
				newHT._tables.swap(_tables);
			}

			HashFunc hf;
			size_t starti = hf(kv.first);
			starti %= _tables.size();

			size_t hashi = starti;
			size_t i = 1;
			// 线性探测/二次探测
			while (_tables[hashi]._state == EXITS)
			{
				hashi = starti + i;
				++i;
				hashi %= _tables.size();
			}

			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXITS;
			_n++;

			return true;
		}

		Data* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			HashFunc hf;
			size_t starti = hf(key);
			starti %= _tables.size();

			size_t hashi = starti;
			size_t i = 1;
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}

				hashi = starti + i;
				++i;
				hashi %= _tables.size();
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			Data* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}

	private:
		vector_tables;
		size_t _n = 0; // 存储关键字个数
	};
}
注：
1.查找元素x时，首先通过哈希函数获取待插入元素在哈希表中的位置，如果该位置是元素x则找到了，如果该位置不是元素x，则使用对应的探索方式（线性探索或二次探测）依次往后找下一个位置是否是x，如果某一次找到的位置是x则找到了，如果某一次找到的位置是空则找不到。 2.采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。如下图一所示，删除元素4，如果直接删除掉，后面44查找起来可能会受影响。因此应该采用标记的伪删除法来删除一个元素，如下图二所示一个元素有三种状态，要删除某个元素时只改变该元素的状态为DELETE，不删除该元素。
3.如下图所示，在插入函数中，我们使用无符号整型starti来获取对应的值，进而通过哈希函数计算得到要插入的位置。这里哈希函数中，应该用starti去模顺序表vector的size而不是capacity，因为顺序表vector是不能在大于size的位置插入数据的，如果是starti模capacity，得到的结果刚好大于size，是无法插入的。
在插入时，如果哈希函数计算得到位置的状态为空EMPTY或者删除DELETE时，可以进行插入，如果哈希函数计算得到位置的状态为存在EXITS时，则继续探索下一个位置，直到探索到的位置状态为空或删除时再进行插入。
思考：哈希表什么情况下进行扩容？如何扩容？
哈希表HashTable类中，我们利用成员变量_n来记录存储关键字的个数，每次插入一个元素对成员变量_n++，如果_n除以哈希表_tables的大小大于等于0.7则进行扩容。
代码_n/_tables.size()>=0.7是有问题的，因为_n和_tables.size()的返回值都是无符号整型的，应该将其强转成浮点型，这里我们不强转，可以用代码_n*10/_tables.size()>=7间接实现该功能。
哈希表的扩容不是简单的进行扩容，而是应该根据要扩容的大小重新创建一个vector，根据新vector的size大小即扩容后的大小，重新计算原来每一个元素的位置并插入到新vector中，然后释放旧vector。
这里我们可以使用一种简单的方式来实现，创建一个新的哈希表HashTable类对象，遍历旧的vector，将遍历到的每个数据插入到新的哈希表HashTable类对象中，这样在插入的过程中就自动根据扩容后的大小算好了旧表元素在新表中的位置并进行插入操作。最后将新哈希表HashTable类中的vector和我们本身的vector进行交换即可，代码如下图所示。
上面的插入函数代码没有去除数据冗余，适合于multiset和multimap类，在插入时我们可以复用find函数去除数据冗余，这样就适合于set和map类，如下图所示。
4.根据哈希表HashTable插入函数的特点，我们可以知道，哈希表的插入函数效率变化图应该类似于下图所示，正常情况下插入的很快，当某一次插入需要扩容时，效率变得很慢，因为这里扩容不仅仅是空间上进行扩容，每个元素还需要重新进行映射位置，因此时间上也会有损耗。
这就是前面验证set和unordered_set插入、查找、删除效率时，当重复数据多时unordered_set插入效率很高、当重复数据少时unordered_set插入效率低的原因。因为重复数据多时数据量小扩容少，重复数据多时，数据量大扩容多。
5.哈希表HashTable的find查找函数首先通过哈希函数计算出查找数据的位置，如果该位置元素状态不是空并且是要查找的数据则返回该元素的地址，如果该位置元素状态不是空但不是要查找的数据，则依次探索下一个位置，直到探索到某元素状态不是空并且是要查找的数据，返回该元素地址，如果遇到探索位置元素状态为空，则没有要查找的元素返回空指针，代码如下图所示。
上面的代码还有两个问题。第一个问题，如果哈希表为空即_table.size=0，则有starti模0的问题。第二个问题是删除的元素还能被找到，因此我们还需要加一个元素状态不为DELETE的判断。解决两个问题的find函数改进代码如下图所示。
6.哈希表HashTable的erase删除函数只需要复用find函数找到要删除的元素位置，如果找到了要删除的元素位置则将该元素的状态改为DELET进行伪删除并返回true，如果没找到要删除的元素位置则返回false，如下图所示。
7.哈希表HashTable的模板参数K和V的类型不确定，也就是哈希表存储的键值对数据pair的first和second数据类型不确定。参数K的类型不确定，如果我们直接使用size_t starti = kv.first获取插入的值，然后哈希函数计算位置，这样只适合于整型，面对字符串、自定义对象或更复杂的情况如何解决呢？
在哈希表HashTable的模板参数中传一个仿函数类来解决，那么使用者使用哈希表HashTable什么类型的模板参数K，就传对应类型的仿函数类即可，如下图所示。仿函数类对象实现把key元素转换成映射的整数，其中不同的元素尽可能转换成不同的整数（如果不同的元素转换成了相同的整数，那么就会造成访问冲突，访问冲突越多哈希表效率越低）。
我们使用DefaultHash仿函数类作为默认的仿函数类解决参数K为整型的情况如下图所示，如果参数K为整型直接返回对应的整型值即可。
我们使用StringHash仿函数类解决参数K为string类的情况如下图一所示，如果参数K为string类，将字符串每个字符的ASCII码加起来进行返回即可。
博客：各种字符串Hash函数 - clq - 博客园 (cnblogs.com)中提到了很多种更加优秀的匹配string类的仿函数，降低了不同元素转换成相同整数的可能，减少了访问冲突。我们使用其中《The C Programming Language》的方案，如下图二所示。
如果是Student类，仿函数类可以返回学号、身份证、电话号码等，如果没有这些唯一项信息，可以多项拼接，例如班级+名字。
8.库里面的unorder_set、unorder_map、unorder_multiset、unorder_multimap即使是sring类也不需要显式的传仿函数类，如下图一所示，这是因为源代码对默认的仿函数类DefaultHash进行了特化，如下图所示二。
9.哈希表HashTable类中不需要专门去写构造函数、析构函数、拷贝构造函数、赋值运算符重载函数。

补充内容：研究表明当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。因此：闭散列大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

2.4.2 开散列

1. 开散列概念开散列法又叫链地址法(开链法)（哈希桶），首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。如下图所示，数据不存在哈希表中，哈希表中存储的是链表指针，冲突的数据以链表的形式挂起来。开散列中每个桶中放的都是发生哈希冲突的元素。
开散列中使用单链表即可，因为每个桶中的元素顺序没有要求，每次插入元素头插即可，并且单链表中少存一个指针，空间占有更少。

2. 开散列实现 HashTable.h文件：
#pragma once
#includetemplatestruct DefaultHash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};


template<>struct DefaultHash{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : key)
		{
			hash = hash * 131 + ch;
		}

		return hash;
	}
};

namespace Bucket
{
	templatestruct HashNode
	{
		pair_kv;
		HashNode* _next;

		HashNode(const pair& kv)
			:_kv(kv)
			, _next(nullptr)
		{}
	};

	template>class HashTable
	{
		typedef HashNodeNode;
	public:
		~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& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}

			HashFunc hf;

			// 负载因子 == 1 扩容
			if (_tables.size() == _n)
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vectornewTable;
				newTable.resize(newSize, nullptr);
				for (size_t i = 0; i< _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						size_t hashi = hf(cur->_kv.first) % newSize;
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}

					_tables[i] = nullptr;
				}

				newTable.swap(_tables);
			}

			size_t hashi = hf(kv.first);
			hashi %= _tables.size();

			// 头插到对应的桶即可
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			++_n;

			return true;
		}

		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			HashFunc hf;
			size_t hashi = hf(key);
			//size_t hashi = HashFunc()(key);

			hashi %= _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)
		{
			if (_tables.size() == 0)
			{
				return false;
			}

			HashFunc hf;
			size_t hashi = hf(key);
			hashi %= _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;

					return true;
				}

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

			return false;
		}

	private:
		// 指针数组
		vector_tables;
		size_t _n = 0;
	};
}
注：
1.开散列哈希表的insert插入函数，也是首先通过哈希函数计算出要插入元素的位置，如果哈希表vector中该位置桶不为空，则新元素节点头插到该桶中即可，如果哈希表vector中该位置桶为空，则让哈希表vector中该位置桶指针指向新元素节点，新元素节点指向空即可。其实上面两种情况可以用同一段代码解决，如下图所示。开散列的哈希表也需要扩容，如果开散列哈希表不扩容，那么可能存在大量的哈希冲突，每个桶中的链表过长影响效率。开散列的哈希表负载因子可以大一点（负载因子小冲突概率小时间效率高空间效率低，负载因子大冲突概率大时间效率低空间效率高），因为开散列处理哈希冲突直接头插即可效率较高，我们取负载因子为1，下面代码当_tables.size()==_n时扩容，就相当于负载因子为1时扩容。扩容方式可以采取和闭散列相同的扩容方式，如下图所示。
上面这种开散列扩容方式和闭散列扩容方式相同，但是开散列使用这种方式是有缺陷的，开散列使用这种方式那么之前哈希表每个桶中的节点将被释放掉不再使用，然后创建完全相同的节点挂在新的哈希表上。我们在扩容的时候其实不需要创建新的节点而是使用原本的节点即可，如下图所示。
2.开散列哈希表的find查找函数，首先通过哈希函数计算出要插入元素的位置，然后遍历该位置的桶中是否有要找元素，找到对应元素返回该元素节点指针，如果没有找到则返回空指针。如果哈希表最开始里面没有数据时，返回空指针，如下图所示。
3.开散列哈希表的~HashTable析构函数，开散列哈希表需要显式的写析构函数，因为如果使用系统自动生成的析构函数，那么系统会去自动调用vector的析构函数释放指针数组成员变量_tables，但是每个桶中的节点空间并不会自动去释放，造成空间泄漏。因此我们应该显式的写析构函数将每个桶中节点空间释放掉。这样自己写的析构函数将桶结点空间释放掉，系统自动调用vector析构函数将指针数组成员变量_tables空间释放掉。
4.开散列哈希表的Erase删除函数，其正常代码实现如下图所示。
5.开散列哈希表的构造函数不需要显式的写，析构函数需要显式的写，拷贝构造函数和赋值运算符重载函数需要显示的写进行深拷贝（如果不写会调用vector的拷贝构造和赋值运算符重载，vector的拷贝构造和赋值运算符重载是深拷贝，vector里面的数据如果是自定义类型，就会去调用对应的拷贝构造函数，这里vector里面的数据是node*类型，也就是指针类型，是内置类型，对于内置类型vector的拷贝构造和赋值运算符重载是进行浅拷贝，那么拷贝的vector和原vector中的指针数据会指向同一个桶）。这里开散列哈希表的拷贝构造函数和赋值运算符重载函数实现我们不再赘述。
6.和闭散列相同，为了让开散列哈希表支持字符串、自定义对象或更复杂的情况，我们增加一个开散列哈希表HashTable模板参数HashFunc，其缺省值给成DefaultHash，如下图所示。
和闭散列相同，使用DefaultHash仿函数类作为默认的仿函数类，解决参数K为整型的情况，特化一个版本来解决参数K为string类的情况，这里不再赘述。

3.哈希开散列模拟实现STL中的unordered_map与unordered_set 3.1.封装开散列代码，同时实现unordered_map和unordered_set

将开散列进行封装，使之可以同时实现unordered_map和unordered_set
这里与对红黑树RBTree进行封装，使之可以同时实现map和set的思路相同。我们将开散列哈希表中每个桶节点HashNode的数据泛化成其模板参数T类型的成员变量_data，开散列哈希表HashTable的模板参数改为K、T和HashFunc，如下图一所示。
如果是unordered_map，那么哈希表HashTable的第一个模板参数传K，第二个模板参数传pair。如果是unordered_set，那么哈希表HashTable的第一个模板参数传K，第二个模板参数传K。
在unordered_map和unordered_set中，使用开散列哈希表HashTable创建对象，除了第一个模板参数和第二个模板参数传对应的类型外，还需要传MapKeyOfT和SetKeyOfT仿函数类作为key值提取函数，哈希表HashTable的模板参数也同时加上一个KeyOfT参数来获取仿函数类如下图所示。
哈希表HashTable的模板参数HashFunc是一个仿函数类，默认传的是DefaultHash仿函数类，解决K是整型的情况，还有一个特化版本，解决K是string类的情况。如果K是自定义类型的，例如是日期Date类型的，就需要我们自己去传仿函数类给哈希表的模板HashFunc参数。
但是我们使用时只能给unordered_map和unordered_set传模板参数而无法直接给哈希表HashTable传模板参数，所以我们应该给unordered_map和unordered_set加一个模板参数HashFunc来获取用户传的哈希函数，然后unordered_map和unordered_set内部调用哈希表HashTable时再将用户传的哈希函数传给哈希表HashTable即可，如下图所示。

3.2.开散列哈希表的迭代器

unordered_set类代码：
#pragma once

#include "HashTable.h"

namespace bit
{
	template>class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename Bucket::HashTable::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		pairinsert(const K& key)
		{
			return _ht.Insert(key);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
	private:
		Bucket::HashTable_ht;
	};

	struct Date
	{
		Date(int year = 1, int month = 1, int day = 1)
			:_year(year)
			, _month(month)
			, _day(day)
		{}

		bool operator==(const Date& d) const
		{
			return _year == d._year
				&& _month == d._month
				&& _day == d._day;
		}

		int _year;
		int _month;
		int _day;
	};

	struct DateHash
	{
		size_t operator()(const Date& d)
		{
			//return d._year + d._month + d._day;
			size_t hash = 0;
			hash += d._year;
			hash *= 131;
			hash += d._month;
			hash *= 1313;
			hash += d._day;

			//cout<< hash<< endl;

			return hash;
		}
	};

	void test_set()
	{
		unordered_sets;
		s.insert(2);
		s.insert(3);
		s.insert(1);
		s.insert(2);
		s.insert(5);
		s.insert(12);

		//unordered_set::iterator it = s.begin();
		unordered_set::iterator it;
		it = s.begin();

		while (it != s.end())
		{
			cout<< *it<< " ";
			++it;
		}
		cout<< endl;


		for (auto e : s)
		{
			cout<< e<< " ";
		}
		cout<< endl;

		unordered_setsd;
		sd.insert(Date(2022, 3, 4));
		sd.insert(Date(2022, 4, 3));
	}
}
unordered_map类代码：
#pragma once

#include "HashTable.h"

namespace bit
{
	template>class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename Bucket::HashTable, MapKeyOfT, HashFunc>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		pairinsert(const pair& kv)
		{
			return _ht.Insert(kv);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

		V& operator[](const K& key)
		{
			pairret = insert(make_pair(key, V()));
			return ret.first->second;
		}

	private:
		Bucket::HashTable, MapKeyOfT, HashFunc>_ht;
	};

	void test_map()
	{
		unordered_mapdict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("left", "左边"));
		dict.insert(make_pair("left", "剩余"));
		dict["string"];
		dict["left"] = "剩余";
		dict["string"] = "字符串";

		unordered_map::iterator it = dict.begin();
		while (it != dict.end())
		{
			cout<< it->first<< " "<< it->second<< endl;
			++it;
		}

		cout<< endl;

		for (auto& kv : dict)
		{
			cout<< kv.first<< " "<< kv.second<< endl;
		}
	}
}
开散列哈希表迭代器部分代码：
templateclass __HTIterator
{
	typedef HashNodeNode;
	typedef __HTIteratorSelf;
public:
	Node* _node;
	HashTable* _pht;

	__HTIterator() {}

	__HTIterator(Node* node, HashTable* pht)
		:_node(node)
		, _pht(pht)
	{}

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else
		{
			KeyOfT kot;
			HashFunc hf;
			size_t hashi = hf(kot(_node->_data)) % _pht->_tables.size();
			++hashi;
			//找下一个不为空的桶
			for (; hashi< _pht->_tables.size(); ++hashi)
			{
				if (_pht->_tables[hashi])
				{
					_node = _pht->_tables[hashi];
					break;
				}
			}

			// 没有找到不为空的桶，用nullptr去做end标识
			if (hashi == _pht->_tables.size())
			{
				_node = nullptr;
			}
		}

		return *this;
	}

	T& operator*()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
};
注：
1.开散列哈希表迭代器__HTIterator需要一个指针成员变量_node和一个哈希表指针成员变量_pht，指针成员变量_node标识此时迭代器走到的位置，哈希表指针成员变量_pht负责支持实现哈希表迭代器的++功能。
2.哈希表迭代器__HTIterator中实现operator++运算符重载函数，如果迭代器的指针成员变量_node指向节点的下一个节点不是空，则_node=_node->_next指向下一个节点，如果迭代器的指针成员变量_node指向节点的下一个节点是空，则计算此时的桶号hashi，然后往后遍历找到下一个不为空的桶，如果找到了下一个不为空的桶，让_node指向该不为空的桶的第一个节点，如果没找到下一个不为空的桶，也就是后面的桶全为空，那么就给_node赋值为空标识走到了end。
3.哈希表HashTable中begin函数需要找到第一个不为空的桶的第一个节点，找到节点的指针作为_node，this指针指向的哈希表地址正好作为_pht，生成哈希表的迭代器，返回该哈希表的迭代器。如果哈希表为空即找不到第一个不为空的桶则返回end。哈希表HashTable中end函数返回迭代器的_node我们用空指针来标识。begin函数和end函数如下图所示
4.哈希表迭代器__HTIterator中operator*、operator->、operator!=和operator==代码实现如下图所示
5.在unordered_map和unordered_set中要将哈希表的迭代器类型重定义iterator作为自己的迭代器，然后修改并复用哈希表的begin、end、Insert、Find、Erase函数来实现自己的begin、end、insert、find、erase函数功能，并且unordered_map中要复用自己的insert函数实现operator[]运算符重载函数，如下图所示。
这里哈希表的迭代器进行类型重定义时要用typename修饰，原因和红黑树封装map和set那里相同，这里不再赘述。
6.哈希表迭代器__HTIterator中使用了哈希表指针成员变量_pht，而编译器遵循向上查找原则，哈希表是在哈希表迭代器的后面定义的，那么要在哈希表迭代器的前面对哈希表进行声明，如下图所示
7.哈希表迭代器__HTIterator中找下一个不为空的桶时要访问哈希表的私有成员变量_tables，因此我们要将哈希表迭代器设置成哈希表的友元，这里哈希表迭代器__HTIterator和哈希表HashTable都是类模板，类模板要设置友元要加上模板参数部分，如下图所示

3.3.开散列哈希表容量为素数的优化

很多研究证明，哈希表的容量如果是一个素数可以有效降低哈希冲突的概率。
如何保证每一次扩容扩容后的结果都是素数呢？我们观察STL源码中是如何解决的。
如下图所示，源码中给了一个静态的素数表，素数表中每一个数都是素数且后一个数约是前一个数的两倍。
在我们的实现中可以增加一个GetNextPrime函数，找比当前素数值大的下一个素数，用来当作哈希表扩容的大小。其中每个素数后面跟着ul，ul是unsigned long代表该素数是unsigned long类型的。

3.4.开散列哈希表模拟实现STL中unordered_map和unordered_set的代码

UnorderedSet.h文件：

#pragma once

#include "HashTable.h"

namespace bit
{
	template>class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename Bucket::HashTable::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		pairinsert(const K& key)
		{
			return _ht.Insert(key);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
	private:
		Bucket::HashTable_ht;
	};

	struct Date
	{
		Date(int year = 1, int month = 1, int day = 1)
			:_year(year)
			, _month(month)
			, _day(day)
		{}

		bool operator==(const Date& d) const
		{
			return _year == d._year
				&& _month == d._month
				&& _day == d._day;
		}

		int _year;
		int _month;
		int _day;
	};

	struct DateHash
	{
		size_t operator()(const Date& d)
		{
			//return d._year + d._month + d._day;
			size_t hash = 0;
			hash += d._year;
			hash *= 131;
			hash += d._month;
			hash *= 1313;
			hash += d._day;

			//cout<< hash<< endl;

			return hash;
		}
	};

	void test_set()
	{
		unordered_sets;
		s.insert(2);
		s.insert(3);
		s.insert(1);
		s.insert(2);
		s.insert(5);
		s.insert(12);

		//unordered_set::iterator it = s.begin();
		unordered_set::iterator it;
		it = s.begin();

		while (it != s.end())
		{
			cout<< *it<< " ";
			++it;
		}
		cout<< endl;


		for (auto e : s)
		{
			cout<< e<< " ";
		}
		cout<< endl;

		unordered_setsd;
		sd.insert(Date(2022, 3, 4));
		sd.insert(Date(2022, 4, 3));
	}
}

UnorderedMap.h文件：

#pragma once

#include "HashTable.h"

namespace bit
{
	template>class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename Bucket::HashTable, MapKeyOfT, HashFunc>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		pairinsert(const pair& kv)
		{
			return _ht.Insert(kv);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

		V& operator[](const K& key)
		{
			pairret = insert(make_pair(key, V()));
			return ret.first->second;
		}

	private:
		Bucket::HashTable, MapKeyOfT, HashFunc>_ht;
	};

	void test_map()
	{
		unordered_mapdict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("left", "左边"));
		dict.insert(make_pair("left", "剩余"));
		dict["string"];
		dict["left"] = "剩余";
		dict["string"] = "字符串";

		unordered_map::iterator it = dict.begin();
		while (it != dict.end())
		{
			cout<< it->first<< " "<< it->second<< endl;
			++it;
		}

		cout<< endl;

		for (auto& kv : dict)
		{
			cout<< kv.first<< " "<< kv.second<< endl;
		}
	}
}

HashTable.h文件：

#pragma once
#includetemplatestruct DefaultHash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};


template<>struct DefaultHash{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : key)
		{
			hash = hash * 131 + ch;
		}

		return hash;
	}
};

namespace Bucket
{
	templatestruct HashNode
	{
		T _data;
		HashNode* _next;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	templateclass HashTable;

	templateclass __HTIterator
	{
		typedef HashNodeNode;
		typedef __HTIteratorSelf;
	public:
		Node* _node;
		HashTable* _pht;

		__HTIterator() {}

		__HTIterator(Node* node, HashTable* pht)
			:_node(node)
			, _pht(pht)
		{}

		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot;
				HashFunc hf;
				size_t hashi = hf(kot(_node->_data)) % _pht->_tables.size();
				++hashi;
				//找下一个不为空的桶
				for (; hashi< _pht->_tables.size(); ++hashi)
				{
					if (_pht->_tables[hashi])
					{
						_node = _pht->_tables[hashi];
						break;
					}
				}

				// 没有找到不为空的桶，用nullptr去做end标识
				if (hashi == _pht->_tables.size())
				{
					_node = nullptr;
				}
			}

			return *this;
		}

		T& operator*()
		{
			return _node->_data;
		}

		T* operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}

		bool operator==(const Self& s) const
		{
			return _node == s._node;
		}
	};

	// unordered_map ->HashTable, MapKeyOfT>_ht;
	// unordered_set ->HashTable_ht;
	templateclass HashTable
	{
		templatefriend class __HTIterator;

		typedef HashNodeNode;
	public:
		typedef __HTIteratoriterator;

		iterator begin()
		{
			for (size_t i = 0; i< _tables.size(); ++i)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return iterator(cur, this);
				}
			}

			return end();
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

		~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;
			}
		}

		size_t GetNextPrime(size_t prime)
		{
			const int PRIMECOUNT = 28;
			static const size_t primeList[PRIMECOUNT] =
			{
				53ul, 97ul, 193ul, 389ul, 769ul,
				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
				1610612741ul, 3221225473ul, 4294967291ul
			};

			// 获取比prime大那一个素数
			size_t i = 0;
			for (; i< PRIMECOUNT; ++i)
			{
				if (primeList[i] >prime)
					return primeList[i];
			}

			return primeList[i];
		}

		pairInsert(const T& data)
		{
			HashFunc hf;
			KeyOfT kot;

			iterator pos = Find(kot(data));
			if (pos != end())
			{
				return make_pair(pos, false);
			}

			// 负载因子 == 1 扩容
			if (_tables.size() == _n)
			{
				//size_t newSize = _tables.size() == 0 ? 11 : _tables.size() * 2;
				size_t newSize = GetNextPrime(_tables.size());
				if (newSize != _tables.size())
				{
					vectornewTable;
					newTable.resize(newSize, nullptr);
					for (size_t i = 0; i< _tables.size(); ++i)
					{
						Node* cur = _tables[i];
						while (cur)
						{
							Node* next = cur->_next;

							size_t hashi = hf(kot(cur->_data)) % newSize;
							cur->_next = newTable[hashi];
							newTable[hashi] = cur;

							cur = next;
						}

						_tables[i] = nullptr;
					}

					newTable.swap(_tables);
				}
			}

			size_t hashi = hf(kot(data));
			hashi %= _tables.size();

			// 头插到对应的桶即可
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			++_n;

			return make_pair(iterator(newnode, this), false);;
		}

		iterator Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return iterator(nullptr, this);
			}

			KeyOfT kot;
			HashFunc hf;
			size_t hashi = hf(key);
			//size_t hashi = HashFunc()(key);

			hashi %= _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur, this);
				}

				cur = cur->_next;
			}

			return iterator(nullptr, this);
		}

		bool Erase(const K& key)
		{
			if (_tables.size() == 0)
			{
				return false;
			}

			HashFunc hf;
			KeyOfT kot;
			size_t hashi = hf(key);
			hashi %= _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;

					return true;
				}

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

			return false;
		}

	private:
		// 指针数组
		vector_tables;
		size_t _n = 0;
	};
}

test.cpp文件：

#include#include#include#include#include#include#includeusing namespace std;

#include "HashTable.h"
#include "UnorderedMap.h"
#include "UnorderedSet.h"

int main()
{
	bit::test_map();

	return 0;
}

4.哈希的应用 4.1.位图 4.1.1.位图概念

直接建立映射关系的问题：

1.数据范围分布很广、不集中，会导致空间复杂度过大，如何解决？

2.key的数据不是整数，是字符串怎么办？是自定义类型对象怎么办？

3.哈希冲突如何解决？

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

名称栏目：c++-第18节-哈希-创新互联
文章分享：http://scyanting.com/article/ceepoo.html

c++-第18节-哈希-创新互联

其他资讯