Data Structure Hash Table

Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

前言

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

哈希表

哈希表介绍:

1)若关键字为k,则其值存放在f(k)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个思想建立的表为散列表。
2)对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),这种现象称为冲突(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。
3)若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

哈希表图解:


google公司的一个上机题:

有一个公司,当有新的员工来报道时,要求将该员工的信息加入(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
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
import java.util.Random;

/**
* @Auther: Arsenal
* @Date: 2020-03-23 19:13
* @Description: 哈希表
*/
public class HashTable {
public static void main(String[] args) {
EmpHashTable empHashTable = new EmpHashTable(6);
/*for (int i = 0; i < 10; i++) {
Emp emp = new Emp(i, "老王" + i);
empHashTable.addEmp(emp);
}
empHashTable.list();
System.out.println("=============================");
//empHashTable.findEmpById(8);
empHashTable.delEmpById(18);
empHashTable.list();*/
/*for (int i = 30; i > 0; i--) {
Emp emp = new Emp(i, "老王" + i);
empHashTable.addEmpByOrder(emp);
}
empHashTable.list();*/

for (int i = 0; i < 20; i++) {
int id = new Random().nextInt(40);
Emp emp = new Emp(id, "老王" + i);
//empHashTable.addEmp(emp);
empHashTable.addEmpByOrder(emp);
}
empHashTable.list();

}
}

/**
* hash表
*/
class EmpHashTable {
public EmpLinkedList[] empLinkedList;
private int size;

// 初始化hashTable
public EmpHashTable(int size) {
this.size = size;
this.empLinkedList = new EmpLinkedList[size];
// 初始化链表
for (int i = 0; i < size; i++) {
empLinkedList[i] = new EmpLinkedList();
}
}

/**
* 添加雇员
* @param emp 雇员
*/
public void addEmp(Emp emp) {
int empLinkedListNo = hashFunction(emp.id);
empLinkedList[empLinkedListNo].addEmp(emp);
}

/**
* 按顺序添加雇员
* @param emp 雇员
*/
public void addEmpByOrder(Emp emp) {
int empLinkedListNo = hashFunction(emp.id);
empLinkedList[empLinkedListNo].addEmpByOrder(emp);
}

/**
* 根据id删除雇员
* @param id 雇员id
*/
public void delEmpById(int id) {
int empLinkedListNo = hashFunction(id);
empLinkedList[empLinkedListNo].delEmpById(id);
}

/**
* 遍历hashtable
*/
public void list() {
for (int i = 0; i < size; i++) {
System.out.println("======第" + (i + 1) + "个子链表======");
empLinkedList[i].list();
}
}

/**
* 根据id查询雇员
* @param id 雇员id
* @return 雇员
*/
public void findEmpById(int id) {
int empLinkedListNo = hashFunction(id);
Emp emp = empLinkedList[empLinkedListNo].findEmpById(id);
if (emp != null) {
System.out.println("该雇员在" + (empLinkedListNo + 1) + "条链表上");
System.out.println(emp);
} else {
System.out.println("没有该雇员");
}
}

// 散列函数,简单取模
public int hashFunction(int id) {
return id % size;
}
}

/**
* 链表
*/
class EmpLinkedList {
private Emp head;

/**
* 添加雇员(直接添加到末尾)
* @param emp 雇员
*/
public void addEmp(Emp emp) {
if (head == null) {
head = emp;
return;
}
// 查找最后一个节点
Emp cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = emp;
}

/**
* 按顺序添加雇员
* @param emp 雇员
*/
public void addEmpByOrder(Emp emp) {
if (head == null) {
head = emp;
return;
}
Emp cur = head;

while (cur != null) {

if (head.id > emp.id) { //比第一个节点还小,插入第一个
Emp temp = head;
head = emp;
emp.next = temp;
break;
} else if (cur.id == emp.id) {
System.out.println("编号为" + emp.id + "的节点已经存在");
break;
} else if (cur.next == null) {//末尾情况
cur.next = emp;
break;
} else if (cur.next.id > emp.id) { //中间的情况
emp.next = cur.next;
cur.next = emp;
break;
}
cur = cur.next;
}
}

/**
* 根据id删除雇员
* @param id 雇员id
*/
public void delEmpById(int id) {
if (head == null) {
System.out.println("该链表为空");
return;
}

Emp cur = head;
boolean flag = false; //是否找到该节点的标志
while (true) {

if (cur.next == null) {
break; //没有找到,退出
}

if (cur.next.id == id) {
//找到了
flag = true;
break;
}
cur = cur.next;
}

//删除
if (flag) {
cur.next = cur.next.next;
} else {
System.out.println("不存在该节点");
}
}

/**
* 遍历链表
*/
public void list() {
if (head == null) {
System.out.println("该链表为空");
return;
}
Emp cur = head;
while (true) {
System.out.println(cur);
if (cur.next == null) {
break;
}
cur = cur.next;
}

}

/**
* 根据id查询雇员
* @param id 雇员id
* @return 如果有则返回该雇员,否则返回null
*/
public Emp findEmpById(int id) {
if (head == null) {
System.out.println("链表为空");
return null;
}

Emp cur = head;
while (true) {
if (cur.id == id) {
break;
}

// 没有找到
if (cur.next == null) {
cur = null;
break;
}
cur = cur.next;
}
return cur;
}
}

/**
* 节点
*/
class Emp {
public int id;
public String name;
public Emp next;

public Emp(int id, String name) {
this.id = id;
this.name = name;
}

@Override
public String toString() {
return "Emp{" + "id=" + id + ", name='" + name + '\'' + '}';
}
}

延伸

    哈希表
    哈希表—什么是哈希表
    韩顺平数据结构和算法
    数据结构 Hash表(哈希表)
    Data Structure and Algorithms - Hash Table

Content
  1. 1. 前言
  2. 2. 哈希表
  3. 3. 延伸