• C++：哈希

    目录

    一、unordered系列关联容器

    二、底层的结构

    哈希结构

    哈希冲突/哈希碰撞

    ①、闭散列 —> 开放定址法

    闭散列的模拟实现

    ②、开散列 —> 拉链法/哈希桶

    哈希桶的模拟实现

    三、哈希封装unordered_set/map

    1、哈希表改变后的代码

    2、unordered_set的实现

    3、unordered_map的实现

    四、哈希应用

    位图

    位图的特点

    位图的模拟实现

    布隆过滤器

    布隆过滤器的模拟实现

    一、unordered系列关联容器

    unordered_set

    unordered_map

    而关于unordered_set和unordered_map与map和set的用法区别不大，具体用法看map和set部分的详解

    unordered_set和unordered_map与map和set主要有以下两个区别：

    1、map和set遍历是有序的，而unordered_set和unordered_map遍历是无序的

    2、map和set是双向迭代器，而unordered_set和unordered_map是单向迭代器

    而引进unordered系列的原因是因为：在大量数据的情况下，增删查改效率更高，尤其是查效率最高

    下面演示一下用法：

    通过结果可以看出unordered_set插入后是无序的，unordered_set与set的用法基本相同，也是有去重的作用，剩下用法参照map和set

    二、底层的结构

    哈希结构

    哈希也叫散列，表示值跟存储位置建立映射关联关系

    在我们还没学习哈希时，做题时也用过类似哈希的思路去解决问题，比如说要查找一个数组中唯一只出现一次的数字

    这时我们只需要遍历一遍数组，遍历到每一个数字时，在一个新数组的对应位置++，最后再遍历一遍新数组，看哪个位置的值为1，该位置所对应的数字即为只出现一次的数字

    但是有时候会出现特殊情况，比如只有极少个数的数，但是它们之间的差距却很大，如果我们开辟与之对应位置的数组，就会导致非常浪费空间，这时就出现了哈希的除留余数法的思想

    哈希中构造出来的结构：哈希表(散列表)，就类比于上面使用的数组

    除留余数法：散列表是大小为n的，用这个几个大小不同的数，分别去模p(%np)，这里的p是最接近n或等于n的质数，之后再存入散列表中，这就是除留余数法，即Hash(i) = i % p(p <= n)这时无论是多大的数，都可以存在这个空间中，也不怕开辟太多的多余空间，造成空间浪费

    例如：有,四个数,7,201,400，40000，这时我们用除留余数法的思想，假设有一个大小为5的散列表，接下来这,四个数分别%5，得到的结果是2，1，0，0，就可以很好地存储进散列表中了，不用像之前一样开辟40000个空间却只存4个数而造成空间浪费

    这时又有问题了，四个数中的400与40000%5后都是0，那怎么解决呢？

    这种情况就叫做哈希冲突/哈希碰撞

    哈希冲突/哈希碰撞

    有两种方法解决哈希碰撞/哈希冲突：

    ①、闭散列 —> 开放定址法

    开放定址法即如果当前位置已经被占用了，那我们就接着往后面找，有没有没有被占用的的位置

    而开放定址法也有两种方式：

    第一种：线性探测

    线性探测就是指一个位置被占用后，就依次往后找没被占用的位置

    但是有可能会出现，位置依次占用后，如果删除一个位置的数据，接下来在找后面的数据时，会因为删除的位置为空而找不到了，所以我们可以用枚举设置一个状态，(EMPTY)空、(EXIST)存在、(DELETE)删除，这样删除完后，如果后面数据发现此位置为空， 但是状态是删除时，就不会终止查找了

    哈希在扩容时引入了负载因子(载荷因子)的概念：

    负载因子 = 填入表中元素个数 / 散列表的长度

    负载因子越大，冲突概率越大；负载因子越小，冲突概率越小

    一旦到了负载因子的基准值，就需要扩容了

    基准值越大，冲突越多，效率越低，空间利用率越高

    基准值越小，冲突越少，效率越高，空间利用率越低

    一般基准值是控制在0.7~0.8

     但是线性探测在一些特殊情况下，就会显得非常不好：

    比如某一个位置非常冲突，连续几个数都要这个位置，所以都会向后延伸，这时如果再遇到该位置后面位置的数，依然还得往后延伸，因此会造成某个位置冲突很多的情况下，互相占用，冲突一片，下面的二次探测能够稍微减轻冲突的情况

    第二种：二次探测

    线性探测是一个数所对应的位置如果有数了，就+i处理，即+1到下一个位置，如果下一个位置还有数+2，以此类推（i >= 0）

    而二次探测则是+ i^2（i >= 0）

    会比线性探测好一点，但是本质依然可能会互相占用概率大，这两种方法统一的弊端就是，例如：好几个数据都在一号位置存，那么就顺延到后面位置存，而后面数据存的时候发现自己的位置被占用，就又会占用其他数据的位置，恶性循环

    下面有一种更好的方式就叫做拉链法/哈希桶，很好解决了上面的问题

    闭散列的模拟实现
    1. //设置状态，表示空、存在、删除
    2. enum State
    3. {
    4. 	EMPTY,
    5. 	EXIST,
    6. 	DELETE
    7. };
    8.  
    9. //有一个状态_state以及一个pair类型的数据_kv
    10. template<class K, class V>
    11. struct HashData
    12. {
    13. 	pair _kv;
    14. 	State _state = EMPTY;
    15. };
    16.  
    17. //这个是正常能取模的数据调用的
    18. template<class K>
    19. struct HashUsual
    20. {
    21. 	size_t operator()(const K& key)
    22. 	{
    23. 		return (size_t)key;
    24. 	}
    25. };
    26.  
    27. //有些数据不能直接取模，例如string，需要自己写仿函数
    28. //也可以不主动调用，特化处理
    29. template<>
    30. struct HashUsual
    31. {
    32. 	//string类型的就返回所有字符的ascll码
    33. 	size_t operator()(const string& key)
    34. 	{
    35. 		size_t val = 0;
    36. 		for (auto& e : key)
    37. 		{
    38. 			val += e;
    39. 		}
    40.  
    41. 		return val;
    42. 	}
    43. };
    44.  
    45. template<class K, class V, class Hash = HashUsual>
    46. class HashTable
    47. {
    48. public:
    49. 	bool Insert(const pair& kv)
    50. 	{
    51. 		//负载因子到了就扩容，一般是0.7~0.8
    52. 		//之所以>=7，不是>=0.7，是因为两个整数除完不能等于0.7这个小数
    53. 		//所以干脆放大十倍就不会有这个问题了
    54. 		if (_table.size() == 0 || 10 * _size / _table.size() >= 7)
    55. 		{
    56. 			size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
    57. 			HashTable newHT;
    58. 			newHT._table.resize(newsize);
    59. 			//旧表的数据映射到新表中
    60. 			for (auto& e : _table)
    61. 			{
    62. 				if (e._state == EXIST)
    63. 				{
    64. 					newHT.Insert(e._kv);
    65. 				}
    66. 			}
    67. 			//旧表与新表交换，执行完毕旧表自动释放了
    68. 			_table.swap(newHT._table);
    69. 		}
    70. 		//线性探测
    71. 		Hash hs;
    72. 		//找到要存储的位置hashi
    73. 		size_t hashi = hs(kv.first) % _table.size();
    74. 		
    75. 		while (_table[hashi]._state == EXIST)
    76. 		{
    77. 			hashi++;
    78. 			//超过散列表的范围后，需要返回到开头
    79. 			hashi %= _table.size();
    80. 		}
    81. 		_table[hashi]._kv = kv;
    82. 		_table[hashi]._state = EXIST;
    83. 		++_size;
    84.  
    85. 	//	//二次探测
    86. 	//	Hash hs;
    87. 	//	//找到要存储的位置start
    88. 	//	size_t start = hs(kv.first) % _table.size();
    89. 	//	size_t i = 0;
    90. 	//	size_t hashi = start;
    91. 	//	while (_table[hashi]._state == EXIST)
    92. 	//	{
    93. 	//		//如果_table[hashi]有值，hashi就+i^2
    94. 	//		i++;
    95. 	//		hashi = start + i * i;
    96. 	//		hashi %= _table.size();
    97. 	//	}
    98. 	//	_table[hashi]._kv = kv;
    99. 	//	_table[hashi]._state = EXIST;
    100. 	//	++_size;
    101.  
    102. 		return true;
    103. 	}
    104.  
    105.  
    106. 	HashData* Find(const K& key)
    107. 	{
    108. 		//如果表为空，就不查找了
    109. 		if (_table.size() == 0)
    110. 		{
    111. 			return nullptr;
    112. 		}
    113. 		Hash hs;
    114. 		//除留余数法
    115. 		size_t hashi = hs(key) % _table.size();
    116. 		while (_table[hashi]._state != EMPTY)
    117. 		{
    118. 			if (_table[hashi]._state != DELETE && _table[hashi]._kv.first == key)
    119. 			{
    120. 				return &_table[hashi];
    121. 			}
    122.  
    123. 			hashi++;
    124. 			//如果超过散列表，就回到开头
    125. 			hashi %= _table.size();
    126. 			//如果回到开头了，就break
    127. 			if (hashi == key % _table.size())
    128. 			{
    129. 				break;
    130. 			}
    131. 		}
    132.  
    133. 		return nullptr;
    134. 	}
    135.  
    136. 	bool Erase(const K& key)
    137. 	{
    138. 		//查找值为key的数据在不在
    139. 		//如果在，只需要改变状态再--_size就完成了删除
    140. 		HashData* ret = Find(key);
    141. 		if (ret)
    142. 		{
    143. 			ret->_state = DELETE;
    144. 			--_size;
    145. 			return true;
    146. 		}
    147. 		else
    148. 		{
    149. 			return false;
    150. 		}
    151. 	}
    152.  
    153. 	void Print()
    154. 	{
    155. 		for (size_t i = 0; i < _table.size(); ++i)
    156. 		{
    157. 			if (_table[i]._state == EXIST)
    158. 			{
    159. 				printf("[%d:%d] ", i, _table[i]._kv.first);
    160. 			}
    161. 			else
    162. 			{
    163. 				printf("[%d:×] ",i);
    164. 			}
    165. 		}
    166. 	}
    167. private:
    168.  
    169. 	//存储的每个数据是HashData的
    170. 	vector> _table;
    171. 	size_t _size = 0;//表示数组中存储了多少有效数据
    172. };
    173.  
    174. void testHT()
    175. {
    176. 	HashTable<int, int> ht;
    177. 	int arr[] = { 3,6,15,13,27,48 };
    178. 	for (auto e : arr)
    179. 	{
    180. 		ht.Insert(make_pair(e, e));
    181. 	}
    182. 	
    183. 	ht.Print();
    184. }
    ②、开散列 —> 拉链法/哈希桶

    哈希桶的方式，就是如果数据在一个位置，就先挂起，先不放入位置中

    哈希桶的表就不是普通数组了，而是指针数组

    每次插入新的数据时，只需要头插即可

    例如下图所示方式： 

    哈希桶的模拟实现
    1. template<class K,class V>
    2. struct HashNode
    3. {
    4. 	pair _kv;
    5. 	HashNode* _next;
    6.  
    7. 	HashNode(const pair& kv)
    8. 		:_kv(kv)
    9. 		,_next(nullptr)
    10. 	{}
    11. };
    12.  
    13. //这个是正常能取模的数据调用的
    14. template<class K>
    15. struct HashUsual
    16. {
    17. 	size_t operator()(const K& key)
    18. 	{
    19. 		return (size_t)key;
    20. 	}
    21. };
    22.  
    23. //有些数据不能直接取模，例如string，需要自己写仿函数
    24. //也可以不主动调用，特化处理
    25. template<>
    26. struct HashUsual
    27. {
    28. 	//string类型的就返回所有字符的ascll码
    29. 	size_t operator()(const string& key)
    30. 	{
    31. 		//BKDR法
    32. 		size_t val = 0;
    33. 		for (auto& e : key)
    34. 		{
    35. 			val *= 131;
    36. 			val += e;
    37. 		}
    38.  
    39. 		return val;
    40. 	}
    41. };
    42.  
    43.  
    44. template<class K,class V,class Hash = HashUsual>
    45. class HashTable
    46. {
    47. 	typedef HashNode Node;
    48. public:
    49. 	//析构，释放哈希桶
    50. 	~HashTable()
    51. 	{
    52. 		for (size_t i = 0; i < _table.size(); ++i)
    53. 		{
    54. 			Node* cur = _table[i];
    55. 			while (cur)
    56. 			{
    57. 				//记录cur的next
    58. 				Node* next = cur->_next;
    59. 				delete cur;
    60. 				cur = next;
    61. 			}
    62. 			//置空
    63. 			_table[i] = nullptr;
    64. 		}
    65. 	}
    66.  
    67. 	bool Insert(const pair& kv)
    68. 	{
    69. 		//去重
    70. 		if (Find(kv.first))
    71. 		{
    72. 			return false;
    73. 		}
    74. 		Hash hs;//仿函数
    75. 		//负载因子到1就扩容
    76. 		if (_size == _table.size())
    77. 		{
    78. 			size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
    79. 			vector newtable;
    80. 			newtable.resize(newsize, nullptr);
    81.  
    82. 			//旧表结点映射到新表
    83.             //这里需要注意的是：扩容采用的是将旧表的指针迁移到新表
    84.             //而学习的闭散列模拟实现是复用insert
    85.             //之所以这里不复用insert，是因为insert会new新结点   
    86.             //如果每次都new，然后将旧表的结点再释放，相当于旧表结点没有派上用处
    87.             //所以直接迁移旧表指针，能更好利用旧表的指针，提高效率
    88. 			for (size_t i = 0; i < _table.size(); ++i)
    89. 			{
    90. 				Node* cur = _table[i];
    91. 				while (cur)
    92. 				{
    93. 					//提前保存cur的next，下面会改变next，不然会找不到
    94. 					Node* next = cur->_next;
    95.  
    96. 					size_t hashi = hs(cur->_kv.first) % newtable.size();
    97. 					//头插：插入结点的next指向新表结点的第一个
    98. 					//插入结点作为新表结点的第一个
    99. 					cur->_next = newtable[hashi];
    100. 					newtable[hashi] = cur;
    101.                     //cur指向旧表的下一个结点
    102.                     cur = next;
    103. 				}
    104. 				_table[i] = nullptr;
    105. 			}
    106. 			//交换_table与newtable,便于运行结束自动删除_table
    107. 			_table.swap(newtable);
    108. 		}
    109. 		
    110.  
    111. 		size_t hashi = hs(kv.first) % _table.size();
    112. 		//头插
    113. 		Node* newnode = new Node(kv);
    114. 		newnode->_next = _table[hashi];
    115. 		_table[hashi] = newnode;
    116. 		++_size;
    117.  
    118. 		return true;
    119. 	}
    120.  
    121. 	Node* Find(const K& key)
    122. 	{
    123. 		//如果表中无数据，直接return
    124. 		if (_table.size() == 0)
    125. 		{
    126. 			return nullptr;
    127. 		}
    128. 		Hash hs;//仿函数
    129. 		//找到要查找数据对应的位置
    130. 		size_t hashi = hs(key) % _table.size();
    131. 		Node* cur = _table[hashi];
    132. 		//在该位置挂起的数据中找
    133. 		while (cur)
    134. 		{
    135. 			if (cur->_kv.first == key)
    136. 			{
    137. 				return cur;
    138. 			}
    139. 			cur = cur->_next;
    140. 		}
    141. 		//如果代码走到这里，说明没找到
    142. 		return nullptr;
    143. 	}
    144.  
    145. 	bool Erase(const K& key)
    146. 	{
    147. 		//如果为空，直接return
    148. 		if (_table.size() == 0)
    149. 		{
    150. 			return nullptr;
    151. 		}
    152. 		Hash hs;//仿函数
    153. 		size_t hashi = hs(key)% _table.size();
    154. 		Node* cur = _table[hashi];
    155. 		Node* prev = nullptr;
    156. 		while (cur)
    157. 		{
    158. 			//如果相等则删除
    159. 			if (cur->_kv.first == key)
    160. 			{
    161. 				//删除的是_table[hashi]的头结点
    162. 				if (prev == nullptr)
    163. 				{
    164. 					_table[hashi] = cur->_next;
    165. 				}
    166. 				//删除的是_table[hashi]的中间结点
    167. 				else
    168. 				{
    169. 					prev->_next = cur->_next;
    170. 				}
    171. 				delete cur;
    172. 				--_size;	
    173.  
    174. 				return true;
    175. 			}
    176. 			prev = cur;
    177. 			cur = cur->_next;
    178. 		}
    179. 		//代码运行到这里，说明没有找到
    180. 		return false;
    181. 	}
    182.  
    183. private:
    184. 	vector _table;
    185. 	size_t _size = 0;//存储的有效数据个数	
    186. };
    187.  
    188. //测试insert和Erase
    189. void test()
    190. {
    191. 	int a[] = { 1,11,4,15,26,7,44,55,88,99 };
    192. 	HashTable<int, int> ht;
    193.  
    194. 	for (auto e : a)
    195. 	{
    196. 		ht.Insert(make_pair(e,e));
    197. 	}
    198.  
    199. 	ht.Insert(make_pair(22, 22));
    200.  
    201. 	ht.Erase(44);
    202. 	ht.Erase(4);
    203. }

    三、哈希封装unordered_set/map

    这里使用的是开散列哈希桶的方式封装

    上面实现的哈希桶，默认就是pair，而我们想要使用哈希表去封装unordered_set和unordered_map，需要两个都满足，所以需要做以改变：

    将上面模拟实现的哈希桶中显示为pair类型的数值，都变为T类型，这样在需要K类型时传K，需要pair类型时传pair即可

    下面是哈希表改变后的代码，具体有注释解释：

    1、哈希表改变后的代码

    1. //这个是正常能取模的数据调用的
    2. template<class K>
    3. struct HashUsual
    4. {
    5. 	size_t operator()(const K& key)
    6. 	{
    7. 		return (size_t)key;
    8. 	}
    9. };
    10.  
    11. //有些数据不能直接取模，例如string，需要自己写仿函数
    12. //也可以不主动调用，特化处理
    13. template<>
    14. struct HashUsual
    15. {
    16. 	//string类型的就返回所有字符的ascll码
    17. 	size_t operator()(const string& key)
    18. 	{
    19. 		//BKDR法
    20. 		size_t val = 0;
    21. 		for (auto& e : key)
    22. 		{
    23. 			val *= 131;
    24. 			val += e;
    25. 		}
    26.  
    27. 		return val;
    28. 	}
    29. };
    30.  
    31. //改造后的HashNode模版变为T
    32. //因为不确定是K还是pair类型的
    33. template<class T>
    34. struct HashNode
    35. {
    36. 	T _data;
    37. 	HashNode* _next;
    38.  
    39. 	HashNode(const T& data)
    40. 		:_data(data)
    41. 		, _next(nullptr)
    42. 	{}
    43. };
    44.  
    45. //前置声明，因为迭代器中要使用HashTable
    46. template<class K, class T, class Hash, class KeyOfT>
    47. class HashTable;
    48.  
    49. //迭代器
    50. template<class K, class T, class Hash, class KeyOfT>
    51. struct __HashIterator
    52. {
    53. 	typedef HashNode Node;
    54. 	typedef HashTable HT;
    55. 	typedef __HashIterator self;
    56.  
    57. 	//有两个成员变量
    58. 	//_node是结点指针
    59. 	//_pht是哈希表
    60. 	Node* _node;
    61. 	HT* _pht;
    62.  
    63. 	__HashIterator(Node* node, HT* pht)
    64. 		:_node(node)
    65. 		, _pht(pht)
    66. 	{}
    67.  
    68. 	T& operator*()
    69. 	{
    70. 		return _node->_data;
    71. 	}
    72.  
    73. 	T* operator->()
    74. 	{
    75. 		return &_node->_data;
    76. 	}
    77.  
    78. 	self& operator++()
    79. 	{
    80. 		//当前桶不为空，在当前桶迭代
    81. 		if (_node->_next)
    82. 		{
    83. 			_node = _node->_next;
    84. 		}
    85. 		//当前桶为空，找下一个不为空的桶
    86. 		else
    87. 		{
    88. 			Hash hs;
    89. 			KeyOfT kot;
    90. 			//i就是当前桶所对应的下标
    91. 			size_t i = hs(kot(_node->_data)) % _pht->_table.size();
    92. 			++i;
    93. 			for (; i < _pht->_table.size(); ++i)
    94. 			{
    95. 				if (_pht->_table[i])
    96. 				{
    97. 					_node = _pht->_table[i];
    98. 					break;
    99. 				}
    100. 			}
    101. 			//走到这说明后面没有有数据的桶了
    102. 			if (i == _pht->_table.size())
    103. 			{
    104. 				_node = nullptr;
    105. 			}
    106. 		}
    107.  
    108. 		return *this;
    109. 	}
    110.  
    111. 	bool operator!=(const self& s) const
    112. 	{
    113. 		return _node != s._node;
    114. 	}
    115.  
    116. 	bool operator==(const self& s) const
    117. 	{
    118. 		return _node == s._node;
    119. 	}
    120. };
    121.  
    122.  
    123. template<class K, class T, class Hash, class KeyOfT>
    124. class HashTable
    125. {
    126. 	typedef HashNode Node;
    127. 	//迭代器中包含了哈希表_table
    128. 	//所以想使用_table就要做哈希表的友元
    129. 	template<class K, class T, class Hash, class KeyOfT>
    130. 	friend struct __HashIterator;
    131. public:
    132. 	typedef __HashIterator iterator;
    133.  
    134. 	iterator begin()
    135. 	{
    136. 		//找到第一个桶的位置
    137. 		for (size_t i = 0; i < _table.size(); ++i)
    138. 		{
    139. 			if (_table[i])
    140. 			{
    141. 				return iterator(_table[i], this);
    142. 			}
    143. 		}
    144. 		return end();
    145. 	}
    146. 	  
    147. 	iterator end()
    148. 	{
    149. 		return iterator(nullptr, this);
    150. 	}
    151. 	//析构，释放哈希桶
    152. 	~HashTable()
    153. 	{
    154. 		for (size_t i = 0; i < _table.size(); ++i)
    155. 		{
    156. 			Node* cur = _table[i];
    157. 			while (cur)
    158. 			{
    159. 				//记录cur的next
    160. 				Node* next = cur->_next;
    161. 				delete cur;
    162. 				cur = next;
    163. 			}
    164. 			//置空
    165. 			_table[i] = nullptr;
    166. 		}
    167. 	}
    168.  
    169. 	pairbool> Insert(const T& data)
    170. 	{
    171. 		Hash hs;//仿函数
    172. 		KeyOfT kot;
    173.  
    174. 		iterator ret = Find(kot(data));
    175. 		//去重
    176. 		if (ret != end())
    177. 		{
    178. 			return make_pair(ret, false);
    179. 		}
    180.  
    181. 		//负载因子到1就扩容
    182. 		if (_size == _table.size())
    183. 		{
    184. 			size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
    185. 			vector newtable;
    186. 			newtable.resize(newsize, nullptr);
    187.  
    188. 			//旧表结点映射到新表
    189. 			//这里需要注意的是：扩容采用的是将旧表的指针迁移到新表
    190. 			//而学习的闭散列模拟实现是复用insert
    191. 			//之所以这里不复用insert，是因为insert会new新结点   
    192. 			//如果每次都new，然后将旧表的结点再释放，相当于旧表结点没有派上用处
    193. 			//所以直接迁移旧表指针，能更好利用旧表的指针，提高效率
    194. 			for (size_t i = 0; i < _table.size(); ++i)
    195. 			{
    196. 				Node* cur = _table[i];
    197. 				while (cur)
    198. 				{
    199. 					//提前保存cur的next，下面会改变next，不然会找不到
    200. 					Node* next = cur->_next;
    201.  
    202. 					size_t hashi = hs(kot(cur->_data)) % newtable.size();
    203. 					//头插：插入结点的next指向新表结点的第一个
    204. 					//插入结点作为新表结点的第一个
    205. 					cur->_next = newtable[hashi];
    206. 					newtable[hashi] = cur;
    207.  
    208. 					cur = next;
    209. 				}
    210. 				_table[i] = nullptr;
    211. 			}
    212. 			//交换_table与newtable,便于运行结束自动删除_table
    213. 			_table.swap(newtable);
    214. 		}
    215.  
    216.  
    217. 		size_t hashi = hs(kot(data)) % _table.size();
    218. 		//头插
    219. 		Node* newnode = new Node(data);
    220. 		newnode->_next = _table[hashi];
    221. 		_table[hashi] = newnode;
    222. 		++_size;
    223.  
    224. 		return make_pair(iterator(newnode, this), true);
    225. 	}
    226.  
    227. 	iterator Find(const K& key)
    228. 	{
    229. 		//如果表中无数据，直接return
    230. 		if (_table.size() == 0)
    231. 		{
    232. 			return end();
    233. 		}
    234. 		Hash hs;//仿函数
    235. 		KeyOfT kot;
    236. 		//找到要查找数据对应的位置
    237. 		size_t hashi = hs(key) % _table.size();
    238. 		Node* cur = _table[hashi];
    239. 		//在该位置挂起的数据中找
    240. 		while (cur)
    241. 		{
    242. 			if (kot(cur->_data) == key)
    243. 			{
    244. 				return iterator(cur, this);
    245. 			}
    246. 			cur = cur->_next;
    247. 		}
    248. 		//如果代码走到这里，说明没找到
    249. 		return end();
    250. 	}
    251.  
    252. 	bool Erase(const K& key)
    253. 	{
    254. 		//如果为空，直接return
    255. 		if (_table.size() == 0)
    256. 		{
    257. 			return false;
    258. 		}
    259. 		Hash hs;//仿函数
    260. 		KeyOfT kot;
    261. 		size_t hashi = hs(key) % _table.size();
    262. 		Node* cur = _table[hashi];
    263. 		Node* prev = nullptr;
    264. 		while (cur)
    265. 		{
    266. 			//如果相等则删除
    267. 			if (kot(cur->_data) == key)
    268. 			{
    269. 				//删除的是_table[hashi]的头结点
    270. 				if (prev == nullptr)
    271. 				{
    272. 					_table[hashi] = cur->_next;
    273. 				}
    274. 				//删除的是_table[hashi]的中间结点
    275. 				else
    276. 				{
    277. 					prev->_next = cur->_next;
    278. 				}
    279. 				delete cur;
    280. 				--_size;
    281.  
    282. 				return true;
    283. 			}
    284. 			prev = cur;
    285. 			cur = cur->_next;
    286. 		}
    287. 		//代码运行到这里，说明没有找到
    288. 		return false;
    289. 	}
    290.  
    291. private:
    292. 	vector _table;
    293. 	size_t _size = 0;//存储的有效数据个数	
    294. };

    2、unordered_set的实现

    1. #pragma once
    2.  
    3. #include "Hashtable.h"
    4.  
    5. namespace fcy
    6. {
    7. 	template<class K, class Hash = HashUsual>
    8. 	class unordered_set
    9. 	{
    10. 		//set创建SetKeyOfT是为了跟map统一路径
    11. 		struct SetKeyOfT
    12. 		{
    13. 			const K& operator()(const K& key)
    14. 			{
    15. 				return key;
    16. 			}
    17. 		};
    18. 	public:
    19. 		//当typedef类模版里面的内嵌类型时，需要加typename
    20. 		typedef typename HashTable::iterator iterator;
    21.  
    22. 		iterator begin()
    23. 		{
    24. 			return _ht.begin();
    25. 		}
    26.  
    27. 		iterator end()
    28. 		{
    29. 			return _ht.end();
    30. 		}
    31.  
    32. 		pairbool> insert(const K& key)
    33. 		{
    34. 			return _ht.Insert(key);
    35. 		}
    36.  
    37. 	private:
    38. 		HashTable _ht;
    39. 	};
    40.  
    41. 	void test_set()
    42. 	{
    43. 		unordered_set<int> us;
    44. 		us.insert(5);
    45. 		us.insert(7);
    46. 		us.insert(22);
    47. 		us.insert(3);
    48. 		us.insert(1);
    49.  
    50. 		unordered_set<int>::iterator it = us.begin();
    51. 		while (it != us.end())
    52. 		{
    53. 			cout << *it << " ";
    54. 			++it;
    55. 		}
    56. 		cout << endl;
    57. 	}
    58. }

    3、unordered_map的实现

     

    1. #pragma once
    2.  
    3. #include "Hashtable.h"
    4.  
    5. namespace fcy
    6. {
    7. 	template<class K, class V, class Hash = HashUsual>
    8. 	class unordered_map
    9. 	{
    10. 		//map的KeyOfT用于返回pair的first即key值
    11. 		struct MapKeyOfT
    12. 		{
    13. 			const K& operator()(const pair& kv)
    14. 			{
    15. 				return kv.first;
    16. 			}
    17. 		};
    18. 	public:
    19. 		//当typedef类模版里面的内嵌类型时，需要加typename
    20. 		typedef typename HashTable, Hash, MapKeyOfT>::iterator iterator;
    21.  
    22. 		iterator begin()
    23. 		{
    24. 			return _ht.begin();
    25. 		}
    26.  
    27. 		iterator end()
    28. 		{
    29. 			return _ht.end();
    30. 		}
    31.  
    32. 		pairbool> insert(const pair& kv)
    33. 		{
    34. 			return _ht.Insert(kv);
    35. 		}
    36.  
    37. 		V& operator[](const K& key)
    38. 		{
    39. 			pairbool> ret = _ht.Insert(make_pair(key,V()));
    40. 			//ret.first是iterator，再->second才是V
    41. 			return ret.first->second;
    42. 		}
    43.  
    44. 	private:
    45. 		HashTable, Hash, MapKeyOfT> _ht;
    46.  
    47. 	};
    48.  
    49. 	void test_map()
    50. 	{
    51. 		//类似字典的功能
    52. 		unordered_map um;
    53. 		um.insert(make_pair("string", "字符串"));
    54. 		um.insert(make_pair("pen", "钢笔"));
    55. 		um.insert(make_pair("apple", "苹果"));
    56.  
    57. 		unordered_map::iterator it = um.begin();
    58. 		while (it != um.end())
    59. 		{
    60. 			cout << it->first << ":" << it->second << endl;
    61. 			++it;
    62. 		}
    63. 		cout << endl;
    64. 		//统计次数
    65. 		unordered_mapint> count;
    66. 		string arr[] = { "桌子","椅子","筷子","桌子","椅子","桌子" };
    67. 		for (auto e : arr)
    68. 		{
    69. 			count[e]++;
    70. 		}
    71. 		for (auto& m : count)
    72. 		{
    73. 			cout << m.first << ":" << m.second << endl;
    74. 		}
    75.  
    76.  	}
    77. }

    最后这里有个小知识点：

    一个类型K去做set和unordered_set的模版参数分别有哪些要求？

    set：要求支持小于比较，或是显示提供比较的仿函数（因为set底层是红黑树，需要进行大小比较，而只需要小于是因为改变参数位置就可以进行大于比较，而支持小于和大于，也就相当于支持等于比较）

    unordered_set：①K类型的对象可以转换为整型取模，或是提供转成整型的仿函数

    ②K类型的对象可以支持等于比较，或是提供等于比较的仿函数

    （因为unordered_set的底层是哈希表，需要进行取模找到插入数据所对应的是第几个桶，而需要支持等于比较是因为，在找某个数据时，取模找到对应的桶，还需要等于比较才能确定有没有需要找的值）

    四、哈希应用

    位图

    有一道题来引出位图的概念：

    假设给40亿个不重复且未排序的无符号整数，然后给出一个无符号整数，如何快速判断这个数是否在这40亿个数中？

    我们的之前学习过的方法例如：堆、搜索树、哈希这些方法确实搜索的速度很快，但是一个无符号整数4个字节，40亿个无符号整数存储空间得占用160亿个字节即大约14GB左右，这肯定是存不下的，只能存在磁盘中，而磁盘查找又很麻烦，效率非常低，所以之前学习的方法是没有办法解决的 

    这里就引入位图的概念，在给的这40亿个无符号整数，给定的一个无符号整数只会有两种状态，在或者不在，那么就可以使用二进制的比特位0/1存储(1表示在，0表示不在)

    因为1GB = 1024MB = 1024 * 1024KB = 1024 * 1024 * 1024 byte约等于10亿，所以40亿字节相当于4GB，而40亿大约是2^32，现在使用位图用的是40亿个比特位，一个byte = 8个比特位，所以位图占用的空间就是4GB / 8 约等于512MB，对比上面所占的空间，可以说是非常小了，效率也很快

    而通过上面的例子，就可以得知，位图就是用每一位来存在某种状态，是用于非常大的数据，且数据无重复的情况，通常是判断某个数据存不存在

    而这2^32比特位我们应该怎么开辟呢，就开辟每个元素是char类型的数组即可，一个char是8个比特位，所以就相当于每8个比特位用一个char存储，即0~7位存储在第一个char，8~15存储在第二个char，以此类推

    这时我们通过/8和%8就分别可以得知在第几个char与在这个char的第几个比特位

    例如前两个char表示的比特位分别是0~7和8~15，那么假设数字10，10 / 8 == 1，10 % 8 == 2，所以数字10就在第一个char的第二个比特位上（注意是从0开始的），如下所示：

    而不论是多少数据，并不是说题目给10亿数据，我们就开10亿个比特位大小的空间，而是不论是10亿，50亿，90亿，我们都开整数的最大值，即42亿9千万多，因为给出的数据是无序的，不能保证数据的大小

    所以开辟时可以有下面的方式：

    bit_set<-1>：可以传-1，是因为位图的非类型模板参数是size_t类型的，即无符号整型，-1表示的就是整型的最大值

    bit_set<0xffffffff>：0xffffffff是用8个16进制位表示的，1个16进制位等于4个2进制位，所以8个16进制位都是f，就表示二进制位都为1，也是整型的最大值

    我们上面也计算了开辟整型的最大值也就是42亿多比特位，算下来就是512MB左右，下面可以看看实际的情况是不是我们所说的那样：

    先用上面的方法创建整型最大值个比特位，然后打断点调试：

    这时打开我们的Windows任务管理器，发现此时运行的这个进程所占内存是0.5MB：

    接下来我们按F10，创建这个bs变量即开辟好整型的最大值个比特位的空间（箭头表示已经走到的位置，说明创建完成了）：

    这时再打开任务管理器：

    可以清楚看到此时该进程所占用的内存变为了512MB

    位图的特点

    1、快，且节省空间（512MB左右）

    2、比较局限，只能映射整型（因为对应比特位的下标都是整数）

    位图是直接定址法，不存在冲突

    位图的模拟实现

    bitset是C++库中的容器，我们只实现了最核心的三个接口：set、reset、test

    set：将一个数对应的比特位变为1

    reset：将一个数对应的比特位变为0

    test：测试一个数存在不存在

    1. //非类型模板参数
    2. template<size_t N>
    3. class bitset
    4. {
    5. public:
    6. 	bitset()
    7. 	{
    8. 		//每次多开一个char，保证所有数据都能存进入
    9. 		//默认所有位初始化为0
    10. 		_bits.resize(N / 8 + 1, 0);
    11. 	}
    12.  
    13. 	//下面的i都表示在第几个char中的比特位中
    14. 	//下面的j都表示在这个char的第几个比特位上
    15. 	void set(size_t x)
    16. 	{
    17. 		size_t i = x / 8;
    18. 		size_t j = x % 8;
    19. 		//算出的比特位按位与1，该位置就为1了
    20. 		_bits[i] |= (1 << j);
    21. 	}
    22.  
    23. 	void reset(size_t x)
    24. 	{
    25. 		size_t i = x / 8;
    26. 		size_t j = x % 8;
    27. 		//~是按位取反，每一位都0变1,1变0
    28. 		_bits[i] &= ~(1 << j);
    29. 	}
    30.  
    31. 	bool test(size_t x)
    32. 	{
    33. 		size_t i = x / 8;
    34. 		size_t j = x % 8;
    35.  
    36. 		return _bits[i] & (1 << j);
    37. 	}
    38. private:
    39. 	vector<char> _bits;
    40. };
    41.  
    42. void test_bitset()
    43. {
    44. 	bitset<-1> bs;
    45. }

    布隆过滤器

    上面所说的位图只能处理整数，而如果是其他类型的例如字符串之类的就不能处理了，所以这里引入了布隆过滤器

    布隆过滤器设计思路：就是将字符串使用字符串哈希算法转换成整型，然后去映射一个位置进行标记

    但是这样实现，会造成误判的情况，比如说有两个字符串完全不同，但是使用字符串哈希算法转换成的整型数值却是一样的，从而造成误判

    而误判只会存在于在的情况，因为有一个字符串映射到a位置，而另一个字符串本身没有出现，但是经过算法算出来的值与上一个字符串相同，这时这个字符串存在的情况就会出现误判

    而字符串不存在的情况是不会有误判的情况出现的，因为如果该位置映射的值为0，那么就说明肯定没有对应该位置的字符串出现，所以也就不存在误判的事情了

    对于上面误判的情况，我们可以加以改进，可以将一个字符串多映射几个位置，这样就可以有效降低误判率，因为一个字符串所映射的一个位置和另一个字符串映射的位置重复了，那再与该字符串映射的其他位置同样重复的情况的可能性就很小了，所以可以有效降低误判率

    我们知道：一个值映射的位越多，误判的概率就越低，但是映射的位如果太多，那么空间的消耗也就会越多

    我们一般选择映射3个位置

    而布隆过滤器的使用场景如果允许误判的情况，例如游戏中给角色起名时，将已经存在的名称存在布隆过滤器中，这样新用户起名时，如果存在，告知用户存在，如果不存在，就起名成功，效率是非常高的

    而如果有场景不允许存在误判，那么就多一个步骤，如果存在布隆过滤器中，就去数据库中查找，确认在或不在，而如果不在布隆过滤器中，那就肯定不在，就不需要再去数据库中查找，也可以有效的提高效率

    布隆过滤器的模拟实现

    1. //N表示映射N个值，Hash1/2/3表示仿函数，即使用三种不同方式映射到不同地址
    2. template<size_t N, class K, class Hash1, class Hash2, class Hash3>
    3. class BloomFilter
    4. {
    5. public:
    6. 	void Set(const K& key)
    7. 	{
    8. 		size_t hash1 = hash1()(key) % _ratio * N;
    9. 		_bits.set(hash1);
    10.  
    11. 		size_t hash2 = hash2()(key) % _ratio * N;
    12. 		_bits.set(hash2);
    13.  
    14. 		size_t hash3 = hash3()(key) % _ratio * N;
    15. 		_bits.set(hash3);
    16. 	}
    17.  
    18. 	void Test(const K& key)
    19. 	{
    20. 		//验证该位置是否存在时，因为一个值映射三个位置
    21. 		//所以不能一个位置满足就当做存在
    22. 		//是需要判断这三个位置是否都不存在
    23. 		//直到三个位置都判断之后才结束，才return true
    24. 		//虽然有误判率，但是误判率也是很小的
    25. 		size_t hash1 = hash1()(key) % (_ratio * N);
    26. 		if (!_bits.set(hash1))
    27. 			return false; //准确判断
    28.  
    29. 		size_t hash2 = hash2()(key) % (_ratio * N);
    30. 		if (!_bits.set(hash2))
    31. 			return false; //准确判断
    32.  
    33. 		size_t hash3 = hash3()(key) % (_ratio * N);
    34. 		if (!_bits.set(hash3))
    35. 			return false; //准确判断
    36.  
    37. 		return true;      //可能误判
    38. 	}
    39. private:
    40. 	//这里的_ratio是使用公式大致算出来，在三个哈希函数时
    41. 	//需要多给大约5个比特位存储
    42. 	//所以N个数据，就开辟_ratio*N个空间
    43. 	const static size_t _ratio = 5;
    44. 	bitset<_ratio* N> _bits;
    45. };

    而关于布隆过滤器的删除操作，也就是reset，是不太建议的，因为一个数据可以对应多个位置，如果有两个数据对应了同一个位置，想删除一个，另一个也就被删除了

    想解决这种问题，只能给每个位置在设置一个值，表示有几个数据映射到这个位置，删除一个数据就--，这样就不会有上面的问题了，但是这样相当于原本每个位置用一个比特位存储，现在每个位置又多了一个字节存储映射该位置的次数，这与布隆过滤器的初衷相违背了，本来布隆过滤器的优势就是空间占用小，效率高，这样空间也变大了，效率也低了，所以一般我们是不考虑删除操作的

  • 相关阅读:
    Java进阶学习各种经典书籍电子版
    Oracle update 关联更新优化方法
    Simulink|电动汽车、永磁电动机建模与仿真
    LabVIEW和NIUSRP硬件加快了认知无线电开发
    【面试】个人宝典 查缺补漏
    【21天学习挑战赛】冒泡排序
    【Vue.js】Vue3全局配置Axios并解决跨域请求问题
    怎么把电脑图片转文字？只需这几步就可以截图转文字
    【剑指offer系列】37. 序列化二叉树
    连续十日票房日冠，《人生大事》带热了电影大盘！它凭何突出重围？
  • 原文地址：https://blog.csdn.net/m0_64411530/article/details/133890484