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

【C++进阶】哈希实现unordered_set && unordered_map_c++ 哈希set

作者：代码探险家 | 2024-08-23 02:39:12

赞

踩

c++ 哈希set

1、unordered_map介绍

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

 1.1 unordered_map的构造

函数声明功能介绍
unordered_map构造不同格式的unordered_map对象

1.2 unordered_map的容量

函数声明功能介绍
bool empty() const检测unordered_map是否为空
size_t size() const获取unordered_map的有效元素个数

1.3 unordered_map的迭代器

函数声明功能介绍
begin返回unordered_map第一个元素的迭代器
end返回unordered_map最后一个元素下一个位置的迭代器
cbegin返回unordered_map第一个元素的const迭代器
cend返回unordered_map最后一个元素下一个位置的const迭代器

1.4 unordered_map的元素访问

函数声明功能介绍
operator[]返回与key对应的value，没有一个默认值

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶
中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，
将key对应的value返回。
 

1.5 unordered_map的查询

函数声明功能介绍
iterator find(const K& key)返回key在哈希桶中的位置
size_t count(const K& key)返回哈希桶中关键码为key的键值对的个数

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

1.6 unordered_map的修改操作

函数声明功能介绍
insert向容器中插入键值对
erase删除容器中的键值对
void clear()清空容器中有效元素个数
void swap(unordered_map&)交换两个容器中的元素

1.7 unordered_map的桶操作

函数声明功能介绍
size_t bucket_count()const返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数
size_t bucket(const K& key)返回元素key所在的桶号

2、unordered_set介绍

set跟map及其相似，参照map使用即可。

3、相关OJ题

在长度为2N的数组中找出重复N次的元素

  1. class Solution {
  2. public:
  3.     int repeatedNTimes(vector<int>& nums) {
  4.         int n = nums.size() / 2;
  5.         //用unordered_map统计每个元素出现的次数
  6.         unordered_map<int, int> m;
  7.         for(auto e : nums)
  8.         {
  9.             m[e]++;
  10.         }
  11.         //找出出现次数为n的元素
  12.         for(auto& e : m)
  13.         {
  14.             if(e.second == n)
  15.                 return e.first;
  16.         }
  17.         return -1;
  18.     }
  19. };

 两个数组的交集

  1. class Solution {
  2. public:
  3.     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
  4.         //对nums1用unordered_set去重
  5.         unordered_set<int> s1;
  6.         for(auto e : nums1)
  7.             s1.insert(e);
  8.         //对nums2用unordered_set去重
  9.         unordered_set<int> s2;
  10.         for(auto e : nums2)
  11.             s2.insert(e);
  12.         //遍历s1找出与s2中相同的元素
  13.         vector<int> v;
  14.         for(auto e : s1)
  15.         {
  16.             if(s2.find(e) != s2.end())
  17.                 v.push_back(e);
  18.         }
  19.         return v;
  20.     }
  21. };

4、底层结构

4.1 哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素
 

当向该结构： 

插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。

 搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置
取元素比较，若关键码相等，则搜索成功。

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称
为哈希表(Hash Table)(或者称散列表)
 

4.2 哈希冲突

不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
 

4.3 哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：

1.哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
2.哈希函数计算出来的地址能均匀分布在整个空间中
3.哈希函数应该比较简单

 常见哈希函数：

1.直接定址法（常用）

2.除留余数法（常用）

3.平方取中法

4.折叠法

5.随机数法

6.数学分析法

4.4 哈希冲突如何解决？

4.4.1 闭散列

闭散列是用的线性探测的方法实现，线性探测

线性探测优点：实现非常简单，
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同
关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降
低。
如何更好的缓解这种情况？

可以进行二次探测

  1. #include<vector>
  2.  
  3. template<class K>
  4. struct HashFunc
  5. {
  6. 	size_t operator()(const K& key)
  7. 	{
  8. 		return (size_t)key;
  9. 	}
  10. };
  11.  
  12. //特化
  13. template<>
  14. struct HashFunc<string>
  15. {
  16. 	size_t operator()(const string& key)
  17. 	{
  18. 		size_t hash = 0;
  19. 		for (auto ch : key)
  20. 		{
  21. 			hash *= 131;
  22. 			hash += ch;
  23. 		}
  24. 		return hash;
  25. 	}
  26. };
  27.  
  28. //开放地址寻址
  29. namespace open_adress
  30. {
  31. 	enum State
  32. 	{
  33. 		EMPTY,
  34. 		EXIST,
  35. 		DELETE
  36. 	};
  37. 	template<class K, class V>
  38. 	struct HashData
  39. 	{
  40. 		pair<K, V> _kv;
  41. 		State _state = EMPTY;
  42. 	};
  43.  
  44.  
  45.  
  46. 	template<class K, class V, class Hash = HashFunc<K>>
  47. 	class HashTable
  48. 	{
  49. 	public:
  50. 		HashTable()
  51. 		{
  52. 			_tables.resize(10);
  53. 		}
  54. 		bool Insert(const pair<K, V>& kv)
  55. 		{
  56. 			
  57. 			if (_n * 10 / _tables.size() >= 7)
  58. 			{
  59. 				//扩容
  60.  
  61. 				HashTable<K, V, Hash> newHT;
  62. 				newHT._tables.resize(_tables.size() * 2);
  63.  
  64. 				for (size_t i = 0; i < _tables.size(); i++)
  65. 				{
  66. 					if (_tables[i]._state == EXIST)
  67. 					{
  68. 						newHT.Insert(_tables[i]._kv);
  69. 					}
  70. 				}
  71. 				_tables.swap(newHT._tables);
  72. 			}
  73. 			Hash hs;
  74. 			size_t hashi = hs(kv.first) % _tables.size();
  75.  
  76. 			//线性探测
  77. 			while (_tables[hashi]._state == EXIST)
  78. 			{
  79. 				++hashi;
  80. 				hashi %= _tables.size();
  81. 			}
  82. 			_tables[hashi]._kv = kv;
  83. 			_tables[hashi]._state = EXIST;
  84. 			_n++;
  85. 			return true;
  86. 		}
  87. 		HashData<K, V>* Find(const K& key)
  88. 		{
  89. 			Hash hs;
  90. 			size_t hashi = hs(key) % _tables.size();
  91. 			while (_tables[hashi]._state != EMPTY)
  92. 			{
  93. 				if (_tables[hashi]._state == EXIST &&
  94. 					_tables[hashi]._kv.first == key)
  95. 				{
  96. 					return &_tables[hashi];
  97. 				}
  98. 				++hashi;
  99. 				hashi %= _tables.size();
  100. 			}
  101.  
  102. 			return nullptr;
  103. 		}
  104. 		bool Erase(const K& key)
  105. 		{
  106. 			HashData<K, V>* ret = Find(key);
  107. 			if (ret != nullptr)
  108. 			{
  109. 				ret->_state = EMPTY;
  110. 				_n--;
  111.  
  112. 				return true;
  113. 			}
  114. 			else
  115. 			{
  116. 				return false;
  117. 			}
  118. 		}
  119. 	private:
  120. 		vector<HashData<K, V>> _tables;
  121. 		size_t _n = 0; //有效数据个数
  122. 	};
  123.  
  124. 	void testHT1()
  125. 	{
  126. 		int a[] = { 12, 33434, 223 ,3 };
  127. 		HashTable<int, int> ht;
  128.  
  129. 		for (auto e : a)
  130. 		{
  131. 			ht.Insert(make_pair(e, e));
  132. 		}
  133.  
  134. 		cout << ht.Find(12) << endl;
  135. 		cout << ht.Find(223) << endl;
  136.  
  137. 		ht.Erase(223);
  138.  
  139. 		cout << ht.Find(12) << endl;
  140. 		cout << ht.Find(223) << endl;
  141. 	}
  142. 	void testHT2()
  143. 	{
  144. 		HashTable<string, int> ht;
  145.  
  146. 		ht.Insert(make_pair("sort", 1));
  147. 		ht.Insert(make_pair("left", 2));
  148. 		ht.Insert(make_pair("right", 3));
  149. 		ht.Insert(make_pair("ok", 4));
  150. 	}
  151. }

闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
 

4.4.2 开散列

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

  1. //哈希桶法
  2. namespace hash_bucket
  3. {
  4. 	template<class T>
  5. 	struct HashNode
  6. 	{
  7. 		T _data;
  8. 		HashNode<T>* next;
  9.  
  10. 		HashNode(const T& data)
  11. 			:_data(data)
  12. 			,next(nullptr)
  13. 		{}
  14. 	};
  15.  
  16. 	前置声明
  17. 	//template<class K, class T, class KeyOfT, class Hash>
  18. 	//class HashTable;
  19.  
  20. 	//template<class K, class T, class KeyOfT, class Hash>
  21. 	//struct __HTIterator
  22. 	//{
  23. 	//	typedef HashNode<T> Node;
  24. 	//	typedef __HTIterator Self;
  25.  
  26. 	//	Node* _node;
  27. 	//	HashTable<K, T, KeyOfT, Hash>* _pht;
  28.  
  29. 	//	__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht)
  30. 	//		:_node(node)
  31. 	//		,_pht(pht)
  32. 	//	{}
  33.  
  34. 	//	Self& operator++()
  35. 	//	{
  36. 	//		if (_node->next)
  37. 	//		{
  38. 	//			//当前桶没走完，找当前桶的下一个节点
  39. 	//			_node = _node->next;
  40. 	//		}
  41. 	//		else
  42. 	//		{
  43. 	//			//当前桶走完了，找下一个不为空的桶的第一个节点
  44. 	//			KeyOfT kot;
  45. 	//			Hash hs;
  46. 	//			size_t i = hs(kot(_node->_data)) % _pht->_tables.size();
  47. 	//			++i;
  48. 	//			for (; i < _pht->_tables.size(); i++)
  49. 	//			{
  50. 	//				if (_pht->_tables)
  51. 	//					break;
  52. 	//			}
  53.  
  54. 	//			if (i == _pht->_tables.size())
  55. 	//			{
  56. 	//				//所有桶都走完了，最后一个的下一个用nullptr标记
  57. 	//				_node = nullptr;
  58. 	//			}
  59. 	//			else
  60. 	//			{
  61. 	//				_node = _pht->_tables[i];
  62. 	//			}
  63. 	//		}
  64. 	//		return *this;
  65. 	//	}
  66.  
  67. 	//	bool operator!=(const Self& s)
  68. 	//	{
  69. 	//		return _node != s._node;
  70. 	//	}
  71. 	//};
  72.  
  73. 	template<class K, class T, class KeyOfT, class Hash>
  74. 	class HashTable
  75. 	{
  76. 		typedef HashNode<T> Node;
  77. 	public:
  78. 		
  79.  
  80. 		友元声明
  81. 		//template<class K, class T, class KeyOfT, class Hash>
  82. 		//friend class HashTable;
  83.  
  84. 		template<class Ptr, class Ref>
  85. 		struct __HTIterator
  86. 		{
  87. 			typedef HashNode<T> Node;
  88. 			typedef __HTIterator Self;
  89.  
  90. 			Node* _node;
  91. 			HashTable* _pht;
  92.  
  93. 			__HTIterator(Node* node, HashTable* pht)
  94. 				:_node(node)
  95. 				, _pht(pht)
  96. 			{}
  97. 			Ref operator*()
  98. 			{
  99. 				return _node->_data;
  100. 			}
  101. 			Ptr operator->()
  102. 			{
  103. 				return &_node->_data;
  104. 			}
  105. 			Self& operator++()
  106. 			{
  107. 				if (_node->next)
  108. 				{
  109. 					//当前桶没走完，找当前桶的下一个节点
  110. 					_node = _node->next;
  111. 				}
  112. 				else
  113. 				{
  114. 					//当前桶走完了，找下一个不为空的桶的第一个节点
  115. 					KeyOfT kot;
  116. 					Hash hs;
  117. 					size_t i = hs(kot(_node->_data)) % _pht->_tables.size();
  118. 					++i;
  119. 					for (; i < _pht->_tables.size(); i++)
  120. 					{
  121. 						if (_pht->_tables[i])
  122. 							break;
  123. 					}
  124.  
  125. 					if (i == _pht->_tables.size())
  126. 					{
  127. 						//所有桶都走完了，最后一个的下一个用nullptr标记
  128. 						_node = nullptr;
  129. 					}
  130. 					else
  131. 					{
  132. 						_node = _pht->_tables[i];
  133. 					}
  134. 				}
  135. 				return *this;
  136. 			}
  137.  
  138. 			bool operator!=(const Self& s)
  139. 			{
  140. 				return _node != s._node;
  141. 			}
  142. 		};
  143. 		typedef __HTIterator<T*, T&> iterator;
  144. 		typedef __HTIterator<const T*, const T&> const_iterator;
  145. 		iterator begin()
  146. 		{
  147. 			for (size_t i = 0; i < _tables.size(); i++)
  148. 			{
  149. 				Node* cur = _tables[i];
  150. 				if (cur)
  151. 				{
  152. 					//this --> HashTable*
  153. 					return iterator(cur, this);
  154. 				}
  155. 			}
  156. 			return end();
  157. 		}
  158. 		iterator end()
  159. 		{
  160. 			return iterator(nullptr, this);
  161. 		}
  162. 		const_iterator begin() const
  163. 		{
  164. 			for (size_t i = 0; i < _tables.size(); i++)
  165. 			{
  166. 				Node* cur = _tables[i];
  167. 				if (cur)
  168. 				{
  169. 					//this --> HashTable*
  170. 					return const_iterator(cur, this);
  171. 				}
  172. 			}
  173. 			return end();
  174. 		}
  175. 		const_iterator end() const
  176. 		{
  177. 			return const_iterator(nullptr, this);
  178. 		}
  179. 		HashTable()
  180. 		{
  181. 			_tables.resize(10, nullptr);
  182. 			_n = 0;
  183. 		}
  184. 		~HashTable()
  185. 		{
  186. 			for (size_t i = 0; i < _tables.size(); i++)
  187. 			{
  188. 				Node* cur = _tables[i];
  189.  
  190. 				while (cur)
  191. 				{
  192. 					Node* next = cur->next;
  193. 					delete cur;
  194. 					cur = next;
  195. 				}
  196. 				_tables[i] = nullptr;
  197. 			}
  198. 		}
  199.  
  200. 		pair<iterator, bool> Insert(const T& data)
  201. 		{
  202. 			Hash hs;
  203. 			KeyOfT kot;
  204. 			iterator it = Find(kot(data));
  205. 			if (it != end())
  206. 				return make_pair(it, false);
  207. 			//扩容
  208. 			//负载因子为1时需要扩容
  209. 			if (_n == _tables.size())
  210. 			{
  211. 				vector<Node*> newTables(_tables.size() * 2, nullptr);
  212. 				for (size_t i = 0; i < _tables.size(); i++)
  213. 				{
  214. 					Node* cur = _tables[i];
  215. 					while (cur)
  216. 					{
  217. 						Node* next = cur->next;
  218. 						//头插新表的位置
  219. 						size_t hashi = hs(kot(cur->_data)) % newTables.size();
  220. 						cur->next = newTables[hashi];
  221. 						newTables[hashi] = cur;
  222.  
  223. 						cur = next;
  224. 					}
  225. 				}
  226. 				_tables.swap(newTables);
  227. 			}
  228.  
  229.  
  230. 			size_t hashi = hs(kot(data)) % _tables.size();
  231.  
  232. 			//头插
  233. 			Node* newnode = new Node(data);
  234. 			newnode->next = _tables[hashi];
  235. 			_tables[hashi] = newnode;
  236.  
  237. 			++_n;
  238. 			return make_pair(iterator(newnode, this), true);
  239. 		}
  240. 		iterator Find(const K& key)
  241. 		{
  242. 			Hash hs;
  243. 			KeyOfT kot;
  244. 			size_t hashi = hs(key) % _tables.size();
  245. 			Node* cur = _tables[hashi];
  246. 			while (cur)
  247. 			{
  248. 				if (kot(cur->_data) == key)
  249. 				{
  250. 					return iterator(cur, this);
  251. 				}
  252. 				cur = cur->next;
  253. 			}
  254. 			return end();
  255. 		}
  256. 		bool Erase(const K& key)
  257. 		{
  258. 			Hash hs;
  259. 			KeyOfT kot;
  260. 			size_t hashi = hs(key) % _tables.size();
  261. 			Node* prev = nullptr;
  262. 			Node* cur = _tables[hashi];
  263. 			while (cur)
  264. 			{
  265. 				if (kot(cur->_data) == key)
  266. 				{
  267. 					//删除的是第一个
  268. 					if (prev == nullptr)
  269. 					{
  270. 						_tables[hashi] = cur->next;
  271. 					}
  272. 					else
  273. 					{
  274. 						prev->next = cur->next;
  275. 					}
  276. 					delete cur;
  277.  
  278. 					return true;
  279. 				}
  280. 				else
  281. 				{
  282. 					prev = cur;
  283. 					cur = cur->next;
  284. 				}
  285. 			}
  286. 			return false;
  287. 		}
  288. 	private:
  289. 		vector<Node*> _tables;
  290. 		size_t _n;
  291. 	};
  292. }

 4.4.3 闭散列与开散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：
由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <=
0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

5、模拟实现

5.1 unordered_map模拟实现

  1. #pragma once
  2.  
  3. namespace bit
  4. {
  5. 	template<class K, class V, class Hash = HashFunc<K>>
  6. 	class unordered_map
  7. 	{
  8. 		struct MapKeyOfT
  9. 		{
  10. 			const K& operator()(const pair<K, V>& kv)
  11. 			{
  12. 				return kv.first;
  13. 			}
  14. 		};
  15. 	public:
  16. 		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
  17. 		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;
  18.  
  19. 		iterator begin()
  20. 		{
  21. 			return _ht.begin();
  22. 		}
  23. 		iterator end()
  24. 		{
  25. 			return _ht.end();
  26. 		}
  27. 		const_iterator begin() const
  28. 		{
  29. 			return _ht.begin();
  30. 		}
  31. 		const_iterator end() const
  32. 		{
  33. 			return _ht.end();
  34. 		}
  35. 		pair<iterator, bool> insert(const pair<K, V>& kv)
  36. 		{
  37. 			return _ht.Insert(kv);
  38. 		}
  39. 		bool Erase(const K& key)
  40. 		{
  41. 			return _ht.Erase(key);
  42. 		}
  43. 		V& operator[](const K& key)
  44. 		{
  45. 			pair<iterator, bool> ret = insert(make_pair(key, V()));
  46. 			return ret.first->second;
  47. 		}
  48. 	private:
  49. 		hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
  50. 	};
  51. 	void test_unordered_map()
  52. 	{
  53. 		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
  54. 	"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
  55. 		unordered_map<string, int> countMap;
  56. 		for (auto& e : arr)
  57. 		{
  58. 			countMap[e]++;
  59. 		}
  60.  
  61. 		unordered_map<string, int>::iterator it = countMap.begin();
  62. 		while (it != countMap.end())
  63. 		{
  64. 			//it->first += 'x'; // key不能修改
  65. 			it->second += 1;  // value可以修改
  66. 			cout << it->first << ":" << it->second << endl;
  67. 			++it;
  68. 		}
  69. 		cout << endl;
  70.  
  71. 		for (auto& kv : countMap)
  72. 		{
  73. 			cout << kv.first << ":" << kv.second << endl;
  74. 		}
  75. 		cout << endl;
  76. 	}
  77. }

5.2 unordered_set模拟实现

  1. #pragma once
  2.  
  3. namespace bit
  4. {
  5. 	template<class K, class Hash = HashFunc<K>>
  6. 	class unordered_set
  7. 	{
  8. 		struct SetKeyOfT
  9. 		{
  10. 			const K& operator()(const K& key)
  11. 			{
  12. 				return key;
  13. 			}
  14. 		};
  15. 	public:
  16. 		typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;
  17. 		typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::const_iterator const_iterator;
  18.  
  19. 		iterator begin()
  20. 		{
  21. 			return _ht.begin();
  22. 		}
  23. 		iterator end()
  24. 		{
  25. 			return _ht.end();
  26. 		}
  27. 		const_iterator begin() const
  28. 		{
  29. 			return _ht.begin();
  30. 		}
  31. 		const_iterator end() const
  32. 		{
  33. 			return _ht.end();
  34. 		}
  35. 		pair<iterator, bool> insert(const K& key)
  36. 		{
  37. 			return _ht.Insert(key);
  38. 		}
  39. 		bool Erase(const K& key)
  40. 		{
  41. 			return _ht.Erase(key);
  42. 		}
  43. 	private:
  44. 		hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
  45. 	};
  46. }

5.3 HashTable模拟实现

  1. #pragma once
  2. #include<vector>
  3.  
  4. template<class K>
  5. struct HashFunc
  6. {
  7. 	size_t operator()(const K& key)
  8. 	{
  9. 		return (size_t)key;
  10. 	}
  11. };
  12.  
  13. //特化
  14. template<>
  15. struct HashFunc<string>
  16. {
  17. 	size_t operator()(const string& key)
  18. 	{
  19. 		size_t hash = 0;
  20. 		for (auto ch : key)
  21. 		{
  22. 			hash *= 131;
  23. 			hash += ch;
  24. 		}
  25. 		return hash;
  26. 	}
  27. };
  28.  
  29. //开放地址寻址
  30. namespace open_adress
  31. {
  32. 	enum State
  33. 	{
  34. 		EMPTY,
  35. 		EXIST,
  36. 		DELETE
  37. 	};
  38. 	template<class K, class V>
  39. 	struct HashData
  40. 	{
  41. 		pair<K, V> _kv;
  42. 		State _state = EMPTY;
  43. 	};
  44.  
  45.  
  46.  
  47. 	template<class K, class V, class Hash = HashFunc<K>>
  48. 	class HashTable
  49. 	{
  50. 	public:
  51. 		HashTable()
  52. 		{
  53. 			_tables.resize(10);
  54. 		}
  55. 		bool Insert(const pair<K, V>& kv)
  56. 		{
  57. 			
  58. 			if (_n * 10 / _tables.size() >= 7)
  59. 			{
  60. 				//扩容
  61.  
  62. 				HashTable<K, V, Hash> newHT;
  63. 				newHT._tables.resize(_tables.size() * 2);
  64.  
  65. 				for (size_t i = 0; i < _tables.size(); i++)
  66. 				{
  67. 					if (_tables[i]._state == EXIST)
  68. 					{
  69. 						newHT.Insert(_tables[i]._kv);
  70. 					}
  71. 				}
  72. 				_tables.swap(newHT._tables);
  73. 			}
  74. 			Hash hs;
  75. 			size_t hashi = hs(kv.first) % _tables.size();
  76.  
  77. 			//线性探测
  78. 			while (_tables[hashi]._state == EXIST)
  79. 			{
  80. 				++hashi;
  81. 				hashi %= _tables.size();
  82. 			}
  83. 			_tables[hashi]._kv = kv;
  84. 			_tables[hashi]._state = EXIST;
  85. 			_n++;
  86. 			return true;
  87. 		}
  88. 		HashData<K, V>* Find(const K& key)
  89. 		{
  90. 			Hash hs;
  91. 			size_t hashi = hs(key) % _tables.size();
  92. 			while (_tables[hashi]._state != EMPTY)
  93. 			{
  94. 				if (_tables[hashi]._state == EXIST &&
  95. 					_tables[hashi]._kv.first == key)
  96. 				{
  97. 					return &_tables[hashi];
  98. 				}
  99. 				++hashi;
  100. 				hashi %= _tables.size();
  101. 			}
  102.  
  103. 			return nullptr;
  104. 		}
  105. 		bool Erase(const K& key)
  106. 		{
  107. 			HashData<K, V>* ret = Find(key);
  108. 			if (ret != nullptr)
  109. 			{
  110. 				ret->_state = EMPTY;
  111. 				_n--;
  112.  
  113. 				return true;
  114. 			}
  115. 			else
  116. 			{
  117. 				return false;
  118. 			}
  119. 		}
  120. 	private:
  121. 		vector<HashData<K, V>> _tables;
  122. 		size_t _n = 0; //有效数据个数
  123. 	};
  124.  
  125. 	void testHT1()
  126. 	{
  127. 		int a[] = { 12, 33434, 223 ,3 };
  128. 		HashTable<int, int> ht;
  129.  
  130. 		for (auto e : a)
  131. 		{
  132. 			ht.Insert(make_pair(e, e));
  133. 		}
  134.  
  135. 		cout << ht.Find(12) << endl;
  136. 		cout << ht.Find(223) << endl;
  137.  
  138. 		ht.Erase(223);
  139.  
  140. 		cout << ht.Find(12) << endl;
  141. 		cout << ht.Find(223) << endl;
  142. 	}
  143. 	void testHT2()
  144. 	{
  145. 		HashTable<string, int> ht;
  146.  
  147. 		ht.Insert(make_pair("sort", 1));
  148. 		ht.Insert(make_pair("left", 2));
  149. 		ht.Insert(make_pair("right", 3));
  150. 		ht.Insert(make_pair("ok", 4));
  151. 	}
  152. }
  153.  
  154. //哈希桶法
  155. namespace hash_bucket
  156. {
  157. 	template<class T>
  158. 	struct HashNode
  159. 	{
  160. 		T _data;
  161. 		HashNode<T>* next;
  162.  
  163. 		HashNode(const T& data)
  164. 			:_data(data)
  165. 			,next(nullptr)
  166. 		{}
  167. 	};
  168.  
  169. 	前置声明
  170. 	//template<class K, class T, class KeyOfT, class Hash>
  171. 	//class HashTable;
  172.  
  173. 	//template<class K, class T, class KeyOfT, class Hash>
  174. 	//struct __HTIterator
  175. 	//{
  176. 	//	typedef HashNode<T> Node;
  177. 	//	typedef __HTIterator Self;
  178.  
  179. 	//	Node* _node;
  180. 	//	HashTable<K, T, KeyOfT, Hash>* _pht;
  181.  
  182. 	//	__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht)
  183. 	//		:_node(node)
  184. 	//		,_pht(pht)
  185. 	//	{}
  186.  
  187. 	//	Self& operator++()
  188. 	//	{
  189. 	//		if (_node->next)
  190. 	//		{
  191. 	//			//当前桶没走完，找当前桶的下一个节点
  192. 	//			_node = _node->next;
  193. 	//		}
  194. 	//		else
  195. 	//		{
  196. 	//			//当前桶走完了，找下一个不为空的桶的第一个节点
  197. 	//			KeyOfT kot;
  198. 	//			Hash hs;
  199. 	//			size_t i = hs(kot(_node->_data)) % _pht->_tables.size();
  200. 	//			++i;
  201. 	//			for (; i < _pht->_tables.size(); i++)
  202. 	//			{
  203. 	//				if (_pht->_tables)
  204. 	//					break;
  205. 	//			}
  206.  
  207. 	//			if (i == _pht->_tables.size())
  208. 	//			{
  209. 	//				//所有桶都走完了，最后一个的下一个用nullptr标记
  210. 	//				_node = nullptr;
  211. 	//			}
  212. 	//			else
  213. 	//			{
  214. 	//				_node = _pht->_tables[i];
  215. 	//			}
  216. 	//		}
  217. 	//		return *this;
  218. 	//	}
  219.  
  220. 	//	bool operator!=(const Self& s)
  221. 	//	{
  222. 	//		return _node != s._node;
  223. 	//	}
  224. 	//};
  225.  
  226. 	template<class K, class T, class KeyOfT, class Hash>
  227. 	class HashTable
  228. 	{
  229. 		typedef HashNode<T> Node;
  230. 	public:
  231. 		
  232.  
  233. 		友元声明
  234. 		//template<class K, class T, class KeyOfT, class Hash>
  235. 		//friend class HashTable;
  236.  
  237. 		template<class Ptr, class Ref>
  238. 		struct __HTIterator
  239. 		{
  240. 			typedef HashNode<T> Node;
  241. 			typedef __HTIterator Self;
  242.  
  243. 			Node* _node;
  244. 			HashTable* _pht;
  245.  
  246. 			__HTIterator(Node* node, HashTable* pht)
  247. 				:_node(node)
  248. 				, _pht(pht)
  249. 			{}
  250. 			Ref operator*()
  251. 			{
  252. 				return _node->_data;
  253. 			}
  254. 			Ptr operator->()
  255. 			{
  256. 				return &_node->_data;
  257. 			}
  258. 			Self& operator++()
  259. 			{
  260. 				if (_node->next)
  261. 				{
  262. 					//当前桶没走完，找当前桶的下一个节点
  263. 					_node = _node->next;
  264. 				}
  265. 				else
  266. 				{
  267. 					//当前桶走完了，找下一个不为空的桶的第一个节点
  268. 					KeyOfT kot;
  269. 					Hash hs;
  270. 					size_t i = hs(kot(_node->_data)) % _pht->_tables.size();
  271. 					++i;
  272. 					for (; i < _pht->_tables.size(); i++)
  273. 					{
  274. 						if (_pht->_tables[i])
  275. 							break;
  276. 					}
  277.  
  278. 					if (i == _pht->_tables.size())
  279. 					{
  280. 						//所有桶都走完了，最后一个的下一个用nullptr标记
  281. 						_node = nullptr;
  282. 					}
  283. 					else
  284. 					{
  285. 						_node = _pht->_tables[i];
  286. 					}
  287. 				}
  288. 				return *this;
  289. 			}
  290.  
  291. 			bool operator!=(const Self& s)
  292. 			{
  293. 				return _node != s._node;
  294. 			}
  295. 		};
  296. 		typedef __HTIterator<T*, T&> iterator;
  297. 		typedef __HTIterator<const T*, const T&> const_iterator;
  298. 		iterator begin()
  299. 		{
  300. 			for (size_t i = 0; i < _tables.size(); i++)
  301. 			{
  302. 				Node* cur = _tables[i];
  303. 				if (cur)
  304. 				{
  305. 					//this --> HashTable*
  306. 					return iterator(cur, this);
  307. 				}
  308. 			}
  309. 			return end();
  310. 		}
  311. 		iterator end()
  312. 		{
  313. 			return iterator(nullptr, this);
  314. 		}
  315. 		const_iterator begin() const
  316. 		{
  317. 			for (size_t i = 0; i < _tables.size(); i++)
  318. 			{
  319. 				Node* cur = _tables[i];
  320. 				if (cur)
  321. 				{
  322. 					//this --> HashTable*
  323. 					return const_iterator(cur, this);
  324. 				}
  325. 			}
  326. 			return end();
  327. 		}
  328. 		const_iterator end() const
  329. 		{
  330. 			return const_iterator(nullptr, this);
  331. 		}
  332. 		HashTable()
  333. 		{
  334. 			_tables.resize(10, nullptr);
  335. 			_n = 0;
  336. 		}
  337. 		~HashTable()
  338. 		{
  339. 			for (size_t i = 0; i < _tables.size(); i++)
  340. 			{
  341. 				Node* cur = _tables[i];
  342.  
  343. 				while (cur)
  344. 				{
  345. 					Node* next = cur->next;
  346. 					delete cur;
  347. 					cur = next;
  348. 				}
  349. 				_tables[i] = nullptr;
  350. 			}
  351. 		}
  352.  
  353. 		pair<iterator, bool> Insert(const T& data)
  354. 		{
  355. 			Hash hs;
  356. 			KeyOfT kot;
  357. 			iterator it = Find(kot(data));
  358. 			if (it != end())
  359. 				return make_pair(it, false);
  360. 			//扩容
  361. 			//负载因子为1时需要扩容
  362. 			if (_n == _tables.size())
  363. 			{
  364. 				vector<Node*> newTables(_tables.size() * 2, nullptr);
  365. 				for (size_t i = 0; i < _tables.size(); i++)
  366. 				{
  367. 					Node* cur = _tables[i];
  368. 					while (cur)
  369. 					{
  370. 						Node* next = cur->next;
  371. 						//头插新表的位置
  372. 						size_t hashi = hs(kot(cur->_data)) % newTables.size();
  373. 						cur->next = newTables[hashi];
  374. 						newTables[hashi] = cur;
  375.  
  376. 						cur = next;
  377. 					}
  378. 				}
  379. 				_tables.swap(newTables);
  380. 			}
  381.  
  382.  
  383. 			size_t hashi = hs(kot(data)) % _tables.size();
  384.  
  385. 			//头插
  386. 			Node* newnode = new Node(data);
  387. 			newnode->next = _tables[hashi];
  388. 			_tables[hashi] = newnode;
  389.  
  390. 			++_n;
  391. 			return make_pair(iterator(newnode, this), true);
  392. 		}
  393. 		iterator Find(const K& key)
  394. 		{
  395. 			Hash hs;
  396. 			KeyOfT kot;
  397. 			size_t hashi = hs(key) % _tables.size();
  398. 			Node* cur = _tables[hashi];
  399. 			while (cur)
  400. 			{
  401. 				if (kot(cur->_data) == key)
  402. 				{
  403. 					return iterator(cur, this);
  404. 				}
  405. 				cur = cur->next;
  406. 			}
  407. 			return end();
  408. 		}
  409. 		bool Erase(const K& key)
  410. 		{
  411. 			Hash hs;
  412. 			KeyOfT kot;
  413. 			size_t hashi = hs(key) % _tables.size();
  414. 			Node* prev = nullptr;
  415. 			Node* cur = _tables[hashi];
  416. 			while (cur)
  417. 			{
  418. 				if (kot(cur->_data) == key)
  419. 				{
  420. 					//删除的是第一个
  421. 					if (prev == nullptr)
  422. 					{
  423. 						_tables[hashi] = cur->next;
  424. 					}
  425. 					else
  426. 					{
  427. 						prev->next = cur->next;
  428. 					}
  429. 					delete cur;
  430.  
  431. 					return true;
  432. 				}
  433. 				else
  434. 				{
  435. 					prev = cur;
  436. 					cur = cur->next;
  437. 				}
  438. 			}
  439. 			return false;
  440. 		}
  441. 	private:
  442. 		vector<Node*> _tables;
  443. 		size_t _n;
  444. 	};
  445. }

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

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

  

闽ICP备14008679号