散列表查找技术（数据结构）

1. 基本思想

散列表，又叫哈希表（Hash Table），是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。
也即，把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。

2. 散列函数

2.1 直接定址法

$$H(key)=a\times key+b$$

2.2 除留余数法

$$H(key)=key\mathrm{m}\mathrm{o}\mathrm{d}b$$

2.3 平方取中法

先计算出关键字值的平方，然后取平方值中间几位作为散列地址。

随机分布的关键字，得到的散列地址也是随机分布的。

3. 冲突处理

3.1 开放定址法

发生冲突时,寻找下一个空地址
$$(H(key)+d_i)\mathrm{m}\mathrm{o}\mathrm{d}m$$

其中:$d_i=1,2,...,m-1$，称为线性探测法

其中:$d_i=1^2,-1^2,2^2,-2^2,...,q^2,-q^2(q\le \sqrt{m})$，称为平方探测法

3.2 拉链法

冲突的元素用链表串起来，也可以用红黑树，AVL树。。。

4. 简单实现

使用除留余数法哈希,开放定址法处理冲突

#include <bits/stdc++.h>
using namespace std;
const int MaxSize = 13;	 // 一个素数
int ht[MaxSize] = { 0 }; // 哈希表
/**
 * @brief 简单的哈希函数（使用除留余数法）
 *
 * @param k 键值
 * @return int hash code
 */
int hash(int k) {
	return k % MaxSize;
}
/**
 * @brief 插入
 *
 * @param k 键
 * @return true 插入成功
 * @return false 插入失败：表满了或者键重复了
 */
bool insert(int k) {
	int h = ::hash(k), i = h; // 这里可能跟标准库的hash函数重名了
	while (ht[i]) {
		if (ht[i] == k)
			return true;
		i = (i + 1) % MaxSize;
		if (i == h)
			return false;
	}
	ht[i] = k;
	return true;
}
/**
 * @brief 搜索
 *
 * @param k 键
 * @return int 在哈希表中的下标 （-1表示不存在）
 */
int search(int k) {
	int h = ::hash(k);
	while (ht[h]) {
		if (ht[h] == k)
			return h;
		h = (h + 1) % MaxSize;
	}
	return -1;
}

int main(int argc, char const* argv[]) {
	// for (int i = 0; i < 15; ++i) {
	// 	cout << "insert: " << i << " " << insert(i) << "\n";
	// }
	// 插入0会有个bug
	cout << "insert: " << 1 << " " << (insert(1) ? "True" : "False") << "\n";
	cout << "insert: " << 14 << " " << (insert(14) ? "True" : "False") << "\n";
	cout << "insert: " << 27 << " " << (insert(27) ? "True" : "False") << "\n";
	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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58