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

【C++】哈希（unordered系列关联式容器）_c++ 容器 hash

作者：小小林熬夜学编程 | 2024-05-11 17:23:03

赞

踩

c++ 容器 hash

需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。

 目录

一、unordered系列的关联式容器

二、unordered系列容器

1、unordered_set

2、unordered_map

三、树形结构和哈希结构插入删除查找性能比较

四、哈希的底层结构

1、哈希结构

2、常见哈希函数

五、闭散列（开放定址法）

1、线性探测

1.1线性探测的插入、查找、删除

1.2线性探测的负载因子（70%-80%）及扩容方式

1.3如何将key值转整型

2、二次探测

六、开散列（拉链法、哈希桶）

1、开散列的概念

2、开散列的负载因子（100%）及扩容方式

七、闭散列和开散列整体代码

八、使用开散列对unordered_set和unordered_map就行封装

1、HashTable.h

2、Unordered_Set.h

3、Unorderer_Map.h

一、unordered系列的关联式容器

        在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到logN，最差情况下也仅需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，unordered系列容器并不是有序的。

        树状关联式容器对key的要求是比较大小，哈希对key的要求是转成整型，用于取模。它们都是通过仿函数来实现的。

二、unordered系列容器

1、unordered_set

        unordered_set并不像set那样支持反向迭代器，它的迭代器底层是一个单向迭代器。 其他功能与set类似。

        unordered_set的插入是无序的，不一定按照插入的顺序进行打印。自带去重功能。

2、unordered_map

单向迭代器+无序。其他功能与map类似。

三、树形结构和哈希结构插入删除查找性能比较

        红黑树的插入删除查找性能都是O(logN)而哈希表的插入删除查找性能理论上都是O(1)，他是相对于稳定的，最差情况下都是高效的。哈希表的插入删除操作的理论上时间复杂度是常数时间的，这有个前提就是哈希表不发生数据碰撞。在发生碰撞的最坏的情况下，哈希表的插入和删除时间复杂度为O(n)。

四、哈希的底层结构

1、哈希结构

        顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数。

        理想的搜索方法：那么可以不经过任何比较，一次直接从表中得到想要搜索的元素？

        如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。在哈希表中插入或查找的方法就叫做哈希函数。

2、常见哈希函数

1. 直接定址法--(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况（范围集中）

2. 除留余数法--(常用)

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，

按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

缺点：可能会存在哈希冲突（哈希碰撞）

哈希函数：1、闭散列(开放定址法)2、开散列(拉链法/哈希桶)

五、闭散列（开放定址法）

1、线性探测

1.1线性探测的插入、查找、删除

        18模10应将18放在数组下标为8的位置。8模10也应当将8放在数组下标为8的位置，但是这个坑位已经被18占了，此时发生哈希冲突，需要将8放在18的后面，8一直往后找，哪个位置没人就放在哪个位置。

        但是每一个坑位其实有三种状态：坑位为空、坑位不为空、坑位是一个被删除的数据。

        现在需要删除27，只需要找到27并将其状态标志位修改为删除状态即可，并不用真正的清除数据，但要注意的是，27的值还在，我们再次对27进行查找，需要先判断27的标志位，不然27明明删掉了，你还说找到了，那就离谱了。

1.2线性探测的负载因子（70%-80%）及扩容方式

        对于线性探测，是不会让这个数组处于充满的状态，需要控制负载因子保证数组长期处于相对恒定的充满率。

        负载因子=表中有效数据的个数/表的大小。负载因子越大，虽然空间利用率越高，但下一次插入时发生哈希冲突的概率越高！

        如何扩容：因为扩容后，表的大小变大，根据映射公式hashi=key%tablesize，整个数组的映射关系全部被改变，所以扩容时，需要将原有数据一个一个的重新映射进新数组。

1.3如何将key值转整型

size_t hashi = hf(kv.first) % _tables.size();

        哈希的核心就是取模，所以key需要能够被取模。一般来说，哈希的key都是整型或字符串，所以这里写了两个仿函数来将外部类型转换为size_t和string类型。

如果使用其他自定义类型充当key，需要自己仿函数，传入哈希。

  1. template <class K, class V>
  2. struct HashData//存储哈希的数据
  3. {
  4. 	std::pair<K, V> _kv;//存储节点的数据
  5. 	State _state = EMPTY;//节点的状态
  6. };
  7. template <class K>
  8. struct HashFunc//仿函数，控制hashi取模操作，把相近类型转为整型
  9. {
  10. 	size_t operator()(const K& key)
  11. 	{
  12. 		return (size_t)key;
  13. 	}
  14. };
  15. template <>//模板的特化 
  16. struct HashFunc<string>
  17. {
  18. 	size_t operator()(const std::string& key)
  19. 	{
  20. 		size_t hash = 0;//通过格式计算string的值
  21. 		//for (auto& ch : key)//直接相加哈希冲突概率大
  22. 		//{
  23. 		//	hash += ch;
  24. 		//}
  25. 		for (auto& ch : key)
  26. 		{
  27. 			hash = hash * 31 + ch;//也可以乘31,131,1313,13131,131313
  28. 		}
  29. 		return hash;
  30. 	}
  31. };

        对于string类型转整形，不能单纯的使用字符相加的方式进行转换，因为“abc”和“acb”依照字符串相加后的整型值是一样的，这就造成了哈希冲突。下面是一个大佬设计BKDR哈希算法，极大地降低了哈希冲突。

原文链接：各种字符串哈希函数

2、二次探测

        线性探测是start+i(加0，加1，加2，加3)，而二次探测就是start+i^2(加0，加1，加4，加9)

        当然二次探测同样没有从本质上解决问题，还是存在占别人坑位的情况。于是就提出了开散列（哈希桶）。

六、开散列（拉链法、哈希桶）

        unorder系统列的底层用的就是开散列。

1、开散列的概念

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

2、开散列的负载因子（100%）及扩容方式

        官方文档中规定开散列的负载因子是1，负载因子是1的意思是当哈希表的size等于节点数量时，就需要扩容了。

  1. if(_tables.size()==_n)
  2. {
  3.     //HashTable<K, V> newHT;
  4.     //newHT._tables.resize(_tables.size() * 2);
  5.     //for (auto& cur : _tables)//遍历表，不为空说明有桶
  6.     //{
  7.     //	while (cur)
  8.     //	{
  9.     //		依次取出旧表的数据插入新表
  10.     //		newHT.Insert(cur->_kv);
  11.     //		cur = cur->_next;
  12.     //	}
  13.     //}
  14.     //_tables.swap(newHT._tables);
  15.     std::vector<Node*> newtables;
  16.     newtables.resize(2 * _tables.size(), nullptr);//
  17.     for (size_t i = 0; i < _tables.size(); ++i)
  18.     {
  19.         Node* cur = _tables[i];
  20.         while (cur)
  21.         {
  22.             Node* next = cur->_next;
  23.             size_t hashi = Hash()(cur->_kv.first) % newtables.size();
  24.             cur->_next = newtables[hashi];
  25.             newtables[hashi] = cur;
  26.             cur = next;
  27.         }
  28.         _tables[i] = nullptr;//旧表置空。防止析构
  29.     }
  30.     _tables.swap(newtables);
  31. }
  1. ~HashTable()//析构函数，释放桶
  2. {
  3.     for (size_t i = 0; i < _tables.size(); ++i)
  4.     {
  5.         Node* cur = _tables[i];
  6.         while (cur)
  7.         {
  8.             Node* next = cur->_next;
  9.             delete cur;
  10.             cur = next;
  11.         }
  12.         _tables[i] = nullptr;
  13.     }
  14. }

        这里是两种扩容写法，注释掉的那一种是把原表的节点拷贝一份插入到新的哈希表，全部元素映射完毕后再交换哈希表。未注释的那种写法是通过修改哈希桶中单链表的指针指向，直接摘取原表元素，同样映射完毕后交换哈希表，没有拷贝构造的过程。不过用的时候记得将原表中的指向置空，否则藕断丝连，原表被交换后会发生析构，因为指向关系没有断，造成刚插入的数据全部被清空。

        为啥闭散列不能必须老老实实的拷贝？因为闭散列中的哈希表存的是值，开散列中存的是节点，节点可以摘下来，值不能摘啊。

        扩容时不一定是两倍，为了一定程度上缓解哈希冲突，stl底层给了扩容的数组大小，均为素数且近似两倍。不过别人拿到你的扩容源码，可以专门设置一组连续冲突的数据来恶心你(比如力扣刷题你用unordered系列。。。)。

        当哈希桶的节点挂载过多时，查找效率逐渐变低，像Java会在哈希桶节点数大于8时，将哈希桶的底层由单链表切换为红黑树。

七、闭散列和开散列整体代码

  1. #pragma once
  2. #include <iostream>
  3. #include <vector>
  4. template <class K>
  5. struct HashFunc//仿函数，控制hashi取模操作，把相近类型转为整型
  6. {
  7. 	size_t operator()(const K& key)
  8. 	{
  9. 		return (size_t)key;
  10. 	}
  11. };
  12. template <>//模板的特化 
  13. struct HashFunc < std::string >
  14. {
  15. 	size_t operator()(const std::string& key)
  16. 	{
  17. 		size_t hash = 0;//通过格式计算string的值
  18. 		//for (auto& ch : key)//直接相加哈希冲突概率大
  19. 		//{
  20. 		//	hash += ch;
  21. 		//}
  22. 		for (auto& ch : key)
  23. 		{
  24. 			hash = hash * 31 + ch;//也可以乘31,131,1313,13131,131313
  25. 		}
  26. 		return hash;
  27. 	}
  28. };
  29. namespace closeHash
  30. {
  31. 	enum State
  32. 	{
  33. 		EMPTY,
  34. 		EXIST,
  35. 		DELTE
  36. 	};
  37. 	template <class K, class V>
  38. 	struct HashData//存储哈希的数据
  39. 	{
  40. 		std::pair<K, V> _kv;//存储节点的数据
  41. 		State _state = EMPTY;//节点的状态
  42. 	};
  43. 	template <class K, class V, class Hash = HashFunc<K>>//Hash:把key转换为可以取模的整型
  44. 	class HashTable
  45. 	{
  46. 		typedef HashData<K, V> Data;
  47. 	public:
  48. 		HashTable()
  49. 			:_n(10)
  50. 		{
  51. 			_tables.resize(10);
  52. 		}
  53. 		bool Insert(const std::pair<K, V>& kv)
  54. 		{
  55. 			if (Find(kv.first) != nullptr)
  56. 				return false;
  57. 			//大于标定的负载因子，就扩容
  58. 			if (_n * 10 >= 7 * _tables.size())
  59. 			{
  60. 				HashTable<K, V> newHT;
  61. 				newHT._tables.resize(_tables.size() * 2);
  62. 				for (auto& e : _tables)
  63. 				{
  64. 					if (e._state == EXIST)
  65. 					{
  66. 						newHT.Insert(e._kv);
  67. 					}
  68. 				}
  69. 				_tables.swap(newHT._tables);
  70. 			}
  71. 			Hash hf;
  72. 			size_t hashi = hf(kv.first) % _tables.size();//找到首先要插入的位置。如果kv.first是string呢？如何取模？
  73. 			while (_tables[hashi]._state == EXIST)   //先将string转化为整数，再进行取模操作？应该用仿函数
  74. 			{
  75. 				++hashi;//线性探测
  76. 				hashi %= _tables.size();
  77.  
  78. 			}
  79. 			//走到这里就是删除或空
  80. 			_tables[hashi]._kv = kv;
  81. 			_tables[hashi]._state = EXIST;
  82. 			++_n;
  83. 			return true;
  84. 		}
  85. 		Data* Find(const K& key)
  86. 		{
  87. 			Hash hf;
  88. 			size_t hashi = hf(key) % _tables.size();
  89. 			while (_tables[hashi]._state != EMPTY)/
  90. 			{
  91. 				if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)//存在且为key
  92. 					return &_tables[hashi];
  93. 				else
  94. 					++hashi;
  95. 				hashi %= _tables.size();
  96. 			}
  97. 			return nullptr;
  98. 		}
  99. 		bool Erase(const K& key)
  100. 		{
  101. 			Data* ret = Find(key);
  102. 			if (ret != nullptr)
  103. 			{
  104. 				ret->_state = DELTE;
  105. 				--_n;
  106. 				return true;
  107. 			}
  108. 			return false;
  109. 		}
  110. 	private:
  111. 		std::vector<Data> _tables;
  112. 		size_t _n = 0;//表中存储的有效数据的个数
  113. 	};
  114. 	void HashTest()
  115. 	{
  116. 		HashTable<int, int> ht;
  117. 		int a[] = { 18,8,7,27,57,3,38,18 };
  118. 		for (auto& e : a)
  119. 		{
  120. 			ht.Insert(std::make_pair(e, e));
  121. 		}
  122. 		ht.Insert(std::make_pair(17, 17));
  123. 		ht.Insert(std::make_pair(5, 5));
  124.  
  125. 		std::cout << ht.Find(7) << std::endl;
  126. 		std::cout << ht.Find(8) << std::endl;
  127. 		ht.Erase(7);
  128. 		std::cout << ht.Find(7) << std::endl;
  129. 		std::cout << ht.Find(8) << std::endl;
  130. 	}
  131. }
  132. namespace buckets
  133. {
  134. 	template<class K, class V>
  135. 	struct HashNode
  136. 	{
  137. 		std::pair<K, V> _kv;
  138. 		HashNode<K, V>* _next;
  139.  
  140. 		HashNode(const std::pair<K,V>& kv)
  141. 			:_kv(kv)
  142. 			, _next(nullptr)
  143. 		{}
  144. 		
  145. 	};
  146. 	template <class K, class V, class Hash = HashFunc<K>>
  147. 	class HashTable
  148. 	{
  149. 		typedef HashNode<K, V> Node;
  150. 	public:
  151. 		HashTable()
  152. 			:_n(0)
  153. 		{
  154. 			_tables.resize(__stl_next_prime(0));
  155. 		}
  156. 		~HashTable()//释放桶
  157. 		{
  158. 			for (size_t i = 0; i < _tables.size(); ++i)
  159. 			{
  160. 				Node* cur = _tables[i];
  161. 				while (cur)
  162. 				{
  163. 					Node* next = cur->_next;
  164. 					delete cur;
  165. 					cur = next;
  166. 				}
  167. 				_tables[i] = nullptr;
  168. 			}
  169. 		}
  170. 		bool Insert(const std::pair<K, V>& kv)
  171. 		{
  172. 			if (Find(kv.first))
  173. 				return false;
  174. 			//负载因子控制在1,超过就扩容
  175. 			if(_tables.size()==_n)
  176. 			{
  177. 				//HashTable<K, V> newHT;
  178. 				//newHT._tables.resize(_tables.size() * 2);
  179. 				//for (auto& cur : _tables)//遍历表，不为空说明有桶
  180. 				//{
  181. 				//	while (cur)
  182. 				//	{
  183. 				//		依次取出旧表的数据插入新表
  184. 				//		newHT.Insert(cur->_kv);
  185. 				//		cur = cur->_next;
  186. 				//	}
  187. 				//}
  188. 				//_tables.swap(newHT._tables);
  189. 				std::vector<Node*> newtables;
  190. 				//newtables.resize(2 * _tables.size(), nullptr);//不是2倍扩容
  191. 				newtables.resize(__stl_next_prime(_tables.size()), nullptr);
  192. 				for (size_t i = 0; i < _tables.size(); ++i)
  193. 				{
  194. 					Node* cur = _tables[i];
  195. 					while (cur)
  196. 					{
  197. 						Node* next = cur->_next;
  198. 						size_t hashi = Hash()(cur->_kv.first) % newtables.size();
  199. 						cur->_next = newtables[hashi];
  200. 						newtables[hashi] = cur;
  201. 						cur = next;
  202. 					}
  203. 					_tables[i] = nullptr;//旧表置空。防止析构
  204. 				}
  205. 				_tables.swap(newtables);
  206. 			}
  207. 			size_t hashi = Hash()(kv.first) % _tables.size();
  208. 			//找到插入位置就头插至桶中
  209. 			Node* newNode = new Node(kv);
  210. 			newNode->_next = _tables[hashi];//_tables[hashi]存的是第一个元素的地址
  211. 			_tables[hashi] = newNode;
  212. 			++_n;
  213. 			return true;
  214. 		}
  215. 		Node* Find(const K& key)
  216. 		{
  217. 			size_t hashi = Hash()(key) % _tables.size();
  218. 			Node* cur = _tables[hashi];
  219. 			while (cur)
  220. 			{
  221. 				if (cur->_kv.first != key)
  222. 				{
  223. 					cur = cur->_next;
  224. 				}
  225. 				else
  226. 					return cur;
  227. 			}
  228. 			return nullptr;
  229. 		}
  230. 		bool Erase(const K& key)
  231. 		{
  232. 			size_t hashi = Hash()(key) % _tables.size();
  233. 			Node* cur = _tables[hashi];
  234. 			Node* prev = nullptr;
  235. 			while (cur)
  236. 			{
  237. 				
  238. 				Node* next = cur->_next;
  239. 				if (cur->_kv.first == key)
  240. 				{
  241. 					delete cur;
  242. 					if (prev == nullptr)
  243. 					{
  244. 						_tables[hashi] = next;
  245. 					}
  246. 					else
  247. 					{
  248. 						prev->_next = next;
  249. 					}
  250. 					--_n;
  251. 					return true;
  252. 				}
  253. 				prev = cur;
  254. 				cur = next;
  255. 			}
  256. 			return false;
  257. 		}
  258. 		inline unsigned long __stl_next_prime(unsigned long n)
  259. 		{
  260. 			static const int __stl_num_primes = 28;
  261. 			static const unsigned long __stl_prime_list[__stl_num_primes] =
  262. 			{
  263. 				53, 97, 193, 389, 769,
  264. 				1543, 3079, 6151, 12289, 24593,
  265. 				49157, 98317, 196613, 393241, 786433,
  266. 				1572869, 3145739, 6291469, 12582917, 25165843,
  267. 				50331653, 100663319, 201326611, 402653189, 805306457,
  268. 				1610612741, 3221225473, 4294967291
  269. 			};
  270.  
  271. 			for (int i = 0; i < __stl_num_primes; ++i)
  272. 			{
  273. 				if (__stl_prime_list[i] > n)
  274. 				{
  275. 					return __stl_prime_list[i];
  276. 				}
  277. 			}
  278.  
  279. 			return __stl_prime_list[__stl_num_primes - 1];//否则返回设定的最大值，够用了
  280. 		}
  281. 	private:
  282. 		std::vector<Node*> _tables;//需要写析构,释放单链表的节点
  283. 		size_t _n = 0;
  284. 	};
  285. 	void HashTest()
  286. 	{
  287. 		HashTable<int, int> ht;
  288. 		int a[] = { 18,8,7,27,57,3,38,18 ,17,88,38,28,48 };
  289. 		for (auto& e : a)
  290. 		{
  291. 			ht.Insert(std::make_pair(e, e));
  292. 		}
  293. 		ht.Insert(std::make_pair(5, 5));
  294. 		ht.Erase(5);
  295. 	}
  296. }

八、使用开散列对unordered_set和unordered_map就行封装

1、HashTable.h

  1. #pragma once
  2. #include <iostream>
  3. #include <vector>
  4. template <class K>
  5. struct HashFunc//仿函数，控制hashi取模操作，把相近类型转为整型
  6. {
  7. 	size_t operator()(const K& key)
  8. 	{
  9. 		return (size_t)key;
  10. 	}
  11. };
  12. template <>//模板的特化 
  13. struct HashFunc < std::string >
  14. {
  15. 	size_t operator()(const std::string& key)
  16. 	{
  17. 		size_t hash = 0;//通过格式计算string的值
  18. 		//for (auto& ch : key)//直接相加哈希冲突概率大
  19. 		//{
  20. 		//	hash += ch;
  21. 		//}
  22. 		for (auto& ch : key)
  23. 		{
  24. 			hash = hash * 31 + ch;//也可以乘31,131,1313,13131,131313
  25. 		}
  26. 		return hash;
  27. 	}
  28. };
  29. namespace closeHash
  30. {
  31. 	enum State
  32. 	{
  33. 		EMPTY,
  34. 		EXIST,
  35. 		DELTE
  36. 	};
  37. 	template <class K, class V>
  38. 	struct HashData//存储哈希的数据
  39. 	{
  40. 		std::pair<K, V> _kv;//存储节点的数据
  41. 		State _state = EMPTY;//节点的状态
  42. 	};
  43. 	template <class K, class V, class Hash = HashFunc<K>>//Hash:把key转换为可以取模的整型
  44. 	class HashTable
  45. 	{
  46. 		typedef HashData<K, V> Data;
  47. 	public:
  48. 		HashTable()
  49. 			:_n(10)
  50. 		{
  51. 			_tables.resize(10);
  52. 		}
  53. 		bool Insert(const std::pair<K, V>& kv)
  54. 		{
  55. 			if (Find(kv.first) != nullptr)
  56. 				return false;
  57. 			//大于标定的负载因子，就扩容
  58. 			if (_n * 10 >= 7 * _tables.size())
  59. 			{
  60. 				HashTable<K, V> newHT;
  61. 				newHT._tables.resize(_tables.size() * 2);
  62. 				for (auto& e : _tables)
  63. 				{
  64. 					if (e._state == EXIST)
  65. 					{
  66. 						newHT.Insert(e._kv);
  67. 					}
  68. 				}
  69. 				_tables.swap(newHT._tables);
  70. 			}
  71. 			Hash hf;
  72. 			size_t hashi = hf(kv.first) % _tables.size();//找到首先要插入的位置。如果kv.first是string呢？如何取模？
  73. 			while (_tables[hashi]._state == EXIST)   //先将string转化为整数，再进行取模操作？应该用仿函数
  74. 			{
  75. 				++hashi;//线性探测
  76. 				hashi %= _tables.size();
  77.  
  78. 			}
  79. 			//走到这里就是删除或空
  80. 			_tables[hashi]._kv = kv;
  81. 			_tables[hashi]._state = EXIST;
  82. 			++_n;
  83. 			return true;
  84. 		}
  85. 		Data* Find(const K& key)
  86. 		{
  87. 			Hash hf;
  88. 			//size_t hashi = hf(key) % _tables.size();
  89.             size_t starti=hashi;
  90. 			while (_tables[hashi]._state != EMPTY)/
  91. 			{
  92. 				if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)//存在且为key
  93. 					return &_tables[hashi];
  94. 				else
  95. 					++hashi;
  96. 				hashi %= _tables.size();
  97.                 //极端场景下，没有空，全是存在或删除状态
  98.                 if(hashi==starti)
  99.                 {
  100.                     break;
  101.                 }
  102. 			}
  103. 			return nullptr;
  104. 		}
  105. 		bool Erase(const K& key)
  106. 		{
  107. 			Data* ret = Find(key);
  108. 			if (ret != nullptr)
  109. 			{
  110. 				ret->_state = DELTE;
  111. 				--_n;
  112. 				return true;
  113. 			}
  114. 			return false;
  115. 		}
  116. 	private:
  117. 		std::vector<Data> _tables;
  118. 		size_t _n = 0;//表中存储的有效数据的个数
  119. 	};
  120. 	void HashTest()
  121. 	{
  122. 		HashTable<int, int> ht;
  123. 		int a[] = { 18,8,7,27,57,3,38,18 };
  124. 		for (auto& e : a)
  125. 		{
  126. 			ht.Insert(std::make_pair(e, e));
  127. 		}
  128. 		ht.Insert(std::make_pair(17, 17));
  129. 		ht.Insert(std::make_pair(5, 5));
  130.  
  131. 		std::cout << ht.Find(7) << std::endl;
  132. 		std::cout << ht.Find(8) << std::endl;
  133. 		ht.Erase(7);
  134. 		std::cout << ht.Find(7) << std::endl;
  135. 		std::cout << ht.Find(8) << std::endl;
  136. 	}
  137. }
  138. namespace buckets
  139. {
  140. 	template<class T>
  141. 	struct HashNode
  142. 	{
  143. 		//std::pair<K, V> _kv;
  144. 		T _data;
  145. 		HashNode<T>* _next;
  146.  
  147. 		HashNode(const T& data)
  148. 			:_data(data)
  149. 			, _next(nullptr)
  150. 		{}
  151. 		
  152. 	};  
  153. 	//哈希表引用迭代器，迭代器引用哈希表的类型，相互引用，需要先前置声明
  154. 	template <class K, class T, class Hash, class KeyOfT>
  155. 	class HashTable;
  156. 	template <class K, class T, class Hash, class KeyOfT>
  157. 	struct __HTIterator
  158. 	{
  159. 		typedef HashNode<T> Node;
  160. 		typedef __HTIterator<K, T, Hash,KeyOfT> Self;
  161. 		typedef HashTable<K, T, Hash, KeyOfT> HT;
  162. 		Node* _node;
  163. 		HT* _ht;
  164. 		__HTIterator(Node* node,HT* ht)
  165. 			:_node(node)
  166. 			,_ht(ht)
  167. 		{}
  168. 		Self& operator++()
  169. 		{
  170. 			if (_node->_next)
  171. 			{
  172. 				_node = _node->_next;
  173. 			}
  174. 			else//当前桶走完了，需要找下一个桶
  175. 			{
  176. 				KeyOfT kot;
  177. 				Hash hash;
  178. 				size_t hashi = hash(kot(_node->_data))%(_ht->_tables.size());//等价于Hash()(KeyOfT()(_node->_data))
  179. 				++hashi;//因为迭代器++是找下一个元素，这个桶走完了，跳过当前hashi
  180. 				while (hashi<_ht->_tables.size())//如果hashi没越界
  181. 				{
  182. 					if (_ht->_tables[hashi]) //哈希表不为空
  183. 					{
  184. 						_node = _ht->_tables[hashi];
  185. 						break;
  186. 					}
  187. 					++hashi;
  188. 				}
  189. 				//说明没有桶了，找完了找不到
  190. 				if (hashi == _ht->_tables.size())
  191. 					_node = nullptr;
  192. 			}
  193. 			return *this;
  194. 		}
  195. 		T& operator*()
  196. 		{
  197. 			return _node->_data;
  198. 		}
  199. 		T* operator->()
  200. 		{
  201. 			return &(_node->_data);
  202. 		}
  203. 		bool operator!=(const Self& it)const
  204. 		{
  205. 			return _node != it._node;
  206. 		}
  207. 		
  208. 	};
  209. 	template <class K, class T, class Hash,class KeyOfT>
  210. 	class HashTable
  211. 	{
  212. 		template <class K, class T, class Hash, class KeyOfT>
  213. 		friend struct __HTIterator;
  214. 		typedef HashNode<T> Node;
  215. 	public:
  216. 		typedef __HTIterator<K, T, Hash, KeyOfT> iterator;
  217. 		iterator begin()
  218. 		{
  219. 			for (size_t i = 0; i < _tables.size(); ++i)
  220. 			{
  221. 				if (_tables[i] != nullptr)
  222. 					return iterator(_tables[i], this);
  223. 			}
  224. 			return iterator(nullptr, this);
  225. 		}
  226. 		iterator end()
  227. 		{
  228. 			return iterator(nullptr, this);
  229. 		}
  230. 		HashTable()
  231. 			:_n(0)
  232. 		{
  233. 			_tables.resize(__stl_next_prime(0));
  234. 		}
  235. 		~HashTable()//释放桶
  236. 		{
  237. 			for (size_t i = 0; i < _tables.size(); ++i)
  238. 			{
  239. 				Node* cur = _tables[i];
  240. 				while (cur)
  241. 				{
  242. 					Node* next = cur->_next;
  243. 					delete cur;
  244. 					cur = next;
  245. 				}
  246. 				_tables[i] = nullptr;
  247. 			}
  248. 		}
  249. 		std::pair<iterator,bool> Insert(const T& data)
  250. 		{
  251. 			KeyOfT kot;
  252. 			iterator it = Find(kot(data));
  253. 			if (it!=end())//说明找到了相同元素。返回false
  254. 				return std::make_pair(it,false);
  255. 			//负载因子控制在1,超过就扩容
  256. 			if(_tables.size()==_n)
  257. 			{
  258. 				//HashTable<K, V> newHT;
  259. 				//newHT._tables.resize(_tables.size() * 2);
  260. 				//for (auto& cur : _tables)//遍历表，不为空说明有桶
  261. 				//{
  262. 				//	while (cur)
  263. 				//	{
  264. 				//		依次取出旧表的数据插入新表
  265. 				//		newHT.Insert(cur->_kv);
  266. 				//		cur = cur->_next;
  267. 				//	}
  268. 				//}
  269. 				//_tables.swap(newHT._tables);
  270. 				std::vector<Node*> newtables;
  271. 				//newtables.resize(2 * _tables.size(), nullptr);//不是2倍扩容
  272. 				newtables.resize(__stl_next_prime(_tables.size()), nullptr);
  273. 				for (size_t i = 0; i < _tables.size(); ++i)
  274. 				{
  275. 					Node* cur = _tables[i];
  276. 					while (cur)
  277. 					{
  278. 						Node* next = cur->_next;
  279. 						size_t hashi = Hash()(kot(cur->_data)) % newtables.size();
  280. 						cur->_next = newtables[hashi];
  281. 						newtables[hashi] = cur;
  282. 						cur = next;
  283. 					}
  284. 					_tables[i] = nullptr;//旧表置空。防止析构
  285. 				}
  286. 				_tables.swap(newtables);
  287. 			}
  288. 			size_t hashi = Hash()(kot(data)) % _tables.size();
  289. 			//找到插入位置就头插至桶中
  290. 			Node* newNode = new Node(data);
  291. 			newNode->_next = _tables[hashi];//_tables[hashi]存的是第一个元素的地址
  292. 			_tables[hashi] = newNode;
  293. 			++_n;
  294. 			return std::make_pair(iterator(newNode,this),true);
  295. 		}
  296. 		iterator Find(const K& key)
  297. 		{
  298. 			KeyOfT kot;
  299. 			size_t hashi = Hash()(key) % _tables.size();
  300. 			Node* cur = _tables[hashi];
  301. 			while (cur)
  302. 			{
  303. 				if (kot(cur->_data) != key)
  304. 				{
  305. 					cur = cur->_next;
  306. 				}
  307. 				else
  308. 					return iterator(cur,this);
  309. 			}
  310. 			return iterator(nullptr,this);
  311. 		}
  312. 		bool Erase(const K& key)
  313. 		{
  314. 			size_t hashi = Hash()(key) % _tables.size();
  315. 			Node* cur = _tables[hashi];
  316. 			Node* prev = nullptr;
  317. 			while (cur)
  318. 			{
  319. 				
  320. 				Node* next = cur->_next;
  321. 				if (cur->_kv.first == key)
  322. 				{
  323. 					delete cur;
  324. 					if (prev == nullptr)
  325. 					{
  326. 						_tables[hashi] = next;
  327. 					}
  328. 					else
  329. 					{
  330. 						prev->_next = next;
  331. 					}
  332. 					--_n;
  333. 					return true;
  334. 				}
  335. 				prev = cur;
  336. 				cur = next;
  337. 			}
  338. 			return false;
  339. 		}
  340. 		inline unsigned long __stl_next_prime(unsigned long n)
  341. 		{
  342. 			static const int __stl_num_primes = 28;
  343. 			static const unsigned long __stl_prime_list[__stl_num_primes] =
  344. 			{
  345. 				53, 97, 193, 389, 769,
  346. 				1543, 3079, 6151, 12289, 24593,
  347. 				49157, 98317, 196613, 393241, 786433,
  348. 				1572869, 3145739, 6291469, 12582917, 25165843,
  349. 				50331653, 100663319, 201326611, 402653189, 805306457,
  350. 				1610612741, 3221225473, 4294967291
  351. 			};
  352.  
  353. 			for (int i = 0; i < __stl_num_primes; ++i)
  354. 			{
  355. 				if (__stl_prime_list[i] > n)
  356. 				{
  357. 					return __stl_prime_list[i];
  358. 				}
  359. 			}
  360.  
  361. 			return __stl_prime_list[__stl_num_primes - 1];//否则返回设定的最大值，够用了
  362. 		}
  363. 	private:
  364. 		std::vector<Node*> _tables;//需要写析构,释放单链表的节点
  365. 		size_t _n = 0;
  366. 	};
  367. 	/*void HashTest()
  368. 	{
  369. 		HashTable<int, int> ht;
  370. 		int a[] = { 18,8,7,27,57,3,38,18 ,17,88,38,28,48 };
  371. 		for (auto& e : a)
  372. 		{
  373. 			ht.Insert(std::make_pair(e, e));
  374. 		}
  375. 		ht.Insert(std::make_pair(5, 5));
  376. 		ht.Erase(5);
  377. 	}*/
  378. }

2、Unordered_Set.h

  1. #pragma once
  2. #include "HashTable.h"
  3. namespace jly
  4. {
  5. 	template <class K, class Hash= HashFunc<K>>//K:key;Hash:将key转为整型的仿函数
  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 buckets::HashTable<K, K,Hash, SetKeyOfT>::iterator iterator;
  17. 		iterator begin()
  18. 		{
  19. 			return _ht.begin();
  20. 		}
  21. 		iterator end()
  22. 		{
  23. 			return _ht.end();
  24. 		}
  25. 		iterator Find(const K& key)
  26. 		{
  27. 			return _ht.Find(key);
  28. 		}
  29. 		bool erase(const K& key)
  30. 		{
  31. 			return _ht.Erase(key);
  32. 		}
  33. 		std::pair<iterator, bool> Insert(const K& data)
  34. 		{
  35. 			return _ht.Insert(data);
  36. 		}
  37.  
  38. 	private:
  39. 		buckets::HashTable<K, K,Hash,SetKeyOfT> _ht;
  40. 	};
  41. 	void test_unordered_set()
  42. 	{
  43. 		unordered_set<int> us;
  44. 		us.Insert(3);
  45. 		us.Insert(13);
  46. 		us.Insert(23);
  47. 		us.Insert(5);
  48. 		us.Insert(5);
  49. 		us.Insert(6);
  50. 		us.Insert(106);
  51. 		us.Insert(53);
  52.  
  53. 		unordered_set<int>::iterator it = us.begin();
  54. 		while (it != us.end())
  55. 		{
  56. 			std::cout << *it << " ";
  57. 			++it;
  58. 		}
  59. 		std::cout << std::endl;
  60. 		for (auto& e : us)
  61. 		{
  62. 			std::cout << e << " ";
  63. 		}
  64. 	}
  65. }

3、Unorderer_Map.h

  1. #pragma once
  2. #include "HashTable.h"
  3. namespace jly
  4. {
  5.  
  6. 	template <class K, class V,class Hash = HashFunc<K>>//Hash:将key转为整型的仿函数
  7. 	class unordered_map
  8. 	{
  9. 		struct MapKeyOfT
  10. 		{
  11. 			const K& operator()(const std::pair<const K, V>& kv)
  12. 			{
  13. 				return kv.first;
  14. 			} 
  15. 		};
  16. 	public:
  17. 		typedef typename buckets::HashTable<K, std::pair<const K, V>, Hash, MapKeyOfT>::iterator iterator;
  18. 		std::pair<iterator,bool> Insert(const std::pair<K, V>& data)
  19. 		{
  20. 			return _ht.Insert(data);
  21. 		}
  22. 		V& operator[](const K& key)
  23. 		{
  24. 			std::pair<iterator, bool> ret = _ht.Insert(std::make_pair(key, V()));
  25. 			return  ret.first->second;
  26.  
  27. 		}
  28. 		iterator Find(const K& key)
  29. 		{
  30. 			return _ht.Find(key);
  31. 		}
  32. 		bool erase(const K& key)
  33. 		{
  34. 			return _ht.Erase(key);
  35. 		}
  36. 		iterator begin()
  37. 		{
  38. 			return _ht.begin();
  39. 		}
  40. 		iterator end()
  41. 		{
  42. 			return _ht.end();
  43. 		}
  44. 	private:
  45. 		buckets::HashTable<K, std::pair<const K,V>,Hash, MapKeyOfT> _ht;
  46. 	};
  47. 	void test_unordered_map()
  48. 	{
  49. 		std::string arr[] = { "牛奶", "水罐", "冰", "牛奶", "冰", "水罐", 
  50. 			"冰", "冰", "冰", "木头", "冰", "木头" };
  51.  
  52. 		unordered_map<std::string, int> countMap;
  53. 		for (auto& e : arr)
  54. 		{
  55. 			countMap[e]++;
  56. 		}
  57.  
  58. 		for (const auto& kv : countMap)
  59. 		{
  60. 			std::cout << kv.first << ":" << kv.second << std::endl;
  61. 		}
  62. 	}
  63. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/555618
推荐阅读
相关标签

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

  

闽ICP备14008679号