• C++---哈希

    目录

    1. unordered系列关联式容器

    1.1 unordered_map

    1.1.1 unordered_map的介绍

    1.1.2 unordered_map的接口说明

    1.2 unordered_set

    2. 底层结构

    2.1 哈希概念

    2.2 哈希冲突

    2.3 哈希函数

    2.4 哈希冲突解决

    2.4.1 闭散列

    2.4.2 开散列

    3. 封装unorder_map和unorder_set

    3.1 unorder_map 的封装

    3.2 unorder_set 的封装

    3.4 unordered_map 加迭代器的封装

    3.5 unordered_set 加迭代器的封装

    1. unordered系列关联式容器

    1.1 unordered_map

    1.1.1 unordered_map的介绍

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

    1.1.2 unordered_map的接口说明

    1. unordered_map的构造

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

    2. unordered_map的容量

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

    3. unordered_map的迭代器

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

    4. unordered_map的元素访问

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

    5. unordered_map的查询

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

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

    6. unordered_map的修改操作

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

    7. unordered_map的桶操作

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

    1.2 unordered_set

    与unordered_map类似，详情见文档unordered_set

    2. 底层结构

    unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

    2.1 哈希概念

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

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

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

    当向该结构中：

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

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

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

    例如：数据集合{1，7，6，4，5，9}；
    哈希函数设置为：hash(key) = key % capacity ; capacity为存储元素底层空间总的大小。

    问题：如果继续向上述哈希表中插入44，会出现什么问题？

    2.2 哈希冲突

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

            发生哈希冲突该如何处理呢？

    2.3 哈希函数

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

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

    常见哈希函数：

    1. 直接定址法--（常用）
    取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
    优点：简单、均匀
    缺点：需要事先知道关键字的分布情况
    使用场景：适合查找比较小且连续的情况

    例题：字符串中的第一个唯一字符

    1. class Solution {
    2. public:
    3.     int firstUniqChar(string s) {
    4.         int hash[256] = {0};
    5.         for(int i = 0; i < s.size(); i++){
    6.             hash[s[i]]++;
    7.         }
    8.         for(int i = 0; i < s.size(); i++){
    9.             if(hash[s[i]] == 1){
    10.                 return i;
    11.             }
    12.         }
    13.         return -1;
    14.     }
    15. };

    2. 除留余数法--(常用)
    设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
    按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。

     注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

    2.4 哈希冲突解决

    解决哈希冲突两种常见的方法是：闭散列和开散列

    2.4.1 闭散列

            闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

    那如何寻找下一个空位置呢？

    1. 线性探测

            比如2.1中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，
    因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

    线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

    插入：
            通过哈希函数获取待插入元素在哈希表中的位置
            如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

    删除：
            采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素
    会影响其他元素的搜索    。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

    1. // 哈希表每个空间给个标记
    2. // EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
    3. enum State
    4. {EMPTY, EXIST, DELETE};

    载荷因子：

            为了解决 “哈希表什么情况下进行扩容？如何扩容？” 的问题，我们引入载荷因子的概念。

            载荷因子 = 表中元素个数 / 散列表容量；

            载荷因子越大，表中元素越多，产生冲突可能性越大；

            载荷因子越小，表中元素越少，产生冲突可能性越小；

            当达到载荷因子我们就扩容，如果载荷因子设置的太小，空间资源浪费就多，载荷因子设置越大，产生冲突的可能性就越大。因此，一般设置载荷因子为 0.7——0.8。

    线性探测简要实现哈希表代码如下：

    1. enum State//标志位
    2. {
    3. 	EMPTY,
    4. 	EXIST,
    5. 	DELETE
    6. };
    7.  
    8. template<class K,class V>
    9. struct HashData//节点元素包含键值对和标志位
    10. {
    11. 	pair _kv;
    12. 	State _state = EMPTY;
    13. };
    14.  
    15. template<class K>
    16. struct HashFunc//用于方便比较的仿函数
    17. {
    18. 	size_t operator()(const K& key)
    19. 	{
    20. 		return (size_t)key;
    21. 	}
    22. };
    23.  
    24. //特化
    25. template<>
    26. struct HashFunc
    27. {
    28. 	size_t operator()(const string& key)
    29. 	{
    30. 		size_t val = 0;
    31. 		for (auto ch : key)
    32. 		{
    33. 			//防止出现abc = cba 这种情况，有大佬提出加每个字符前*131
    34. 			val *= 131;
    35. 			val += ch;
    36. 		}
    37. 		return val;
    38. 	}
    39. };
    40.  
    41. //因为如果K为string类型，无法用 % 来实现映射关系，因此我们写个Hash仿函数
    42. template<class K, class V, class Hash = HashFunc>
    43. class HashTable
    44. {
    45. public:
    46. 	bool Insert(const pair& kv)
    47. 	{
    48. 		if (Find(kv.first))
    49. 			return false;
    50.  
    51. 		//表为空或载荷因子超70%就扩容
    52. 		if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7)
    53. 		{
    54. 			size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    55. 			HashTable newHT;
    56. 			newHT._tables.resize(newSize);
    57. 			//旧表数据映射到新表
    58. 			for (auto e : _tables)
    59. 			{
    60. 				if (e._state == EXIST)
    61. 				{
    62. 					newHT.Insert(e._kv);
    63. 				}
    64. 			}
    65. 			_tables.swap(newHT._tables);
    66. 		}
    67.  
    68. 		Hash hash;
    69. 		size_t hashi = hash(kv.first) % _tables.size();
    70. 		//线性探测
    71. 		while (_tables[hashi]._state == EXIST)
    72. 		{
    73. 			hashi++;
    74. 			hashi %= _tables.size();
    75. 		}
    76. 		_tables[hashi]._kv = kv;
    77. 		_tables[hashi]._state = EXIST;
    78. 		++_size;
    79.  
    80. 		return true;
    81. 	}
    82.  
    83. 	HashData* Find(const K& key)
    84. 	{
    85. 		if (_tables.size() == 0)
    86. 		{
    87. 			return nullptr;
    88. 		}
    89.  
    90. 		Hash hash;
    91. 		size_t hashi = hash(key) % _tables.size();
    92. 		while (_tables[hashi]._state != EMPTY)
    93. 		{
    94. 			if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
    95. 			{
    96. 				return &_tables[hashi];
    97. 			}
    98. 			hashi++;
    99. 			hashi %= _tables.size();
    100. 		}
    101. 		return nullptr;
    102. 	}
    103.  
    104. 	bool Erase(const K& key)
    105. 	{
    106. 		HashData* ret = Find(key);
    107. 		if (ret)
    108. 		{
    109. 			ret->_state = DELETE;
    110. 			--_size;
    111. 			return true;
    112. 		}
    113. 		else
    114. 		{
    115. 			return false;
    116. 		}
    117. 	}
    118.  
    119.  
    120. private:
    121. 	vector> _tables;
    122. 	size_t _size = 0;//存储多少有效数据
    123. };

    总结：

            线性探测优点：实现非常简单
            线性探测缺点：某个位置冲突很多的情况下，互相占用，冲突一片，如下图：

    2. 二次探测

    二次探测不是探测二次，是探测2的 i 次方：

     二次探测只需要把原来线性探测略微改动一下即可：

    1. bool Insert(const pair& kv)
    2. 	{
    3. 		if (Find(kv.first))
    4. 			return false;
    5.  
    6. 		//表为空或载荷因子超70%就扩容
    7. 		if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7)
    8. 		{
    9. 			size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    10. 			HashTable newHT;
    11. 			newHT._tables.resize(newSize);
    12. 			//旧表数据映射到新表
    13. 			for (auto e : _tables)
    14. 			{
    15. 				if (e._state == EXIST)
    16. 				{
    17. 					newHT.Insert(e._kv);
    18. 				}
    19. 			}
    20. 			_tables.swap(newHT._tables);
    21. 		}
    22.  
    23. 		Hash hash;
    24. 		size_t start = hash(kv.first) % _tables.size();
    25. 		size_t i = 0;
    26. 		size_t hashi = start;
    27. 		//二次探测
    28. 		while (_tables[hashi]._state == EXIST)
    29. 		{
    30. 			++i;
    31. 			hashi = start + i * i;
    32. 			hashi %= _tables.size();
    33. 		}
    34. 		_tables[hashi]._kv = kv;
    35. 		_tables[hashi]._state = EXIST;
    36. 		++_size;
    37.  
    38. 		return true;
    39. 	}

    2.4.2 开散列

    开散列概念

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

    哈希桶简单实现：

    1. template<class K>
    2. struct HashFunc
    3. {
    4. 	size_t operator()(const K& key)
    5. 	{
    6. 		return (size_t)key;
    7. 	}
    8. };
    9.  
    10. //特化
    11. template<>
    12. struct HashFunc
    13. {
    14. 	size_t operator()(const string& key)
    15. 	{
    16. 		size_t val = 0;
    17. 		for (auto ch : key)
    18. 		{
    19. 			//防止出现abc = cba 这种情况，有大佬提出加每个字符前*131
    20. 			val *= 131;
    21. 			val += ch;
    22. 		}
    23. 		return val;
    24. 	}
    25. };
    26.  
    27. namespace HashBucket
    28. {
    29. 	template<class K, class V>
    30. 	struct HashNode
    31. 	{
    32. 		pair _kv;
    33. 		HashNode* _next;
    34.  
    35. 		HashNode(const pair& kv)
    36. 			:_kv(kv)
    37. 			,_next(nullptr)
    38. 		{}
    39. 	};
    40.  
    41. 	template<class K,class V, class Hash = HashFunc>
    42. 	class HashTable
    43. 	{
    44. 		typedef HashNode Node;
    45. 	public:
    46. 		~HashTable()
    47. 		{
    48. 			for (size_t i = 0; i < _tables.size(); ++i)
    49. 			{
    50. 				Node* cur = _tables[i];
    51. 				while (cur)
    52. 				{
    53. 					Node* next = cur->_next;
    54. 					delete cur;
    55. 					cur = next;
    56. 				}
    57. 				_tables[i] = nullptr;
    58. 			}
    59. 		}
    60.  
    61. 		bool Insert(const pair& kv)
    62. 		{
    63. 			//去重
    64. 			if (Find(kv.first))
    65. 			{
    66. 				return false;
    67. 			}
    68. 			Hash hash;
    69. 			//负载因子到1就扩容
    70. 			if (_size == _tables.size())
    71. 			{
    72. 				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    73. 				vector newTables;
    74. 				newTables.resize(newSize, nullptr);
    75. 				//旧表中节点移动映射到新表
    76. 				for (size_t i = 0; i < _tables.size(); ++i)
    77. 				{
    78. 					Node* cur = _tables[i];
    79. 					while (cur)
    80. 					{
    81. 						Node* next = cur->_next;
    82.  
    83. 						size_t hashi = hash(cur->_kv.first) % newTables.size();
    84. 						cur->_next = newTables[hashi];
    85. 						newTables[hashi] = cur;
    86.  
    87. 						cur = next;
    88. 					}
    89. 					_tables[i] = nullptr;
    90. 				}
    91. 				_tables.swap(newTables);
    92. 			}
    93.  
    94. 			size_t hashi = hash(kv.first) % _tables.size();
    95. 			//头插
    96. 			Node* newnode = new Node(kv);
    97. 			newnode->_next = _tables[hashi];
    98. 			_tables[hashi] = newnode;
    99. 			++_size;
    100.  
    101. 			return true;
    102. 		}
    103. 		Node* Find(const K& key)
    104. 		{
    105. 			if (_tables.size() == 0)
    106. 			{
    107. 				return nullptr;
    108. 			}
    109.  
    110. 			Hash hash;
    111. 			size_t hashi = hash(key) % _tables.size();
    112. 			Node* cur = _tables[hashi];
    113. 			while (cur)
    114. 			{
    115. 				if (cur->_kv.first == key)
    116. 				{
    117. 					return cur;
    118. 				}
    119. 				cur = cur->_next;
    120. 			}
    121. 			return nullptr;
    122. 		}
    123.  
    124. 		bool Erase(const K& key)
    125. 		{
    126. 			if (_tables.size() == 0)
    127. 			{
    128. 				return false;
    129. 			}
    130.  
    131. 			Hash hash;
    132. 			size_t hashi = hash(key) % _tables.size();
    133. 			Node* prev = nullptr;
    134. 			Node* cur = _tables[hashi];
    135. 			while (cur)
    136. 			{
    137. 				if (cur->_kv.first == key)
    138. 				{
    139. 					// 1、头删
    140. 					// 2、中间删
    141. 					if (prev == nullptr)
    142. 					{
    143. 						_tables[hashi] = cur->_next;
    144. 					}
    145. 					else
    146. 					{
    147. 						prev->_next = cur->_next;
    148. 					}
    149.  
    150. 					delete cur;
    151. 					--_size;
    152. 					return true;
    153. 				}
    154.  
    155. 				prev = cur;
    156. 				cur = cur->_next;
    157. 			}
    158.  
    159. 			return false;
    160. 		}
    161.  
    162. 		size_t Size()
    163. 		{
    164. 			return _size;
    165. 		}
    166.  
    167. 		// 表的长度
    168. 		size_t TablesSize()
    169. 		{
    170. 			return _tables.size();
    171. 		}
    172.  
    173. 		// 桶的个数
    174. 		size_t BucketNum()
    175. 		{
    176. 			size_t num = 0;
    177. 			for (size_t i = 0; i < _tables.size(); ++i)
    178. 			{
    179. 				if (_tables[i])
    180. 				{
    181. 					++num;
    182. 				}
    183. 			}
    184.  
    185. 			return num;
    186. 		}
    187.  
    188. 		size_t MaxBucketLenth()
    189. 		{
    190. 			size_t maxLen = 0;
    191. 			for (size_t i = 0; i < _tables.size(); ++i)
    192. 			{
    193. 				size_t len = 0;
    194. 				Node* cur = _tables[i];
    195. 				while (cur)
    196. 				{
    197. 					++len;
    198. 					cur = cur->_next;
    199. 				}
    200.  
    201. 				//if (len > 0)
    202. 					//printf("[%d]号桶长度:%d\n", i, len);
    203.  
    204. 				if (len > maxLen)
    205. 				{
    206. 					maxLen = len;
    207. 				}
    208. 			}
    209.  
    210. 			return maxLen;
    211. 		}
    212. 	private:
    213. 		vector _tables;
    214. 		size_t _size = 0;//存储有效数据个数
    215. 	};
    216. }

    3. 封装unorder_map和unorder_set

    简单修改上述哈希桶用于封装实现unorder_map和unorder_set.

    首先，我们将原来节点中用来存储节点值的 pair键值对 改为 模板参数 T.

    1.  
    2. // 因为关联式容器中存储的是的键值对，因此
    3. // k为key的类型，
    4. // T: 如果是map，则为pair; 如果是set，则为k
    5. // KeyOfT: 通过T来获取key的一个仿函数类
    6. namespace Bucket
    7. {
    8. 	template<class T>
    9. 	struct HashNode
    10. 	{
    11. 		T _data;
    12. 		HashNode* _next;
    13.  
    14. 		HashNode(const T& data)
    15. 			:_data(data)
    16. 			,_next(nullptr)
    17. 		{}
    18. 	};
    19.  
    20. 	template<class K,class T, class Hash, class KeyOfT>
    21. 	class HashTable
    22. 	{
    23. 		typedef HashNode Node;
    24. 	public:
    25. 		~HashTable()
    26. 		{
    27. 			for (size_t i = 0; i < _tables.size(); ++i)
    28. 			{
    29. 				Node* cur = _tables[i];
    30. 				while (cur)
    31. 				{
    32. 					Node* next = cur->_next;
    33. 					delete cur;
    34. 					cur = next;
    35. 				}
    36. 				_tables[i] = nullptr;
    37. 			}
    38. 		}
    39.  
    40. 		bool Insert(const T& data)
    41. 		{
    42. 			Hash hash;
    43. 			KeyOfT kot;
    44. 			//去重
    45. 			if (Find(kot(data)))
    46. 			{
    47. 				return false;
    48. 			}
    49. 			//负载因子到1就扩容
    50. 			if (_size == _tables.size())
    51. 			{
    52. 				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    53. 				vector newTables;
    54. 				newTables.resize(newSize, nullptr);
    55. 				//旧表中节点移动映射到新表
    56. 				for (size_t i = 0; i < _tables.size(); ++i)
    57. 				{
    58. 					Node* cur = _tables[i];
    59. 					while (cur)
    60. 					{
    61. 						Node* next = cur->_next;
    62.  
    63. 						size_t hashi = hash(kot(cur->_data)) % newTables.size();
    64. 						cur->_next = newTables[hashi];
    65. 						newTables[hashi] = cur;
    66.  
    67. 						cur = next;
    68. 					}
    69. 					_tables[i] = nullptr;
    70. 				}
    71. 				_tables.swap(newTables);
    72. 			}
    73.  
    74. 			size_t hashi = hash(kot(data)) % _tables.size();
    75. 			//头插
    76. 			Node* newnode = new Node(data);
    77. 			newnode->_next = _tables[hashi];
    78. 			_tables[hashi] = newnode;
    79. 			++_size;
    80.  
    81. 			return true;
    82. 		}
    83. 		Node* Find(const K& key)
    84. 		{
    85. 			if (_tables.size() == 0)
    86. 			{
    87. 				return nullptr;
    88. 			}
    89.  
    90. 			Hash hash;
    91. 			KeyOfT kot;
    92. 			size_t hashi = hash(key) % _tables.size();
    93. 			Node* cur = _tables[hashi];
    94. 			while (cur)
    95. 			{
    96. 				if (kot(cur->_data) == key)
    97. 				{
    98. 					return cur;
    99. 				}
    100. 				cur = cur->_next;
    101. 			}
    102. 			return nullptr;
    103. 		}
    104.  
    105. 		bool Erase(const K& key)
    106. 		{
    107. 			if (_tables.size() == 0)
    108. 			{
    109. 				return false;
    110. 			}
    111.  
    112. 			KeyOfT kot;
    113. 			Hash hash;
    114. 			size_t hashi = hash(key) % _tables.size();
    115. 			Node* prev = nullptr;
    116. 			Node* cur = _tables[hashi];
    117. 			while (cur)
    118. 			{
    119. 				if (kot(cur->_data) == key)
    120. 				{
    121. 					// 1、头删
    122. 					// 2、中间删
    123. 					if (prev == nullptr)
    124. 					{
    125. 						_tables[hashi] = cur->_next;
    126. 					}
    127. 					else
    128. 					{
    129. 						prev->_next = cur->_next;
    130. 					}
    131.  
    132. 					delete cur;
    133. 					--_size;
    134. 					return true;
    135. 				}
    136.  
    137. 				prev = cur;
    138. 				cur = cur->_next;
    139. 			}
    140.  
    141. 			return false;
    142. 		}
    143.  
    144. 		size_t Size()
    145. 		{
    146. 			return _size;
    147. 		}
    148.  
    149. 		// 表的长度
    150. 		size_t TablesSize()
    151. 		{
    152. 			return _tables.size();
    153. 		}
    154.  
    155. 		// 桶的个数
    156. 		size_t BucketNum()
    157. 		{
    158. 			size_t num = 0;
    159. 			for (size_t i = 0; i < _tables.size(); ++i)
    160. 			{
    161. 				if (_tables[i])
    162. 				{
    163. 					++num;
    164. 				}
    165. 			}
    166.  
    167. 			return num;
    168. 		}
    169.  
    170. 		size_t MaxBucketLenth()
    171. 		{
    172. 			size_t maxLen = 0;
    173. 			for (size_t i = 0; i < _tables.size(); ++i)
    174. 			{
    175. 				size_t len = 0;
    176. 				Node* cur = _tables[i];
    177. 				while (cur)
    178. 				{
    179. 					++len;
    180. 					cur = cur->_next;
    181. 				}
    182.  
    183. 				//if (len > 0)
    184. 					//printf("[%d]号桶长度:%d\n", i, len);
    185.  
    186. 				if (len > maxLen)
    187. 				{
    188. 					maxLen = len;
    189. 				}
    190. 			}
    191.  
    192. 			return maxLen;
    193. 		}
    194. 	private:
    195. 		vector _tables;
    196. 		size_t _size = 0;//存储有效数据个数
    197. 	};
    198. }

    3.1 unorder_map 的封装

    1. #include"HashTable.h"//HashTable.h即为上面哈希桶的实现
    2.  
    3. namespace zj
    4. {
    5. 	template<class K, class V, class Hash = HashFunc>
    6. 	class unorder_map
    7. 	{
    8. 		struct MapKeyOfT
    9. 		{
    10. 			const K& operator()(const pair& kv)
    11. 			{
    12. 				return kv.first;
    13. 			}
    14. 		};
    15. 	public:
    16. 		bool Insert(const pair& kv)
    17. 		{
    18. 			return _ht.Insert(kv);
    19. 		}
    20. 	private:
    21. 		Bucket::HashTable, Hash, MapKeyOfT> _ht;
    22. 	};
    23. }

    3.2 unorder_set 的封装

    1. #include"HashTable.h"//HashTable.h即为上面哈希桶的实现
    2.  
    3. namespace zj
    4. {
    5. 	template<class K, class Hash = HashFunc>
    6. 	class unorder_set
    7. 	{
    8. 		struct SetKeyOfT
    9. 		{
    10. 			const K& operator()(const K& key)
    11. 			{
    12. 				return key;
    13. 			}
    14. 		};
    15. 	public:
    16. 		bool Insert(const K& key)
    17. 		{
    18. 			return _ht.Insert(key);
    19. 		}
    20. 	private:
    21. 		Bucket::HashTable _ht;
    22. 	};
    23. }

    3.3 哈希桶迭代器模板

    1. namespace Bucket
    2. {
    3. 	template<class T>
    4. 	struct HashNode
    5. 	{
    6. 		T _data;
    7. 		HashNode* _next;
    8.  
    9. 		HashNode(const T& data)
    10. 			:_data(data)
    11. 			,_next(nullptr)
    12. 		{}
    13. 	};
    14. 	//前置声明，不然__HashIterator里定义不了_pht
    15. 	template<class K, class T, class Hash, class KeyOfT>
    16. 	class HashTable;
    17.  
    18. 	template<class K, class T, class Hash, class KeyOfT>
    19. 	struct __HashIterator
    20. 	{
    21. 		typedef HashNode Node;
    22. 		typedef HashTable HT;
    23. 		typedef __HashIterator Self;
    24.  
    25. 		Node* _node;
    26. 		HT* _pht;
    27.  
    28. 		__HashIterator(Node* node, HT* pht)
    29. 			:_node(node)
    30. 			,_pht(pht)
    31. 		{}
    32.  
    33. 		T& operator*()
    34. 		{
    35. 			return _node->_data;
    36. 		}
    37.  
    38. 		T* operator->()
    39. 		{
    40. 			return &_node->_data;
    41. 		}
    42.  
    43. 		Self& operator++()
    44. 		{
    45. 			if (_node->_next)
    46. 			{
    47. 				// 当前桶中迭代
    48. 				_node = _node->_next;
    49. 			}
    50. 			else
    51. 			{
    52. 				// 找下一个桶
    53. 				Hash hash;
    54. 				KeyOfT kot;
    55. 				size_t i = hash(kot(_node->_data)) % _pht->_tables.size();
    56. 				++i;
    57. 				for (; i < _pht->_tables.size(); ++i)
    58. 				{
    59. 					if (_pht->_tables[i])
    60. 					{
    61. 						_node = _pht->_tables[i];
    62. 						break;
    63. 					}
    64. 				}
    65.  
    66. 				// 说明后面没有有数据的桶了
    67. 				if (i == _pht->_tables.size())
    68. 				{
    69. 					_node = nullptr;
    70. 				}
    71. 			}
    72.  
    73. 			return *this;
    74. 		}
    75.  
    76. 		bool operator!=(const Self& s) const
    77. 		{
    78. 			return _node != s._node;
    79. 		}
    80.  
    81. 		bool operator==(const Self& s) const
    82. 		{
    83. 			return _node == s._node;
    84. 		}
    85. 	};
    86.  
    87. 	template<class K,class T, class Hash, class KeyOfT>
    88. 	class HashTable
    89. 	{
    90. 		typedef HashNode Node;
    91.  
    92. 		template<class K, class T, class Hash, class KeyOfT>//模板参数友元要带声明
    93. 		friend struct __HashIterator;
    94. 	public:
    95. 		typedef __HashIterator iterator;
    96.  
    97. 		iterator begin()
    98. 		{
    99. 			for (size_t i = 0; i < _tables.size(); ++i)
    100. 			{
    101. 				if (_tables[i])
    102. 				{
    103. 					return iterator(_tables[i], this);
    104. 				}
    105. 			}
    106.  
    107. 			return end();
    108. 		}
    109.  
    110. 		iterator end()
    111. 		{
    112. 			return iterator(nullptr, this);
    113. 		}
    114.  
    115. 		~HashTable()
    116. 		{
    117. 			for (size_t i = 0; i < _tables.size(); ++i)
    118. 			{
    119. 				Node* cur = _tables[i];
    120. 				while (cur)
    121. 				{
    122. 					Node* next = cur->_next;
    123. 					delete cur;
    124. 					cur = next;
    125. 				}
    126. 				_tables[i] = nullptr;
    127. 			}
    128. 		}
    129.  
    130. 		pairbool> Insert(const T& data)
    131. 		{
    132. 			Hash hash;
    133. 			KeyOfT kot;
    134.  
    135. 			// 去重
    136. 			iterator ret = Find(kot(data));
    137. 			if (ret != end())
    138. 			{
    139. 				return make_pair(ret, false);
    140. 			}
    141.  
    142. 			//负载因子到1就扩容
    143. 			if (_size == _tables.size())
    144. 			{
    145. 				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    146. 				vector newTables;
    147. 				newTables.resize(newSize, nullptr);
    148. 				//旧表中节点移动映射到新表
    149. 				for (size_t i = 0; i < _tables.size(); ++i)
    150. 				{
    151. 					Node* cur = _tables[i];
    152. 					while (cur)
    153. 					{
    154. 						Node* next = cur->_next;
    155.  
    156. 						size_t hashi = hash(kot(cur->_data)) % newTables.size();
    157. 						cur->_next = newTables[hashi];
    158. 						newTables[hashi] = cur;
    159.  
    160. 						cur = next;
    161. 					}
    162. 					_tables[i] = nullptr;
    163. 				}
    164. 				_tables.swap(newTables);
    165. 			}
    166.  
    167. 			size_t hashi = hash(kot(data)) % _tables.size();
    168. 			//头插
    169. 			Node* newnode = new Node(data);
    170. 			newnode->_next = _tables[hashi];
    171. 			_tables[hashi] = newnode;
    172. 			++_size;
    173.  
    174. 			return make_pair(iterator(newnode, this), true);
    175. 		}
    176. 		iterator Find(const K& key)
    177. 		{
    178. 			if (_tables.size() == 0)
    179. 			{
    180. 				return end();
    181. 			}
    182.  
    183. 			Hash hash;
    184. 			KeyOfT kot;
    185. 			size_t hashi = hash(key) % _tables.size();
    186. 			Node* cur = _tables[hashi];
    187. 			while (cur)
    188. 			{
    189. 				if (kot(cur->_data) == key)
    190. 				{
    191. 					return iterator(cur, this);
    192. 				}
    193. 				cur = cur->_next;
    194. 			}
    195. 			return end();
    196. 		}
    197.  
    198. 		bool Erase(const K& key)
    199. 		{
    200. 			if (_tables.size() == 0)
    201. 			{
    202. 				return false;
    203. 			}
    204.  
    205. 			KeyOfT kot;
    206. 			Hash hash;
    207. 			size_t hashi = hash(key) % _tables.size();
    208. 			Node* prev = nullptr;
    209. 			Node* cur = _tables[hashi];
    210. 			while (cur)
    211. 			{
    212. 				if (kot(cur->_data) == key)
    213. 				{
    214. 					// 1、头删
    215. 					// 2、中间删
    216. 					if (prev == nullptr)
    217. 					{
    218. 						_tables[hashi] = cur->_next;
    219. 					}
    220. 					else
    221. 					{
    222. 						prev->_next = cur->_next;
    223. 					}
    224.  
    225. 					delete cur;
    226. 					--_size;
    227. 					return true;
    228. 				}
    229.  
    230. 				prev = cur;
    231. 				cur = cur->_next;
    232. 			}
    233.  
    234. 			return false;
    235. 		}
    236.  
    237.         ....
    238.  
    239. 	private:
    240. 		vector _tables;
    241. 		size_t _size = 0;//存储有效数据个数
    242. 	};
    243.  
    244. }

    3.4 unordered_map 加迭代器的封装

    1. #include"HashTable.h"
    2.  
    3. namespace zj
    4. {
    5. 	template<class K, class V, class Hash = HashFunc>
    6. 	class unordered_map
    7. 	{
    8. 		struct MapKeyOfT
    9. 		{
    10. 			const K& operator()(const pair& kv)
    11. 			{
    12. 				return kv.first;
    13. 			}
    14. 		};
    15. 	public:
    16. 		typedef typename Bucket::HashTable, Hash, MapKeyOfT>::iterator iterator;
    17.  
    18. 		iterator begin()
    19. 		{
    20. 			return _ht.begin();
    21. 		}
    22.  
    23. 		iterator end()
    24. 		{
    25. 			return _ht.end();
    26. 		}
    27.  
    28. 		pairbool> Insert(const pair& kv)
    29. 		{
    30. 			return _ht.Insert(kv);
    31. 		}
    32.  
    33. 		V& operator[](const K& key)
    34. 		{
    35. 			pairbool> ret = _ht.Insert(make_pair(key, V()));
    36. 			return ret.first->second;
    37. 		}
    38. 	private:
    39. 		Bucket::HashTable, Hash, MapKeyOfT> _ht;
    40. 	};
    41.  
    42. 	void test_map()
    43. 	{
    44. 		unordered_map dict;
    45. 		dict.Insert(make_pair("sort", ""));
    46. 		dict.Insert(make_pair("string", ""));
    47. 		dict.Insert(make_pair("left", ""));
    48.  
    49. 		unordered_map::iterator it = dict.begin();
    50. 		while (it != dict.end())
    51. 		{
    52. 			cout << it->first << ":" << it->second << endl;
    53. 			++it;
    54. 		}
    55. 		cout << endl;
    56.  
    57. 	}
    58. }

    3.5 unordered_set 加迭代器的封装

    1. #include"HashTable.h"
    2.  
    3. namespace zj
    4. {
    5. 	template<class K, class Hash = HashFunc>
    6. 	class unorder_set
    7. 	{
    8. 		struct SetKeyOfT
    9. 		{
    10. 			const K& operator()(const K& key)
    11. 			{
    12. 				return key;
    13. 			}
    14. 		};
    15. 	public:
    16. 		typedef typename Bucket::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. 		pairbool> Insert(const K& key)
    29. 		{
    30. 			return _ht.Insert(key);
    31. 		}
    32. 	private:
    33. 		Bucket::HashTable _ht;
    34. 	};
    35.  
    36. 	void test_set()
    37. 	{
    38. 		unordered_set<int> s;
    39. 		s.insert(2);
    40. 		s.insert(3);
    41. 		s.insert(1);
    42. 		s.insert(2);
    43. 		s.insert(5);
    44.  
    45. 		unordered_set<int>::iterator it = s.begin();
    46. 		//auto it = s.begin();
    47. 		while (it != s.end())
    48. 		{
    49. 			cout << *it << " ";
    50. 			++it;
    51. 		}
    52. 		cout << endl;
    53. 	}
    54. }

  • 相关阅读:
    Java日志框架log4j、logback、jul这么多？到底如何选择，他们之间有有什么关联？如何整合使用？
    XMLGregorianCalendar与Date互转
    从零用VitePress搭建博客教程(5) - 如何自定义页面模板、给页面添加独有的className和使页面标题变成侧边目录？
    Mysql binlog的三种模式statement,row,mixed详解，以及无主键造成复制延时的测试
    【QT】QListWidget
    空心三角形
    C++实现单链表的各种操作（数据结构）
    2023燕山大学计算机考研信息汇总
    手机备忘录可以设置密码吗 能锁屏加密的备忘录
    【深度学习】ONNX模型快速部署【入门】
  • 原文地址：https://blog.csdn.net/blue_jun_/article/details/127809151