【C++进阶】：哈希

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

一.unordered_map

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

二.底层结构

1.哈希概念

复杂的说

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

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

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

简单的说

上述就是一种k,v的映射关系，为了避免数组越界，我们还会对K(铅笔的号数)进行取模(%capcity)。相信大家也能发现，铅笔的号数肯定远远不止5个，例如：5号铅笔和10号铅笔都会储存在0号位置，这就是下哈希冲突。

2.解决哈希冲突

1.闭散列

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

第一种：线性探测

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

总的来说，将数据放入hash表时，如果该位置被占据，就向后查找，直到找到空位置进行插入。在查询数据时，一直查询直到找到或者找到空位置或者原点时停止。基于查找时找到空位置时停止，所以删除时就不能直接置空，需要标记该位置已被删除。接下来还有一个难点就是扩容。

根据查找规则来看，如果等hash表填满才扩容，毫无疑问会发生很多冲突，这是很低效的，所以必须有一个扩容规则来判断何时扩容。

enum State
{
	EXIST,
	DELETE,
	EMPTY
};

template<class K,class V>
struct HashData//创建hash表的类型
{
	pair<K, V> _kv;
	State _state=EMPTY;
};

template<class K,class V>
class Hash
{
public:
	Hash()
	{
		_table.resize(10);//初始开10给空间
	}

	void insert(const pair<K, V>& kv)
	{
		//判断是否需要扩容
		if (n * 10 / _table.size() >= 7)
		{
			//开一个新的表容量为原来二倍
			size_t newHash = _table.size() * 2;
			Hash<K, V>newHT;
			newHT._table.resize(newHash);

			//将旧表的值插入到新表里
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]._state == EXIST)
					newHT.insert(_table[i]._kv);
			}
			//交换新旧表
			_table.swap(newHT._table);
		}

		//线性探测
		size_t hashi = kv.first % _table.size();//插入位置
		while (_table[hashi]._state == EXIST)//判断应该插入的位置
		{
			hashi++;
			hashi %= _table.size();
		}
		_table[hashi]._state = EXIST;
		_table[hashi]._kv = kv;
		n++;//有效长度加一
	}
private:
	vector<HashData<K, V>>_table;//创建hash表
	size_t n = 0;//记录有效长度
};
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

第二种二次探测

二次探测与线性探测基本一致，只是线性探测在找空位时依次向后找，而二次探测在找空位时，一次走i的平方。

2.开散列

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

接下来是扩容操作，其实开散表即使不扩容也能正常使用，但如果数据插入过多，会导致桶越来越长，最终变成长链表，导致查找效率降低。所以我们需要引入负载因子来判断何时应该扩容（负载因子计算看与闭散表一致）。

整个扩容需要遍历所有链表，把它们的指针都指向新链表就可以了。

这里需要补充一点，因为我们的K值不一定都是int类型，所以需要写仿函数来将它转成int，这样才能对应数组下标。

又因为字符串是我们常用的数据类型，所以我们可以将它进行一个特例化，单独将字符串转化拎出来（字符串转化规则是根据字符串哈希转化规则进行转化的，不明白的可以自行百度）。

接下来删除和查找都比较简单，直接看完整源代码。

Hash.h

#include
#include
using namespace std;


template<class K>
struct DefaultHashFunc//仿函数
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct DefaultHashFunc<string>//特例化
{
	size_t operator()(const string& str)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};

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

	template<class K, class V>
	struct HashData//创建hash表的类型
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V>
	class Hash
	{
	public:
		Hash()
		{
			_table.resize(10);//初始开10给空间
		}

		void insert(const pair<K, V>& kv)
		{
			//判断是否需要扩容
			if (n * 10 / _table.size() >= 7)
			{
				//开一个新的表容量为原来二倍
				size_t newHash = _table.size() * 2;
				Hash<K, V>newHT;
				newHT._table.resize(newHash);

				//将旧表的值插入到新表里
				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_table[i]._state == EXIST)
						newHT.insert(_table[i]._kv);
				}
				//交换新旧表
				_table.swap(newHT._table);
			}

			//线性探测
			size_t hashi = kv.first % _table.size();//插入位置
			while (_table[hashi]._state == EXIST)//判断应该插入的位置
			{
				hashi++;
				hashi %= _table.size();
			}
			_table[hashi]._state = EXIST;
			_table[hashi]._kv = kv;
			n++;//有效长度加一
		}
	private:
		vector<HashData<K, V>>_table;//创建hash表
		size_t n = 0;//记录有效长度
	};
}



namespace hash_bucket
{
	template<class K,class V>
	struct HashData//创建节点
	{
		HashData<K, V>* next;
		pair<K, V>_kv;
		HashData(const pair<K,V>&kv)
			:next(nullptr)
			,_kv(kv)
		{}
	};


	template<class K,class V,class HashFunc= DefaultHashFunc<K>>
	class Hash
	{
		typedef HashData<K, V> Node;
	public:
		Hash()
		{
			_table.resize(10,nullptr);
		}
		~Hash()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->next;
					delete cur;
					cur = next;
				}

				_table[i] = nullptr;
			}
		}
		HashFunc hf;
		bool Insert(const pair<K, V>& kv)
		{
			//如果重复插入返回false
			if (Find(kv.first))
			{
				return false;
			}

			//扩容
			if (_n == _table.size())
			{
				vector<Node*>newTable;
				newTable.resize(_table.size() * 2, nullptr);
				//遍历所有节点
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						size_t hashi = hf(cur->_kv.first) % newTable.size();
						cur->next = newTable[hashi];
						newTable[hashi] = cur;
						cur = cur->next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newTable);
			}


			size_t hashi = hf(kv.first) % _table.size();
			//头插
			Node*newNode = new Node(kv);
			newNode->next = _table[hashi];
			_table[hashi] = newNode;
			_n++;

			return true;
		}

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

		bool Erase(const K& key)
		{
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->next;
					}
					else
					{
						prev->next = cur->next;
					}

					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->next;
			}
			--_n;
			
			return false;
		}

		void Print()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				while (cur)
				{
					cout << cur->_kv.first << ":" << cur->_kv.second << "->";
					cur = cur->next;
				}
				printf("NULL\n");
			}
			cout << endl;
		}

	private:
		vector<Node*>_table;
		size_t _n = 0;
	};
	
}
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

test.cpp

int main()
{
	hash_bucket::Hash<int, int> ht;
	int a[] = { 1,111,4,7,15,25,44,9 };
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}
	ht.Print();

	ht.Insert(make_pair(14, 14));
	ht.Print();

	ht.Insert(make_pair(24, 24));
	ht.Print();

	ht.Insert(make_pair(34, 34));
	ht.Print();

	ht.Erase(44);
	ht.Erase(4);
	ht.Erase(24);
	ht.Print();

	hash_bucket::Hash<string, string> dict;
	dict.Insert(make_pair("sort", "排序"));
	dict.Insert(make_pair("left", "xxx"));
	dict.Insert(make_pair("insert", "插入"));
	dict.Insert(make_pair("string", "字符串"));
	dict.Insert(make_pair("bucket", "桶"));

	auto dret = dict.Find("left");
	//dret->_kv.first = "xx";
	dret->_kv.second = "左边";
	dict.Print();

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