• C++ STL(九) -------- 哈希表封装unordered_map和unordered_set

    目录

    1.哈希表源代码

    2.哈希表模板参数的控制

    3.string类型无法取模的问题

    4.哈希表默认成员函数实现

    5.哈希表正向迭代器的实现

    6.哈希表的实现进行补充 

    7.unordered_set的模拟实现 

    8.unordered_map的模拟实现 

    9.封装之后的代码

     

    1.哈希表源代码

    • 对一个KV模型的哈希表进行封装，同时模拟实现出C++STL库当中的unordered_map和unordered_set
    1. //每个哈希桶中存储数据的结构
    2. template<class K, class V>
    3. struct HashNode
    4. {
    5. 	pair _kv;
    6. 	HashNode* _next;
    7.  
    8. 	//构造函数
    9. 	HashNode(const pair& kv)
    10. 		:_kv(kv)
    11. 		, _next(nullptr)
    12. 	{}
    13. };
    14.  
    15. //哈希表
    16. template<class K, class V>
    17. class HashTable
    18. {
    19. 	typedef HashNode Node; //哈希结点类型
    20. public:
    21.  
    22. 	//获取本次增容后哈希表的大小
    23. 	size_t GetNextPrime(size_t prime)
    24. 	{
    25. 		const int PRIMECOUNT = 28;
    26. 		//素数序列
    27. 		const size_t primeList[PRIMECOUNT] =
    28. 		{
    29. 			53ul, 97ul, 193ul, 389ul, 769ul,
    30. 			1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    31. 			49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    32. 			1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    33. 			50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    34. 			1610612741ul, 3221225473ul, 4294967291ul
    35. 		};
    36.  
    37. 		size_t i = 0;
    38. 		for (i = 0; i < PRIMECOUNT; i++)
    39. 		{
    40. 			if (primeList[i] > prime)
    41. 				return primeList[i];
    42. 		}
    43. 		return primeList[i];
    44. 	}
    45.  
    46.  
    47. 	//插入函数
    48. 	bool Insert(const pair& kv)
    49. 	{
    50. 		//1、查看哈希表中是否存在该键值的键值对
    51. 		Node* ret = Find(kv.first);
    52. 		if (ret) //哈希表中已经存在该键值的键值对（不允许数据冗余）
    53. 		{
    54. 			return false; //插入失败
    55. 		}
    56.  
    57. 		//2、判断是否需要调整哈希表的大小
    58. 		if (_n == _table.size()) //哈希表的大小为0，或负载因子超过1
    59. 		{
    60. 			//增容
    61. 			//a、创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍（若哈希表大小为0，则将哈希表的初始大小设置为10）
    62. 			vector newtable;
    63.  
    64. 			newtable.resize(GetNextPrime(_table.size()));
    65. 				
    66. 			//b、将原哈希表当中的结点插入到新哈希表
    67. 			for (size_t i = 0; i < _table.size(); i++)
    68. 			{
    69. 				if (_table[i]) //桶不为空
    70. 				{
    71. 					Node* cur = _table[i];
    72. 					while (cur) //将该桶的结点取完为止
    73. 					{
    74. 						Node* next = cur->_next; //记录cur的下一个结点
    75. 						size_t index = cur->_kv.first%newtable.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
    76. 						//将该结点头插到新哈希表中编号为index的哈希桶中
    77. 						cur->_next = newtable[index];
    78. 						newtable[index] = cur;
    79.  
    80. 						cur = next; //取原哈希表中该桶的下一个结点
    81. 					}
    82. 					_table[i] = nullptr; //该桶取完后将该桶置空
    83. 				}
    84. 			}
    85. 			//c、交换这两个哈希表
    86. 			_table.swap(newtable);
    87. 		}
    88.  
    89. 		//3、将键值对插入哈希表
    90. 		size_t index = kv.first % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
    91. 		Node* newnode = new Node(kv); //根据所给数据创建一个待插入结点
    92. 		//将该结点头插到新哈希表中编号为index的哈希桶中
    93. 		newnode->_next = _table[index];
    94. 		_table[index] = newnode;
    95.  
    96. 		//4、哈希表中的有效元素个数加一
    97. 		_n++;
    98. 		return true;
    99. 	}
    100.  
    101. 	//查找函数
    102. 	HashNode* Find(const K& key)
    103. 	{
    104. 		if (_table.size() == 0) //哈希表大小为0，查找失败
    105. 		{
    106. 			return nullptr;
    107. 		}
    108.  
    109. 		size_t index = key % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
    110. 		//遍历编号为index的哈希桶
    111. 		HashNode* cur = _table[index];
    112. 		while (cur) //直到将该桶遍历完为止
    113. 		{
    114. 			if (cur->_kv.first == key) //key值匹配，则查找成功
    115. 			{
    116. 				return cur;
    117. 			}
    118. 			cur = cur->_next;
    119. 		}
    120. 		return nullptr; //直到该桶全部遍历完毕还没有找到目标元素，查找失败
    121. 	}
    122.  
    123. 	//删除函数
    124. 	bool Erase(const K& key)
    125. 	{
    126. 		//1、通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
    127. 		size_t index = key % _table.size();
    128. 		//2、在编号为index的哈希桶中寻找待删除结点
    129. 		Node* prev = nullptr;
    130. 		Node* cur = _table[index];
    131. 		while (cur) //直到将该桶遍历完为止
    132. 		{
    133. 			if (cur->_kv.first == key) //key值匹配，则查找成功
    134. 			{
    135. 				//3、若找到了待删除结点，则删除该结点
    136. 				if (prev == nullptr) //待删除结点是哈希桶中的第一个结点
    137. 				{
    138. 					_table[index] = cur->_next; //将第一个结点从该哈希桶中移除
    139. 				}
    140. 				else //待删除结点不是哈希桶的第一个结点
    141. 				{
    142. 					prev->_next = cur->_next; //将该结点从哈希桶中移除
    143. 				}
    144. 				delete cur; //释放该结点
    145.  
    146. 				//4、删除结点后，将哈希表中的有效元素个数减一
    147. 				_n--;
    148. 				return true; //删除成功
    149. 			}
    150. 			prev = cur;
    151. 			cur = cur->_next;
    152. 		}
    153. 		//假删除可能会导致迭代器失效
    154. 			
    155. 		return false; //直到该桶全部遍历完毕还没有找到待删除元素，删除失败
    156. 	}
    157. private:
    158. 	vector _table; //哈希表
    159. 	size_t _n = 0; //哈希表中的有效元素个数
    160. };

                            

                                            

    2.哈希表模板参数的控制

    (1)用一份哈希表代码同时封装出K模型和KV模型的容器，我们必定要对哈希表的模板参数进行控制。 

    ①与原哈希表的模板参数进行区分，这里将哈希表的第二个模板参数的名字改为T

    1. template<class K, class T>
    2. class HashTable

                     

    ②如果上层使用的是unordered_set容器，那么传入哈希表的模板参数就是key和key

    1. template<class K>
    2. class unordered_set
    3. {
    4. public:
    5. 	//...
    6. private:
    7. 	HashTable _ht; //传入底层哈希表的是K和K
    8. };

                     

     ③如果上层使用的是unordered_map容器，那么传入哈希表的模板参数就是key以及key和value构成的键值对

    1. template<class K, class V>
    2. class unordered_map
    3. {
    4. public:
    5. 	//...
    6. private:
    7. 	HashTable> _ht; //传入底层哈希表的是K以及K和V构成的键值对
    8. };

                     

    ④哈希表中的模板参数T的类型到底是什么，完全却决于上层所使用容器的种类。

                             

    ⑤更改模板参数后，哈希结点的定义如下 

    1. //哈希结点的定义
    2. template<class T>
    3. struct HashNode
    4. {
    5. 	T _data;
    6. 	HashNode* _next;
    7.  
    8. 	//构造函数
    9. 	HashNode(const T& data)
    10. 		:_data(data)
    11. 		, _next(nullptr)
    12. 	{}
    13. };

                             

    (2)仿函数获取键值

    现在由于我们在哈希结点当中存储的数据类型是T，这个T可能就是一个键值，也可能是一个键值对，对于底层的哈希表来说，它并不知道哈希结点当中存储的数据究竟是什么类型，因此需要由上层容器提供一个仿函数，用于获取T类型数据当中的键值。 

                             

    ①unordered_map容器需要向底层哈希表提供一个仿函数，该仿函数返回键值对当中的键值。 

    1. template<class K, class V>
    2. class unordered_map
    3. {
    4. 	//仿函数
    5. 	struct MapKeyOfT
    6. 	{
    7. 		const K& operator()(const pair& kv) //返回键值对当中的键值key
    8. 		{
    9. 			return kv.first;
    10. 		}
    11. 	};
    12. public:
    13. 	//...
    14. private:
    15. 	HashTable, MapKeyOfT> _ht;
    16. };

                             

     ②unordered_set容器传入哈希表的T就是键值，但是底层哈希表并不知道上层容器的种类，底层哈希表在获取键值时会统一通过传入的仿函数进行获取，因此unordered_set容器也需要向底层哈希表提供一个仿函数。

    1. template<class K>
    2. class unordered_set
    3. {
    4. 	//仿函数
    5. 	struct SetKeyOfT
    6. 	{
    7. 		const K& operator()(const K& key) //返回键值key
    8. 		{
    9. 			return key;
    10. 		}
    11. 	};
    12. public:
    13. 	//...
    14. private:
    15. 	HashTable _ht;
    16. };

    ·· 

    ③底层哈希表的模板参数现在需要增加一个，用于接收上层容器提供的仿函数。

    1. template<class K, class T, class KeyOfT>
    2. class HashTable

                            

                            

                             

    3.string类型无法取模的问题

    (1)字符串无法取模，是哈希问题中最常见的问题

    • 经过上面的分析后，我们让哈希表增加了一个模板参数，此时无论上层容器是unordered_set还是unordered_map，我们都能够通过上层容器提供的仿函数获取到元素的键值。
    • 但是在我们日常编写的代码中，用字符串去做键值key是非常常见的事，比如我们用unordered_map容器统计水果出现的次数时，就需要用各个水果的名字作为键值。
    • 而字符串并不是整型，也就意味着字符串不能直接用于计算哈希地址，我们需要通过某种方法将字符串转换成整型后，才能代入哈希函数计算哈希地址。
    • 但遗憾的是，我们无法找到一种能实现字符串和整型之间一对一转换的方法，因为在计算机中，整型的大小是有限的，比如用无符号整型能存储的最大数字是4294967295，而众多字符能构成的字符串的种类却是无限的。
    • 鉴于此，无论我们用什么方法将字符串转换成整型，都会存在哈希冲突，只是产生冲突的概率不同而已。
       

                             

     (2)BKDRHash算法无论是在实际效果还是编码实现中，效果都是最突出的

     ①现在我们需要在哈希表的模板参数中再增加一个仿函数，用于将键值key转换成对应的整型。

    1. template<class K, class T, class KeyOfT, class HashFunc = Hash>
    2. class HashTable

                             

    ②若是上层没有传入该仿函数，我们则使用默认的仿函数，该默认仿函数直接返回键值key即可，但是用字符串作为键值key是比较常见的，因此我们可以针对string类型写一个类模板的特化，此时当键值key为string类型时，该仿函数就会根据BKDRHash算法返回一个对应的整型。 

    1. template<class K>
    2. struct Hash
    3. {
    4. 	size_t operator()(const K& key) //返回键值key
    5. 	{
    6. 		return key;
    7. 	}
    8. };
    9.  
    10. //string类型的特化
    11. template<>
    12. struct Hash
    13. {
    14. 	size_t operator()(const string& s) //BKDRHash算法
    15. 	{
    16. 		size_t value = 0;
    17. 		for (auto ch : s)
    18. 		{
    19. 			value = value * 131 + ch;
    20. 		}
    21. 		return value;
    22. 	}
    23. };

                                    

                                                    

    4.哈希表默认成员函数实现

    (1)构造函数

    • _table会自动调用vector的默认构造函数进行初始化。
    • _n会根据我们所给的缺省值被设置为0。
    1. vector _table; //哈希表
    2. size_t _n = 0; //哈希表中的有效元素个数

                             

    •  我们不需要编写构造函数，使用默认生成的构造函数就足够了，但是由于我们后面需要编写拷贝构造函数，编写了拷贝构造函数后，默认的构造函数就不会生成了，此时我们需要使用default关键字显示指定生成默认构造函数。
    1. //构造函数
    2. HashTable() = default; //显示指定生成默认构造函数

            

    (2)拷贝构造函数 

    哈希表的拷贝构造函数(深拷贝)实现逻辑如下：

    1. 将哈希表的大小调整为ht._table的大小。
    2. 将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中。
    3. 更改哈希表当中的有效数据个数。
    1. //拷贝构造函数
    2. HashTable(const HashTable& ht)
    3. {
    4. 	//1、将哈希表的大小调整为ht._table的大小
    5. 	_table.resize(ht._table.size());
    6.  
    7. 	//2、将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中（深拷贝）
    8. 	for (size_t i = 0; i < ht._table.size(); i++)
    9. 	{
    10. 		if (ht._table[i]) //桶不为空
    11. 		{
    12. 			Node* cur = ht._table[i];
    13. 			while (cur) //将该桶的结点取完为止
    14. 			{
    15. 				Node* copy = new Node(cur->_data); //创建拷贝结点
    16. 				//将拷贝结点头插到当前桶
    17. 				copy->_next = _table[i];
    18. 				_table[i] = copy;
    19. 				cur = cur->_next; //取下一个待拷贝结点
    20. 			}
    21. 		}
    22. 	}
    23.  
    24. 	//3、更改哈希表当中的有效数据个数
    25. 	_n = ht._n;
    26. }

                             

    (3)赋值运算符重载函数 

    • 现代写法
    •  实现赋值运算符重载函数时，可以通过参数间接调用拷贝构造函数，之后将拷贝构造出来的哈希表和当前哈希表的两个成员变量分别进行交换即可，当赋值运算符重载函数调用结束后，拷贝构造出来的哈希表会因为出了作用域而被自动析构，此时原哈希表之前的数据也就顺势被释放了。
    1. //赋值运算符重载函数
    2. HashTable& operator=(HashTable ht)
    3. {
    4. 	//交换哈希表中两个成员变量的数据
    5. 	_table.swap(ht._table);
    6. 	swap(_n, ht._n);
    7.  
    8. 	return *this; //支持连续赋值
    9. }

                     

    (4)析构函数 

    •  哈希表当中存储的结点都是new出来的，因此在哈希表被析构时必须进行结点的释放。在析构哈希表时我们只需要依次取出非空的哈希桶，遍历哈希桶当中的结点并进行释放即可。
    1. //析构函数
    2. ~HashTable()
    3. {
    4. 	//将哈希表当中的结点一个个释放
    5. 	for (size_t i = 0; i < _table.size(); i++)
    6. 	{
    7. 		if (_table[i]) //桶不为空
    8. 		{
    9. 			Node* cur = _table[i];
    10. 			while (cur) //将该桶的结点取完为止
    11. 			{
    12. 				Node* next = cur->_next; //记录下一个结点
    13. 				delete cur; //释放结点
    14. 				cur = next;
    15. 			}
    16. 			_table[i] = nullptr; //将该哈希桶置空
    17. 		}
    18. 	}
    19. }

                    

                                            

    5.哈希表正向迭代器的实现

    (1)哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，但是由于在实现++运算符重载时，可能需要在哈希表中去寻找下一个非空哈希桶，因此每一个正向迭代器中都应该存储哈希表的地址。 

    1. //正向迭代器
    2. template<class K, class T, class KeyOfT, class HashFunc = Hash>
    3. struct __HTIterator
    4. {
    5. 	typedef HashNode Node; //哈希结点的类型
    6. 	typedef HashTable HT; //哈希表的类型
    7. 	typedef __HTIterator Self; //正向迭代器的类型
    8.  
    9. 	Node* _node; //结点指针
    10. 	HT* _pht; //哈希表的地址
    11. };

     

    (2)其他的实现

    1. //构造函数
    2. __HTIterator(Node* node, HT* pht)
    3. 	:_node(node) //结点指针
    4. 	, _pht(pht) //哈希表地址
    5. {}
    6.  
    7. T& operator*()
    8. {
    9. 	return _node->_data; //返回哈希结点中数据的引用
    10. }
    11.  
    12. T* operator->()
    13. {
    14. 	return &_node->_data; //返回哈希结点中数据的地址
    15. }
    16.  
    17. bool operator!=(const Self& s) const
    18. {
    19. 	return _node != s._node; //判断两个结点的地址是否不同
    20. }
    21.  
    22. bool operator==(const Self& s) const
    23. {
    24. 	return _node == s._node; //判断两个结点的地址是否相同
    25. }

                     

     (3)++运算符重载

    • 哈希表的迭代器类型是单向迭代器，没有反向迭代器，即没有实现- -运算符的重载，若是想让哈希表支持双向遍历，可以考虑将哈希桶中存储的单链表结构换为双链表结构。 

                    

    • 若当前结点不是当前哈希桶中的最后一个结点，则++后走到当前哈希桶的下一个结点。
    • 若当前结点是当前哈希桶的最后一个结点，则++后走到下一个非空哈希桶的第一个结点。
    1. //前置++
    2. Self& operator++()
    3. {
    4. 	if (_node->_next) //该结点不是当前哈希桶中的最后一个结点
    5. 	{
    6. 		_node = _node->_next; //++后变为当前哈希桶中的下一个结点
    7. 	}
    8. 	else //该结点是当前哈希桶中的最后一个结点
    9. 	{
    10. 		KeyOfT kot;
    11. 		HashFunc hf;
    12. 		size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //通过哈希函数计算出当前所处哈希桶编号index（除数不能是capacity）
    13.  
    14. 		index++; //从下一个位置开始找一个非空的哈希桶
    15. 		while (index < _pht->_table.size()) //直到将整个哈希表找完
    16. 		{
    17. 			if (_pht->_table[index]) //当前哈希桶非空
    18. 			{
    19. 				_node = _pht->_table[index]; //++后变为当前哈希桶中的第一个结点
    20. 				return *this;
    21. 			}
    22. 			index++; //当前哈希桶为空桶，找下一个哈希桶
    23. 		}
    24. 		_node = nullptr; //哈希表中已经没有空桶了，++后变为nullptr
    25. 	}
    26. 	return *this;
    27. }

                            

                     

    (4)哈希表的其他实现方式

    • 这种方式的单链表对于+ +实现更简单了

                             

     

    6.哈希表的实现进行补充 

    •  进行正向迭代器类型的typedef，需要注意的是，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在public区域进行typedef。
    • 由于正向迭代器中++运算符重载函数在寻找下一个结点时，会访问哈希表中的成员变量_table，而_table成员变量是哈希表的私有成员，因此我们需要将正向迭代器类声明为哈希表类的友元。
    • 将哈希表中查找函数返回的结点指针，改为返回由结点指针和哈希表地址构成的正向迭代器。
    • 将哈希表中插入函数的返回值类型，改为由正向迭代器类型和布尔类型所构成的键值对。
    1. //哈希表的实现
    2. template<class K, class T, class KeyOfT, class HashFunc = Hash>
    3. class HashTable
    4. {
    5. 	//将正向迭代器类声明为哈希表类的友元
    6. 	template<class K, class T, class KeyOfT, class HashFunc>
    7. 	friend struct __HTIterator;
    8.  
    9. 	typedef HashNode Node; //哈希结点类型
    10. public:
    11. 	typedef __HTIterator iterator; //正向迭代器的类型
    12.  
    13. 	iterator begin()
    14. 	{
    15. 		size_t i = 0;
    16. 		while (i < _table.size()) //找到第一个非空哈希桶
    17. 		{
    18. 			if (_table[i]) //该哈希桶非空
    19. 			{
    20. 				return iterator(_table[i], this); //返回该哈希桶中的第一个结点的正向迭代器
    21. 			}
    22. 			i++;
    23. 		}
    24. 		return end(); //哈希桶中无数据，返回end()
    25. 	}
    26.  
    27. 	iterator end()
    28. 	{
    29. 		return iterator(nullptr, this); //返回nullptr的正向迭代器
    30. 	}
    31. private:
    32. 	vector _table; //哈希表
    33. 	size_t _n = 0; //哈希表中的有效元素个数
    34. };

                    

                                    

    7.unordered_set的模拟实现 

    1. template<class K>
    2. class unordered_set
    3. {
    4. 	//仿函数
    5. 	struct SetKeyOfT
    6. 	{
    7. 		const K& operator()(const K& key) //返回键值key
    8. 		{
    9. 			return key;
    10. 		}
    11. 	};
    12.  
    13. public:
    14.  
    15. 	//现在没有实例化，没办法到HashTable里面找iterator，所以typename就是告诉编译器这里是一个类型，实例化以后再去取
    16. 	typedef typename HashTable::iterator iterator;
    17.  
    18. 	iterator begin()
    19. 	{
    20. 		return _ht.begin();
    21. 	}
    22.  
    23. 	iterator end()
    24. 	{
    25. 		return _ht.end();
    26. 	}
    27.  
    28. 	//插入函数
    29. 	pairbool> insert(const K& key)
    30. 	{
    31. 		return _ht.Insert(key);
    32. 	}
    33.  
    34. 	//删除函数
    35. 	void erase(const K& key)
    36. 	{
    37. 		_ht.Erase(key);
    38. 	}
    39.  
    40. 	//查找函数
    41. 	iterator find(const K& key)
    42. 	{
    43. 		return _ht.Find(key);
    44. 	}
    45. private:
    46. 	HashTable _ht;
    47. };

                    

    8.unordered_map的模拟实现 

    1. template<class K, class V>
    2. class unordered_map
    3. {
    4. 	//仿函数
    5. 	struct MapKeyOfT
    6. 	{
    7. 		const K& operator()(const pair& kv) //返回键值对当中的键值key
    8. 		{
    9. 			return kv.first;
    10. 		}
    11. 	};
    12.  
    13. public:
    14. 	typedef typename HashTable, MapKeyOfT>::iterator iterator;
    15.  
    16. 	iterator begin()
    17. 	{
    18. 		return _ht.begin();
    19. 	}
    20.  
    21. 	iterator end()
    22. 	{
    23. 		return _ht.end();
    24. 	}
    25.  
    26. 	//插入函数
    27. 	pairbool> insert(const pair& kv)
    28. 	{
    29. 		return _ht.Insert(kv);
    30. 	}
    31.  
    32. 	//赋值运算符重载
    33. 	V& operator[](const K& key)
    34. 	{
    35. 		pairbool> ret = insert(make_pair(key, V()));
    36. 		iterator it = ret.first;
    37. 		return it->second;
    38. 	}
    39.  
    40. 	//删除函数
    41. 	void erase(const K& key)
    42. 	{
    43. 		_ht.Erase(key);
    44. 	}
    45.  
    46. 	//查找函数
    47. 	iterator find(const K& key)
    48. 	{
    49. 		return _ht.Find(key);
    50. 	}
    51.  
    52. private:
    53. 	HashTable, MapKeyOfT> _ht;
    54. };

                            

                     

    9.封装之后的代码

    (1)哈希表的代码 

    1. //哈希结点的定义
    2. template<class T>
    3. struct HashNode
    4. {
    5. 	T _data;
    6. 	HashNode* _next;
    7.  
    8. 	//构造函数
    9. 	HashNode(const T& data)
    10. 		:_data(data)
    11. 		, _next(nullptr)
    12. 	{}
    13. };
    14.  
    15. template<class K>
    16. struct Hash
    17. {
    18. 	size_t operator()(const K& key) //返回键值key
    19. 	{
    20. 		return key;
    21. 	}
    22. };
    23.  
    24. //string类型的特化
    25. template<>
    26. struct Hash
    27. {
    28. 	size_t operator()(const string& s) //BKDRHash算法
    29. 	{
    30. 		size_t value = 0;
    31. 		for (auto ch : s)
    32. 		{
    33. 			value = value * 131 + ch;
    34. 		}
    35. 		return value;
    36. 	}
    37. };
    38.  
    39.  
    40. //哈希表的实现
    41. template<class K, class T, class KeyOfT, class HashFunc = Hash>
    42. class HashTable
    43. {
    44. 	//将正向迭代器类声明为哈希表类的友元
    45. 	template<class K, class T, class KeyOfT, class HashFunc>
    46. 	friend struct __HTIterator;
    47. 	//friend struct __HTIterator;
    48.  
    49. 	typedef HashNode Node; //哈希结点类型
    50.  
    51. public:
    52. 	typedef __HTIterator iterator; //正向迭代器的类型
    53.  
    54. 	iterator begin()
    55. 	{
    56. 		size_t i = 0;
    57. 		while (i < _table.size()) //找到第一个非空哈希桶
    58. 		{
    59. 			if (_table[i]) //该哈希桶非空
    60. 			{
    61. 				return iterator(_table[i], this); //返回该哈希桶中的第一个结点的正向迭代器
    62. 			}
    63. 			i++;
    64. 		}
    65. 		return end(); //哈希桶中无数据，返回end()
    66. 	}
    67.  
    68. 	iterator end()
    69. 	{
    70. 		return iterator(nullptr, this); //返回nullptr的正向迭代器
    71. 	}
    72.  
    73. 	//构造函数
    74. 	HashTable() = default; //显示指定生成默认构造
    75.  
    76. 	//拷贝构造函数
    77. 	HashTable(const HashTable& ht)
    78. 	{
    79. 		//1、将哈希表的大小调整为ht._table的大小
    80. 		_table.resize(ht._table.size());
    81.  
    82. 		//2、将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中（深拷贝）
    83. 		for (size_t i = 0; i < ht._table.size(); i++)
    84. 		{
    85. 			if (ht._table[i]) //桶不为空
    86. 			{
    87. 				Node* cur = ht._table[i];
    88. 				while (cur) //将该桶的结点取完为止
    89. 				{
    90. 					Node* copy = new Node(cur->_data); //创建拷贝结点
    91. 					//将拷贝结点头插到当前桶
    92. 					copy->_next = _table[i];
    93. 					_table[i] = copy;
    94. 					cur = cur->_next; //取下一个待拷贝结点
    95. 				}
    96. 			}
    97. 		}
    98. 		//3、更改哈希表当中的有效数据个数
    99. 		_n = ht._n;
    100. 	}
    101.  
    102. 	//赋值运算符重载函数
    103. 	HashTable& operator=(HashTable ht)
    104. 	{
    105. 		//交换哈希表中两个成员变量的数据
    106. 		_table.swap(ht._table);
    107. 		swap(_n, ht._n);
    108.  
    109. 		return *this; //支持连续赋值
    110. 	}
    111.  
    112. 	//析构函数
    113. 	~HashTable()
    114. 	{
    115. 		//将哈希表当中的结点一个个释放
    116. 		for (size_t i = 0; i < _table.size(); i++)
    117. 		{
    118. 			if (_table[i]) //桶不为空
    119. 			{
    120. 				Node* cur = _table[i];
    121. 				while (cur) //将该桶的结点取完为止
    122. 				{
    123. 					Node* next = cur->_next; //记录下一个结点
    124. 					delete cur; //释放结点
    125. 					cur = next;
    126. 				}
    127. 				_table[i] = nullptr; //将该哈希桶置空
    128. 			}
    129. 		}
    130. 	}
    131.  
    132. 	//获取本次增容后哈希表的大小
    133. 	size_t GetNextPrime(size_t prime)
    134. 	{
    135. 		const int PRIMECOUNT = 28;
    136. 		//素数序列
    137. 		const size_t primeList[PRIMECOUNT] =
    138. 		{
    139. 			53ul, 97ul, 193ul, 389ul, 769ul,
    140. 			1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    141. 			49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    142. 			1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    143. 			50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    144. 			1610612741ul, 3221225473ul, 4294967291ul
    145. 		};
    146.  
    147. 		size_t i = 0;
    148. 		for (i = 0; i < PRIMECOUNT; i++)
    149. 		{
    150. 			if (primeList[i] > prime)
    151. 				return primeList[i];
    152. 		}
    153. 		return primeList[i];
    154. 	}
    155.  
    156. 	//插入函数
    157. 	pairbool> Insert(const T& data)
    158. 	{
    159. 		KeyOfT kot;
    160.  
    161. 		//1、查看哈希表中是否存在该键值的键值对
    162. 		iterator ret = Find(kot(data));
    163. 		if (ret != end()) //哈希表中已经存在该键值的键值对（不允许数据冗余）
    164. 		{
    165. 			return make_pair(ret, false); //插入失败
    166. 		}
    167.  
    168. 		//2、判断是否需要调整哈希表的大小
    169. 		if (_n == _table.size()) //哈希表的大小为0，或负载因子超过1
    170. 		{
    171. 			//增容
    172. 			//a、创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍（若哈希表大小为0，则将哈希表的初始大小设置为10）
    173. 			HashFunc hf;
    174. 			vector newtable;
    175. 			//size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
    176. 			//newtable.resize(newsize);
    177.  
    178. 			newtable.resize(GetNextPrime(_table.size()));
    179. 				
    180. 			//b、将原哈希表当中的结点插入到新哈希表
    181. 			for (size_t i = 0; i < _table.size(); i++)
    182. 			{
    183. 				if (_table[i]) //桶不为空
    184. 				{
    185. 					Node* cur = _table[i];
    186. 					while (cur) //将该桶的结点取完为止
    187. 					{
    188. 						Node* next = cur->_next; //记录cur的下一个结点
    189. 						size_t index = hf(kot(cur->_data))%newtable.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
    190.  
    191. 						//将该结点头插到新哈希表中编号为index的哈希桶中
    192. 						cur->_next = newtable[index];
    193. 						newtable[index] = cur;
    194.  
    195. 						cur = next; //取原哈希表中该桶的下一个结点
    196. 					}
    197. 					_table[i] = nullptr; //该桶取完后将该桶置空
    198. 				}
    199. 			}
    200. 			//c、交换这两个哈希表
    201. 			_table.swap(newtable);
    202. 		}
    203.  
    204. 		//3、将键值对插入哈希表
    205. 		HashFunc hf;
    206. 		size_t index = hf(kot(data)) % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
    207. 		Node* newnode = new Node(data); //根据所给数据创建一个待插入结点
    208.  
    209. 		//将该结点头插到新哈希表中编号为index的哈希桶中
    210. 		newnode->_next = _table[index];
    211. 		_table[index] = newnode;
    212.  
    213. 		//4、哈希表中的有效元素个数加一
    214. 		_n++;
    215. 		return make_pair(iterator(newnode, this), true);
    216. 	}
    217.  
    218. 	//查找函数
    219. 	iterator Find(const K& key)
    220. 	{
    221. 		if (_table.size() == 0) //哈希表大小为0，查找失败
    222. 		{
    223. 			return end();
    224. 		}
    225.  
    226. 		KeyOfT kot;
    227. 		HashFunc hf;
    228. 		size_t index = hf(key) % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
    229.  
    230. 		//遍历编号为index的哈希桶
    231. 		HashNode* cur = _table[index];
    232. 		while (cur) //直到将该桶遍历完为止
    233. 		{
    234. 			if (kot(cur->_data) == key) //key值匹配，则查找成功
    235. 			{
    236. 				return iterator(cur, this);
    237. 			}
    238. 			cur = cur->_next;
    239. 		}
    240. 		return end(); //直到该桶全部遍历完毕还没有找到目标元素，查找失败
    241. 	}
    242.  
    243. 	//删除函数
    244. 	bool Erase(const K& key)
    245. 	{
    246. 		KeyOfT kot;
    247. 		HashFunc hf;
    248. 		//1、通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
    249. 		size_t index = hf(key) % _table.size();
    250.  
    251. 		//2、在编号为index的哈希桶中寻找待删除结点
    252. 		Node* prev = nullptr;
    253. 		Node* cur = _table[index];
    254. 		while (cur) //直到将该桶遍历完为止
    255. 		{
    256. 			if (kot(cur->_data) == key) //key值匹配，则查找成功
    257. 			{
    258. 				//3、若找到了待删除结点，则删除该结点
    259. 				if (prev == nullptr) //待删除结点是哈希桶中的第一个结点
    260. 				{
    261. 					_table[index] = cur->_next; //将第一个结点从该哈希桶中移除
    262. 				}
    263. 				else //待删除结点不是哈希桶的第一个结点
    264. 				{
    265. 					prev->_next = cur->_next; //将该结点从哈希桶中移除
    266. 				}
    267. 				delete cur; //释放该结点
    268.  
    269. 				//4、删除结点后，将哈希表中的有效元素个数减一
    270. 				_n--;
    271. 				return true; //删除成功
    272. 			}
    273. 			prev = cur;
    274. 			cur = cur->_next;
    275. 		}
    276. 		//假删除可能会导致迭代器失效
    277. 			
    278. 		return false; //直到该桶全部遍历完毕还没有找到待删除元素，删除失败
    279. 	}
    280. private:
    281. 	vector _table; //哈希表
    282. 	size_t _n = 0; //哈希表中的有效元素个数
    283. };

                     

    (2)正向迭代器的代码

    1. //前置声明, HashTable和__HTIterator互相依赖
    2. template<class K, class T, class KeyOfT, class HashFunc>
    3. class HashTable;
    4.  
    5. //正向迭代器
    6. template<class K, class T, class KeyOfT, class HashFunc = Hash>
    7. struct __HTIterator
    8. {
    9. 	typedef HashNode Node; //哈希结点的类型
    10. 	typedef HashTable HT; //哈希表的类型
    11. 	typedef __HTIterator Self; //正向迭代器的类型
    12.  
    13. 	Node* _node; //结点指针
    14. 	HT* _pht; //哈希表的地址
    15.  
    16. 	//构造函数
    17. 	__HTIterator(Node* node, HT* pht)
    18. 		:_node(node) //结点指针
    19. 		, _pht(pht) //哈希表地址
    20. 	{}
    21.  
    22. 	T& operator*()
    23. 	{
    24. 		return _node->_data; //返回哈希结点中数据的引用
    25. 	}
    26.  
    27. 	T* operator->()
    28. 	{
    29. 		return &_node->_data; //返回哈希结点中数据的地址
    30. 	}
    31.  
    32. 	bool operator!=(const Self& s) const
    33. 	{
    34. 		return _node != s._node; //判断两个结点的地址是否不同
    35. 	}
    36.  
    37. 	bool operator==(const Self& s) const
    38. 	{
    39. 		return _node == s._node; //判断两个结点的地址是否相同
    40. 	}
    41.  
    42. 	//前置++
    43. 	Self& operator++()
    44. 	{
    45. 		if (_node->_next) //该结点不是当前哈希桶中的最后一个结点
    46. 		{
    47. 			_node = _node->_next; //++后变为当前哈希桶中的下一个结点
    48. 		}
    49. 		else //该结点是当前哈希桶中的最后一个结点
    50. 		{
    51. 			KeyOfT kot;
    52. 			HashFunc hf;
    53. 			size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //通过哈希函数计算出当前所处哈希桶编号index（除数不能是capacity）
    54.  
    55. 			index++; //从下一个位置开始找一个非空的哈希桶
    56. 			while (index < _pht->_table.size()) //直到将整个哈希表找完
    57. 			{
    58. 				if (_pht->_table[index]) //当前哈希桶非空
    59. 				{
    60. 					_node = _pht->_table[index]; //++后变为当前哈希桶中的第一个结点
    61. 					return *this;
    62. 				}
    63. 				index++; //当前哈希桶为空桶，找下一个哈希桶
    64. 			}
    65. 			_node = nullptr; //哈希表中已经没有空桶了，++后变为nullptr
    66. 		}
    67. 		return *this;
    68. 	}
    69. };

                     

    (3)unordered_set的代码

    1. namespace XM //防止命名冲突
    2. {
    3. 	template<class K>
    4. 	class unordered_set
    5. 	{
    6. 		//仿函数
    7. 		struct SetKeyOfT
    8. 		{
    9. 			const K& operator()(const K& key) //返回键值key
    10. 			{
    11. 				return key;
    12. 			}
    13. 		};
    14. 	public:
    15. 		//现在没有实例化，没办法到HashTable里面找iterator，所以typename就是告诉编译器这里是一个类型，实例化以后再去取
    16. 		typedef typename HashTable::iterator iterator;
    17.  
    18. 		iterator begin()
    19. 		{
    20. 			return _ht.begin();
    21. 		}
    22. 		iterator end()
    23. 		{
    24. 			return _ht.end();
    25. 		}
    26.  
    27. 		//插入函数
    28. 		pairbool> insert(const K& key)
    29. 		{
    30. 			return _ht.Insert(key);
    31. 		}
    32.  
    33. 		//删除函数
    34. 		void erase(const K& key)
    35. 		{
    36. 			_ht.Erase(key);
    37. 		}
    38.  
    39. 		//查找函数
    40. 		iterator find(const K& key)
    41. 		{
    42. 			return _ht.Find(key);
    43. 		}
    44. 	private:
    45. 		HashTable _ht;
    46. 	};
    47. }

                     

    (4)unordered_map的代码 

    1. namespace XM //防止命名冲突
    2. {
    3. 	template<class K, class V>
    4. 	class unordered_map
    5. 	{
    6. 		//仿函数
    7. 		struct MapKeyOfT
    8. 		{
    9. 			const K& operator()(const pair& kv) //返回键值对当中的键值key
    10. 			{
    11. 				return kv.first;
    12. 			}
    13. 		};
    14.  
    15. 	public:
    16. 		typedef typename HashTable, MapKeyOfT>::iterator iterator;
    17.  
    18. 		iterator begin()
    19. 		{
    20. 			return _ht.begin();
    21. 		}
    22. 		iterator end()
    23. 		{
    24. 			return _ht.end();
    25. 		}
    26.  
    27. 		//插入函数
    28. 		pairbool> insert(const pair& kv)
    29. 		{
    30. 			return _ht.Insert(kv);
    31. 		}
    32.  
    33. 		//赋值运算符重载
    34. 		V& operator[](const K& key)
    35. 		{
    36. 			pairbool> ret = insert(make_pair(key, V()));
    37. 			iterator it = ret.first;
    38. 			return it->second;
    39. 		}
    40.  
    41. 		//删除函数
    42. 		void erase(const K& key)
    43. 		{
    44. 			_ht.Erase(key);
    45. 		}
    46.  
    47. 		//查找函数
    48. 		iterator find(const K& key)
    49. 		{
    50. 			return _ht.Find(key);
    51. 		}
    52. 	private:
    53. 		HashTable, MapKeyOfT> _ht;
    54. 	};
    55. }

  • 相关阅读:
    基于SpringBoot的的师生健康信息管理系统
    一篇文章带你了解Python常用自动化测试框架 —— Pytest
    阿里云Linux中安装MySQL,并使用navicat连接以及报错解决
    java飞机航班信息查询系统演示视频2021计算机毕业设计MyBatis+系统+LW文档+源码+调试部署
    用AI打造一个属于自己的歌手，让她C位霸气出道
    数据结构学习笔记——数据结构概论
    如何在 Rocky Linux 上安装 Apache Kafka？
    SSM+教学网站 毕业设计-附源码211611
    Java23种设计模式-创建型模式之单例模式
    vue项目npm run build报错Error: Cannot find module ‘@vue/cli-plugin-babel‘的解决方法
  • 原文地址：https://blog.csdn.net/m0_52169086/article/details/126709111