散列表
介绍
散列表(Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。存储位置 = f(key)，这个映射函数叫做散列函数，存放记录的数组叫做散列表。
散列技术既是一种存储方法，也是一种查找方法。散列技术最适合的求解问题是查找与给定值相等的记录。
散列冲突
在理想的情况下，每一个关键码值，通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。我们时常会碰到两个关键字key1 ≠ key2，但是却有f(key1)=f(key2)，这种现象我们称为冲突(collision)，并把key1和key2称为这个散列函数的同义词(synonym)。
散列函数的构造方法
好的散列函数满足两个原则：1.计算简单 2.散列地址分布均匀
如果关键字是字符串如何处理？其实无论是英文字符，还是中文字符，也包括各种各样的符号，它们都可以转化为某种数字来对待，比如ASClI码或者Unicode码等，因此也就可以使用下面的这些方法。
总之，现实中，应该视不同的情况采用不同的散列函数。我们只能给出一些考虑的因素来提供参考：
- 计算散列地址所需的时间。
- 关键字的长度。
- 散列表的大小。
- 关键字的分布情况。
- 记录查找的频率。
综合这些因素，才能决策选择哪种散列函数更合适。
直接定址法
取关键字或关键字的某个线性函数为Hash地址，即H(key)=key 或者H(key)=a*key+b，其中a和b为常数。
这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。
数字分析法
假设关键字是r进制数（如十进制数），并且Hash表中可能出现的关键字都是事先知道的，则可选取关键字的若干数位组成Hash地址。选取的原则是使得到的Hash地址尽量减少冲突，即所选数位上的数字尽可能是随机的。
若我们现在要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的。那么我们选择后面的四位成为散列地址就是不错的选择。如果这样的抽取工作还是容易出现冲突问题，还可以对抽取出来的数字再进行反转（如1234改成4321）、右环位移（如1234改成4123）、左环位移、甚至前两数与后两数叠加（如1234改成12+34=46）等方法。总的目的就是为了提供一个散列函数，能够合理地将关键字分配到散列表的各位置。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。
平方取中法
取关键字平方后的中间几位作为Hash地址。通常在选定Hash函数的时候不一定能知道关键字的全部情况，仅取其中的几位为地址不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此得到的Hash地址随机性更大，取的位数由表长决定。
平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。
折叠法
折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如我们的关键字是9876543210，散列表表长为三位，我们将它分为四组，
987|654|321|0，然后将它们叠加求和987+654+321+0=1962，再求后3位得到散列地址为962。
有时可能这还不能够保证分布均匀，不妨从一端向另一端来回折叠后对齐相加。
比如我们将987和321反转，再与654和0相加，变成789+654+123+0=1566，此时散列地址为566。
除留余数法(常用)
取关键字被某个不大于Hash表表长m的数p除后所得的余数为Hash地址，即
H（key）=key mod p（p≤m）
在本方法中，p的选择很重要，一般p选择小于或者等于表长的最大素数，这样可以减少冲突。
随机数法
选择一个随机数，取关键字的随机函数值为它的散列地址。也就是f（key）= random（key）。这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
处理散列冲突的方法
只能尽量减少冲突的发生，不可完全避免冲突。
开放定址法
线性探测法：从发生冲突的地址（设为d）开始，依次探查d的下一个地址（当到达下标为m-1的Hash表表尾时，下一个探查的地址是表首地址0），直到找到一个空位置为止，当m≥n（n是表中关键字的个数）时一定能找到一个空位置。
它的公式是：
f（key）=（f（key）+d）MOD m（d=1，2，3，……，m-1）
使用线性探测法会出现不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。堆积会使我们的存入和查找效率降低。
二次探测法：也叫平方探测法，可以双向寻找空位置，减少堆积问题的出现。
它的公式是：
f（key）=（f（key）+d）MOD m（d=1²，-1²，2²，-2²……，q²,-q²,q<=m/2）
使用二次探测法不能探查到哈希表上的所有单元，但至少能探测到一半的单元。
此外，开放定址法的探查方法还有伪随机序列法， d=伪随机数序列
再散列法
再散列法：Hi=RHi(key),i=1,2，…， RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
链地址法(常用)
链地址法是把所有的同义词用单链表连接起来的方法。在这种方法中，Hash表每个单元中存放的不再是记录本身，而是相应同义词单链表的表头指针。
链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链表的性能损耗。
散列表查找算法实现
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
| package com.nanzx.hashtab;
import java.util.Scanner;
public class HashTabDemo {
public static void main(String[] args) {
HashTab hashTab = new HashTab(7);
String key = "";
Scanner scanner = new Scanner(System.in);
while (true) {
System.out.println("add: 添加雇员");
System.out.println("list: 显示雇员");
System.out.println("find: 查找雇员");
System.out.println("exit: 退出系统");
key = scanner.next();
switch (key) {
case "add":
System.out.println("输入id");
int id = scanner.nextInt();
System.out.println("输入名字");
String name = scanner.next();
Emp emp = new Emp(id, name);
hashTab.add(emp);
break;
case "list":
hashTab.list();
break;
case "find":
System.out.println("请输入要查找的id");
id = scanner.nextInt();
hashTab.findEmpById(id);
break;
case "exit":
scanner.close();
System.exit(0);
default:
break;
}
}
}
}
class Emp {
public int id;
public String name;
public Emp next;
public Emp(int id, String name) {
super();
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Emp [id=" + id + ", name=" + name + "]";
}
}
class EmpLinkedList {
private Emp head;
public void add(Emp emp) {
if (head == null) {
head = emp;
return;
}
Emp curEmp = head;
while (true) {
if (curEmp.next == null) {
curEmp.next = emp;
return;
}
curEmp = curEmp.next;
}
}
public void list(int no) {
if (head == null) {
System.out.println("第 " + (no + 1) + " 链表为空");
return;
}
System.out.print("第 " + (no + 1) + " 链表的信息为");
Emp curEmp = head;
while (true) {
System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
if (curEmp.next == null) {
break;
}
curEmp = curEmp.next;
}
System.out.println();
}
public Emp findEmpById(int id) {
if (head == null) {
System.out.println("链表为空");
return null;
}
Emp curEmp = head;
while (true) {
if (curEmp.id == id) {
break;
}
if (curEmp.next == null) {
curEmp = null;
break;
}
curEmp = curEmp.next;
}
return curEmp;
}
}
class HashTab {
private EmpLinkedList[] empLinkedListArray;
private int size;
public HashTab(int size) {
this.size = size;
empLinkedListArray = new EmpLinkedList[size];
for (int i = 0; i < size; i++) {
empLinkedListArray[i] = new EmpLinkedList();
}
}
public void add(Emp emp) {
int empLinkedListNO = hashFun(emp.id);
empLinkedListArray[empLinkedListNO].add(emp);
}
public void list() {
for (int i = 0; i < size; i++) {
empLinkedListArray[i].list(i);
}
}
public void findEmpById(int id) {
int empLinkedListNO = hashFun(id);
Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
if (emp != null) {
System.out.printf("在第%d条链表中找到 雇员 id = %d\n", (empLinkedListNO + 1), id);
} else {
System.out.println("在哈希表中，没有找到该雇员~");
}
}
public int hashFun(int id) {
return id % size;
}
}
|
微信
支付宝