哈希

在这里插入图片描述

欢迎来到Cefler的博客😁
🕌博客主页：那个传说中的man的主页
🏠个人专栏：题目解析
🌎推荐文章：题目大解析（3）

在这里插入图片描述

👉🏻unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 $log_2 N$ ，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同(unordered系列底层是哈希表)

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_set

unordered_set官方文档：unordered_set

1.无序集合是存储没有特定顺序的唯一元素的容器，它允许基于它们的值快速检索单个元素。

2.在unordered_set中，元素的值同时也是唯一标识它的键。键是不可变的，因此，在容器中不能修改unordered_set中的元素——但是可以插入和删除它们。

3.在内部，unordered_set中的元素没有按照任何特定的顺序排序，而是根据它们的散列值组织到bucket中，以便通过它们的值直接快速访问单个元素(平均时间复杂度为常数)。

4.Unordered_set容器在按键访问单个元素时比set容器快，尽管它们在通过其元素子集进行范围迭代时通常效率较低。

5.容器中的迭代器至少是前向迭代器。

👉🏻哈希概念

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

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

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

插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

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

哈希/散列：映射，关键字和另一个值建立一个关联关系
哈希表/散列表：映射，关键字和存储位置建立一个关联关系

👉🏻哈希函数

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

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

☃️常见的哈希函数有：

直接定址法–(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀，关键字—存储位置是一对一的关系，不存在哈希冲突
缺点：需要事先知道关键字的分布情况
使用场景：关键字范围集中，量不大的情况
除留余数法–(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
其关键字-存储位置是多对一的关系，多个关键字对应一个位置，存在哈希冲突
使用场景：关键字可以很分散，量可以很大

例如该下面这个就是采取除留余数法

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

在这里插入图片描述
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？

👉🏻哈希冲突

🧋 $概念$
对于两个数据元素的关键字 $k_i$ 和 $k_j$ (i != j)，有 $k_i$ != $k_j$ ，但有：Hash( $k_i$ ) == Hash( $k_j$ )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
发生哈希冲突该如何处理呢？ 🤔

👉🏻 哈希冲突解决方法

闭散列

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

线性探测

比如刚刚的场景中，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，
因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
线性探测向后找可以表示为：hashi+i(i>=0)

即线性探测的插入和删除表现为：

插入

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

删除

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响，因为我们查找到4时，此时4的位置为空，我们就停下来了不往后找，自然就找不到44了。因此线性探测采用标记的伪删除法(标记状态为DELETE)来删除一个元素。

👉🏻哈希闭散列模拟实现

哈希数据和哈希状态

enum Status
	{
		EMPTY,
		EXIST,
		DELETE

	};
	template <class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		Status _s;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13

返回哈希值的key

1.常规类型返回：如int、double等

template <class  K>
	struct HashFunc
	{
		operator()(const K& key)
		{
			return (size_t)key;
		}
	};
1
2
3
4
5
6
7
8

2.字符串类型返回
这个就不能直接返回字符串，因为字符串是不能用于取余的，但是我们可以将字符串中的每一个字符的ASCII码值全部相加以整型的形式返回即可。
但是我们知道字符串的组合是无数种的，可size_t的值却是有上限的，那么多字符串最终会有很多字符串相加的ASCII码值会相等，这就会发生哈希冲突。对于哈希冲突，我们不可避免，但是在这个基础上，有算法大佬提供了牛逼的算法，可以减少这之间的哈希冲突的产生。
以下是一个著名的BRDK算法
在这里插入图片描述
我们借鉴这个算法进行将字符串转换为整型返回

template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash = hash * 31 + e;
			}
			return hash;
		}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13

我们观察到针对于这两种情况，我们都是采用了模板进行实例化，而字符串类型返回比较特殊这边用了全特化。
有人可能会问，为什么不把写成类的函数重载，而是用模板特化？
答案是这里会出现坑，当我们进行函数重载时，如果传进来的K是string,此时类中就会有两个size_t operator()(const string& key)，发生冲突。
而特化就可以解决这个问题。

哈希插入（含扩容和线性探测）

🌊扩容：

//如果空间不够？
			//负载因子0.7就扩容
			if (_n * 10 / _tables.capacity() == 7)
			{
				//不能原地扩容，因为原地扩容会使映射关系发生变化，比如size(10)->size(20),原本3的位置会变到13去
				//所以我们开辟新空间
				size_t newSize = _tables.size() * 2;
				HashTable<K, V,Hash> newHT;
				newHT._tables.resize(newSize);
				//遍历旧表，将旧表的值插入到新表中
				for (int i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._s == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				//最后旧表变新表
				_tables.swap(newHT._tables);

			}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

🌊线性探测:

Hash hf;//HashFunc
			size_t hashi = hf(kv.first) % _tables.size();//size_t可以解决负数问题，负数隐式类型转换为无符号
			while (_tables[hashi]._s== EXIST) {
			  //存在则找下一个空位置
				hashi++;

				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIST;
			++_n;
			return true;
1
2
3
4
5
6
7
8
9
10
11
12

整体插入代码：

bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			//如果空间不够？
			//负载因子0.7就扩容
			if (_n * 10 / _tables.capacity() == 7)
			{
				//不能原地扩容，因为原地扩容会使映射关系发生变化，比如size(10)->size(20),原本3的位置会变到13去
				//所以我们开辟新空间
				size_t newSize = _tables.size() * 2;
				HashTable<K, V，Hash> newHT;
				newHT._tables.resize(newSize);
				//遍历旧表，将旧表的值插入到新表中
				for (int i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._s == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				//最后旧表变新表
				_tables.swap(newHT._tables);

			}
			//线性探测
			Hash hf;//HashFunc
			size_t hashi = hf(kv.first) % _tables.size();//size_t可以解决负数问题，负数隐式类型转换为无符号
			while (_tables[hashi]._s== EXIST) {
			  //存在则找下一个空位置
				hashi++;

				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIST;
			++_n;
			return true;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

哈希查找

//哈希查找
		HashData<K, V>* Find(const K& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s == EXIST && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}
				++hashi;
				hashi %= _tables.size();
			}
			return nullptr;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

哈希的伪删除

伪删除就很简单，直接找到对应的位置，将该位置的状态改为DELETE,然后_n减一即可。

//伪删除
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_s = DELETE;
				_n--;
				return true;
			}
			else
				return false;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13

哈希打印

//打印
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)
				{
					//printf("[%d]->%d\n", i, _tables[i]._kv.first);
					cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;
				}
				else if (_tables[i]._s == EMPTY)
				{
					printf("[%d]->\n", i);
				}
				else
				{
					printf("[%d]->D\n", i);
				}
			}

			cout << endl;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

哈希闭散列完整代码附测试代码

#pragma once
#include
#include
using namespace std;
namespace close_address
{
	enum Status
	{
		EMPTY,
		EXIST,
		DELETE

	};
	template <class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		Status _s;
	};
	//返回哈希的key
	//1.常规类型
	template <class  K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	//2.字符串转换为整型返回
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash = hash * 31 + e;
			}
			return hash;
		}
	};
	template <class K,class V,class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);//一开始扩容为10
		}
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			//如果空间不够？
			//负载因子0.7就扩容
			if (_n * 10 / _tables.capacity() == 7)
			{
				//不能原地扩容，因为原地扩容会使映射关系发生变化，比如size(10)->size(20),原本3的位置会变到13去
				//所以我们开辟新空间
				size_t newSize = _tables.size() * 2;
				HashTable<K, V,Hash> newHT;
				newHT._tables.resize(newSize);
				//遍历旧表，将旧表的值插入到新表中
				for (int i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._s == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				//最后旧表变新表
				_tables.swap(newHT._tables);

			}
			//线性探测
			Hash hf;//HashFunc
			size_t hashi = hf(kv.first) % _tables.size();//size_t可以解决负数问题，负数隐式类型转换为无符号
			while (_tables[hashi]._s== EXIST) {
			  //存在则找下一个空位置
				hashi++;

				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIST;
			++_n;
			return true;
		}

		//哈希查找
		HashData<K, V>* Find(const K& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s == EXIST && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}
				++hashi;
				hashi %= _tables.size();
			}
			return nullptr;
		}
		//伪删除
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_s = DELETE;
				_n--;
				return true;
			}
			else
				return false;
		}
		//打印
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)
				{
					//printf("[%d]->%d\n", i, _tables[i]._kv.first);
					cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;
				}
				else if (_tables[i]._s == EMPTY)
				{
					printf("[%d]->\n", i);
				}
				else
				{
					printf("[%d]->D\n", i);
				}
			}

			cout << endl;
		}
	private:
		vector<HashData<K,V>> _tables;
		size_t _n = 0;//存储关键字的个数
	};
	void TestHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 4,14,24,34,5,7,1 };
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}

		ht.Print();
	}
	void TestHT2()
	{
		string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		//HashTable ht;
		HashTable<string, int> ht;
		for (auto& e : arr)
		{
			//auto ret = ht.Find(e);
			HashData<string, int>* ret = ht.Find(e);
			if (ret)
			{
				ret->_kv.second++;
			}
			else
			{
				ht.Insert(make_pair(e, 1));
			}
		}

		ht.Print();

		ht.Insert(make_pair("apple", 1));
		ht.Insert(make_pair("sort", 1));

		ht.Insert(make_pair("abc", 1));
		ht.Insert(make_pair("acb", 1));
		ht.Insert(make_pair("aad", 1));

		ht.Print();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

👉🏻哈希开散列（哈希桶）模拟实现

概念

开放寻址法（Open Addressing）是一种解决哈希冲突的方法。在开放寻址法中，当发生冲突时，会通过一定的探测序列（如线性探测、二次探测等）在哈希表中的其他位置继续寻找空闲槽来存储冲突的元素。

而开散列（Open Hashing），也被称为链地址法（Chaining），是另一种解决哈希冲突的方法。在开散列中，具有相同地
址的关键码归于同一子集合，每一个子集合称为一个桶，当发生哈希冲突时，冲突的元素会被链接成一个链表或其他数据结构存储在同一个桶中。

在这里插入图片描述

哈希节点

template<class K,class V>
	struct HashNode
	{
		HashNode<K, V>* _next;
		pair<K, V> _kv;

		HashNode(const HashNode<K,V>& kv)
			:_kv(kv._kv)
			,_next(nullptr)
		{}

	};
1
2
3
4
5
6
7
8
9
10
11
12

哈希插入（含扩容）

bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			//扩容，这里负载因子可以最大到1
			if (_n == _tables.size())
			{
				size_t newSize() = _tables.size() * 2;
				HashTable<K,V> newHT;
				newHT._tables.resize(newSize);
				//遍历旧表，插入新表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						newHT.Insert(cur->_kv);
						cur = cur->_next;
					}
				}
				_tables.swap(newHT._tables);
			
			}
			//插入的新节点头插
			Hash hf;
			size_t hashi = hf(kv.first) % _tables.size();
			Node* newnode = new Node(kv);

			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			_n++;
			return true;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

扩容方法2：

if (_n == _tables.size())
			{
			

				vector<Node*> newTables;
				newTables.resize(_tables.size() * 2, nullptr);
				// 遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while(cur)
					{
						Node* next = cur->_next;

						// 挪动到映射的新表
						size_t hashi = hf(cur->_kv.first) % newTables.size();
						cur->_next = newTables[i];
						newTables[i] = cur;

						cur = next;
					}

					_tables[i] = nullptr;
				}

				_tables.swap(newTables);
			}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

析构函数

~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

返回哈希值的key

//返回哈希的key
	//1.常规类型
	template <class  K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	//2.字符串转换为整型返回
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash = hash * 31 + e;
			}
			return hash;
		}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

哈希查找

//哈希查找
		Node* Find(const K& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_next == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

哈希删除

//哈希删除
		bool Erase(const K& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true ;
				}
				prev = cur;
				cur = cur->_next;
				
			}
			return false;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

显示哈希的一些情况（桶的数量、长度等）

void Some()
		{
			size_t bucketSize = 0;
			size_t maxBucketLen = 0;
			size_t sum = 0;
			double averageBucketLen = 0;

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					++bucketSize;
				}

				size_t bucketLen = 0;
				while (cur)
				{
					++bucketLen;
					cur = cur->_next;
				}

				sum += bucketLen;

				if (bucketLen > maxBucketLen)
				{
					maxBucketLen = bucketLen;
				}
			}

			averageBucketLen = (double)sum / (double)bucketSize;

			printf("all bucketSize:%d\n", _tables.size());
			printf("bucketSize:%d\n", bucketSize);
			printf("maxBucketLen:%d\n", maxBucketLen);
			printf("averageBucketLen:%lf\n\n", averageBucketLen);
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

哈希开散列完整代码附测试代码

#pragma once
#include
#include
#include
#include
using namespace std;
namespace hash_bucket
{
	template<class K,class V>
	struct HashNode
	{
		HashNode<K, V>* _next;
		pair<K, V> _kv;

		HashNode(const pair<K,V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}

	};
	//返回哈希的key
	//1.常规类型
	template <class  K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	//2.字符串转换为整型返回
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash = hash * 31 + e;
			}
			return hash;
		}
	};
	template<class K,class V,class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		typedef HashNode<K, V> Node;
		HashTable()
		{
			_tables.resize(10);
		}
		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}
		
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			//扩容，这里负载因子可以最大到1
			if (_n == _tables.size())
			{
				size_t newSize = _tables.size() * 2;
				HashTable<K,V> newHT;
				newHT._tables.resize(newSize);
				//遍历旧表，插入新表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						newHT.Insert(cur->_kv);
						cur = cur->_next;
					}
				}
				_tables.swap(newHT._tables);
			
			}
			//插入的新节点头插
			Hash hf;
			size_t hashi = hf(kv.first) % _tables.size();
			Node* newnode = new Node(kv);

			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			_n++;
			return true;
		}
		//哈希查找
		Node* Find(const K& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
		//哈希删除
		bool Erase(const K& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true ;
				}
				prev = cur;
				cur = cur->_next;
				
			}
			return false;
		}
		void Some()
		{
			size_t bucketSize = 0;
			size_t maxBucketLen = 0;
			size_t sum = 0;
			double averageBucketLen = 0;

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					++bucketSize;
				}

				size_t bucketLen = 0;
				while (cur)
				{
					++bucketLen;
					cur = cur->_next;
				}

				sum += bucketLen;

				if (bucketLen > maxBucketLen)
				{
					maxBucketLen = bucketLen;
				}
			}

			averageBucketLen = (double)sum / (double)bucketSize;

			printf("all bucketSize:%d\n", _tables.size());
			printf("bucketSize:%d\n", bucketSize);
			printf("maxBucketLen:%d\n", maxBucketLen);
			printf("averageBucketLen:%lf\n\n", averageBucketLen);
		}
	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};
	void TestHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 4,14,24,34,5,7,1,15,25,3 };
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}

		ht.Insert(make_pair(13, 13));

		cout << ht.Find(4) << endl;
		ht.Erase(4);
		cout << ht.Find(4) << endl;


	}
	void TestHT2()
	{
		string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		HashTable<string, int> ht;
		for (auto& e : arr)
		{
			//auto ret = ht.Find(e);
			HashNode<string, int>* ret = ht.Find(e);
			if (ret)
			{
				ret->_kv.second++;
			}
			else
			{
				ht.Insert(make_pair(e, 1));
			}
		}
	}
	//测试效率
	void TestHT3()
	{
		const size_t N = 10000;

		unordered_set<int> us;
		set<int> s;
		HashTable<int, int> ht;

		vector<int> v;
		v.reserve(N);
		srand(time(0));
		for (size_t i = 0; i < N; ++i)
		{
			//v.push_back(rand()); // N比较大时，重复值比较多
			v.push_back(rand() + i); // 重复值相对少
			//v.push_back(i); // 没有重复，有序
		}

		// 21:15
		size_t begin1 = clock();
		for (auto e : v)
		{
			s.insert(e);
		}
		size_t end1 = clock();
		cout << "set insert:" << end1 - begin1 << endl;

		size_t begin2 = clock();
		for (auto e : v)
		{
			us.insert(e);
		}
		size_t end2 = clock();
		cout << "unordered_set insert:" << end2 - begin2 << endl;

		size_t begin10 = clock();
		for (auto e : v)
		{
			ht.Insert(make_pair(e, e));
		}
		size_t end10 = clock();
		cout << "HashTbale insert:" << end10 - begin10 << endl << endl;


		size_t begin3 = clock();
		for (auto e : v)
		{
			s.find(e);
		}
		size_t end3 = clock();
		cout << "set find:" << end3 - begin3 << endl;

		size_t begin4 = clock();
		for (auto e : v)
		{
			us.find(e);
		}
		size_t end4 = clock();
		cout << "unordered_set find:" << end4 - begin4 << endl;

		size_t begin11 = clock();
		for (auto e : v)
		{
			ht.Find(e);
		}
		size_t end11 = clock();
		cout << "HashTable find:" << end11 - begin11 << endl << endl;

		cout << "插入数据个数：" << us.size() << endl << endl;
		ht.Some();

		size_t begin5 = clock();
		for (auto e : v)
		{
			s.erase(e);
		}
		size_t end5 = clock();
		cout << "set erase:" << end5 - begin5 << endl;

		size_t begin6 = clock();
		for (auto e : v)
		{
			us.erase(e);
		}
		size_t end6 = clock();
		cout << "unordered_set erase:" << end6 - begin6 << endl;

		size_t begin12 = clock();
		for (auto e : v)
		{
			ht.Erase(e);
		}
		size_t end12 = clock();
		cout << "HashTable Erase:" << end12 - begin12 << endl << endl;
	}
	//结果HashTable尽显优势
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319

如上便是本期的所有内容了，如果喜欢并觉得有帮助的话，希望可以博个点赞+收藏+关注🌹🌹🌹❤️ 🧡 💛,学海无涯苦作舟,愿与君一起共勉成长

在这里插入图片描述

相关阅读:
计算机应用专业，报软考应该选什么？
35 LRU缓存
 yocto stm32mp1集成ros
git 撤销提交撤销暂存区取消操作
 JTS-通过Coordinate点截断几何Geometry
H5自定义属性
 （Note）同比和环比
 [node.js] node.js下载与安装；nodejs模块化介绍；同步与异步区别try-catch捕捉异常；fs模块；path路径模块；http模块
 Django如何配置数据库
 c语言入门---自定义类型：结构体，枚举，联合
原文地址：https://blog.csdn.net/cefler/article/details/134394547

哈希

目录

👉🏻unordered系列关联式容器

unordered_map

unordered_set

👉🏻哈希概念

👉🏻哈希函数

👉🏻哈希冲突

👉🏻 哈希冲突解决方法

闭散列

线性探测

👉🏻哈希闭散列模拟实现

哈希数据和哈希状态

返回哈希值的key

哈希插入（含扩容和线性探测）

哈希查找

哈希的伪删除

哈希打印

哈希闭散列完整代码附测试代码

👉🏻哈希开散列（哈希桶）模拟实现

概念

哈希节点

哈希插入（含扩容）

析构函数

返回哈希值的key

哈希查找

哈希删除

显示哈希的一些情况（桶的数量、长度等）

哈希开散列完整代码附测试代码