devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++数据结构：哈希桶 -- 通过开散列的方法解决哈希冲突_哈希冲突的解决方法,哈希桶是什么

作者：花生_TL007 | 2024-05-16 13:16:11

赞

踩

哈希冲突的解决方法,哈希桶是什么

目录

一. 什么是哈希桶

二. 哈希桶的实现

2.1 哈希表节点数据

2.2 特定Key值的查找find

2.3 哈希桶的扩容

2.4 数据插入操作insert

2.5 数据删除操作erase

2.6 哈希桶的析构函数 

附录：哈希桶的实现完整版代码

一. 什么是哈希桶

之前的博客中我提到过，可以采用闭散列（二次探测、线性探测）的方法来解决哈希冲突，但是，无论是线性探测还是二次探测，其解决哈希冲突的本质方法都是去“占位”，即：发生哈希冲突的Key会去占用其他Key值原本应当占用的位置，这样一个冲突可能引发一串冲突。

为了解决闭散列方法的上述弊端，可以使用哈希桶（开散列）的方法来解决哈希冲突。在hashTable的每个位置都挂一个哈希桶，哈希桶用单链表来表示。将所有发生冲突的数据都挂在一个桶上。

此时，hashTable存储的数据类型时单链表节点，hashTable[i]是每个哈希桶的头结点，发生冲突时的数据插入相当于单链表的头插操作。

图1.1 哈希桶结构图

二. 哈希桶的实现

2.1 哈希表节点数据

由于哈希桶的本质是挂在哈希表上的单链表，因此，哈希表节点的数据应当为单链表节点，包括：

  • 一个键值对pair<K, V> _kv，记录key值和与之配对的value值。
  • 一个节点指针_next，指向单链表的下一个节点。

在Hash类模板中，将hashDate<K, V>类型重定义为Node。

代码2.1：（哈希表节点）

  1. template<class K, class V>
  2. struct hashDate
  3. {
  4. 	std::pair<K, V> _kv;
  5. 	hashDate<K, V>* _next;
  6.  
  7. 	hashDate(const std::pair<K, V>& kv)
  8. 		: _kv(kv)
  9. 		, _next(nullptr)
  10. 	{ }
  11. };

2.2 特定Key值的查找find

函数Node* find(const K& key)，找到了返回key所在的节点地址，找不到返回nullptr。

  1. 通过哈希函数，获取key所在的哈希桶应当挂在_hashTable哪个下标位置处(记为hashi)。
  2. 遍历以_hashTable[hashi]为头结点的单链表，查找key，找到了返回链表节点。
  3. 如果遍历到nullptr还没找到，则表示key不存在于哈希桶中，函数返回false。

代码2.2：（find函数的实现）

  1. 	Node* find(const K& key)
  2. 	{
  3. 		//哈希表中没有数据就直接返回false
  4. 		//这里是为了避免模0(%0)错误
  5. 		if (_hashTable.size() == 0)
  6. 		{
  7. 			return nullptr;
  8. 		}
  9.  
  10. 		HashKey hashKey;
  11. 		//通过哈希函数计算key所在哈希桶
  12. 		size_t hashi = hashKey(key) % _hashTable.size();  
  13. 		//哈希桶单链表头结点
  14. 		Node* cur = _hashTable[hashi];
  15.  
  16. 		//变量哈希桶（单链表），寻找key
  17. 		while (cur)
  18. 		{
  19. 			if (hashKey(cur->_kv.first) == hashKey(key))
  20. 			{
  21. 				return cur;
  22. 			}
  23.  
  24. 			cur = cur->_next;
  25. 		}
  26.  
  27. 		return nullptr;
  28. 	}

2.3 哈希桶的扩容

如果通过闭散列（线性探测或二次探测）的方法来解决哈希冲突，那么哈希表中存储的数据个数_size一定不能超过_table.size()。但是如果使用哈希桶，哈希表的每个位置挂的哈希桶可以有多个数据，因此负载因子是可以大于1的。

闭散列一般当负载因子大于0.7~0.8是扩容，而哈希桶则应适度提高。可以认为当插入数据后负载因子大于1就扩容。

哈希桶扩容同样需要改变原来的结构，因为不同的Key值对于的存储位置会发生改变。这里不再复用insert函数来实现数据位置的改变，而是依次遍历每个哈希桶的每个节点，创建一个新的vector作为hashTable，通过单链表头插，来使数据满足扩容后的哈希结构要求。

图2.3 扩容前后哈希桶结构的变化

代码2.3：（哈希表扩容） 

  1. 		//扩容(负载因子大于1)
  2. 		if (_hashTable.size() == 0 || _size == _hashTable.size())
  3. 		{
  4. 			size_t newSize = _hashTable.size() == 0 ? 10 : 2 * _hashTable.size();
  5.  
  6. 			//将原来哈希表数据的位置进行相应改变
  7. 			//这里使用一个新的vector来实现
  8. 			std::vector<Node*> newTable;
  9. 			newTable.resize(newSize, nullptr);
  10.  
  11. 			//将原来table每个位置处挂的单链表，挪到新的table对应位置
  12. 			for (size_t i = 0; i < _hashTable.size(); ++i)
  13. 			{
  14. 				Node* cur = _hashTable[i];
  15.  
  16. 				while (cur)
  17. 				{
  18. 					Node* next = cur->_next;
  19. 					size_t newHashi = hashKey(cur->_kv.first) % newSize;
  20.  
  21. 					//执行头插操作
  22. 					cur->_next = newTable[newHashi];
  23. 					newTable[newHashi] = cur;
  24.  
  25. 					cur = next;
  26. 				}
  27.  
  28. 				_hashTable[i] = nullptr;
  29. 			}
  30.  
  31. 			_hashTable.swap(newTable);
  32. 		}

2.4 数据插入操作insert

哈希桶是挂在hashTable指定位置处的单链表。进行数据插入时，只需在检查数据是否已经存在、是否需要扩容之后，要通过哈希函数Hash(Key)找到对应的位置，然后执行单链表头插操作即可。

图2.4 数据插入操作

2.5 数据删除操作erase

通过哈希函数获得哈希桶的位置后，遍历单链表（哈希桶）找到key所在的位置，执行单链表节点删除操作即可。

代码2.5：（数据删除）

  1. 	bool erase(const K& key)
  2. 	{
  3. 		if (_hashTable.size() == 0)
  4. 		{
  5. 			return false;
  6. 		}
  7.  
  8. 		HashKey hashKey;
  9.  
  10. 		size_t hashi = hashKey(key) % _hashTable.size();
  11. 		Node* prev = nullptr;
  12. 		Node* cur = _hashTable[hashi];
  13.  
  14. 		while (cur)
  15. 		{
  16. 			//找到key了，删除
  17. 			if (hashKey(cur->_kv.first) == key)
  18. 			{
  19. 				//头删
  20. 				if (prev == nullptr)
  21. 				{
  22. 					_hashTable[hashi] = cur->_next;
  23. 					free(cur);
  24. 					cur = nullptr;
  25. 				}
  26. 				else  //中间删或尾删
  27. 				{
  28. 					prev->_next = cur->_next;
  29. 					free(cur);
  30. 					cur = nullptr;
  31. 				}
  32.  
  33. 				--_size;
  34. 				return true;
  35. 			}
  36.  
  37. 			prev = cur;
  38. 			cur = cur->_next;
  39. 		}
  40.  
  41. 		return false;
  42. 	}

2.6 哈希桶的析构函数 

自己编写代码，依次对每个哈希桶进行释放，每个哈希桶的析构等同于单链表的析构。由于vector为自定义类型数据，编译的会主动调用vector的析构函数释放hashTable的空间。

代码2.6：（析构函数）

  1. 	~Hash()   //析构函数
  2. 	{
  3. 		//释放每个节点上挂的数据
  4. 		for (size_t i = 0; i < _hashTable.size(); ++i)
  5. 		{
  6. 			Node* cur = _hashTable[i];
  7.  
  8. 			//释放每个非空节点
  9. 			while (cur)
  10. 			{
  11. 				Node* next = cur->_next;
  12. 				delete cur;
  13. 				cur = next;
  14. 			}
  15.  
  16. 			_hashTable[i] = nullptr;
  17. 		}
  18. 	}

附录：哈希桶的实现完整版代码

  1. #include<vector>
  2.  
  3. template<class K, class V>
  4. struct hashDate
  5. {
  6. 	std::pair<K, V> _kv;
  7. 	hashDate<K, V>* _next;
  8.  
  9. 	hashDate(const std::pair<K, V>& kv)
  10. 		: _kv(kv)
  11. 		, _next(nullptr)
  12. 	{ }
  13. };
  14.  
  15. template<class K>
  16. struct HashKeyVal
  17. {
  18. 	size_t operator()(const K& key)
  19. 	{
  20. 		return (size_t)key;
  21. 	}
  22. };
  23.  
  24. template<class K, class V, class HashKey = HashKeyVal<K>>
  25. class Hash
  26. {
  27. 	typedef hashDate<K, V> Node;
  28.  
  29. public:
  30. 	~Hash()   //析构函数
  31. 	{
  32. 		//释放每个节点上挂的数据
  33. 		for (size_t i = 0; i < _hashTable.size(); ++i)
  34. 		{
  35. 			Node* cur = _hashTable[i];
  36.  
  37. 			//释放每个非空节点
  38. 			while (cur)
  39. 			{
  40. 				Node* next = cur->_next;
  41. 				delete cur;
  42. 				cur = next;
  43. 			}
  44.  
  45. 			_hashTable[i] = nullptr;
  46. 		}
  47. 	}
  48.  
  49. 	bool insert(const std::pair<K, V>& kv)
  50. 	{
  51. 		//查找 -- 确保不插入重复数据
  52. 		if (find(kv.first))
  53. 		{
  54. 			return false;
  55. 		}
  56.  
  57. 		HashKey hashKey;
  58.  
  59. 		//扩容(负载因子大于1)
  60. 		if (_hashTable.size() == 0 || _size == _hashTable.size())
  61. 		{
  62. 			size_t newSize = _hashTable.size() == 0 ? 10 : 2 * _hashTable.size();
  63.  
  64. 			//将原来哈希表数据的位置进行相应改变
  65. 			//这里使用一个新的vector来实现
  66. 			std::vector<Node*> newTable;
  67. 			newTable.resize(newSize, nullptr);
  68.  
  69. 			//将原来table每个位置处挂的单链表，挪到新的table对应位置
  70. 			for (size_t i = 0; i < _hashTable.size(); ++i)
  71. 			{
  72. 				Node* cur = _hashTable[i];
  73.  
  74. 				while (cur)
  75. 				{
  76. 					Node* next = cur->_next;
  77. 					size_t newHashi = hashKey(cur->_kv.first) % newSize;
  78.  
  79. 					//执行头插操作
  80. 					cur->_next = newTable[newHashi];
  81. 					newTable[newHashi] = cur;
  82.  
  83. 					cur = next;
  84. 				}
  85.  
  86. 				_hashTable[i] = nullptr;
  87. 			}
  88.  
  89. 			_hashTable.swap(newTable);
  90. 		}
  91.  
  92. 		//获取插入位置
  93. 		size_t hashi = hashKey(kv.first) % _hashTable.size();
  94. 		Node* node = new Node(kv);
  95.  
  96. 		//插入数据
  97. 		node->_next = _hashTable[hashi];
  98. 		_hashTable[hashi] = node;
  99.  
  100. 		++_size;
  101. 	}
  102.  
  103. 	bool erase(const K& key)
  104. 	{
  105. 		if (_hashTable.size() == 0)
  106. 		{
  107. 			return false;
  108. 		}
  109.  
  110. 		HashKey hashKey;
  111.  
  112. 		size_t hashi = hashKey(key) % _hashTable.size();
  113. 		Node* prev = nullptr;
  114. 		Node* cur = _hashTable[hashi];
  115.  
  116. 		while (cur)
  117. 		{
  118. 			//找到key了，删除
  119. 			if (hashKey(cur->_kv.first) == key)
  120. 			{
  121. 				//头删
  122. 				if (prev == nullptr)
  123. 				{
  124. 					_hashTable[hashi] = cur->_next;
  125. 					free(cur);
  126. 					cur = nullptr;
  127. 				}
  128. 				else  //中间删或尾删
  129. 				{
  130. 					prev->_next = cur->_next;
  131. 					free(cur);
  132. 					cur = nullptr;
  133. 				}
  134.  
  135. 				--_size;
  136. 				return true;
  137. 			}
  138.  
  139. 			prev = cur;
  140. 			cur = cur->_next;
  141. 		}
  142.  
  143. 		return false;
  144. 	}
  145.  
  146. 	Node* find(const K& key)
  147. 	{
  148. 		//哈希表中没有数据就直接返回false
  149. 		//这里是为了避免模0(%0)错误
  150. 		if (_hashTable.size() == 0)
  151. 		{
  152. 			return nullptr;
  153. 		}
  154.  
  155. 		HashKey hashKey;
  156. 		//通过哈希函数计算key所在哈希桶
  157. 		size_t hashi = hashKey(key) % _hashTable.size();  
  158. 		//哈希桶单链表头结点
  159. 		Node* cur = _hashTable[hashi];
  160.  
  161. 		//变量哈希桶（单链表），寻找key
  162. 		while (cur)
  163. 		{
  164. 			if (hashKey(cur->_kv.first) == hashKey(key))
  165. 			{
  166. 				return cur;
  167. 			}
  168.  
  169. 			cur = cur->_next;
  170. 		}
  171.  
  172. 		return nullptr;
  173. 	}
  174.  
  175. private:
  176. 	size_t _size = 0;   //哈希表中数据个数
  177. 	std::vector<Node*> _hashTable;   //哈希表（存储桶节点）
  178. };
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/578904
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号