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

【C++】哈希

作者：Monodyee | 2024-04-20 00:10:47

赞

踩

【C++】哈希

1. unordered系列关联式容器

STL提供了底层为红黑树结构的一系列关联式容

这里介绍 unordered_set 和 unordered_map

a. unordered_map

  1. unordered_map 是存储<key, value>键值对的关联式容器，其允许通过 key 快速的索引到与

其对应的 value

  1. unordered_map 容器通过 key 访问单个元素要比 map 快，但它通常在遍历元素子集的范围迭

代方面效率较低

  1. unordered_map 实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value
  2. 它的迭代器至少是前向迭代器
  3. 重复数据可以去重

b. unordered_set

  1. unordered_set 允许通过 key 快速的索引是否存在
  2. 重复数据可以去重
  3. 删除，查找，插入，效率都很快

2. unordered_map 的接口说明

a. unordered_map 的容量

函数声明

1. bool empty() const

2. size_t size() const

功能介绍

1. 检测unordered_map是否为空

2. 获取unordered_map的有效元素个数

b. unordered_map 的迭代器

函数声明

1. iterator begin()

2. iterator end()

3. iterator cbegin() const

4. iterator cend() const

功能介绍

1. 返回 unordered_map 第一个元素的迭代器

2. 返回 unordered_map 最后一个元素下一个位置的迭代器

3. 返回 unordered_map 第一个元素的const迭代器

4. 返回 unordered_map 最后一个元素下一个位置的const迭代器

c. unordered_map 的元素访问

函数声明

1. K& operator[]

功能介绍

1. 返回与 key 对应的 value ，允许被修改

d. unordered_map 的查询

函数声明

1. iterator find(const K& key)

2. size_t count(const K& key)

功能介绍

1. 返回key在哈希桶中的位置

2. 返回哈希桶中关键码为key的键值对的个数

注意：

unordered_map 中 key 是不能重复的，因此 count函数的返回值最大为 1

e. unordered_map 的桶操作

函数声明

1. size_t bucket_count() const

2. size_t bucket_size(size_t n) const

3. size_t bucket(const K& key)

功能介绍

1. 返回哈希桶中桶的总个数

2. 返回n号桶中有效元素的总个数

3. 返回元素key所在的桶号

注意：

unordered_set 用法差不多，就不介绍了

3. 哈希概念

通过位置关系找到对应的 key

a. 哈希冲突解决

先说上述问题的解决：

设插入的值为 key，n 为数组的大小

hashi (数组下标) = key % n (若 key 不为整数， 另做处理)

但是在插入的过程中，我们容易遇到以下问题：

  1. hashi 已经有数值存入 （这种问题又叫 哈希冲突 ）

第一种方法：（闭散列）

如果是这种情况，直接往后找，直到遇到空位置 （数组里面存入什么值都很难表示这个位置的状态，所以我们自己可以加入）

     2. 所有的位置都有没有位置了

这种问题一定要涉及到空间的开辟 （但是这里我们需要谈论的是什么时候扩空间比较好）

注意：

这种分情况，后面实现再讲

另外一种方法解决（开散列）：

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地

址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链

接起来，各链表的头结点存储在哈希表中

4. 闭散列实现

代码

 

  1. enum State
  2. {
  3. 	Empty,
  4. 	Exist,
  5. 	Delete
  6. };
  7. template<class K,class V>
  8. struct HashTable
  9. {
  10. 	pair<K,V> _table;
  11. 	State _state = Empty;
  12. };
  13. template<class K, class V>
  14. class Hsah
  15. {
  16. public:
  17. 	bool insert(const pair<K, V>& kv)
  18. 	{
  19. 		if (_t.size() == 0 || n * 10 / _t.size() >= 7)
  20. 		{
  21. 			Hsah<K, V> x;
  22. 			size_t size = _t.size() == 0 ? 10 : _t.size() * 2;
  23. 			x._t.resize(size);
  24. 			for (auto i : _t)
  25. 			{
  26. 				if (i._state == Exist)
  27. 				{
  28. 					x.insert(i._table);
  29. 				}
  30. 			}
  31. 			_t.swap(x._t);
  32.  
  33. 		}
  34. 		size_t hashi = kv.first % _t.size();
  35. 		int index = hashi;
  36. 		size_t i = 1;
  37. 		while (_t[index]._state != Empty)
  38. 		{
  39. 			index = hashi + i;
  40. 			index %= _t.size();
  41. 			i++;
  42. 		}
  43. 		_t[index]._table = kv;
  44. 		_t[index]._state = Exist;
  45. 		n++;
  46. 		return true;
  47. 	}
  48. 	HashTable<K, V>* find(const K& key)
  49. 	{
  50. 		if (_t.size() == 0)
  51. 		{
  52. 			return nullptr;
  53. 		}
  54. 		size_t hashi = key % _t.size();
  55. 		int index = hashi;
  56. 		size_t i = 1;
  57. 		while (_t[index]._state != Empty)
  58. 		{
  59. 			if (_t[index]._table.first == key)
  60. 			{
  61. 				if (_t[index]._state == Delete)
  62. 				{
  63. 					return nullptr;
  64. 				}
  65. 				return &_t[index];
  66. 			}
  67. 			index = hashi + i;
  68. 			index %= _t.size();
  69. 			i++;
  70. 			if (index == hashi)
  71. 			{
  72. 				break;
  73. 			}
  74. 		}
  75. 		return nullptr;
  76. 		
  77. 		
  78. 	}
  79. 	bool Erase(const K& key)
  80. 	{
  81. 		HashTable<K, V>* t = find(key);
  82. 		if (t == nullptr || t->_state == Delete)
  83. 		{
  84. 			return false;
  85. 		}
  86. 		t->_state = Delete;
  87. 	}
  88. private:
  89. 	size_t n = 0;
  90. 	vector<HashTable<K,V>> _t;
  91. };

5. 开散列实现

代码

  1. template<class K, class V>
  2. struct HashNode
  3. {
  4. 	HashNode(const pair<K, V>& kv)
  5. 		:_kv(kv)
  6. 		,next(nullptr)
  7. 	{}
  8. 	HashNode<K, V>* next;
  9. 	pair<K, V> _kv;
  10. };
  11. template<class K, class V>
  12. class HashBucket
  13. {
  14. public:
  15. 	typedef  HashNode<K, V>  Node;
  16. 	void insert(const pair<K, V>& kv)
  17. 	{
  18. 		if (n == _hash.size())
  19. 		{
  20. 			size_t newsize = _hash.size() == 0 ? 10 : _hash.size() * 2;
  21. 			vector<Node*> newnode(newsize, nullptr);
  22. 			for (auto cur : _hash)
  23. 			{
  24. 				while (cur)
  25. 				{
  26. 					int hashi = cur->_kv.first % newsize;
  27. 					Node* prev = newnode[hashi];
  28. 					newnode[hashi] = cur;
  29. 					cur->next = prev;
  30. 					cur = cur->next;
  31. 				}
  32. 			}
  33. 			_hash.swap(newnode);
  34. 		}
  35. 		int hashi = kv.first % _hash.size();
  36. 		Node* cur = new Node(kv);
  37. 		Node* _next = _hash[hashi];
  38. 		_hash[hashi] = cur;
  39. 		cur->next = _next;
  40. 		n++;
  41. 	}
  42. 	bool find(const K& key)
  43. 	{
  44. 		if (_hash.size() == 0)
  45. 		{
  46. 			return false;
  47. 		}
  48. 		int hashi = key % _hash.size();
  49. 		Node* cur = _hash[hashi];
  50. 		while (cur)
  51. 		{
  52. 			if (cur->_kv.first = key)
  53. 			{
  54. 				return true;
  55. 			}
  56. 			cur = cur->next;
  57. 		}
  58. 		return false;
  59. 	}
  60. 	Node* erase(const K& key)
  61. 	{
  62. 		int hashi = key % _hash.size();
  63. 		Node* prev = nullptr;
  64. 		Node* cur = _hash[hashi];
  65. 		while (cur)
  66. 		{
  67. 			if (cur->_kv.first = key)
  68. 			{
  69. 				if (prev == nullptr)
  70. 				{
  71. 					_hash[hashi] = cur->next;
  72. 				}
  73. 				else
  74. 				{
  75. 					prev->next = cur->next;
  76. 				}
  77. 				delete cur;
  78. 				break;
  79. 				
  80. 			}
  81. 			prev = cur;
  82. 			cur = cur->next;
  83. 		}
  84. 		return nullptr;
  85. 	}
  86. private:
  87. 	size_t n = 0;
  88. 	vector<Node*> _hash;
  89. };

//这里插入选择了头插

6. unordered_map , unordered_set 底层实现

代码

“test.h” :

  1. #pragma once
  2. template<class K>
  3. struct Compare
  4. {
  5. 	size_t operator()(const K& key)
  6. 	{
  7. 		return key;
  8. 	}
  9. };
  10. template<>
  11. struct Compare<string>
  12. {
  13. 	size_t operator()(const string& k)
  14. 	{
  15. 		size_t x = 0;
  16. 		for (auto i : k)
  17. 		{
  18. 			x += i;
  19. 			x *= 31;
  20. 		}
  21. 		return x;
  22. 	}
  23. };
  24. namespace unordered
  25. {
  26. 	template<class K, class T>
  27. 	struct HashNode
  28. 	{
  29. 		HashNode(const T& data)
  30. 			:_data(data)
  31. 			, next(nullptr)
  32. 		{}
  33. 		HashNode<K, T>* next;
  34. 		T _data;
  35. 	};
  36.  
  37. 	template<class K, class T, class Key0f, class compare>
  38. 	class HashBucket;
  39.  
  40. 	template<class K, class T,class Ref,class Ptr, class Key0f, class compare>
  41. 	struct HashIterator
  42. 	{
  43. 		
  44. 		typedef  typename HashIterator<K, T,Ref,Ptr, Key0f, compare> Self;
  45. 		typedef  HashNode<K, T>  Node;
  46. 		HashIterator(Node* hash,const HashBucket<K, T, Key0f, compare>* x)
  47. 			:_node(hash)
  48. 			,p(x)
  49. 		{}
  50. 		Self& operator++()
  51. 		{
  52. 			
  53. 			if (_node->next)
  54. 			{
  55. 				_node = _node->next;
  56. 			}
  57. 			else
  58. 			{
  59. 				Key0f kf;
  60. 				int hashi = compare()(kf(_node->_data)) % (p->_hash.size());
  61. 				++hashi;
  62. 				while (hashi < p->_hash.size())
  63. 				{
  64. 					if (p->_hash[hashi])
  65. 					{
  66. 						_node = p->_hash[hashi];
  67. 						break;
  68. 					}
  69. 					else
  70. 					{
  71. 						++hashi;
  72. 					}
  73. 				}
  74. 				if (hashi == p->_hash.size())
  75. 				{
  76. 					_node = nullptr;
  77. 				}
  78. 			}
  79. 			return *this;
  80. 		}
  81. 		Ref operator*()
  82. 		{
  83. 			return _node->_data;
  84. 		}
  85. 		Ptr operator->()
  86. 		{
  87. 			return  &_node->_data;
  88. 		}
  89. 		bool operator!=(const Self& ptr)
  90. 		{
  91. 			return _node != ptr._node;
  92. 		}
  93. 		const HashBucket<K, T, Key0f, compare>* p;
  94. 		Node* _node;
  95. 	};
  96. 	template<class K, class T, class Key0f, class compare>
  97. 	class HashBucket
  98. 	{
  99. 		template <class K, class T,class Ref,class Ptr, class Key0f, class compare>
  100. 		friend class HashIterator;
  101. 	public:
  102. 		
  103. 		typedef  HashNode<K, T>  Node;
  104. 		typedef typename HashBucket<K, T, Key0f, compare> Self;
  105. 		typedef typename HashIterator<K, T,T& ,T* ,Key0f, compare> Iterator;
  106. 		typedef typename HashIterator<K,T,const T&, const T*, Key0f, compare> const_Iterator;
  107. 		Iterator begin()
  108. 		{
  109. 			for (int i = 0; i < _hash.size(); i++)
  110. 			{
  111. 				if (_hash[i])
  112. 				{
  113. 					return Iterator(_hash[i], this);
  114. 				}
  115. 			}
  116. 			return end();
  117. 		}
  118. 		const_Iterator begin() const
  119. 		{
  120. 			for (int i = 0; i < _hash.size(); i++)
  121. 			{
  122. 				if (_hash[i])
  123. 				{
  124. 					return const_Iterator(_hash[i], this);
  125. 				}
  126. 			}
  127. 			return end();
  128. 		}
  129.  
  130. 		Iterator end()
  131. 		{
  132. 			return Iterator(nullptr, this);
  133. 		}
  134. 		const_Iterator end() const
  135. 		{
  136. 			return const_Iterator(nullptr, this);
  137. 		}
  138. 		pair<Iterator,bool> insert(const T& data)
  139. 		{
  140. 			Key0f kf;
  141. 			Iterator it = find(kf(data));
  142. 			if (it != Iterator(nullptr,this))
  143. 			{
  144. 				return make_pair(it, false);
  145. 			}
  146. 			if (n == _hash.size())
  147. 			{
  148. 				size_t newsize = _hash.size() == 0 ? 10 : _hash.size() * 2;
  149. 				vector<Node*> newnode(newsize, nullptr);
  150. 				for (auto cur : _hash)
  151. 				{
  152. 					while (cur)
  153. 					{
  154. 						int hashi = compare()(kf(cur->_data)) % newsize;
  155. 						Node* prev = newnode[hashi];
  156. 						newnode[hashi] = cur;
  157. 						cur->next = prev;
  158. 						cur = cur->next;
  159. 					}
  160. 				}
  161. 				_hash.swap(newnode);
  162. 			}
  163. 			int hashi = compare()(kf(data)) % _hash.size();
  164. 			Node* cur = new Node(data);
  165. 			Node* _next = _hash[hashi];
  166. 			_hash[hashi] = cur;
  167. 			cur->next = _next;
  168. 			n++;
  169. 			return make_pair(Iterator(cur,this), true);
  170. 		}
  171. 		Iterator find(const K& key)
  172. 		{
  173. 			Key0f kf;
  174. 			if (_hash.size() == 0)
  175. 			{
  176. 				return Iterator(nullptr,this);
  177. 			}
  178. 			int hashi = compare()(key) % _hash.size();
  179. 			Node* cur = _hash[hashi];
  180. 			while (cur)
  181. 			{
  182. 				if (kf(cur->_data) == key)
  183. 				{
  184. 					return Iterator(cur, this);
  185. 				}
  186. 				cur = cur->next;
  187. 			}
  188. 			return Iterator(nullptr, this);
  189. 		}
  190. 		T* erase(const K& key)
  191. 		{
  192. 			Key0f kf;
  193. 			int hashi = compare()(key) % _hash.size();
  194. 			Node* prev = nullptr;
  195. 			Node* cur = _hash[hashi];
  196. 			while (cur)
  197. 			{
  198. 				if (kf(cur->_data) == key)
  199. 				{
  200. 					if (prev == nullptr)
  201. 					{
  202. 						_hash[hashi] = cur->next;
  203. 					}
  204. 					else
  205. 					{
  206. 						prev->next = cur->next;
  207. 					}
  208. 					delete cur;
  209. 					break;
  210.  
  211. 				}
  212. 				prev = cur;
  213. 				cur = cur->next;
  214. 			}
  215. 			return nullptr;
  216. 		}
  217. 	private:
  218. 		size_t n = 0;
  219. 		vector<Node*> _hash;
  220. 	};
  221.  
  222. }

 

 "my_map.h" :

  1. #pragma once
  2. #include "test.h"
  3. template<class K,class V,class Hash = Compare<K>>
  4. class map
  5. {
  6. 	struct MapOf
  7. 	{
  8. 		const K& operator()(const pair<K,V>& _key)
  9. 		{
  10. 			return _key.first;
  11. 		}
  12. 	};
  13. public:
  14. 	typedef typename unordered::HashBucket<K, pair<const K, V>, MapOf, Hash>::const_Iterator  Iterator;
  15. 	typedef typename unordered::HashBucket<K, pair<const K, V>, MapOf, Hash>::const_Iterator  const_Iterator;
  16. 	pair<const_Iterator, bool> insert(const pair<K, V>& data)
  17. 	{
  18. 		return  pair<const_Iterator, bool>(const_Iterator(key.insert(data).first._node,&key), key.insert(data).second);
  19. 	}
  20. 	Iterator find(const K& data)
  21. 	{
  22. 		return key.find(data);
  23. 	}
  24. 	pair<K, V>* erase(const K& data)
  25. 	{
  26. 		return key.erase(data);
  27. 	}
  28. 	const_Iterator begin() const
  29. 	{
  30. 		return key.begin();
  31. 	}
  32. 	const_Iterator end() const
  33. 	{
  34. 		return key.end();
  35. 	}
  36. 	V& operator[](const K& k)
  37. 	{
  38. 		pair<const_Iterator, bool> ret = key.insert(make_pair(k,V()));
  39. 		return ret.first->second;
  40. 	}
  41. private:
  42. 	unordered::HashBucket<K, pair<const K, V>, MapOf,Hash> key;
  43. };

 

 "my_set.h" :

  1. #pragma once
  2. #include "test.h"
  3. template<class K,class Hash = Compare<K>>
  4. class set
  5. {
  6. 	
  7. 	struct SetOf
  8. 	{
  9. 		const K& operator()(const K& _key)
  10. 		{
  11. 			return _key;
  12. 		}
  13. 	};
  14. public:
  15. 	typedef typename unordered::HashBucket<K, const K ,SetOf, Hash>::const_Iterator  Iterator;
  16. 	typedef typename unordered::HashBucket<K, const K, SetOf, Hash>::const_Iterator  const_Iterator;
  17. 	pair<const_Iterator,bool> insert(const K& data)
  18. 	{
  19. 		return pair<const_Iterator, bool>(const_Iterator(key.insert(data).first._node,&key), key.insert(data).second);
  20. 	}
  21. 	Iterator find(const K& data)
  22. 	{
  23. 		return key.find(data);
  24. 	}
  25. 	const K* erase(const K& data)
  26. 	{
  27. 		return key.erase(data);
  28. 	}
  29. 	
  30. 	const_Iterator begin() const
  31. 	{
  32. 		return key.begin();
  33. 	}
  34. 	
  35. 	const_Iterator  end() const
  36. 	{
  37. 		return key.end();
  38. 	}
  39. private:
  40. 	unordered::HashBucket<K, const K, SetOf,Hash> key;
  41. };

 

 

仿函数实现分析

”test.h“ 中：

其中：

这个完成了偏特化，将 string 可以变成 整型数，方便计算下标 hashi

细节注意

”my_map.h“ 中 ：

”my_set.h“ 中 ：

确保 map 和 set 都可以使用，

如果类型是 map ，得到的就是 pair<K,V>里面的 K 类型

如果类型是 set ，得到的就是 K 类型

迭代器问题分析

由于在operator++过程中，需要访问HashBucket的成员变量，所以需要友元

且在构造时需要HashBucket类，则需要前置声明

（前置声明）

迭代器注意：

  1. pair<const_Iterator, bool> insert(const pair<K, V>& data)
  2. 	{
  3. 		return  pair<const_Iterator, bool>(const_Iterator(key.insert(data).first._node,&key), key.insert(data).second);
  4. 	}

// return pair<const_Iterator, bool>(key.insert(data)) 是错误的

key.insert(data)是 pair<Iterator, bool> 类型，普通迭代器不能转换成 const迭代器

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/454330
推荐阅读
相关标签

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

  

闽ICP备14008679号