C++进阶--哈希

哈希概念

哈希（Hash）是一种常见的密码学技术和数据结构，它将任意长度的输入通过散列算法转换成固定长度的输出，这个输出被称为散列值或哈希值。哈希函数是一种单向函数，即从哈希值无法反推出原始输入值。

哈希函数具有以下特点：

1. 唯一性：相同的输入一定会得到相同的输出，保证了相同数据的哈希值是唯一的。
2. 固定长度：不论输入的长度是多少，哈希函数都能生成固定长度的哈希值。
3. 高效性：哈希函数计算速度快，适用于大规模数据的处理。
4. 不可逆性：从哈希值无法推导出输入的原始数据，即使输入数据的微小变化也会导致输出值的巨大变化，保证了数据的安全性和完整性。

哈希冲突

哈希冲突是指在使用哈希函数将数据映射到哈希表存储时，可能会出现两个或多个不同的键被映射到相同的哈希值的情况。由于哈希表的存储空间是有限的，而要存储的数据量可能很大，所以哈希冲突是不可避免的。

哈希冲突可能会导致以下问题：

1. 数据丢失：当两个键被映射到相同的哈希值时，只能存储其中一个键，另一个键的数据可能会丢失。
2. 性能下降：哈希冲突会导致在查找、插入和删除操作时需要进行额外的处理，从而降低了哈希表的性能。

哈希冲突的解决

为了解决哈希冲突，常见的方法有以下四种：

1. 开放定址法：在遇到哈希冲突时，寻找一个新的空闲的哈希地址来存储冲突的元素。常见的开放定址法包括线性探测法、二次探测法和双重散列法等。
2. 链地址法（拉链法）：将哈希表的每个槽（桶）设为链表头节点，每个链表存储哈希值相同的元素。当发生哈希冲突时，冲突的元素会被添加到对应槽的链表中。

开放地址法

线性探测和删除问题

线性探测：当插入一个键值对时，如果发生哈希冲突，线性探测会尝试在哈希表中找到下一个可用的位置来存储冲突的数据。
.
具体而言，线性探测的步骤如下：

1. 当发生哈希冲突时，计算下一个位置，通常使用线性递增的方式，即当前位置加上一个固定的增量。
2. 如果下一个位置为空闲（没有被占用），则将冲突的数据存储在该位置。
3. 如果下一个位置仍然被占用，继续计算下一个位置，直到找到空闲位置或遍历整个哈希表。

删除问题：如果对于一个key值进行删除，直接表示位置为空；那么会对相同哈希值的key值产生影响。
如上面的5与25；通过我们的线性探测：

这样不符合我们的想法；所以这里还需要通过标记的方法，对删除过的key不能直接标记为空；

代码

template<class K>
struct Hashfunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
//特化
template<>
struct Hashfunc<string>
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto a : s)
		{
			hash += a;
			hash *= 31;
		}
		return hash;
	}
};

namespace open_address
{
	enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _data;
		State _state = EMPTY;
	};

	
	template<class K, class V, class Hash = Hashfunc<K>>
	class HashTable
	{
	public:
		HashTable(size_t size = 10)
		{
			_tables.resize(size);
		}
		HashData<K, V>* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (key == _tables[hashi]._data.first && _tables[hashi]._state == EXIST)
				{
					return &_tables[hashi];
				}
				hashi++;
				hashi %= _tables.size();
			}
			return nullptr;
		}
		bool Insert(const pair<K, V>& data)
		{
			//保证不能有相同的元素
			if (Find(data.first))
				return false;
			//扩容
			if (_n * 10 / _tables.size() >= 7)
			{
				HashTable<K, V> newHT(_tables.size() * 2);
				for (auto& a : _tables)
				{
					if (a._state == EXIST)
					{
						newHT.Insert(a._data);
					}
				}
				_tables.swap(newHT._tables);
			}
			Hash hs;
			//线性探测
			size_t hashi = hs(data.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)
			{
				hashi++;
				hashi %= _tables.size();
			}

			_tables[hashi]._data = data;
			_tables[hashi]._state = EXIST;
			_n++;

			return true;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				_n--;
				ret->_state = DELETE;
				return true;
			}
			else
			{
				return false;
			}
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0; //实际存储的数据个数
	};

	void TestHT1()
	{
		int a[] = { 1,5,25,35,7,44,17,37 };
		HashTable<int, int> ht;
		//插入到哈希表
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}
		//遍历和打印状态
		for (auto e : a)
		{
			auto ret = ht.Find(e);
			if (ret)
			{
				cout << ret->_data.first << ":Exist" << endl;
			}
			else
			{
				cout << ret->_data.first << ":Delete" << endl;
			}
		}
		cout << endl;

		ht.Erase(44);
		ht.Erase(25);
		for (auto e : a)
		{
			auto ret = ht.Find(e);
			if (ret)
			{
				cout << ret->_data.first << ":Exist" << endl;
			}
			else
			{
				cout << e << ":Delete" << endl;
			}
		}
		cout << endl;
	}

	struct Date
	{
		int _year;
		int _month;
		int _day;
	};

	struct HashFuncDate
	{
		size_t operator()(const Date& d)
		{
			size_t hash = 0;
			hash += d._year;
			hash *= 31;

			hash += d._month;
			hash *= 31;

			hash += d._day;
			hash *= 31;
			return hash;
		}
	};

	struct Person
	{
		string _name;
		string _id;
		string _tel;
		int _age;
		string _class;
		string _address;
	};
	struct HashFuncPerson
	{
		size_t operator()(const Person& p)
		{
			size_t hash = 0;
			for (auto e : p._id)
			{
				hash += e;
				hash *= 31;
			}
			return hash;
		}
	};
	void TestHT2()
	{
		HashTable<string, string> ht;
		ht.Insert(make_pair("length", "长度"));
		ht.Insert(make_pair("data", "数据"));

		HashTable<Person, int, HashFuncPerson> ht1;
		HashTable<Date, string, HashFuncDate> ht2;
	}
}
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

解释

负载因子：负载因子（load factor）是指哈希表中已经存储的元素数量与哈希表容量之比。它可以用来衡量哈希表的填充程度。一般情况下，负载因子越高，表示哈希表中已经存储的元素越多，哈希冲突的概率可能会增加，因此需要进行扩容操作来降低冲突。
.
负载因子通常用一个小数来表示，例如0.75表示哈希表已经存储的元素数量占总容量的75%。负载因子的取值范围通常是0到1之间。
.
具体计算哈希表的负载因子可以根据实际情况来决定。一般来说，当负载因子超过一定阈值（如0.75），就需要考虑进行哈希表的扩容操作，以保持哈希表的性能和效率。
.
记住，哈希表的负载因子并非越高越好。过高的负载因子可能会导致哈希冲突增加，从而影响哈希表的效率；过低的负载因子可能会存在哈希的底层空间过大，插入的key值远低于底层空间大小，这样会浪费不必要的空间。因此，在设计哈希表时，需要根据实际情况选择合适的负载因子阈值，以平衡空间利用率和性能要求。

测试1：


测试2：

对于Date和Person：

链地址法

代码

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

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

	template<class K,class V,class Hash=Hashfunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_tables.resize(10, nullptr);
			_n = 0;
		}

		~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;
			}
		}

		Node* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}

				cur = cur->_next;
			}

			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			//查找是否有相同元素
			if (Find(kv.first))
				return false;

			Hash hs;
			//扩容
			if (_n == _tables.size())
			{
				vector<Node*> newTables(_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 = hs(cur->_kv.first) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}	

			size_t hashi = hs(kv.first) % _tables.size();
			Node* newnode = new Node(kv);

			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			++_n;
			return true;
		}

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first==key)
				{
					if (prev)
					{
						prev->_next = cur->_next;
					}
					else
					{
						_tables[hashi] = cur->_next;
					}
					delete cur;
					_n--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					
					cout << "哈希值：" << i << "--" << "data:" << cur->_kv.first << endl;
					cur = cur->_next;
				}
			}
		}

		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("load factor:%lf\n", (double)_n / _tables.size());//负载因子
			printf("哈希桶数:%d\n", _tables.size());
			printf("节点总数:%d\n", bucketSize);
			printf("最大哈希桶高度:%d\n", maxBucketLen);
			printf("平均哈希桶高度:%lf\n\n", averageBucketLen);
		}
	private:
		vector<Node*> _tables;
		size_t _n;
	};

	void TestHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 1,4,24,34,7,44,17,37 };
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}

		//插入测试打印
		ht.Print();
		cout << endl;
		//扩容后查看对应的哈希值
		ht.Insert(make_pair(5, 5));
		ht.Insert(make_pair(15, 15));
		ht.Insert(make_pair(25, 25));
		ht.Print();
		cout << endl;
		//删除测试
		ht.Erase(5);
		ht.Erase(15);
		ht.Erase(25);
		ht.Erase(35);

		ht.Print();
	}

	void TestHT2()
	{
		const size_t N = 100000;

		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); // 没有重复，有序
		}

		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;
	}
}
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

解释

测试：

性能测试