散列表（Hash Table）概念、散列冲突、开散列模拟实现散列表_开散列表

散列表提供了一种完全不同的存储和搜索方式，通过将关键码映射到表中某个位置上来存储元素，然后根据关键码用同样的方式直接访问。

理想的搜索方法是可以不经过任何比较，一次直接从表中拿到搜索的元素，如果在元素的存储位置与它的关键码之间建立一个确定的对应函数关系Hash()，使得每个关键码与结构中的一个唯一的存储位置相对应Adderss = Hash(Key)。

插入元素：根据待插入元素的关键码，以此函数计算该元素的存储位置并按此位置进行存放；

搜索元素：对元素的关键码进行计算，将求得的函数值作为元素的存储位置，在表中按此位置取元素比较，若关键码相等，则搜索成功。

这种方法就叫做散列方法，使用的转换函数称为散列函数，构建的表又称为散列表。

对于不同的关键码，通过散列函数计算得到了同一散列地址，称这些散列地址相同的不同关键码为同义词。按照这样的地址加入散列表时就产生了冲突，冲突太多会降低搜索效率。

冲突是不可避免的，只能尽量避免、减少冲突。

1. 散列函数

在构造散列函数需要注意：

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

常见散列函数：

1. 除留余数法（常用）

设表中允许的地址数为m，取一个不大于m，但最接近于或等于m的质数p作为除数，散列函数为：
hash（key） = key % p （p ≤ m）

2. 平方取中法

先计算构成关键码的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址，设标识符可以用一个计算机字长的内码表示，内码平方数的中间几位一般是由标识符所有字符决定，所以对不同的标识符计算出的散列地址大多不相同，即使可能有些字符相同。

3. 折叠法

将关键码自左向右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些，将这些部分叠加起来，就可以得到具有该关键码记录的散列地址，两种叠加方法：
（1）移位法：把各部分的最后移位对齐相加；
（2）分界法：各部分不折断，沿各部分的分界来回折叠，然后对其相加，将相加的结果作为散列地址。
例：key = 23938587841，存储空间为3位，则划分结果分为每段3位，则
239 385 878 41

将超出地址位数的最高位删除，保留最低的3位。

2. 解决散列冲突办法

最常见的两种方法：闭散列和开散列。

2.1 闭散列

闭散列：**又称开放定址法，当发送散列冲突时，如果散列表未被装满，说明在散列表中还有空位置，那么就可以把key存放到冲突位置中的下一个空位置中去。**寻找下一个空位置

1. 线性探测：从发起冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

散列表的大小为8，红色方格代表了产生了散列冲突，依次寻找下一个空位置。
删除时：闭散列解决散列冲突时，不能随便物理删除散列表已有的元素，若是直接删除元素会影响其它元素的搜索，则线性探测需要采用标记的伪删除法删除一个元素。
线性探查方法容易产生“堆积”问题，即不同探查序列的关键码占据了可利用的空桶，使得为寻找某一关键码需要经历不同的探查序列的元素。

2. 二次探查法

二次探查法寻找下一个空位置公式为：$H_i$ = ($H_0$ + $i^2$) % m，或者$H_i$ = ($H_0$ - $i^2$) % m，其中i = 1，2，3…，$H_0$是通过散列函数计算得到的位置，m为散列表的大小。
$H_i$ = ($H_0$ + $i^2$) % m 则 $H_{i+1}$ = ($H_0$ + ${(i+1)}^2$) % m，则$H_{i+1}-H_i=2i+1$，则$H_{i+1}=H_0+2i+1$。
当表的长度为质数且表中装载因子不超过0.5时，新的关键码一定能够插入，而且任意位置不会被探查两次。如果装在因子超出0.5时，需要考虑对表进行扩容。
在删除时，也只能做逻辑删除，不能将该位置进行删除。

2.2 开散列

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

如图：

开散列桶中，每个桶存放的都是发送散列冲突的关键码。

随着元素的插入，散列表中每一个桶中的元素都会增加，当某些桶中的链表节点非常多时，会影响散列表的性能，因此则考虑为散列表进行扩容。

最优的情况：一个桶中只放一个元素，则当前元素个数等于散列表桶的个数时，对散列表进行扩容。

3. 开散列模拟实现散列表

代码：

#pragma once
#include <string>
#include <vector>

const int num_primes = 28;
static const unsigned long Prime_list[num_primes] =
{
  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
};

template<class V>
struct HashTableNode//哈希节点
{
	HashTableNode(const V& x = V())
		:next(nullptr)
		,val(x)
	{}
	HashTableNode* next;
	V val;
};

//此时数据为整形
template<class T>
class DataIntDef
{
public:
	const T& operator()(const T& data)const
	{
		return data;
	}
};

//数据为string类型
class StrToInt
{
public:
	size_t operator()(const std::string& data)const
	{
		return ELFHash(data.c_str());
	}

	size_t ELFHash(const char *str)const
	{
		unsigned int hash = 0;
		unsigned int x = 0;

		while (*str)
		{
			hash = (hash << 4) + (*str++);
			if ((x = hash & 0xF0000000L) != 0)
			{
				hash ^= (x >> 24);
				hash &= ~x;
			}
		}
		return (hash & 0x7FFFFFFF);
	}
};


template<class T>
class KOFV//数据类型
{
public:
	T operator()(T data)const
	{
		return data;
	}
};


template<class K, class KOFV, class DataToInt = StrToInt>
class HashTable;

//迭代器
template<class K, class KOFV, class DataToInt>
struct HashTableIterator
{
	typedef HashTableNode<K> Node;
	typedef HashTableIterator<K, KOFV, DataToInt> Self;

	Node* pnode;
	HashTable<K, KOFV, DataToInt>* ht;

	HashTableIterator(Node* node = nullptr, HashTable<K, KOFV, DataToInt>* HT = nullptr)
		:pnode(node)
		,ht(HT)
	{}

	K& operator*()
	{
		return pnode->val;
	}

	K* operator->()
	{
		return &(operator*());
	}

	Self& operator++()//前置++
	{
		Next();
		return *this;
	}

	Self& operator++(int)//后置++
	{
		Self temp(*this);
		Next();
		return temp;
	}

	bool operator!=(const Self& data)
	{
		return !(*this == data);
	}

	bool operator==(const Self& data)
	{
		return pnode == data.pnode && ht == data.ht;
	}

	void Next()
	{
		if (pnode->next)
			pnode = pnode->next;
		else
		{
			size_t tablenumber = ht->HashFunc(pnode->val, ht->capacity()) + 1;

			for (; tablenumber < ht->capacity(); ++tablenumber)
			{
				if (ht->table[tablenumber])
				{
					pnode = ht->table[tablenumber];
					return;
				}
			}
			pnode = nullptr;
		}
	}
};

template<class K, class KOFV, class DataToInt>
class HashTable
{
	typedef HashTableNode<K> Node;
	friend HashTableIterator<K, KOFV, DataToInt>;声明迭代器为友元，则迭代器才能访问该散列表
public:
	typedef HashTableIterator<K, KOFV, DataToInt> iterator;


private:
	std::vector<Node*> table;//哈希表
	size_t _size;//表中元素个数

public:
	HashTable(size_t capacity = 10)//构造函数
		:table(capacity)
		,_size(0)
	{}

	~HashTable()
	{
		clear();
	}

	iterator begin()
	{
		for (size_t i = 0; i < capacity(); ++i)
		{
			if (table[i])
				return iterator(table[i], this);
		}
		return end();
	}

	iterator end()
	{
		return iterator(nullptr, this);
	}

	pair<iterator, bool> InsertUnique(const K& data)//插入元素，没有重复的元素
	{
		_CheckCapacity();
		size_t tablenumber = HashFunc(data, table.capacity());
		Node* cur = table[tablenumber];

		//检测当前元素是否存在
		while (cur)
		{
			if (KOFV()(data) == KOFV()(cur->val))
				return make_pair(iterator(cur, this), false);
			cur = cur->next;
		}

		cur = new Node(data);
		cur->next = table[tablenumber];
		table[tablenumber] = cur;
		++_size;
		return make_pair(iterator(cur, this), true);

	}

	pair<iterator, bool> InsertEqual(const K& data)//插入可重复元素
	{
		_CheckCapacity();
		size_t tablenumber = HashFunc(data, table.capacity());
		Node* cur = new Node(data);
		cur->next = table[tablenumber];
		table[tablenumber] = cur;
		++_size;
		return make_pair(iterator(cur, this), true);
	}

	size_t EraseUnique(const K& data)//删除元素，无重复元素
	{
		size_t tablenumber = HashFunc(data, capacity());

		Node* cur = table[tablenumber];

		if (cur)
		{
			Node* prev = nullptr;
			while (cur)
			{
				if (KOFV()(cur->val) == KOFV()(data))
				{
					if (prev == nullptr)
						table[tablenumber] = cur->next;
					else
						prev->next = cur->next;

					delete cur;
					cur = nullptr;
					--_size;
					return 1;
				}
				else
				{
					prev = cur;
					cur = cur->next;
				}
			}
		}
		return 0;
	}

	size_t EraseEqual(const K& data)//删除元素，元素有重复
	{
		size_t tablenumber = HashFunc(data, capacity());

		Node* cur = table[tablenumber];
		size_t count = 0;
		if (cur)
		{
			Node* prev = nullptr;
			while (cur)
			{
				if (KOFV()(cur->val) == KOFV()(data))
				{
					if (prev == nullptr)
					{
						table[tablenumber] = cur->next;
						delete cur;
						cur = table[tablenumber];
					}
					else
					{
						prev->next = cur->next;
						delete cur;
						cur = cur->next;
					}
					--_size;
					++count;
					continue;
				}
				prev = cur;
				cur = cur->next;
			}
		}
		return count;
	}

	bool Find(const K& data)//元素查找
	{
		size_t tablenumber = HashFunc(data, capacity());

		Node* cur = table[tablenumber];

		while (cur)
		{
			if (KOFV()(cur->val) == KOFV()(data))
				return true;
			cur = cur->next;
		}
		return false;
	}

	void PrintHashTable()//打印hashtable
	{
		for (size_t i = 0; i < capacity(); ++i)
		{
			cout << "[" << i << "] :";
			Node* cur = table[i];
			while (cur)
			{
				cout << cur->val << "--->";
				cur = cur->next;
			}

			cout << "NULL" << endl;
		}
		cout << "--------------------------------------------------" << endl;
	}

	bool Empty()
	{
		return _size == 0;
	}

	size_t Size()
	{
		return _size;
	}

	size_t capacity()
	{
		return table.capacity();
	}


private:
	size_t HashFunc(const K& data, size_t capacity)
	{
		return DataToInt()(KOFV()(data)) % capacity;
	}

	void _CheckCapacity()
	{
		if (_size == table.capacity())
		{
			//HashTable<K> newHT(table.capacity() * 2);
			vector<Node*> newHT(GetNextPrime(table.capacity()));
			for (size_t i = 0; i < table.capacity(); ++i)
			{
				Node* cur = table[i];
				while (cur)
				{
					table[i] = cur->next;

					size_t tablenumber = HashFunc(cur->val, newHT.capacity());

					cur->next = newHT[tablenumber];
					newHT[tablenumber] = cur;

					cur = table[i];
				}
			}
			table.swap(newHT);
		}
	}

	unsigned long GetNextPrime(size_t capacity)//stl容器中使用的方法，lower_bound
	{
		const unsigned long* first = Prime_list;
		const unsigned long* last = Prime_list + (int)num_primes;

		const unsigned long* pos = std::lower_bound(first, last, capacity);

		return pos == last ? *(last - 1) : *pos;
	}

	void clear()
	{
		for (size_t i = 0; i < capacity(); ++i)
		{
			Node* cur = table[i];
			while (cur)
			{
				table[i] = cur->next;
				delete cur;
				cur = table[i];
			}
			cur = nullptr;
		}
	}
};

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
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394

测试用例：

int main()
{
	HashTable<string, KOFV<string>> ht;
	ht.InsertUnique("小王");
	ht.InsertUnique("小刘");
	ht.InsertUnique("小李");
	ht.InsertUnique("小张");

	ht.PrintHashTable();

	ht.InsertEqual("小张");
	ht.InsertEqual("小李");
	ht.PrintHashTable();


	ht.PrintHashTable();
	cout << ht.capacity() << endl;
	cout << ht.Size() << endl;
	cout << ht.Find("小五") << endl;
	auto it = ht.begin();

	cout << *it << endl;
	cout << it->data() << endl;
	ht.PrintHashTable();

	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