【C++】STL --- 哈希

2024-02-27 1098阅读

温馨提示：这篇文章已超过404天没有更新，请注意相关的内容是否还可用！

哈希

一、 unordered 系列关联式容器

1. unordered系列关联式容器
2. unordered_map
3. unordered_set
二、底层结构

1. 哈希概念
2. 哈希冲突
3. 哈希函数
4. 解决哈希冲突

（1）闭散列
（2）开散列
三、封装哈希表

1. 模板参数列表的改造
2. 迭代器
3. HashTable 改造
4. my_unordered_map
5. my_unordered_set
四、哈希的应用

1. 位图

2. 布隆过滤器

一、 unordered 系列关联式容器

1. unordered系列关联式容器

在 C++98 中，STL 提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 O(logN)，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在 C++11 中，STL 又提供了4个 unordered 系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对 unordered_map 和 unordered_set 进行介绍，unordered_multimap 和 unordered_multiset 大家可以查看文档介绍 - - - unordered_multimap / unordered_multiset.

2. unordered_map

在学习 unordered_map 之前，我们可以先看一下关于 unordered_map 的文档介绍：unordered_map.

简单介绍：

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

unordered_map 的接口说明：

unordered_map 的容量接口：

unordered_map 的迭代器：

unordered_map 的元素访问：

unordered_map 的查询：

unordered_map 的修改操作

unordered_map 的桶操作

unordered_map 的简单使用如下，统计水果的个数：

		int main()
		{
			string arr[] = { "香蕉", "哈密瓜","苹果", "西瓜", "橙子", "西瓜", "苹果", "苹果", "西瓜", "橙子", "香蕉", "苹果", "香蕉" };
		
			unordered_map hash;
		
			for (auto& str : arr)
			{
				hash[str]++;
			}
		
			unordered_map::iterator it = hash.begin();
			while (it != hash.end())
			{
				cout first _next)
					{
						_node = _node->_next;
					}
		
					// 当前桶已经走完了，找下一个不为空的桶
					else
					{
						// 走到下一个桶
						++_hashi;
						while (_hashi _tables.size())
						{
							// 如果当前桶不为空，就将当前桶的指针给 _node
							if (_pht->_tables[_hashi])
							{
								_node = _pht->_tables[_hashi];
								break;
							}
							++_hashi;
						}
		
						// 如果遍历完所有桶，说明桶里面全是空，返回 nullptr
						if (_hashi == _pht->_tables.size())
						{
							_node = nullptr;
						}
					}
					return *this;
				}
		
				Ref operator*()
				{
					return _node->_data;
				}
		
				Ptr operator->()
				{
					return &_node->_data;
				}
		
				bool operator!=(const Self& s)
				{
					return _node != s._node;
				}
			};

3. HashTable 改造

			template
			class HashTable
			{
				typedef HashNode Node;
		
				// 让 __Iterator 成为友元
				template
				friend struct __Iterator;
		
			public:
				typedef __Iterator iterator;
				typedef __Iterator const_iterator;
		
				iterator begin()
				{
					for (size_t i = 0; i _next;
							delete cur;
							cur = next;
						}
						_tables[i] = nullptr;
					}
				}
		
				pair Insert(const T& data)
				{
					Hash ht;
					KeyOfT kot;
		
					auto rit = Find(kot(data));
					if (rit !=	end())
						return make_pair(rit, false);
		
					// 扩容
					if (_n == _tables.size())
					{
						vector NewTable(_tables.size() * 2, nullptr);
						//NewTable.resize(_tables.size() * 2, nullptr); // ???
						
						for (size_t i = 0; i _next;
		
								// 挪动到新映射后的新表
								size_t hashi = ht(kot(cur->_data)) % NewTable.size();
								cur->_next = NewTable[hashi];
								NewTable[hashi] = cur;
		
								cur = next;
							}
							_tables[i] = nullptr;
						}
						_tables.swap(NewTable);
					}
		
					size_t hashi = ht(kot(data)) % _tables.size();
					Node* newnode = new Node(data);
		
					// 头插
					newnode->_next = _tables[hashi];
					_tables[hashi] = newnode;
					++_n;
		
					return make_pair(iterator(newnode, this, hashi), true);
				}
		
				iterator Find(const K& key)
				{
					Hash ht;
					KeyOfT kot;
		
					size_t hashi = ht(key) % _tables.size();
					Node* cur = _tables[hashi];
		
					while (cur)
					{
						if (kot(cur->_data) == key)
						{
							return iterator(cur, this, hashi);
						}
						cur = cur->_next;
					}
					return end();
				}
		
				bool Erase(const K& key)
				{
					Hash ht;
					KeyOfT kot;
		
					size_t hashi = ht(kot(key)) % _tables.size();
					Node* prev = nullptr, * cur = _tables[hashi];
					while (cur)
					{
						if (cur->_kv.first == key)
						{
							if (prev == nullptr)
							{
								_tables[hashi] = cur;
							}
							else
							{
								prev->_next = cur->_next;
							}
							delete cur;
							return true;
						}
		
						prev = cur;
						cur = cur->_next;
					}
					return false;
				}
		
			private:
				vector _tables;
				size_t _n = 0;
			};

4. my_unordered_map

			#pragma once
			
			#include "HashTable.h"
			
			
			template
			class my_unordered_map
			{
				struct MapOfKey
				{
					const K& operator()(const pair& kv)
					{
						return kv.first;
					}
				};
			
			public:
				typedef typename hash_bucket::HashTable::iterator iterator;
				typedef typename hash_bucket::HashTable::const_iterator const_iterator;
			
				iterator begin()
				{
					return _ht.begin();
				}
			
				iterator end()
				{
					return _ht.end();
				}
			
				const_iterator begin() const
				{
					return _ht.begin();
				}
			
				const_iterator end() const
				{
					return _ht.end();
				}
			
				pair insert(const pair& kv)
				{
					return _ht.Insert(kv);
				}
			
				const V& operator[](const K& key) const
				{
					pair ret = _ht.Insert(make_pair(key, V()));
					return ret.first->second;
				}
			
				V& operator[](const K& key)
				{
					pair ret = _ht.Insert(make_pair(key, V()));
					return ret.first->second;
				}
			
				iterator find(const K& key)
				{
					return _ht.Find(key);
				}
			
				bool erase(const K& key)
				{
					return _ht.Erase(key);
				}
			
			private:
				hash_bucket::HashTable _ht;
			};

5. my_unordered_set

			#pragma once
			#include "HashTable.h"
			
			
			template
			class my_unordered_set
			{
				struct SetOfKey
				{
					const K& operator()(const K& key)
					{
						return key;
					}
				};
			
			public:
			
				typedef typename hash_bucket::HashTable::const_iterator iterator;
				typedef typename hash_bucket::HashTable::const_iterator const_iterator;
			
				const_iterator begin() const
				{
					return _ht.begin();
				}
			
				const_iterator end() const
				{
					return _ht.end();
				}
			
				pair insert(const K& key)
				{
					auto ret = _ht.Insert(key);
					return pair(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
				}
			
				iterator find(const K& key)
				{
					return _ht.Find(key);
				}
			
				bool erase(const K& key)
				{
					return _ht.Erase(key);
				}
			private:
				hash_bucket::HashTable _ht;
			};

四、哈希的应用

1. 位图

位图概念
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

我们先来看一下下面这道题：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？

首先我们能想到的是遍历一遍，但是这样的时间复杂度是 O(N) ，而且内存也开不出这么大的连续空间去存放这些数；首先每个整型是 4 个 byte，这里需要 40 亿个整型单位，也就是 160 亿个 byte，也就是 14 G 左右，不符合实际情况。

第二种我们能想到的是二分查找，但是二分查找的前提是有序，而排序的代价更大，而且也会同时面临第一种方法的内存问题，也不符合实际。

最后我们可以考虑用一个比特位来标记某一个数是否出现过，这就是最后一个方法解决：位图；也就是每个值映射一个比特位，此时我们只需要 0.5G 左右的内存，如下图所示：

那么我们要怎样计算某一个数在数组中的哪一个整型中呢？因为每个整型 32 个 bit 位，所以我们设某一个数为 x，想要知道它在数组的哪一个整型，可以用 i = x / 32，i 就是 x 在数组中的第 i 整型中。

那么又怎么计算 x 在这个整型的第几位呢？我们可以用 j = x % 32 得到，也就是 x 除以 32 的余数。

下面我们简单实现一下位图，只需要用到简单的位运算即可，代码如下：
```
		template
		class bit_set
		{
		public:
			bit_set()
			{
				_bits.resize(N / 32 + 1, 0);
			}
		
			void set(size_t x)
			{
				size_t i = x / 32;
				size_t j = x % 32;
				_bits[i] |= (1  11
				// 11 -> 不变
				if (_bs1.test(x) == false && _bs2.test(x) == false)
				{
					_bs2.set(x);
				}
				else if (_bs1.test(x) == false && _bs2.test(x) == true)
				{
					_bs1.set(x);
					_bs2.reset(x);
				}
				else if (_bs1.test(x) == true && _bs2.test(x) == false)
				{
					_bs1.set(x);
					_bs2.set(x);
				}
			}
		
			// 打印出出现次数不超过两次的整数
			void Print()
			{
				for (size_t i = 0; i 
```

VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

【C++】STL --- 哈希

哈希

一、 unordered 系列关联式容器

1. unordered系列关联式容器

2. unordered_map

3. HashTable 改造

4. my_unordered_map

5. my_unordered_set

四、哈希的应用

1. 位图

相关阅读

怎么把织梦的模板替换?

dedecms怎么调用特定的栏目文档?

怎么抓包一个网页?

wap怎么封装app?

目录[+]