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

C++数据结构——哈希桶HashBucket_c++哈希桶

作者：weixin_40725706 | 2024-07-17 03:57:08

赞

踩

c++哈希桶

目录

一、前言

1.1 闭散列

1.2 开散列

1.3 string 与 非 string 

二、哈希桶的构成

2.1 哈希桶的节点

2.2 哈希桶类

三、 Insert 函数

3.1 无需扩容时

3.2 扩容

复用 Insert：

逐个插入：

优缺点比对：

第一种写法优点

第一种写法缺点

第二种写法优点

第二种写法缺点

3.3 完整代码

四、 Erase 函数

4.1 析构函数

4.2 Erase 函数

五、 Find 函数

六、完整代码 

一、前言

上一篇文章讲的哈希表，属于闭散列。可以解决哈希冲突有两种方式：闭散列和开散列。现在要学习的哈希桶就是开散列。

1.1 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

1.2 开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地
址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链
接起来，各链表的头结点存储在哈希表中。

下面则是即将学习的哈希桶的简易图：

类似于一个数组中存了若干个链表头，每个头所代表的链表成为一个桶。

1.3 string 与 非 string 

在上一篇博客的最后：哈希表HashTable-CSDN博客
探讨过当 Key 为负数、浮点数、字符串...时，类函数逻辑中有关 Key 取模的问题，当 Key 为负数、浮点数、字符、字符串时，显然这几个内置类型无法完成取模的操作，这时就用到了仿函数，这里不再多说，直接来看仿函数的代码，下面会直接使用仿函数来完成 HashBucket

  1. template<class T>
  2. class HashFunc<>
  3. {
  4.     size_t operator()(const T& Key)
  5.     {
  6.         return (size_t)Key;
  7.     }
  8. }
  9. template<>
  10. class HashFunc<string>
  11. {
  12.     size_t operator()(const string& Key)
  13.     {
  14.         size_t hash = 0;
  15.         for (auto ch : Key)
  16.         {
  17.             hash *= 131;
  18.             hash += ch;
  19.         }
  20.         return hash;
  21.     }
  22. }

二、哈希桶的构成

2.1 哈希桶的节点

由上图就可以看出来，每个结点必要存一个 pair 和一个指向下一个节点的指针 _next。

  1. template<class K, class V>
  2. struct HashNode
  3. {
  4.     pair<K, V> _kv;
  5.     HashNode* _next;
  6. }

2.2 哈希桶类

哈希桶类的构成和哈希表类似，都是一个由一个 vector 存放每个节点，但是这里与 HashTable 不同的是需要存放的是节点的指针。还有一个 _n 代表有效数据的个数：

  1. template<class K, class V, class Hash = HashFunc<K>>
  2. class HashBucket
  3. {
  4.     typedef HashNode Node;
  5. private:
  6.     vector<Node*> _bucket;
  7.     size_t _n;
  8. };

三、 Insert 函数

3.1 无需扩容时

下面要介绍的是不需要扩容时的插入逻辑：

此时只需要使用 Key 模数组的大小来计算出该节点需要连接在 vector 上的位置，然后使用 new 得到储存 kv 的新节点，当 new 一个新节点时，节点的构造函数必不可少，下面先来看一下单个节点的构造函数以及类的构造函数：

  1. template<class K, class V>
  2. struct HashNode
  3. {
  4. 	pair<K, V> _kv;
  5. 	HashNode* _next;
  6. 	HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr)
  7. 	{}
  8. };
  9. template<class K, class V, class Hash = HashFunc<K>>
  10. class HashBucket
  11. {    
  12.     typedef HashNode<K, V> Node;
  13.     HashBucket()
  14.     {
  15.         _bucket.resize(10, nullptr);
  16.         _n = 0;
  17.     }
  18. private:
  19.     vector<Node*> _bucket;
  20.     size_t _n;
  21. }

此时需要思考的是，既然 vector 每个节点都要存放一个链表，那么链表头插还是尾插的效率更高呢？

显然是头插，所以这个新结点就需要以类似头插的方式添加到 vector 的这个位置上，

  1. bool Insert(const pair<K, V>& kv)
  2. {
  3.     Hash hs;
  4.     size_t index = hs(kv.first) % _bucket.size(); 
  5.     Node* newnode = new Node(kv);
  6.     newnode->_next = _bucket[index];
  7.     _buckte[index] = newnode;
  8.     ++_n;
  9.     return true;
  10. }

3.2 扩容

这里的载荷因子可以直接设为1，至于载荷因子是什么，可以查看上一篇博客哈希表HashTable-CSDN博客，在扩容中的何时扩容标题下，介绍了载荷因子的概念。

在扩容中，既可以使用 HashTable 中类似的写法直接复用 Insert ，也可以直接挨个让节点插入，下面先介绍每种方式，再进行优缺点的处理：

复用 Insert：

  1. bool Insert(const pair<K, V>& kv)
  2. {
  3.     Hash hs;
  4.     if (_n == _bucket.size())
  5.     {
  6.         HashBucket newHB = new HashBucket;
  7.         newHB._bucket.resize(_bucket.size() * 2, nullptr);
  8.         for (size_t i = 0; i < _bucket.size(); i++)
  9.         {
  10.             Node* cur = _bucket[i];
  11.             while(cur)
  12.             {
  13.                 Node* next = cur->_next;  // 保存下一个节点指针
  14. 			    newHB.Insert(cur->_kv);   // 插入当前节点的键值对到新哈希表
  15. 				cur = next;               // 移动到下一个节点
  16.             }
  17.             _bucket[i] = nullptr;
  18.         }
  19.         _bucket.swap(newHB);
  20.     }
  21. }

逐个插入：

  1. bool Insert(const pair<K, V>& kv)
  2. {
  3.     Hash hs;
  4. 	if (_n == _bucket.size())
  5. 	{
  6. 		vector<Node*> newBucket(_bucket.size() * 2, nullptr);
  7. 		for (size_t i = 0; i < _bucket.size(); i++)
  8. 		{
  9. 			Node* cur = _bucket[i];
  10. 			while (cur)
  11. 			{
  12. 				Node* next = cur->_next;
  13. 				size_t index = hs(cur->_kv.first) % newBucket.size();
  14. 				cur->_next = newBucket[index];
  15. 				newBucket[index] = cur;
  16. 				cur = next;
  17. 			}
  18. 			_bucket[i] = nullptr;
  19. 		}
  20. 		_bucket.swap(newBucket);
  21. 	}
  22. }

优缺点比对：

第一种写法优点
  1. 代码复用：通过调用 newHB.Insert(cur->_kv) 来重新插入节点，重用了 Insert 方法，减少了代码重复。
  2. 逻辑清晰：将旧节点迁移到新桶中，然后交换桶，逻辑分离清晰。
第一种写法缺点
  1. 性能：因为每次扩容时调用 Insert，可能会多次计算哈希值和处理冲突，性能可能稍差。
第二种写法优点
  1. 性能：直接处理节点迁移，无需调用 Insert 方法，减少了函数调用和重复计算，提高了性能。
  2. 直接操作：直接操作指针，代码简洁，性能高效。
第二种写法缺点
  1. 代码重复：需要手动处理节点迁移逻辑，代码重复。
  2. 复杂性：直接操作指针可能增加代码的复杂性，增加错误的可能性。

3.3 完整代码

  1.     bool Insert(const pair<K, V>& kv)
  2. 	{
  3. 		if (Find(kv.first)) return false;
  4. 		Hash hs;
  5. 		if (_n == _bucket.size())
  6. 		{
  7. 			HashBucket newHB;
  8. 			newHB._bucket.resize(_bucket.size() * 2, nullptr);
  9. 			for (size_t i = 0; i < _bucket.size(); i++)
  10. 			{
  11. 				Node* cur = _bucket[i];
  12. 				while (cur)
  13. 				{
  14. 					Node* next = cur->_next;  // 保存下一个节点指针
  15. 					newHB.Insert(cur->_kv);   // 插入当前节点的键值对到新哈希表
  16. 					cur = next;               // 移动到下一个节点
  17. 				}
  18. 				_bucket[i] = nullptr;
  19. 			}
  20. 			_bucket.swap(newHB._bucket);
  21. 		}
  22. 		size_t index = hs(kv.first) % _bucket.size();
  23. 		Node* newnode = new Node(kv);
  24. 		newnode->_next = _bucket[index];
  25. 		_bucket[index] = newnode;
  26. 		++_n;
  27. 		return true;
  28. 	}
  29.     bool Insert(const pair<K, V>& kv)
  30. 	{
  31. 		if (Find(kv.first)) return false;
  32. 		Hash hs;
  33. 		if (_n == _bucket.size())
  34. 		{
  35. 			vector<Node*> newBucket(_bucket.size() * 2, nullptr);
  36. 			for (size_t i = 0; i < _bucket.size(); i++)
  37. 			{
  38. 				Node* cur = _bucket[i];
  39. 				while (cur)
  40. 				{
  41. 					Node* next = cur->_next;
  42.  
  43. 					size_t index = hs(cur->_kv.first) % newBucket.size();
  44. 					cur->_next = newBucket[index];
  45. 					newBucket[index] = cur;
  46.  
  47. 					cur = next;
  48. 				}
  49. 				_bucket[i] = nullptr;
  50. 			}
  51. 			_bucket.swap(newBucket);
  52. 		}
  53. 		size_t index = hs(kv.first) % _bucket.size();
  54. 		Node* newnode = new Node(kv);
  55. 		newnode->_next = _bucket[index];
  56. 		_bucket[index] = newnode;
  57. 		++_n;
  58. 		return true;
  59. 	}

四、 Erase 函数

4.1 析构函数

根据 Insert 函数中，可以得知， HashBucket 的每个节点都是 new 出来的，那删除的时候就要使用 delete ，又因为每个节点都是自定义类型，所以要为 HashBucket 写一个析构函数。
对类的析构就是遍历 vector 的每个节点，再从每个节点遍历每个链表，以此遍历全部节点。

  1.     ~HashBucket()
  2. 	{
  3. 		for (size_t i = 0; i < _bucket.size(); i++)
  4. 		{
  5. 			Node* cur = _bucket[i];
  6. 			while (cur)
  7. 			{
  8. 				Node* next = cur->_next;
  9. 				delete cur;
  10. 				cur = next;
  11. 			}
  12. 			_bucket[i] = nullptr;
  13. 		}
  14. 	}

4.2 Erase 函数

下面介绍一下Erase函数的步骤：

  1. 计算哈希值：使用哈希函数 hs 计算给定键 Key 的哈希值，并确定它在桶中的索引 index。

  2. 遍历链表：从索引 index 开始，遍历链表中的每个节点。

  3. 查找节点：检查当前节点的键是否等于 Key。

    • 如果找到匹配节点：
      • 如果该节点是链表的第一个节点，将桶的头指针 _bucket[index] 指向下一个节点。
      • 否则，将前一个节点的 _next 指针指向当前节点的下一个节点。
      • 删除当前节点 cur，释放内存。
      • 返回 true，表示删除成功。
    • 如果没有找到匹配节点，继续遍历链表，更新 prev 和 cur。

  4. 返回结果：如果遍历完整个链表未找到匹配节点，返回 false，表示删除失败。

  1.     bool Erase(const K& Key)
  2. 	{
  3. 		Hash hs;
  4. 		size_t index = hs(Key) % _bucket.size();
  5. 		Node* cur = _bucket[index];
  6. 		Node* prev = nullptr;
  7. 		while (cur)
  8. 		{
  9. 			if (cur->_kv.first == Key)
  10. 			{
  11. 				//删除的是第一个节点
  12. 				if (prev == nullptr)
  13. 				{
  14. 					_bucket[index] = cur->_next;
  15. 				}
  16. 				else
  17. 				{
  18. 					prev->_next = cur->_next;
  19. 				}
  20. 				delete cur;
  21. 				return true;
  22. 			}
  23. 			else
  24. 			{
  25. 				prev = cur;
  26. 				cur = cur->_next;
  27. 			}
  28. 		}
  29. 		return false;
  30. 	}

五、 Find 函数

这里的 Find 函数与 HashTable 中的 Find 函数逻辑略有不同，因为这里如果发送哈希冲突，那么存储的位置还是 vector 中取模后的位置，不需要像 HashTable 那样进行线性探测，只需要取一个指针挨个遍历位于 _bucket[index] 链表上的节点即可。

  1.     Node* Find(const K& Key)
  2. 	{
  3. 		if (_bucket.empty()) return nullptr;
  4. 		Hash hs;
  5. 		size_t index = hs(Key) % _bucket.size();
  6. 		Node* cur = _bucket[index];
  7. 		while (cur)
  8. 		{
  9. 			if (cur->_kv.first == Key)
  10. 				return cur;
  11. 			else cur = cur->_next;
  12. 		}
  13. 		return nullptr;
  14. 	}

写完 Find 后，还可以进一步改进 Insert 函数，在插入时可以先进行查找，如果存在，那就插入失败；如果不存在，再继续插入。这样避免了哈希桶中数据冗余的结果。

六、完整代码 

  1. #pragma once
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5.  
  6. using namespace std;
  7.  
  8. template<class K>
  9. struct HashFunc
  10. {
  11. 	size_t operator()(const K& Key)
  12. 	{
  13. 		return (size_t)Key;
  14. 	}
  15. };
  16.  
  17. template<>
  18. struct HashFunc<string>
  19. {
  20. 	size_t operator()(const string& Key)
  21. 	{
  22. 		size_t hash = 0;
  23. 		for (auto ch : Key)
  24. 		{
  25. 			hash *= 131;
  26. 			hash += ch;
  27. 		}
  28. 		return hash;
  29. 	}
  30. };
  31.  
  32. template<class K, class V>
  33. struct HashNode
  34. {
  35. 	pair<K, V> _kv;
  36. 	HashNode* _next;
  37. 	HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr)
  38. 	{}
  39. };
  40.  
  41. template<class K, class V, class Hash = HashFunc<K>>
  42. class HashBucket
  43. {
  44.     typedef HashNode<K, V> Node;
  45. public:
  46. 	HashBucket()
  47. 	{
  48. 		_bucket.resize(10, nullptr);
  49. 		_n = 0;
  50. 	}
  51. 	~HashBucket()
  52. 	{
  53. 		for (size_t i = 0; i < _bucket.size(); i++)
  54. 		{
  55. 			Node* cur = _bucket[i];
  56. 			while (cur)
  57. 			{
  58. 				Node* next = cur->_next;
  59. 				delete cur;
  60. 				cur = next;
  61. 			}
  62. 			_bucket[i] = nullptr;
  63. 		}
  64. 	}
  65. 	bool Insert(const pair<K, V>& kv)
  66. 	{
  67. 		if (Find(kv.first)) return false;
  68. 		Hash hs;
  69. 		if (_n == _bucket.size())
  70. 		{
  71. 			vector<Node*> newBucket(_bucket.size() * 2, nullptr);
  72. 			for (size_t i = 0; i < _bucket.size(); i++)
  73. 			{
  74. 				Node* cur = _bucket[i];
  75. 				while (cur)
  76. 				{
  77. 					Node* next = cur->_next;
  78.  
  79. 					size_t index = hs(cur->_kv.first) % newBucket.size();
  80. 					cur->_next = newBucket[index];
  81. 					newBucket[index] = cur;
  82.  
  83. 					cur = next;
  84. 				}
  85. 				_bucket[i] = nullptr;
  86. 			}
  87. 			_bucket.swap(newBucket);
  88. 		}
  89. 		size_t index = hs(kv.first) % _bucket.size();
  90. 		Node* newnode = new Node(kv);
  91. 		newnode->_next = _bucket[index];
  92. 		_bucket[index] = newnode;
  93. 		++_n;
  94. 		return true;
  95. 	}
  96. 	bool Insert(const pair<K, V>& kv)
  97. 	{
  98. 		if (Find(kv.first)) return false;
  99. 		Hash hs;
  100. 		if (_n == _bucket.size())
  101. 		{
  102. 			HashBucket newHB;
  103. 			newHB._bucket.resize(_bucket.size() * 2, nullptr);
  104. 			for (size_t i = 0; i < _bucket.size(); i++)
  105. 			{
  106. 				Node* cur = _bucket[i];
  107. 				while (cur)
  108. 				{
  109. 					Node* next = cur->_next;  // 保存下一个节点指针
  110. 					newHB.Insert(cur->_kv);   // 插入当前节点的键值对到新哈希表
  111. 					cur = next;               // 移动到下一个节点
  112. 				}
  113. 				_bucket[i] = nullptr;
  114. 			}
  115. 			_bucket.swap(newHB._bucket);
  116. 		}
  117. 		size_t index = hs(kv.first) % _bucket.size();
  118. 		Node* newnode = new Node(kv);
  119. 		newnode->_next = _bucket[index];
  120. 		_bucket[index] = newnode;
  121. 		++_n;
  122. 		return true;
  123. 	}
  124. 	bool Erase(const K& Key)
  125. 	{
  126. 		Hash hs;
  127. 		size_t index = hs(Key) % _bucket.size();
  128. 		Node* cur = _bucket[index];
  129. 		Node* prev = nullptr;
  130. 		while (cur)
  131. 		{
  132. 			if (cur->_kv.first == Key)
  133. 			{
  134. 				//删除的是第一个节点
  135. 				if (prev == nullptr)
  136. 				{
  137. 					_bucket[index] = cur->_next;
  138. 				}
  139. 				else
  140. 				{
  141. 					prev->_next = cur->_next;
  142. 				}
  143. 				delete cur;
  144. 				return true;
  145. 			}
  146. 			else
  147. 			{
  148. 				prev = cur;
  149. 				cur = cur->_next;
  150. 			}
  151. 		}
  152. 		return false;
  153. 	}
  154. 	Node* Find(const K& Key)
  155. 	{
  156. 		if (_bucket.empty()) return nullptr;
  157. 		Hash hs;
  158. 		size_t index = hs(Key) % _bucket.size();
  159. 		Node* cur = _bucket[index];
  160. 		while (cur)
  161. 		{
  162. 			if (cur->_kv.first == Key)
  163. 				return cur;
  164. 			else cur = cur->_next;
  165. 		}
  166. 		return nullptr;
  167. 	}
  168. private:
  169. 	vector<Node*> _bucket;
  170. 	size_t _n;
  171. };
  172. void TestHB1()
  173. {
  174. 	int ret[] = {5, 15, 3, 12, 13, 31};
  175. 	HashBucket<int, int> hb;
  176. 	
  177. 	for (auto e : ret)
  178. 	{
  179. 		hb.Insert(make_pair(e, e));
  180. 	}
  181. 	cout << hb.Erase(0) << endl;
  182. 	cout << hb.Erase(5) << endl;
  183. }
  184. void TestHB2()
  185. {
  186. 	HashBucket<string, int> hb;
  187. 	hb.Insert(make_pair("sort", 1));
  188. 	hb.Insert(make_pair("left", 1));
  189. 	hb.Insert(make_pair("insert", 1));
  190.  
  191. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/837861
推荐阅读
相关标签

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

  

闽ICP备14008679号