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

学习-＞C++篇十六：哈希表与unordered_map、unordered_set_c++ 哈希表unordered

作者：知新_RL | 2024-05-11 17:22:33

赞

踩

c++ 哈希表unordered

目录

 

1.哈希表概念          

2.常用哈希函数：

解决哈希冲突的两个方法：

一.闭散列法（开放定址法）：

二.开散列法（哈希桶）：

3.封装unordered_map,unordered_set

 1.哈希表概念          

顺序结构以及平衡树中，元素键值与其存储位置之间没有对应的关系，因此在查找一个元素
时，必须要经过键值的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即
O(log2N)，搜索的效率取决于搜索过程中元素的比较次数，倘若无需进行多次比较，直接从表中获得所需的元素，这就需将键值和存储位置建立映射关系，以便快速查找元素。
        该方法为 哈希法（散列法），哈希方法中使用将键值转换为存储位置的转换函数称为哈希(散列)函数，构造出来的结构称 为 哈希表(或散列表）。
        哈希冲突：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突 或哈希碰撞。

2.常用哈希函数：

        1. 直接定址法--(常用) 取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
        2. 除留余数法--(常用) 设散列表中的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数， 按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。

解决哈希冲突的两个方法：

一.闭散列法（开放定址法）：

1.线性探测法：
代码模拟实现： 
  1. #pragma once
  2. #include<unordered_map>
  3. #include<vector>
  4. using std::vector;
  5. using std::pair;
  6.  
  7. //线性探测法
  8. // 
  9. //给每一个空间标记
  10. enum state{EXIST,DELETE,EMPTY};
  11. template<class K,class V>
  12. class hashtable
  13. {
  14. 	//表中存储elem结构，包含pair键值对和标记状态的state
  15. 	struct elem
  16. 	{
  17. 		pair<K, V> _val;
  18. 		state _state;
  19. 	};
  20.  
  21. public:
  22. 	hashtable(size_t capacity=3)
  23. 		:_ht(capacity)
  24. 		,_size(0)
  25. 	{
  26. 		for (size_t i = 0; i < capacity; i++)
  27. 		{
  28. 			_ht[i]._state = EMPTY;
  29. 		}
  30. 	}
  31. 	~hashtable()
  32. 	{}
  33.  
  34. 	bool Insert(const pair<K, V>& val)
  35. 	{
  36. 		checkCapacity();
  37. 		size_t hashi = val.first % _ht.size();
  38. 		while (_ht[hashi]._state != EMPTY)
  39. 		{
  40. 			if (_ht[hashi]._state == EXIST 
  41. 				&& _ht[hashi]._val.first == val.first)
  42. 				return false;
  43. 			++hashi;
  44. 			if (hashi == _ht.size())
  45. 				hashi = 0;
  46. 		}
  47. 		_ht[hashi]._state = EXIST;
  48. 		_ht[hashi]._val = val;
  49. 		_size++;
  50. 		return true;
  51. 	}
  52.  
  53. 	elem* Find(const K& k)
  54. 	{
  55. 		if (_ht.size() == 0)
  56. 			return nullptr;
  57. 		size_t hashi = k % _ht.size();
  58. 		while (_ht[hashi]._state != EMPTY)
  59. 		{
  60. 			if (_ht[hashi]._state == EXIST && _ht[hashi]._val.first == k)
  61. 				return &_ht[hashi];
  62. 			++hashi;
  63. 			if (hashi == _ht.size())
  64. 				hashi = 0;
  65. 		}
  66. 		return nullptr;
  67. 	}
  68. private:
  69. 	void checkCapacity()
  70. 	{
  71. 		if (_size * 10 / _ht.size() >= 7)
  72. 		{
  73. 			size_t newsize = _ht.size() * 2;
  74. 			hashtable<K,V>newht(newsize);
  75. 			for (auto e : _ht)
  76. 			{
  77. 				if (e._state == EXIST)
  78. 					newht.Insert({ e._val.first,e._val.second });
  79. 			}
  80. 			newht._size = _size;
  81. 			newht._ht.swap(_ht);
  82. 		}
  83. 	}
  84.  
  85. 	bool Erase(const K&k)
  86. 	{
  87. 		if (elem* p = Find(k))
  88. 		{
  89. 			p->_state = DELETE;
  90. 			--_size;
  91. 			return true;
  92. 		}
  93. 		return false;
  94. 	}
  95. 	size_t HashFunc(const K& k)
  96. 	{
  97. 		return k % _ht.size();
  98. 	}
  99. private:
  100. 	vector<elem>_ht;
  101. 	size_t _size;
  102. };
2.二次探测法：
与线性探测法类似，将插入和查找的探测元素的顺序变成hashi，hashi+1^2，hashi+2^2,hashi+3^2......即可，记得计算好的哈希地址对哈希表的总大小取模，代码如下： 
  1. //二次探测法
  2. 	bool Insert(const pair<K, V>& val)
  3. 	{
  4. 		checkCapacity();
  5. 		size_t hashi = val.first % _ht.size();
  6. 		size_t index = hashi;
  7. 		int i = 0;
  8. 		while (_ht[hashi]._state != EMPTY)
  9. 		{
  10. 			if (_ht[hashi]._state == EXIST
  11. 				&& _ht[hashi]._val.first == val.first)
  12. 				return false;
  13. 			++i;
  14. 			hashi=index+i*i;
  15. 			hashi %= _ht.size();
  16. 		}
  17. 		_ht[hashi]._state = EXIST;
  18. 		_ht[hashi]._val = val;
  19. 		_size++;
  20. 		return true;
  21. 	}
  22.  
  23.  
  24. 	//二次探测法
  25. 	elem* Find(const K& k)
  26. 	{
  27. 		if (_ht.size() == 0)
  28. 			return nullptr;
  29. 		size_t hashi = k % _ht.size();
  30. 		size_t index = hashi;
  31. 		int i = 0;
  32. 		while (_ht[hashi]._state != EMPTY)
  33. 		{
  34. 			if (_ht[hashi]._state == EXIST && _ht[hashi]._val.first == k)
  35. 				return &_ht[hashi];
  36. 			i++;
  37. 			hashi=index+i*i;
  38. 			hashi %= _ht.size();
  39. 		}
  40. 		return nullptr;
  41. 	}

二.开散列法（哈希桶）：

开散列法：首先对关键码的集合通过哈希函数映射到对应地址，具有相同地址的的关键码归于同一个子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。（即将哈希冲突的元素放在单链表中）

简单实现：

  1. namespace openhash
  2. {
  3. 	template<class V>
  4. 	struct hashBucketNode
  5. 	{
  6. 		hashBucketNode(const V& data)
  7. 			:_next(nullptr)
  8. 			, _data(data)
  9. 		{}
  10.  
  11. 		hashBucketNode<V>* _next;
  12. 		V _data;
  13. 	};
  14.  
  15. 	template<class V>
  16. 	class hashBucket
  17. 	{
  18. 		typedef hashBucketNode<V> Node;
  19. 	public:
  20. 		hashBucket(size_t capacity = 3)
  21. 			:_size(0)
  22. 		{
  23. 			_ht.resize(capacity, nullptr);
  24. 		}
  25.  
  26. 		Node* insert(const V& data)
  27. 		{
  28. 			//几号桶
  29. 			size_t Bucketi = data % _ht.size();
  30. 			Node* cur = _ht[Bucketi];
  31. 			while (cur)
  32. 			{
  33. 				if (cur->_data == data)
  34. 					return cur;
  35. 				cur = cur->_next;
  36. 			}
  37. 			Node* newnode = new Node(data);
  38. 			newnode->_next = _ht[Bucketi];
  39. 			_ht[Bucketi] = newnode;
  40. 			_size++;
  41. 			return newnode;
  42. 		}
  43.  
  44. 		Node* erase(const V& data)
  45. 		{
  46. 			size_t Bucketi = data % _ht.size();
  47. 			Node* cur = _ht[Bucketi], prev = nullptr;
  48. 			while (cur)
  49. 			{
  50. 				if (cur->_data == data)
  51. 				{
  52. 					if (prev)
  53. 						prev->_next = cur->_next;
  54. 					else
  55. 						_ht[Bucketi] = cur->_next;
  56. 					//返回删除元素的下一个节点
  57. 					prev = cur->_next;
  58. 					delete cur;
  59. 					--_size;
  60. 					return prev;
  61. 				}
  62. 			}
  63. 			return nullptr;
  64. 		}
  65.  
  66. 		Node* Find(const V& data)
  67. 		{
  68. 			size_t Bucketi = data % _ht.size();
  69. 			Node* cur = _ht[Bucketi];
  70. 			while (cur)
  71. 			{
  72. 				if (cur->_data == data)
  73. 					return cur;
  74. 				cur = cur->_next;
  75. 			}
  76. 			return nullptr;
  77. 		}
  78. 		size_t size()const { return _size; }
  79. 		bool Empty()const { return _size == 0; }
  80. 		void clear()
  81. 		{
  82. 			for (int i = 0; i < _ht.size(); i++)
  83. 			{
  84. 				while (_ht[i])
  85. 				{
  86. 					Node* cur = _ht[i];
  87. 					_ht[i] = cur->_next;
  88. 					delete cur;
  89. 				}
  90. 			}
  91. 			_size = 0;
  92. 		}
  93. 		~hashBucket() { clear(); }
  94. 	private:
  95. 		size_t hashFunc(const V& data) { return data % _ht.size(); }
  96. 	private:
  97. 		vector<Node*> _ht;
  98. 		size_t _size;
  99. 	};
  100. }

开散列法的扩容：

因为扩容时桶的总数改变了，每个元素需要重新映射地址，所以有大的性能消耗。理想情况下是每个桶一个元素，于是，可以在桶的个数等于存储的元素个数的时候进行哈希表的扩容操作。

扩容代码：（将原链表节点一个个插入到新的哈希桶）

  1. size_t BucketCount()const
  2. 		{
  3. 			size_t bc = 0;
  4. 			for (auto p : _ht)
  5. 				if (p)++bc;
  6. 			return bc;
  7. 		}
  8. 	private:
  9. 		void checkCapacity()
  10. 		{
  11. 			if (BucketCount() == _size)
  12. 			{
  13. 				vector<Node*>newht(_size == 0 ? 3:_size * 2);
  14. 				for (auto& p : _ht)
  15. 				{
  16. 					Node* pnode = p;
  17. 					while (pnode)
  18. 					{
  19. 						p = p->_next;
  20. 						size_t Bucketi = pnode->_data % newht.size();
  21. 						pnode->_next = newht[Bucketi];
  22. 						newht[Bucketi] = pnode;
  23. 						pnode = p;
  24. 					}
  25. 				}
  26. 				_ht.swap(newht);
  27. 			}
  28. 		}

3.封装unordered_map,unordered_set

上述实现是将key取模得到存储地址，如果要处理字符串，则需提供字符串哈希函数，如果要处理自定义类型也需提供哈希函数，可以通过传入仿函数实现，为封装unordered_map和unordered_set还需实现迭代器，与红黑树类似，还需有一个取value中key的仿函数。
简单实现封装如下： 
  1. //hashtable11-3.h
  2.  
  3. namespace openhash
  4. {
  5. 	template<class T>
  6. 	struct HashFunc
  7. 	{
  8. 		//默认的哈希函数
  9. 		size_t operator()(const T& val) { return val; }
  10. 	};
  11. 	//针对字符串哈希函数->模板特化
  12. 	template<>
  13. 	struct HashFunc<string>
  14. 	{
  15. 		size_t operator()(const string& s)
  16. 		{
  17. 			const char* str = s.c_str();
  18. 			size_t seed = 31;
  19. 			size_t hash = 0;
  20. 			while (*str)
  21. 			{
  22. 				hash = hash * seed + (*str++);
  23. 			}
  24. 			return hash;
  25. 		}
  26. 	};
  27.  
  28. 	//定义节点：存储的T可能是K,也可能是pair<K,V>
  29. 	template<class T>
  30. 	struct HashNode
  31. 	{
  32. 		HashNode(const T&data)
  33. 			:_next(nullptr)
  34. 			,_data(data)
  35. 		{}
  36. 		HashNode<T>* _next;
  37. 		T _data;
  38. 	};
  39.  
  40. 	//迭代器需用到哈希桶，要做前置声明
  41. 	template<class K,class T,class KeyOfT,class HashFunc>
  42. 	class HashBucket;
  43.  
  44. 	//实现迭代器，其中有一个节点指针和哈希桶的指针
  45. 	template<class K,class T,class KeyOfT,class HashFunc>
  46. 	class __HBIterator
  47. 	{
  48. 		typedef HashNode<T> Node;
  49. 		typedef HashBucket<K, T, KeyOfT, HashFunc>* Phb;
  50. 		typedef __HBIterator<K, T, KeyOfT, HashFunc> Self;
  51. 	public:
  52. 		__HBIterator(){}
  53. 		__HBIterator(Node*node,Phb phb)
  54. 			:_node(node),_phb(phb)
  55. 		{}
  56.  
  57. 		//单向迭代器只需实现++
  58. 		Self& operator++()//前置加加
  59. 		{
  60. 			assert(_node);//当_node为空(即end，不可以++)
  61. 			if (_node->_next)
  62. 				_node = _node->_next;
  63. 			else
  64. 			{
  65. 				KeyOfT kot;
  66. 				HashFunc hf;
  67. 				size_t sz = _phb->_table.size();
  68. 				//计算下一个桶
  69. 				size_t hashi = hf(kot(_node->_data)) % sz + 1;
  70. 				//寻找下一个不为nullptr的桶
  71. 				while (hashi < sz && !_phb->_table[hashi])
  72. 					++hashi;
  73. 				if (hashi == sz)
  74. 					_node = nullptr;//已经走完最后一个哈希桶
  75. 				else
  76. 					_node = _phb->_table[hashi];
  77. 			}
  78. 			return *this;
  79. 		}
  80.  
  81. 		Self& operator++(int)//后置加加
  82. 		{
  83. 			Self ret(_node, _phb);
  84. 			operator++();
  85. 			return ret;
  86. 		}
  87.  
  88. 		T& operator*() { return _node->_data; }
  89. 		T* operator->() { return &_node->_data; }
  90. 		bool operator!=(const Self& s) const { return _node != s._node; }
  91. 		bool operator==(const Self& s) const { return _node == s._node; }
  92. 	private:
  93. 		Node* _node;
  94. 		Phb _phb;
  95. 	};
  96.  
  97. 	template<class K,class T,class KeyOfT,class HashFunc>
  98. 	class HashBucket
  99. 	{
  100. 		template<class K,class T,class KeyOfT,class hashFunc>
  101. 		friend class __HBIterator;//将迭代器作为哈希桶的友元类模板，以便能访问哈希表(遍历桶)
  102. 		typedef HashNode<T> Node;
  103. 	public:
  104. 		typedef __HBIterator<K, T, KeyOfT, HashFunc> Iterator;
  105. 		Iterator begin()
  106. 		{
  107. 			for (auto p : _table)
  108. 				if (p)return Iterator(p, this);
  109. 			return Iterator(nullptr, this);
  110. 		}
  111. 		Iterator end() { return Iterator(nullptr, this); }
  112.  
  113. 		HashBucket(size_t capacity = 0)
  114. 			:_table(GetNextPrime(_table.size()),nullptr)
  115. 			,_size(0)
  116. 		{}
  117.  
  118. 		~HashBucket() { Clear(); }
  119.  
  120. 		void Clear()
  121. 		{
  122. 			for (size_t i = 0; i < _table.size(); i++)
  123. 			{
  124. 				while (_table[i])
  125. 				{
  126. 					Node* cur = _table[i];
  127. 					_table[i] = cur->_next;
  128. 					delete cur;
  129. 				}
  130. 			}
  131. 			_size = 0;
  132. 		}
  133.  
  134. 		Iterator find(const K& key)
  135. 		{
  136. 			HashFunc hf;
  137. 			size_t hashi = hf(key) % _table.size();
  138. 			Node* cur = _table[hashi];
  139. 			while (cur)
  140. 			{
  141. 				if (KeyOfT()(cur->_data) == key)
  142. 					return Iterator(cur, this);
  143. 				cur = cur->_next;
  144. 			}
  145. 			return Iterator(nullptr, this);
  146. 		}
  147.  
  148. 		pair<Iterator, bool> insert(const T& data)
  149. 		{
  150. 			Iterator it = find(KeyOfT()(data));
  151. 			if (it != end())
  152. 				return make_pair(it, false);
  153. 			checkCapacity();
  154. 			Node* newnode = new Node(data);
  155. 			size_t hashi = HashFunc()(KeyOfT()(data)) % _table.size();
  156. 			newnode->_next = _table[hashi];
  157. 			_table[hashi] = newnode;
  158. 			++_size;
  159. 			return make_pair(Iterator(newnode, this), true);
  160. 		}
  161.  
  162. 		size_t erase(const K& key)
  163. 		{
  164. 			KeyOfT kot;
  165. 			HashFunc hf;
  166. 			size_t hashi = hf(key)%_table.size();
  167. 			Node* prev = nullptr;
  168. 			Node* cur = _table[hashi];
  169. 			while (cur)
  170. 			{
  171. 				if (kot(cur->_data) == key)
  172. 				{
  173. 					if (prev)
  174. 						prev->_next = cur->_next;
  175. 					else
  176. 						_table[hashi] = cur->_next;
  177. 					delete cur;
  178. 					--_size;
  179. 					return 1;
  180. 				}
  181. 				prev = cur;
  182. 				cur = cur->_next;
  183. 			}
  184. 			return 0;
  185. 		}
  186.  
  187. 	private:
  188. 		//将桶的数量设置为一个素数，据说能减少哈希冲突
  189. 		size_t GetNextPrime(size_t prime)
  190. 		{
  191. 			const int PRIMECOUNT = 28;
  192. 			//素数表
  193. 			static const size_t primeList[PRIMECOUNT] =
  194. 			{
  195. 				53ul, 97ul, 193ul, 389ul, 769ul,
  196. 				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
  197. 				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
  198. 				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
  199. 				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
  200. 				1610612741ul, 3221225473ul, 4294967291ul
  201. 			};
  202.  
  203. 			// 获取比prime大那一个素数
  204. 			size_t i = 0;
  205. 			for (; i < PRIMECOUNT; ++i)
  206. 			{
  207. 				if (primeList[i] > prime)
  208. 					return primeList[i];
  209. 			}
  210. 			return primeList[i];
  211. 		}
  212.  
  213. 		void checkCapacity()
  214. 		{
  215. 			if (_size == _table.size())
  216. 			{
  217. 				KeyOfT kot;
  218. 				HashFunc hf;
  219. 				vector<Node*>newtable(GetNextPrime(_table.size()),nullptr);
  220. 				for (auto p : _table)
  221. 				{
  222. 					auto cur = p;
  223. 					while (cur)
  224. 					{
  225. 						Node* next = cur->_next;
  226. 						cur->_next = newtable[hf(kot(p->_data))];
  227. 						newtable[hf(kot(p->_data))] = cur;
  228. 						cur = next;
  229. 					}
  230. 				}
  231. 				newtable.swap(_table);
  232. 			}
  233. 		}
  234. 	private:
  235. 		vector<Node*>_table;
  236. 		size_t _size;
  237. 	};
  238. }
封装unordered_map和unordered_set类似：
unordered_map主要要多实现一个operator[]函数，注意这个函数是先调用insert实现的。 
  1. #pragma once
  2. #include"hashtable11-3.h"
  3. namespace openhash
  4. {
  5. 	template<class K, class V, class HashFunc = HashFunc<K> >
  6. 	class unordered_map
  7. 	{
  8. 		struct MapKeyOfT { const K& operator()(const pair<K, V>& p) { return p.first; } };
  9. 	public:
  10. 		typedef typename HashBucket<K, pair<K, V>, MapKeyOfT, HashFunc>::Iterator iterator;
  11. 		iterator begin() { return _hb.begin(); }
  12. 		iterator end() { return _hb.end(); }
  13.  
  14. 		iterator find(const K& key) {
  15. 			return _hb.find(key);
  16. 		}
  17. 		size_t erase(const K& key) {
  18. 			return _hb.erase(key);
  19. 		}
  20. 		pair<iterator, bool>insert(const pair<K, V>& p) {
  21. 			return _hb.insert(p);
  22. 		}
  23. 		V& operator[](const K& k) {
  24. 			pair<iterator, bool>p = insert(make_pair(k, V()));
  25. 			return p.first->second;
  26. 		}
  27. 	private:
  28. 		HashBucket<K, pair<K, V>, MapKeyOfT, HashFunc>_hb;
  29. 	};
  30. }
  1. #pragma once
  2. namespace openhash
  3. {
  4. #include"hashtable11-3.h"
  5. 	template<class K, class HashFunc = HashFunc<K> >
  6. 	class unordered_set
  7. 	{
  8. 		struct SetKeyOfT { const K& operator()(const K& k) { return k; } };
  9. 	public:
  10. 		typedef typename HashBucket<K,K,SetKeyOfT, HashFunc>::Iterator iterator;
  11. 		iterator begin() { return _hb.begin(); }
  12. 		iterator end() { return _hb.end(); }
  13.  
  14. 		iterator find(const K& key) {
  15. 			return _hb.find(key);
  16. 		}
  17. 		size_t erase(const K& key) {
  18. 			return _hb.erase(key);
  19. 		}
  20. 		pair<iterator, bool>insert(const K& k) {
  21. 			return _hb.insert(k);
  22. 		}
  23. 	private:
  24. 		HashBucket<K, K, SetKeyOfT, HashFunc>_hb;
  25. 	};
  26. }

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

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

  

闽ICP备14008679号