散列表(Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
2. 雇员的管理系统[增删改查]google 公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工 的 id 时,要求查找到该员工的所有信息.
要求:
1) 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)
2) 添加时，保证按照雇员的 id 从低到高插入
2.1. 思路
1) 使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息]
2) 思路分析并画出示意图
2.2. 实现
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
package main
import "fmt"
type Emp struct {
Id int
Name string
Next *Emp //链表连接
}
func (this *Emp) ShowMe() {
fmt.Printf("id:%d,姓名:%s\n", this.Id, this.Name)
}
func (this *Emp) UpdateMe(name string) {
this.Name = name
}
type Emplink struct {
Head *Emp //头指针，指向链表
}
//插入方法2 -- 单一
func (this *Emplink) Insert(emp *Emp) {
if this.Head == nil {
//证明目前暂时没有节点，直接添加即可
this.Head = emp
} else {
//此时证明有成员，需要进行插入
//需要根据大小插入
tail := this.Head //第一个雇员节点
head := tail.Next //下一个雇员节点
if tail.Id >= emp.Id {
//第一个雇员节点都比他大，证明他是最小的，放在第一位
this.Head = emp
emp.Next = tail
} else {
for {
if head == nil || head.Id >= emp.Id {
//此时到了链表最后或者找到了插入位置
break
}
tail = head
head = head.Next
}
tail.Next = emp
emp.Next = head
}
}
}
//单一显示
func (this *Emplink) Show(i int) {
if this.Head == nil {
//链表为空
fmt.Printf("链表 %d 为空", i)
} else {
head := this.Head
fmt.Printf("链表 %d 信息: ", i)
for {
fmt.Printf("编号:%d , 姓名:%s -->", head.Id, head.Name)
head = head.Next
if head == nil {
break
}
}
}
fmt.Println()
}
//根据ID查找
func (this *Emplink) FindById(id int) *Emp {
if this.Head == nil {
return nil
} else {
head := this.Head
for {
if head.Id == id {
return head
}
head = head.Next
if head == nil {
break
}
}
return nil
}
}
//根据ID删除
func (this *Emplink) DeleteById(id int) bool {
if this.Head == nil {
//没有成员，无法删除
return false
} else {
//给2个指针，开始查找
head := this.Head
tail := head
if head.Id == id {
//如果第一个就是，直接处理
this.Head = head.Next
return true
}
for {
if head.Next == nil {
//没有找到，直接退出
return false
}
if head.Next.Id == id {
break
}
head = head.Next
tail = head
}
//走到这里说明找到了
tail.Next = head.Next.Next
return true
}
}
type Hashtable struct {
LinkArr [7]Emplink //结构体数组
}
//插入方法1
func (this *Hashtable) Insert1(emp *Emp) {
//根据哈希算法，找到数组下标
linkNo := this.HashFun(emp.Id)
emplink := this.LinkArr[linkNo]
if emplink.Head == nil {
//证明目前暂时没有节点，直接添加即可
emplink.Head = emp
} else {
//此时证明有成员，需要进行插入
//需要根据大小插入
tail := emplink.Head //第一个雇员节点
head := tail.Next //下一个雇员节点
if tail.Id >= emp.Id {
//第一个雇员节点都比他大，证明他是最小的，放在第一位
emplink.Head = emp
emp.Next = tail
} else {
for {
if head == nil || head.Id >= emp.Id {
//此时到了链表最后或者找到了插入位置
break
}
tail = head
head = head.Next
}
tail.Next = emp
emp.Next = head
}
}
//因为结构体数组本质还是结构体，结构体是值传递，上面修改不会影响当前值，所以要重新赋值一次。
this.LinkArr[linkNo] = emplink
}
//插入方法2 -- 所有
func (this *Hashtable) Insert2(emp *Emp) {
//根据哈希算法，找到数组下标
linkNo := this.HashFun(emp.Id)
this.LinkArr[linkNo].Insert(emp)
}
//显示所有
func (this *Hashtable) ShowAll() {
for i := 0; i < len(this.LinkArr); i++ {
this.LinkArr[i].Show(i)
}
}
func (this *Hashtable) HashFun(id int) int {
return id % len(this.LinkArr)
}
//根据ID查找
func (this *Hashtable) FindById(id int) *Emp {
linkNo := this.HashFun(id)
return this.LinkArr[linkNo].FindById(id)
}
//根据ID删除
func (this *Hashtable) DeleteById(id int) bool {
linkNo := this.HashFun(id)
return this.LinkArr[linkNo].DeleteById(id)
}
func main() {
key := ""
id := 0
name := ""
var hashtable Hashtable
for {
fmt.Println("===============雇员系统菜单============")
fmt.Println("input 表示添加雇员")
fmt.Println("show 表示显示雇员")
fmt.Println("find 表示查找雇员")
fmt.Println("edit 表示修改雇员")
fmt.Println("del 表示删除雇员")
fmt.Println("exit 表示退出系统")
fmt.Println("请输入你的选择")
fmt.Scanln(&key)
switch key {
case "input":
fmt.Println("输入雇员 id")
fmt.Scanln(&id)
fmt.Println("输入雇员 name")
fmt.Scanln(&name)
emp := &Emp{
Id: id,
Name: name}
hashtable.Insert2(emp)
case "show":
hashtable.ShowAll()
case "find":
fmt.Println("输入雇员 id")
fmt.Scanln(&id)
emp := hashtable.FindById(id)
if emp == nil {
fmt.Printf("对不起，没有找到id为 %d 的雇员\n", id)
} else {
emp.ShowMe()
}
case "edit":
fmt.Println("输入要修改的雇员 id")
fmt.Scanln(&id)
fmt.Println("输入要修改雇员name的值")
fmt.Scanln(&name)
emp := hashtable.FindById(id)
if emp == nil {
fmt.Printf("对不起，没有找到id为 %d 的雇员\n", id)
} else {
emp.UpdateMe(name)
}
case "del":
fmt.Println("输入要删除的雇员 id")
fmt.Scanln(&id)
ok := hashtable.DeleteById(id)
if !ok {
fmt.Printf("对不起，没有找到id为 %d 的雇员\n", id)
} else {
fmt.Printf("删除id为 %d 的雇员 成功\n", id)
}
case "exit":
default:
fmt.Println("输入错误")
}
}
}