• 封装unordered_map和unordered_set

       先前用红黑树封装出了map和set，现在就要用哈希来封装unordered_map和unordered_set（为了简化名称，后面称u_map和u_set），u_map和u_set在学习map时曾了解过，只知道是无序，我还在想，不能排序有啥用呢?原来用于查找数据效率高得很。有了封装map和set的经历，下面的封装就好理解多了，难点基本上都是迭代器和模板参数。

    一 模板参数

    从u_map和u_set传的模板参数来理解

    下图为哈希表接收的模板参数

       本文的哈希是开散列的，因为开散列可以更好地解决哈希冲突，所以哈希表中存的就是每个桶中第一个节点的指针，而T就是节点用于存各种数据类型的，也就是说u_map和u_set给哈希表模板传的第二个模板参数就是想要哈希表节点存的类型。接来下看看两个容器在节点存的类型。

     节点类内部实现

    1. template<class T>//T为节点所存数据
    2. 	struct HashNode
    3. 	{
    4. 		HashNode(const T& data)
    5. 			:_data(data)
    6. 			, _next(nullptr)
    7. 		{
    8. 			;
    9. 		}
    10. 		T _data;
    11. 		HashNode* _next;
    12. 	};

    u_map实例化的哈希表变量

      如下图,u_map存在节点的是一个pair。至于为什么要对K加上const，我想如果了解过map和set的封装的同学肯定能猜到(后面会再提及)。

    u_set实例化的哈希表变量

      而u_set要节点存的就是一个K类型的，毕竟u_set和set是类似的，只存一个key值，为了让节点可以用一个变量，例如T _data，既可以存u_set的一个key值，又可以存u_map的key和value这两个值，只能让key和value绑在一个结构体上，总不能让节点内多加一个变量吧，u_set又用不了那么多，不就浪费了吗。

    综上，传给哈希表的第二个模板参数是节点存的数据的类型，可能是一个pair，也可能是一个K类型的key值。但是哈希表还有其余的模板参数，这就要结合哈希表的实现才能说清楚，如下。

    HashBucketTable其余模板参数介绍

      第一个就简单了，是专门提供给find这类参数是const K&key的，而T已经介绍过了。

      而剩下的两个模板参数都在下面一行代码里了

       由于我们前面将u_map的key和value统一为一个值，不仅方便了节点类内变量存储，insert也只要插入一个值就好了，这就说明插入的元素kv可能是个K类型的，也可能是一个pair。

      如果是一个pair,  我们要取出里面的key，然后%_table.size()求下标，但是如果u_set调用insert，就可以直接取模，因为这时候的kv就是key, 这就导致这里对不同类型要做不同的处理，借鉴封装map的经验，我们可以用一个仿函数GetKey将key返回，但这也不意味着可以直接取模，如果key是字符串呢，这就要用到第四个模板参数，它就是将一些自定义类型转为整数，然后用于取模，这个仿函数介绍哈希成员函数时会出代码，所以这两个仿函数是互相配合。

    map的GetKey

    set的GetKey

    二 使key不可被修改

       当我们大致了解了哈希表的模板参数，还有个大问题前面提了却未解决，u_map和u_set的key都应该是不能修改的，那我们如何实现呢?

    1 使u_set的key不可修改

       一般来说普通迭代器可以修改节点内的数据，也就是说u_set的普通迭代器可以修改节点内的数据，那不就意味着可以修改key?这样显然是不行的，所以我们要让外部取得iterator定义出的变量具有const_iterator的特性，还是老套路，用typedef重命名来欺骗使用者。

    临场发问:typename的作用是什么?

      上图中我们自认为是从HashBucketTable这个类内取一个类型，可编译器编译的时候哪知道，假设有一个静态变量a，

      访问静态变量a的方式:HashBucketTable, GainMapKey>::a，这个形式和前面取iterator不是一模一样吗，编译器哪分得清，而且你类又没实例化，编译器又没办法核实，所以会报错，只能我们写个关键字typename，告诉编译器这是个类型，等实例化了再检查，现在先别报错。

    2 使u_map的key不可修改

      先前没说为什么要给K加上const，现在可以说了，就是使得K不可修改。

       仅仅只是我博客这些功能，u_set也可以通过传const K的方法去实现iterator有const_iterator的作用，但是库里大佬肯定比我想的细致，应该是我没考虑到这种方式对其余功能的阻碍。

    三 迭代器实现

      这个迭代器的实现则与先前的有些不同，因为当我们++后，如果到空节点了，要去下一个不为空的桶，此时迭代器存的节点指针是没办法找到下一个桶的，这意味着我们需要访问哈希表，所以应该增加一个成员，哈希表指针。

       还有个问题，我们需要从深入迭代器实现才可以解决，就是_ht调用返回的pair中的iterator和外面u_set的iterator是不同的，因为外部的iterator是const_iterator重定义的，而内部iterator就是普通迭代器，类型已经不匹配了，这是我们自己定义的类型，编译器无法强转，除非我们写了对应的构造函数，编译器才有可能偷偷帮我们转换一下，接来下就带着问题看看迭代器如何支持的这个类型转换。

    迭代器代码

    1. template<class K, class T,class KeyofT, class Hashfunc>
    2.     class HashBucketTable;
    3.  
    4. 要前置声明,不然迭代器内会不认识哈希表指针
    5.  
    6.  template<class K, class T, class Ptr, class Ref,class KeyofT, class Hashfunc>
    7. 	struct HashIterator    K，KeyofT, Hashfunc是给哈希表的模板参数
    8. 	{
    9. 		typedef HashNode Node;
    10. 		typedef HashIterator Self; 
    11.      重命名为Self, 方便下面使用，模板参数变量也只需要改这里
    12.  
    13. 		typedef HashIterator iterator;
    14.  
    15. HashIterator(Node* node, const HashBucketTable* pht)
    16. 			:_node(node)
    17. 			, _pht(pht)
    18. 		{
    19. 			;
    20. 		}
    21. 		HashIterator(const iterator& it)  
    22. 			:_node(it._node)
    23. 			, _pht(it._pht)
    24. 		{
    25. 			;
    26. 		}
    27. 		Self& operator++()
    28. 		{
    29. 			KeyofT kot;
    30. 			Hashfunc hf;
    31. 			Node* cur = _node;
    32. 			if (cur->_next)  下一个节点不为空
    33. 			{
    34. 				_node = _node->_next;
    35. 			}
    36. 			else  去下一个桶找
    37. 			{
    38. 				size_t hashi = (hf(kot(cur->_data)) % _pht->_table.size()) + 1;
    39. 				while (hashi<_pht->_table.size())  防止往后找不为空的桶时越界
    40. 				{
    41. 					if(!_pht->_table[hashi])
    42. 					  hashi++;
    43. 					else
    44. 					{
    45. 						_node = _pht->_table[hashi];
    46. 						return *this;
    47. 					}
    48. 				}
    49. 				_node = nullptr;  先前还没返回,说明全是空桶,达到end位置
    50. 			}
    51. 			return *this;
    52. 		}
    53. 		Ref operator*()  通过控制Ptr和Ref来达到const迭代器的作用
    54. 		{
    55. 			return _node->_data;
    56. 		}
    57. 		Ptr operator->()
    58. 		{
    59. 			return &_node->_data;
    60. 		}
    61. 		bool operator!=(const Self& it)
    62. 		{
    63. 			return _node != it._node;
    64. 		}
    65. 		bool operator==(const Self& it)
    66. 		{
    67. 			return _node == it._node;
    68. 		}
    69. 		Node* _node;
    70. 		const HashBucketTable* _pht; 哈希表指针
    71. 	};

     

       当HashIterator被实例化为const迭代器， 这个就可以给u_set的insert做类型转换使用，所以我们前面需要定义一个普通迭代器，就是为了这一步 

       有没有注意到这个成员加了const，首先加上const绝对是可以的，因为限制我们通过_pht这个指针修改哈希表也是合理的。

    或许你会说，不对，是因为构造函数是用const的指针接收的。

      那就看看下面的，哈希表指针是用this指针初始化的，而this指针的类型是 T*const，这个const不限制赋值，限制了感觉反而不好，举个例子，int* const p1=&a; int*p2=p1;你p1不能修改自己的值，总不能让p2也不能修改自己的值吧，好像不太合理，但如果是const迭代器,那this指针就是const T*const，所以构造函数需要加上const，否则无法匹配，也就是使得哈希表指针这个成员变量要加const。

     

    最后我说一下我之前的一个问题，我想it是const类型的，它的成员也是const类型的，为什么就能赋值给Node* _node, 现在我想明白了,it._node这个的类型是Node*const的，由前面的，这个const不限制，所以可以赋值。

    u_map封装代码

    u_map的成员函数都是复用_ht变量的函数，比较有意思的就是[]的实现了。

    1. template<class K,class V>
    2. class Unordered_map
    3. {
    4. public:
    5. 	struct GainMapKey//用来返回pair中的key
    6. 	{
    7. 		const K& operator()(const pair& data)
    8. 		{
    9. 			return data.first;
    10. 		}
    11. 	};
    12. 	typedef HashNodeconst K, V>> Node;
    13. 	typedef typename  HashBucketTableconst K, V>, GainMapKey>::iterator iterator;
    14. 	typedef typename  HashBucketTableconst K, V>, GainMapKey>::const_iterator const_iterator;
    15. 	
    16. 	pairbool> insert(const pair& p1)
    17. 	{
    18. 		return _ht.insert(p1);
    19. 	}
    20. 	bool Erase(const K& k1)
    21. 	{
    22. 		return _ht.Erase(k1);
    23. 	}
    24. 	iterator find(const K& key) 这里find和_ht.find()返回类型和下面的insert一样
    25.                                 类型是不匹配的，但是构造函数支持了这种类型转换。
    26. 	{
    27. 		return _ht.find(key);
    28. 	}
    29. 	iterator begin()
    30. 	{
    31. 		return _ht.begin();
    32. 	}
    33. 	iterator end()
    34. 	{
    35. 		return _ht.end();
    36. 	}
    37. 	const_iterator begin()const
    38. 	{
    39. 		return _ht.begin();
    40. 	}
    41. 	const_iterator end()const
    42. 	{
    43. 		return _ht.end();
    44. 	}
    45. 	V& operator[](const K& p1)
    46. 	{
    47. 		pairbool> ret=_ht.insert(make_pair(p1,V()));
    48. 		return (*ret.first).second;
    49.        
    50.      ret.first取得是iterator，*解引用就返回_node->_data的引用，
    51.      这个_data对于u_map而言就是一个pair，我们再取second就是[]需要返回的value  
    52. 	}
    53. private:
    54. 	HashBucketTableconst K,V>, GainMapKey> _ht; 偏特化
    55. };

    u_set封装代码

    1. template<class K>
    2. class Unordered_set
    3. {
    4. public:
    5. 	struct GainSetKey  为了map和set传模板参数保持一致,set也要传一个GainSetKey
    6. 	{
    7. 		const K& operator()(const K& data)
    8. 		{
    9. 			return data;
    10. 		}
    11. 	};
    12. 	typedef HashNode Node;
    13. 	typedef	typename HashBucketTable::const_iterator iterator;
    14. 	typedef	typename HashBucketTable::const_iterator const_iterator;
    15.  
    16. 	
    17. 	pairbool> insert(const K& k1)
    18. 	{
    19. 		return _ht.insert(k1);
    20. 	}
    21. 	bool Erase(const K& k1)
    22. 	{
    23. 		return _ht.Erase(k1);
    24. 	}
    25. 	iterator find(const K& key)
    26. 	{
    27. 		return _ht.find(key);
    28. 	}
    29.     
    30.    只提供const版本的begin和end函数，就是为了_ht调用的begin和end函数返回的是const_iterator
    31. 	const_iterator begin()const
    32. 	{
    33. 		return _ht.begin();  
    34. 	}
    35. 	const_iterator end()const 
    36. 	{
    37. 		return _ht.end();
    38. 	}
    39. private:
    40. 	HashBucketTable _ht; 偏特化
    41. };

    四  哈希类成员函数介绍

    1. template<class K>
    2. struct DefaultHashfunc
    3. {
    4. 	size_t operator()(const K& key)
    5. 	{
    6. 		return (size_t)key;
    7. 	}
    8. };
    9. template<>
    10. struct DefaultHashfunc    将string转为整数的仿函数
    11. {   
    12. 	size_t operator()(const string& s)
    13. 	{
    14. 		int hash = 1;
    15. 		for (auto e : s)
    16. 			hash = hash * 131 + e;  BKDR
    17. 		return (size_t)hash;
    18. 	}
    19. };
    20. 	
    21. 	
    22. template<class K, class T, class KeyofT, class Hashfunc = DefaultHashfunc>
    23.   class HashBucketTable
    24. 	{
    25. 	public:
    26. 		template<class K, class T, class Ptr, class Ref,class KeyofT, class Hashfunc>//友元类的声明
    27. 		friend	struct HashIterator;  
    28.      HashIterator要访问HashBucketTable的私有成员，所以是
    29. 		   在HashBucketTable对HashIterator友元声明
    30.  
    31.          typedef HashNode Node;
    32. 		typedef HashIterator iterator;
    33. 		typedef HashIteratorconst T*,const T&, KeyofT, Hashfunc> const_iterator;
    34.          通过传const T*,const T&来达到const迭代器的效果		
    35.  
    36.         HashBucketTable()
    37. 		{
    38. 			_table.resize(5);
    39. 		}
    40.  
    41. 		  析构函数函数
    42. 		~HashBucketTable()
    43. 		{
    44. 			for (size_t i = 0; i < _table.size(); i++) 
    45. 			{
    46. 				Node* cur = _table[i]; 
    47. 				while (cur)       找到一个非空桶，遍历链表，delete释放节点
    48. 				{
    49. 					Node* next = cur->_next;
    50. 					_table[i] = next;
    51. 					delete cur;
    52. 					cur = next;
    53. 				}
    54. 			}
    55. 		}
    56. 		iterator begin()
    57. 		{
    58. 			for (size_t i = 0; i < _table.size(); i++)//遍历哈希表ht
    59. 			{
    60. 				Node* cur = _table[i];
    61. 				if (cur)  找到第一个不为空的桶
    62. 				{
    63. 					return iterator(cur, this);
    64. 				}
    65. 			}
    66. 			return iterator(nullptr, this);
    67. 		}
    68. 		iterator end()
    69. 		{
    70. 			return  iterator(nullptr, this);
    71. 		}
    72. 		const_iterator begin()const
    73. 		{
    74. 			for (size_t i = 0; i < _table.size(); i++)//遍历哈希表ht
    75. 			{
    76. 				Node* cur = _table[i];
    77. 				if (cur)//找到第一个不为空的桶
    78. 				{
    79. 					return  const_iterator(cur, this);
    80. 				}
    81. 			}
    82. 			return const_iterator(nullptr, this);
    83. 		}
    84. 		const_iterator end()const
    85. 		{
    86. 			return  const_iterator(nullptr, this);
    87. 		}
    88.  
    89.          拷贝构造函数
    90. 		HashBucketTable(const HashBucketTable& ht)
    91. 		{
    92. 			KeyofT kot;
    93. 			Hashfunc hf;
    94. 			_table.resize(ht._table.size());
    95. 			for (size_t i = 0; i < ht._table.size(); i++)//遍历哈希表ht
    96. 			{
    97. 				Node* cur = ht._table[i];
    98. 				while (cur)//遍历该桶
    99. 				{
    100. 					Node* newnode = new Node(cur->_data);
    101. 					size_t hashi = hf(kot(cur->_data)) % _table.size();
    102. 					newnode->_next = _table[hashi];
    103. 					_table[hashi] = newnode;
    104. 					cur = cur->_next;//去桶的下一个节点
    105. 				}
    106. 			}
    107. 		}
    108. 	
    109. 		iterator find(const K& key)  此处还是返回普通迭代器
    110. 		{
    111. 			Hashfunc hf;
    112. 			KeyofT kot;
    113. 			size_t hashi = hf(key) % _table.size();
    114. 			Node* cur = _table[hashi];
    115. 			while (cur)
    116. 			{
    117. 				if (kot(cur->_data) == key)
    118. 				{
    119. 					return iterator(cur, this);
    120. 				}
    121. 				cur = cur->_next;
    122. 			}
    123. 			return iterator(nullptr,this);
    124. 		}
    125. 		bool Erase(const K& key)
    126. 		{
    127. 			KeyofT kot;
    128. 			Hashfunc hf;
    129.             iterator ret=find(key);
    130.             if(ret._node==nullptr)  没找到节点，返回false
    131.              return false;
    132. 			size_t hashi = hf(key) % _table.size();
    133. 			Node* pre = nullptr;
    134. 			Node* cur = _table[hashi];
    135. 			while (cur)
    136. 			{
    137. 				if (kot(cur->_data) == key)
    138. 				{
    139. 					if (pre == nullptr)//头删
    140. 					{
    141. 						_table[hashi] = cur->_next;//链接
    142. 					}
    143. 					else
    144. 					{
    145. 						pre->_next = cur->_next;
    146. 					}
    147. 					delete cur;
    148. 					--_size;//负载因子要--
    149. 					return true;
    150. 				}
    151. 				pre = cur;
    152. 				cur = cur->_next;
    153. 			}
    154. 			return false;  没找到,erase失败
    155. 		}
    156. 		pairbool> insert(const T& kv)
    157. 		{
    158. 			KeyofT kot;
    159. 			Hashfunc hf;
    160. 			查找该节点是否已经存在
    161. 			iterator it = find(kot(kv));
    162. 			if (it._node)//该节点存在，返回该节点迭代器,并且插入失败
    163. 				return make_pair(it, false);
    164. 			//扩容
    165. 			if (_size >= _table.size())
    166. 			{
    167. 				size_t newsize = _table.size() * 2;
    168.                 
    169. 				vector newtable;
    170. 				newtable.resize(newsize);
    171. 				for (size_t i = 0; i < _table.size(); i++)
    172. 				{
    173. 					Node* cur = _table[i]; 搬运旧表上的节点,省得自己new和delete
    174. 					while (cur)
    175. 					{
    176. 						Node* next = cur->_next;
    177. 						_table[i] = next;
    178. 						size_t hashi = hf(kot(cur->_data)) % newtable.size();//计算新表映射下标
    179. 						搬到新表
    180. 						cur->_next = newtable[hashi];
    181. 						newtable[hashi] = cur;
    182. 						cur = next;//搬下个节点
    183. 					}
    184. 				}
    185.                 新旧表交换
    186. 				_table.swap(newtable);
    187. 			}
    188.          
    189.             正常插入节点
    190. 			size_t hasi = hf(kot(kv)) % _table.size();
    191. 			Node* newnode = new Node(kv);
    192. 			newnode->_next = _table[hasi];
    193. 			_table[hasi] = newnode;
    194. 			_size++;
    195. 			return make_pair(iterator(newnode,this),true);
    196. 		}
    197. 	private:
    198. 		vector _table;
    199. 		size_t _size = 0;
    200. 	};

  • 相关阅读:
    springboot学生课程成绩信息管理系统74m06-java-ssm
    DHCP原理与配置
    seata框架
    antd tree 懒加载+局部刷新
    使用Bind提供的域名解析服务
    Linux系统导入导出docker容器的sql数据
    NLP - truecase
    代码格式化----逗号问题
    AAA认证，授权，计费
    【爬虫基础】万字长文详解XPath
  • 原文地址：https://blog.csdn.net/m0_62792369/article/details/133576379