[C++] 哈希详解_c++哈希介绍

1. 哈希概念

  哈希是一种高效用来搜索的数据结构，与传统的查找方式进行比较，发现传统的方式都需要进行元素的比较，性能高低取决于元素的比较次数。让元素在查找时不进行比较，或者减少比较次数。

  顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2 N)，搜索的效率取决于搜索过程中元素的比较次数。
  理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一对一映射的关系，那么在查找时通过该函数可以很快找到该元素。

2. 实现机制

2.1 插入时

1.通过函数计算插入位置，该函数成为哈希函数
2.通过计算出的存储位置进行元素的插入，通过这种方法构造出来结构称为哈希表(散列表)

2.2 查找时

1.通过哈希函数对关键码进行计算，得出元素的存储位置
2.根据存储位置在哈希表中，取出元素进行比较，若关键码相同，则查找成功。

这里使用除留余数法举例

2.3 缺陷

  对于两个数据元素的关键字 ki 和 kj (i != j)，有 ki != kj，但有：Hash(ki) == Hash(kj)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

举例：
上述图片中，1的位置上已经插入了一，如果我们还想插入11，使用除留余数法11 % 10 = 1，插入位置还是 1 的位置，这就发生了哈希冲突。

2.4 常见哈希函数

2.4.1 直接定制法

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

2.4.2 除留余数法

原理：设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。
注意: 一般情况下，p最好是一个不超过m的最大素数

2.4.3 平方取中法

原理：假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
场景：平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

2.4.4 折叠法

原理：折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
场景：折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

注意

不论一个哈希函数设计的有多么精妙，都不能完全解决哈希冲突，只能是，哈希函数越精妙，产生的哈希冲突概率越低

3. 解决哈希冲突

3.1 闭散列

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

3.1.1 线性探测

原理
  从发生冲突的位置逐个挨着一次往后查找，如果查找到空间的末尾，也没有发现空位置时，再折回空间起始位置继续查找，直到找到空位置插入进去。

缺陷
  容易产生数据堆积，如果发生了冲入，冲突的元素可能连成一片，因为查找下一个空位置的方式，是逐个向后查找到。

如何避免
不要挨着依次向后查找空位置，二次探测。

3.1.2 二次探测

  解决数据堆积的问题，每次查找空位置时，都向后偏移不同的举例进行检测。

查找下一个空位置的方法

H(i) = (H0 + i ^ 2) % cap / H(i) = (H0 - i ^ 2) % cap
所以: H(i + 1) = H(i) + 2 * i + 1

缺陷
  当表格中空位置比较少时，可能需要查找很多次

3.1.3 闭散列缺点

  当表格中数据较多时，或者哈希表中的空位置较少时，发生冲突的概率非常高，而且找下一个空位置的效率比较低，不论是线性探测还是二次探测都需要找好多次才能找到。

  当哈希表中有效元素比较多时，对哈希表的性能影响非常大。
  哈希期望查找时间复杂度是 O(1)，但空位置比较少时，性能远远超过O(1).
哈希使用时间换空间

解决方法
  不要让表格存储太多元素，达到一定程度时就进行扩容，即: 哈希表中的元素一定不会存满

  负载因子 = 填入表的有效元素的个数 / 散列表的长度 线性探测为：70%左右，二次探测为：50%~60%，在这个区间内就需要扩容了，存的多了就会导致冲突概率上升，存的少了就会空间利用率降低。

3.2 开散列

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

操作
  插入或查找时，当中存在一个循环，即：遍历链表，检测data是否存在，表面上时间复杂度O(n)，但实际认为操作时的时间复杂度为O(1)，因为链表不会很长

3.2.1 容量问题

1. 如果元素特别多，或元素特别特殊，大部分元素都集中到了某一个链表中

  导致某些链表特别长，在哈希桶中查找某个元素，就退化成了在单链表中查找。

  如果每个哈希桶中的元素不是特别多的情况下，哈希桶的时间复杂度为O(1).
  如果哈希桶当中某些链表中挂的结点非常多，哈希桶就退化成了在链表中进行查找，时间复杂度变成了O(n)。

  所以在插入元素的过程中，需要避免上述的情况，在闭散列中，元素多到一定程度通过扩容来降低冲突概率，哈希桶中也是如此，通过扩容，把链表中的结点分散开来。

2. 什么情况下进行扩容？什么情况下哈希桶最优(空间利用率高、查找性能高)?
  最优状态: 每个桶只挂一个结点。当哈希桶中元素个数与桶的个数相同时就要考虑扩容。因为扩容之后，哈希桶的容量变了，哈希函数计算出来的结果就发生了变化，再将旧哈希桶中的元素往新哈希桶中插入，就可以基本到达较优。

3. 随着哈希桶中的元素不断增多，哈希桶的的容量也会不断增大，怎么解决？
  扩容之后，继续往哈希桶中插入元素，或者对方在向哈希表中插入元素是，每个插入哈希桶中的元素都是发生哈希冲突的，可能又会出现某些链表特别长的场景出现，扩容之后依旧不能达到目的。(哈希桶性能又下降了，但是还没有达到扩容的时机)。

解决方案
  当链表中的结点达到一定的阈值，还没有达到扩容的条件时，可以将链表转换成红黑树，当结点个数小于阈值就转换成链表。

4. 哈希函数
  除留取余法：最好模上一个素数，发生冲突的概率相对而言能稍微低一些，而元素的个数与表格容量相等时，需要扩容，按照两倍的方式扩容。可以用素数表将含有两倍关系的素数存下来。

const int PRIMECOUNT = 28;
const size_t primeList[PRIMECOUNT] =
{
	53ul, 97ul, 193ul, 389ul, 769ul,
	1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
	49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
	1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
	50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
	1610612741ul, 3221225473ul, 4294967291ul
};
1
2
3
4
5
6
7
8
9
10

5. 泛型存储
  哈希函数中任意类型都能存储，但是使用除留取余法，只能转换整数，所以还要传入一个模板参数，可以将其它类型进行转换，使之能够使用除留取余法。

4. 开散列的代码实现

#include <iostream>
using namespace std;

#include <vector>
#include "Common.h"

// 哈希桶：数组+链表(无头单链表)

template<class T>
struct HashBucketNode
{
	HashBucketNode<T>* next;
	T data;

	HashBucketNode(const T& x = T())
		: next(nullptr)
		, data(x)
	{}
};


// T 如果是整形家族
template<class T>
class T2IntDef
{
public:
	const T& operator()(const T& data)
	{
		return data;
	}
};


class Str2Int
{
public:
	size_t operator()(const string& s)
	{
		const char* str = s.c_str();
		unsigned int seed = 131; // 31 131 1313 13131 131313
		unsigned int hash = 0;
		while (*str)
		{
			hash = hash * seed + (*str++);
		}
		return (hash & 0x7FFFFFFF);
	}
};


// 假设：当前实现的哈希表中元素唯一
// T：哈希表中存储的元素的类型
// T2Int: 将T转换为整形的结果

template<class T, class T2Int = T2IntDef<T>>
class HashBucket
{
	typedef HashBucketNode<T> Node;
public:
	HashBucket(size_t capacity = 53)
		: table(GetNextPrime(capacity))    // n个值为data的构造方法在构造哈希桶
		, size(0)
	{}

	~HashBucket()
	{
		Destroy();
	}

	/*
	虽然从代码层面来看，Insert当中存在一个循环，即：遍历链表，检测data是否存在---->表面上Insert的时间复杂度O(N)
	但是实际认为Insert的时间复杂度仍旧为O(1)---->因为：在哈希桶中，每个桶对应的链表当中的节点的格式都不是非常多
	*/
	bool Insert(const T& data)
	{
		// 0. 检测是否需要扩容
		CheckCapacity();

		// 1. 通过哈希函数计算元素所在桶号
		size_t bucketNo = HashFunc(data);

		// 2. 检测元素是否存在
		Node* cur = table[bucketNo];
		while (cur)
		{
			if (data == cur->data)
				return false;

			cur = cur->next;
		}

		// 3. 插入元素
		cur = new Node(data);
		cur->next = table[bucketNo];
		table[bucketNo] = cur;
		++size;
		return true;
	}

	bool Erase(const T& data)
	{
		// 1. 先通过哈希函数计算元素所在的桶号
		size_t bucketNo = HashFunc(data);

		// 2. 找元素在bucketNo桶中是否处在，存在则删除
		// 核心操作--->删除链表当中只为data的节点
		//  该节点可能是链表中的第一个节点
		//  该节点可能是链表中的非第一个节点

		Node* cur = table[bucketNo];
		Node* prev = nullptr;   // 标记cur的前一个节点
		while (cur)
		{
			if (data == cur->data)
			{
				// 删除cur节点
				// 删除的节点如果是第一个节点
				if (nullptr == prev)
					table[bucketNo] = cur->next;
				else
					prev->next = cur->next;

				delete cur;
				--size;
				return true;
			}
			else
			{
				// 当前节点不是要找的data，则两个指针同时往后移动
				prev = cur;
				cur = cur->next;
			}
		}

		// 哈希桶中不存在值为data的元素，无法删除即删除失败
		return false;
	}

	Node* Find(const T& data)
	{
		// 1. 先通过哈希函数计算元素所在的桶号
		size_t bucketNo = HashFunc(data);

		// 2. 在检测该元素是否存在对应的链表中
		Node* cur = table[bucketNo];
		while (cur)
		{
			if (data == cur->data)
				return cur;

			cur = cur->next;
		}

		return nullptr;
	}

	size_t Size()const
	{
		return size;
	}

	bool Empty()const
	{
		return 0 == size;
	}

	/
	// 为了方便对哈希桶的理解，实现打印哈希桶的方法
	void Print()
	{
		for (size_t i = 0; i < table.capacity(); ++i)
		{
			Node* cur = table[i];

			cout << "table[" << i << "]:";

			while (cur)
			{
				cout << cur->data << "--->";
				cur = cur->next;
			}

			cout << "NULL" << endl;
		}
		cout << "=========================================" << endl;
	}

	void Swap(HashBucket<T, T2Int>& ht)
	{
		table.swap(ht.table);
		std::swap(size, ht.size);
	}

private:
	// 哈希函数---除留余数法
	size_t HashFunc(const T& data)
	{
		T2Int t2Int;
		return t2Int(data) % table.capacity();
	}

	void Destroy()
	{
		// 循环去销毁：table中的每个链表
		for (size_t i = 0; i < table.capacity(); ++i)
		{
			Node* cur = table[i];

			// 采用：头删法删除链表中的每个节点
			while (cur)
			{
				table[i] = cur->next;
				delete cur;
				cur = table[i];
			}
		}

		size = 0;
	}

	void CheckCapacity()
	{
		if (size == table.capacity())
		{
			// 扩容---将表格放大----然后将桶中的元素往新桶中插入
			HashBucket<T, T2Int> newHT(GetNextPrime(table.capacity()));

			// 将就哈希桶中的节点拆下来，移动到新哈希桶中
			for (size_t i = 0; i < table.capacity(); ++i)
			{
				Node* cur = table[i];
				while (cur)
				{
					// 1. 将cur节点拆下来
					table[i] = cur->next;

					// 2. 将cur节点往newHT中插入
					// 找位置
					size_t bucketNo = newHT.HashFunc(cur->data);

					// 头插法
					cur->next = newHT.table[bucketNo];
					newHT.table[bucketNo] = cur;
					newHT.size++;

					cur = table[i];
				}
			}

			// 已经将旧哈希桶中的元素全部移动到新哈希桶当中了
			this->Swap(newHT);
		}
	}
private:
	// table当中将来存放所有的链表--->实际只需要存放链表首节点的地址
	std::vector<Node*> table;
	size_t size;   // 有效元素的个数
};
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