哈希表
1 哈希表的概念
哈希表是根据码值(key value)而直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，带入函数后若能得到包含该关键字的记录在表中的地址，称表M为哈希表，函数(key)为哈希函数。
哈希表是时间与空间之间的平衡，因此哈希函数的设计很重要。所以哈希函数应该尽量减少哈希冲突，也就是“键”通过哈希函数得到的“索引”分布越均匀越好。
哈希函数是根据关键字设计的，有很多复杂的函数，主要的原理就是根据数组的大小求模运算。(关键字)%(数组大小)，数组的大小一般设计为质数，因为需要均匀的分布。
2 散列函数
如果我们有一个能保存M个键值对的数组，那么我们就需要一个能够将任意键转化为该数组范围内的索引([0,M-1]范围内的整数)的散列函数。要找的散列函数应该易于计算并且能够均匀分布所有的键。即对于任意的键，0到M-1之间的每个整数都有相等的可能性与之对应(与键无关)。散列函数和键的类型有关，对于每种类型的键我们都需要一个与之对应的散列函数。
2.1 正整数
将整数是散列的最常用的方法是除留余数法，选择大小为素数M的数组，对于任意的k，计算k除以M的余数。如果不是素数的话，可能无法利用键中包含的所有信息，导致无法均匀地散列散列值。
2.2 浮点数
如果键是0到1之间的实数，我们可以将它乘以M并四舍五入得到一个0至M-1之间的索引值。但是这种方法有局限性，因为这种情况下键的高位起作用更大，最低位对散列的结果没有影响。修正这个问题的方法是将键表示为二进制数然后再使用除留余数法。
2.3 字符串
除留余数法也可以处理较长的键，例如字符串，我们只需要将其当做大整数即可。如下： 1
2
3
4int hash = 0;
for(int i = 0; i < s.length(); i++){
hash = (R*hash + s.charAt(i)) % M;
}
2.4 组合键
如果键的种类有多个变量类型，我们可以和String类型一样将它们混合起来。例如，假设被查找的键的类型是Date，其中含有几个整型的域：day（两个数字表示的日）和month(两个数字表示的月)和year(四个数字表示的年)，可以如下计算它的散列值： 1
int hash = (((day*R + month)%M)*R+year)%M;
3 简单的哈希表的实现
题目：有一个公司，当有新的员工来报道时，要求将该员工的信息加入(id,性别,年龄,住址等)，当输入该员工的id时，要求查找到该员工的所有信息。 要求：不使用数据库，速度越快越好，添加后，保证id从低到高插入===》哈希表 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
163public class Demo {
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("exit：退出系统");
System.out.println("find:查找雇员");
key = scanner.next();
switch (key){
case "add" :
System.out.println("输入id：");
int id = scanner.nextInt();
System.out.println("输入名字：");
String name = scanner.next();
Employee employee = new Employee(id, name);
hashTab.add(employee);
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 HashTab{
private EmpLinkedList[] empLinkedListArray;
private int size;//表示共有多少条链表
//构造器
public HashTab(int size){
this.size = size;
//初始化empLinkedListArray
empLinkedListArray = new EmpLinkedList[size];
for (int i = 0; i < size; i++) {
empLinkedListArray[i] = new EmpLinkedList();
}
}
//添加雇员
public void add(Employee employee){
//根据员工的id，得到员工应当添加到那条链表
int empLinkedListNO = hashFun(employee.id);
//将emp添加到对应的链表中
empLinkedListArray[empLinkedListNO].add(employee);
}
//遍历哈希表
public void list(){
for (int i = 0; i < size; i++) {
empLinkedListArray[i].list(i);
}
}
//根据输入的id遍历hashtab
public void findEmpById(int id){
//使用散列函数确定到那条链表查找
int empLinkedListNO = hashFun(id);
Employee 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;
}
}
class Employee{
public int id;
public String name;
public Employee next;//next默认为null
/**
* 构造器
* @param id
* @param name
*/
public Employee(int id,String name){
super();
this.id = id;
this.name = name;
}
}
//创建EmpLinkedList，表示链表
class EmpLinkedList{
//头指针，执行第一个Emp，因此这个链表的head直接指向第一个emp
private Employee head;//默认null
//添加雇员到链表
//id自增长，那么直接添加到链表的最后就好
public void add(Employee employee){
//添加第一个员工
if (head == null){
head = employee;
return;
}
//如果不是第一个员工，加入辅助指针，帮助定位到最后
Employee curEmp = head;
while (true){
if (curEmp.next == null){
break;//到链表的最后
}
curEmp = curEmp.next;//后移
}
curEmp.next = employee;
}
//遍历链表的雇员信息
public void list(int no){
if (head == null){
//链表为空
System.out.println("第"+no+" 链表为空");
return;
}
System.out.println("第"+no+"链表信息为：");
Employee 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 Employee findEmpbyId(int id){
//判断链表是否为空
if (head == null){
System.out.println("链表为空");
return null;
}
//辅助指针
Employee curEmp = head;
while (true){
if (curEmp.id == id){
break;
}
if (curEmp.next == null){
//说明遍历当前链表没有找到该雇员
curEmp = null;
break;
}
curEmp = curEmp.next;
}
return curEmp;
}
}