数据结构32-33
上一篇 /
下一篇 2010-07-04 21:11:43
第三十二课
本课主题： 哈希表（一）
教学目的： 掌握哈希表的概念作用及意义，哈希表的构造方法
教学重点： 哈希表的构造方法
教学难点： 哈希表的构造方法
授课内容：
一、哈希表的概念及作用
一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录
的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比
较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。
理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和
它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。
哈希表最常见的例子是以学生学号为关键字的成绩表，１号学生的记
录位置在第一条，１０号学生的记录位置在第１０条...
如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以
直接找到相应记录呢？
|
a
|
b
|
c
|
d
|
e
|
f
|
g
|
h
|
i
|
j
|
k
|
l
|
m
|
n
|
o
|
p
|
q
|
r
|
s
|
t
|
u
|
v
|
w
|
x
|
y
|
z
|
|
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
|
|
|
刘丽
|
刘宏英
|
吴军
|
吴小艳
|
李秋梅
|
陈伟
|
...
|
|
姓名中各字拼音首字母
|
ll
|
lhy
|
wj
|
wxy
|
lqm
|
cw
|
...
|
|
用所有首字母编号值相加求和
|
24
|
46
|
33
|
72
|
42
|
26
|
...
|
|
最小值可能为3
最大值可能为78 可放75个学生
|
用上述得到的数值作为对应记录在表中的位置，得到下表：
|
|
|
成绩一
|
成绩二...
|
|
3
|
...
|
|
|
|
...
|
...
|
|
|
|
24
|
刘丽
|
82
|
95
|
|
25
|
...
|
|
|
|
26
|
陈伟
|
|
|
|
...
|
...
|
|
|
|
33
|
吴军
|
|
|
|
...
|
...
|
|
|
|
42
|
李秋梅
|
|
|
|
...
|
...
|
|
|
|
46
|
刘宏英
|
|
|
|
...
|
...
|
|
|
|
72
|
吴小艳
|
|
|
|
...
|
...
|
|
|
|
78
|
...
|
|
|
上面这张表即哈希表。
如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：
李秋梅:lqm
12+17+13=42 取表中第42条记录即可。
问题：如果两个同学分别叫
刘丽 刘兰 该如何处理这两条记录？
这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。
二、哈希表的构造方法
１、直接定址法
例如：有一个从1到
100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。
|
地址
|
01
|
02
|
...
|
25
|
26
|
27
|
...
|
100
|
|
年龄
|
1
|
2
|
...
|
25
|
26
|
27
|
...
|
...
|
|
人数
|
3000
|
2000
|
...
|
1050
|
...
|
...
|
...
|
...
|
|
...
|
|
|
|
|
|
|
|
|
２、数字分析法
有学生的生日数据如下：
年.月.日
75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15
...
经分析,第一位，第二
位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。
３、平方取中法
取关键字平方后的中间几位为哈希地址。
收藏
举报
TAG:
