2001 -- 12 --31
华中科技大学计算机学院 (11)数据结构
9.3 哈希 (Hash)表和 哈希法常用连续存储单元存储数据元素的查找表有两种：
（ 1） 顺序表,对 数据元素的存储一般有两 种形式：
(a) 是按到来次序 连续存放,则查找时使用顺序查找法；
(b) 二是按关键字的相对关系整理后以递增或递减形式 连续存放,则查找时使用顺序查找法和二分查找法。
（ 2）哈希表：存储数据元素时，利用一个 Hash函数根据数据元素的关键字计算出该数据元素的存储位置，查找时，也是根据给定的数据元素的关键字计算出该数据元素可能存储位置，这样一来，存储和查找的效率相当高，
哈希表也称为 散列表,其数据元素的存储一般是不连续的。 通过 Hash函数计算出的地址称为 哈希地址或散列地址 。
9.3.1 根据设定的 哈希函数 H(k)和处理冲突 的 方法,
Hash函数实现的是 将一组关键字映象到一个有限的地址区间上,
理想的情况是不同的关键字得到不同的地址 。
设 K1和 K2为 关键字,若 K1≠K 2,H(K1)=H(K2),则称
K1,K2为 同义词,K2与 K1为发生了 冲突例 设 H(k)=k%17
k1=5 k2=22
∵ H(5)=5%17=5 H(22)=22%17=5
H(5)=H(22)=5
∴ 5和 22是同义词,5和 22发生冲突例 1 人口统计表
1 10.5
2 12.6
3 11.0
4 20.8
...,..
150,..
序号
(地址 ) 年 龄 人 数 (万 )
1
2
3
4
150
H(key)=key = 地址
H(年龄） = 年龄
key
9.3.2 构造哈希函数的方法
1.直接定址法取关键字或关键字的某个线性函数值为哈希地址
H(key)=key
H(key)=a.key+b
例 2 学生成绩表
200041 刘大海 男 80 75
200042 王 伟 男 90 83
200043 吴晓英 女 82 88
200044 王 伟 女 80 90
......,....,..,.,.
......,....,..,.,.
1
2
3
4
n
key
序号
(地址 )学 号 姓 名 性别 数学 外语
H(key) = key - 200040 = 地址
H(学号 )= 学号 - 200040
例 3 标识符表
ABC
CAD
DAT
FOX
YAB
ZOO
1
2
3
4
5
6
25
26
序号 标识符 (key)
H(key)=key的第一个字母在字母表中的序号
key =ABC CAD DAT FOX YAB ZOO
H(key)=1 3 4 6 25 26
2.除留余数法设 哈希表 HT[0..m-1]的 表长为 m,哈希地址为 key
除以 p所的的余数：
H(key)=key MOD p //PASCAL语言
H(key)=key % p //C语言其中,MOD,%为,取模,或,求余,
p<=m,p为接近 m的质数 (素数 ),如：
3,5,7,11,13,17,19,23,29,31,37......
或不包含小于 20的质因子的合数,如：
713(=23*31)
例 1 设 m=130,取 p=127,H(key)=key % 127
0 1 2,...,129
例 2 设 m=256 取 p=251 H(key)=key % 251
0 1 2,...,255
例 设 哈希表 的地址范围为 0～ 20,哈希函数为 H(K)=K % 19
输入关键字序列,39,22,21,37,36,38,19,解决冲突的方法为 线性探测再散列 (哈希 ),构造 哈希表 HT[0..20]。
38
39
21
22
19
36
37
关键字 K H(K)=K%19
39 39%19=1
22 22%19=3
21 21%19=2
37 37%19=18
36 36%19=17
38 38%19=0
19 19%19=0
19与 38冲突,再与 39,21,
22冲突,存入 HT[4]
0
1
2
3
4
5
17
18
19
20
HT[0..20]
key
38
39
21
22
19
55
36
37
17
56
再输入 17,56,55
17%19=17
17与 36冲突,再与 37冲突,存入
HT[19]。
56%19=18
56与 37冲突,再与 17冲突,存入
HT[20]。
55%19=17
55与 36冲突,再与 37,17,56冲突,再与 38,39,21,22,19冲突,存入 HT[5]。
对于 H(k)=k % 19,所有的 19a+b为同义词,0≤ b≤19
如,5,24,43,62,81,.....
0
1
2
3
4
5
17
18
19
20
HT[0..20]
key
3.平方取中法 ----取关键字平方后的中间某几位为哈希地址,即：
H(k)=取 k2的 中间某几位数字例,设 哈希表为 HT[0..99],哈希函数为：
H(K)=取 k2的 中间 2位 数,输入关键字序列,39,21,6,36,38,13,用线性探测再散列法解决冲突,构造 HT[0..99]。
K k2 H(K)
39 1521 52
21 0441 44
6 0036 03
36 1296 29
38 1444 44
13 0169 16
6
13
36
21
38
39
0
3
16
29
44
45
52
99
key
4.折叠法将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为哈希地址 。
(1)边界 折叠法设表地址范围为 0～ 999
● k1=056439527
650 + 439 + 725 =1814
H(k1)=814
● k2=123486790
321 + 486 + 097 =907
H(k2)=907
● k3=300600007
003 + 600 + 700 =1303
H(k2)=303
300600007
056439527
123486790
0
1
303
814
907
999
HT[0.,999]
4.折叠法将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为哈希地址 。
(2)移位 折叠法 (移位 法 )
设表地址范围为 0～ 999
● k1=056439527
056 + 439 + 527 =1022
H(k1)=022
● k2=123486790
123 + 486 + 790 =1399
H(k2)=399
● k3=300600007
300 + 600 + 007 =907
H(k2)=907
056439527
123486790
300600007
0
1
22
399
907
999
HT[0.,999]
5.数字分析法设哈希表中可能出现的关键字都是事先知道的,则可取关键字的 若干分布均匀的位组成哈希地址 。
k H(k)
9020067 206
9044313 431
9013456 145
9044326 432
9053243 524
9061791 679
9013456
9020067
9044313
9044326
9053243
9061791
145
206
431
432
524
679
HT[0..999]
6.随机数法
H(key)=random(key)
random(key)为产生伪随机数的函数
7.灵活构造哈希函数例,设 哈希表为 HT[0..40],哈希函数为：
H(K)=取 k2的 中间 2位 数 *40/99
其中 40/99将其 00～ 99压缩到 00～ 40之内，
输入关键字序列,39,21,6,36,38,13,
用 线性探测再散列 法解决冲突。
K k2 H(K)
39 1521 52*40/99=21
21 0441 44*40/99=17
6 0036 03*40/99=1
77 5929 92*40/99=37
38 1444 44*40/99=17
13 0169 16*40/99=6
6
13
21
38
39
77
0
1
3
6
17
18
21
37
40
key
9.3.3 如何解决冲突
1.开放地址法 (开式寻址法 )
假定记录 Ri,RX的关键字 Ki,KX为同义词，散列地址为 q,Ri已存入 HT[0..m-1]中的 HT[q]中，则 RX 存入 HT中的某个空位上。
依次在地址 q+1,q+2,...,m-1,0,1,...,q-1中寻找一个空位，叫做线性探测再散列。
(1) 线性探测再散列
Ki,..
HT[0..m-1]
0
1
q-1
q
q+1
m-1
RiRX
课堂练习：设 H(k)=k的首字母在字母表中的序号,用线性探测再散列法解决冲突，依次用下列关键字，造哈希表 HT[0..28]。
k H(k)
A 1
DEC 4
ZMN 26
DAB 4
ZE 26
ANT 1
YY 25
ZOO 26
CAD 3
YES 25
ZY 26
LL 12
DE 4
0
1
2
3
4
5
6
7
12
13
25
26
27
28
HT[0..28]
1
2
3
4
5
6
7
8
9
10
11
12
13
例 设 H(k)=k的首字母在字母表中的序号,用线性探测再散列法解决冲突，依次用下列关键字，造哈希表 HT[0..28]。
YES
A
ANT
CAD
DEC
DAB
ZY
DE
LL
YY
ZMN
ZE
Z00
k H(k)
A 1
DEC 4
ZMN 26
DAB 4
ZE 26
ANT 1
YY 25
ZOO 26
CAD 3
YES 25
ZY 26
LL 12
DE 4
0
1
2
3
4
5
6
7
12
25
26
27
28
HT[0..28]
1
2
3
4
5
6
7
8
9
10
11
12
13
(2) 二次探测再散列假定记录 Ri和 Rj的关键字 Ki和 Kj为同义词，散列地址为 q,
Ri已存入 HT[0..m-1]中的 HT[q]中。
若依次在地址 q+12,q-12,q+22,q-22,...,q+i2,q-i2,...中寻找一个空位，叫做二次探测再散列。
例 设记录 X和 A为同义词，散列地址为 50,二次探测再散列的地址序列为,51,49,54,46,59,41,66,34,75,......
HT[0..99]
G E C A B D F
0 34 41 46 49 50 51 54 59 66 75 99
X X XXXXXX
HT[0..99]
G E C A B D F X
0 34 41 46 49 50 51 54 59 66 75 99
2.链地址法将关键字为同义词的所有记录存入同一链表中。
例 设 H(k)=k的首字母在字母表中的序号,用下列关键字造哈希表 HT[1..26]
k H(k)
A 1
DEC 4
ZMN 26
DAB 4
ZE 26
ANT 1
YY 25
ZOO 26
CAD 3
YES 25
ZY 26
LL 12
DE 4
1
2
3
4
5
6
7
8
9
10
11
12
13
∧
∧
∧
∧
HT[1..26]
ZEZOOZY ZMN ∧
DE
YES YY ∧
CAD ∧
ANT A ∧
DAB DEC ∧
LL ∧
1
2
3
4
12
25
26
2.链地址法将关键字为同义的所有记录存入同一链表中。
例 设 H(k)=k的首字母在字母表中的序号,用下列关键字造哈希表 HT[1..26]
k H(k)
A 1
DEC 4
ZMN 26
DAB 4
ZE 26
ANT 1
YY 25
ZOO 26
CAD 3
YES 25
ZY 26
LL 12
DE 4
1
2
3
4
5
6
7
8
9
10
11
12
13
HT[1..26]
ZOOZEZMN ZY ∧
DEC
YY YES ∧
CAD ∧
A ANT ∧
DAB DE ∧
LL ∧
∧
∧
∧
∧
1
2
3
4
12
25
26
3.建立公共溢出区将发生冲突的所有记录存入一个 公共溢出表 OT[0..v]中。
例 设 H(k)=k的首字母在字母表中的序号,用下列关键字生成基本表 HT[1..26]和溢出表 OT[0..50]
k H(k)
A 1
DEC 4
ZMN 26
DAB 4
ZE 26
ANT 1
YY 25
ZOO 26
CAD 3
YES 25
ZY 26
LL 12
DE 4
1
2
3
4
5
6
7
8
9
10
11
12
13
A
CAD
DEC
LL
YY
ZMN
HT[1..26]
1
2
3
4
12
25
26
DAB
ZE
ANT
ZOO
YES
ZY
DE
OT[0..50]
1
2
3
4
5
6
7
50
4.再哈希法发生冲突时，使用下一个哈希函数计算哈希地址,
j1=H1(K)； j2=H2(K)； j3=H3(K)；,.....
9.3.4 哈希表的查找及其分析
∧
∧
∧
∧
ZEZOOZY ZMN ∧
DE
YES YY ∧
CAD ∧
ANT A ∧
DAB DEC ∧
LL ∧
例 1 假定每个记录的查找概率相等，查找成功时的平均查找长度：
ASL=(1+2+1+1+2+3+1+1+2+
1+2+3+4)/13
= 24/13
≈ 1.85
例 2 假定每个记录的查找概率相等，
查找成功时的平均查找长度,
关键字 K H(K) 比较次数
YES 25 5
A 1 1
ANT 1 2
CAD 3 1
DEC 4 1
DAB 4 2
ZY 26 10
DE 4 4
LL 12 1
YY 25 1
ZMN 26 1
ZE 26 2
Z00 26 3
合计 34
ASL=34/13≈ 2.62
YES
A
ANT
CAD
DEC
DAB
ZY
DE
LL
YY
ZMN
ZE
Z00
HT[0..28]
0
1
2
3
4
5
6
7
12
13
25
26
27
28
家庭作业
1.顺序查找 1000个记录的顺序表,当使用监视哨时,若查找成功,比较关键字的 次数最少 是多少？最多是多少？
假定每个记录的查找概率相同,求查找成功时的平均查找长度 ASL。
2.折半查找 22个记录的有序表,若查找成功,比较关键字的次数最少 是多少？最多是多少？
假定每个记录的查找概率相同,求查找成功时的 ASL；
画出对应的判定树。
3.对长度为 800的表采用分块查找,最理想的块长是多少？
假定每个记录的查找概率相同,试求查找成功时的 ASL。
4.试按表 (13,06,04,12,20,05,02,26)中元素的排列次序,
生成一棵 二叉排序树,
(1)画出二叉排序树；
(2)对该树进行中序遍历,写出中序遍历序列；
(3)假定每个结点的查找概率相等,求查找成功时的 ASL。
5.设哈希 (Hash)函数为,H(k)=k%14,其中 k为关键字,%为取模运算，用线性探测再散列法处理冲突,在地址范围为 0～ 15的散列区 中,试用关键字序列 (19,27,26,28,29,40,64,21,15,12,
42,41)造一个哈希表,
(1)画出该哈希表的存储结构图；
(2)若查找关键字 40,必须依次与表中哪些关键字比较大小?
(3)假定每个关键字的查找概率相同,试求查找成功时的 ASL。
华中科技大学计算机学院 (11)数据结构
9.3 哈希 (Hash)表和 哈希法常用连续存储单元存储数据元素的查找表有两种：
（ 1） 顺序表,对 数据元素的存储一般有两 种形式：
(a) 是按到来次序 连续存放,则查找时使用顺序查找法；
(b) 二是按关键字的相对关系整理后以递增或递减形式 连续存放,则查找时使用顺序查找法和二分查找法。
（ 2）哈希表：存储数据元素时，利用一个 Hash函数根据数据元素的关键字计算出该数据元素的存储位置，查找时，也是根据给定的数据元素的关键字计算出该数据元素可能存储位置，这样一来，存储和查找的效率相当高，
哈希表也称为 散列表,其数据元素的存储一般是不连续的。 通过 Hash函数计算出的地址称为 哈希地址或散列地址 。
9.3.1 根据设定的 哈希函数 H(k)和处理冲突 的 方法,
Hash函数实现的是 将一组关键字映象到一个有限的地址区间上,
理想的情况是不同的关键字得到不同的地址 。
设 K1和 K2为 关键字,若 K1≠K 2,H(K1)=H(K2),则称
K1,K2为 同义词,K2与 K1为发生了 冲突例 设 H(k)=k%17
k1=5 k2=22
∵ H(5)=5%17=5 H(22)=22%17=5
H(5)=H(22)=5
∴ 5和 22是同义词,5和 22发生冲突例 1 人口统计表
1 10.5
2 12.6
3 11.0
4 20.8
...,..
150,..
序号
(地址 ) 年 龄 人 数 (万 )
1
2
3
4
150
H(key)=key = 地址
H(年龄） = 年龄
key
9.3.2 构造哈希函数的方法
1.直接定址法取关键字或关键字的某个线性函数值为哈希地址
H(key)=key
H(key)=a.key+b
例 2 学生成绩表
200041 刘大海 男 80 75
200042 王 伟 男 90 83
200043 吴晓英 女 82 88
200044 王 伟 女 80 90
......,....,..,.,.
......,....,..,.,.
1
2
3
4
n
key
序号
(地址 )学 号 姓 名 性别 数学 外语
H(key) = key - 200040 = 地址
H(学号 )= 学号 - 200040
例 3 标识符表
ABC
CAD
DAT
FOX
YAB
ZOO
1
2
3
4
5
6
25
26
序号 标识符 (key)
H(key)=key的第一个字母在字母表中的序号
key =ABC CAD DAT FOX YAB ZOO
H(key)=1 3 4 6 25 26
2.除留余数法设 哈希表 HT[0..m-1]的 表长为 m,哈希地址为 key
除以 p所的的余数：
H(key)=key MOD p //PASCAL语言
H(key)=key % p //C语言其中,MOD,%为,取模,或,求余,
p<=m,p为接近 m的质数 (素数 ),如：
3,5,7,11,13,17,19,23,29,31,37......
或不包含小于 20的质因子的合数,如：
713(=23*31)
例 1 设 m=130,取 p=127,H(key)=key % 127
0 1 2,...,129
例 2 设 m=256 取 p=251 H(key)=key % 251
0 1 2,...,255
例 设 哈希表 的地址范围为 0～ 20,哈希函数为 H(K)=K % 19
输入关键字序列,39,22,21,37,36,38,19,解决冲突的方法为 线性探测再散列 (哈希 ),构造 哈希表 HT[0..20]。
38
39
21
22
19
36
37
关键字 K H(K)=K%19
39 39%19=1
22 22%19=3
21 21%19=2
37 37%19=18
36 36%19=17
38 38%19=0
19 19%19=0
19与 38冲突,再与 39,21,
22冲突,存入 HT[4]
0
1
2
3
4
5
17
18
19
20
HT[0..20]
key
38
39
21
22
19
55
36
37
17
56
再输入 17,56,55
17%19=17
17与 36冲突,再与 37冲突,存入
HT[19]。
56%19=18
56与 37冲突,再与 17冲突,存入
HT[20]。
55%19=17
55与 36冲突,再与 37,17,56冲突,再与 38,39,21,22,19冲突,存入 HT[5]。
对于 H(k)=k % 19,所有的 19a+b为同义词,0≤ b≤19
如,5,24,43,62,81,.....
0
1
2
3
4
5
17
18
19
20
HT[0..20]
key
3.平方取中法 ----取关键字平方后的中间某几位为哈希地址,即：
H(k)=取 k2的 中间某几位数字例,设 哈希表为 HT[0..99],哈希函数为：
H(K)=取 k2的 中间 2位 数,输入关键字序列,39,21,6,36,38,13,用线性探测再散列法解决冲突,构造 HT[0..99]。
K k2 H(K)
39 1521 52
21 0441 44
6 0036 03
36 1296 29
38 1444 44
13 0169 16
6
13
36
21
38
39
0
3
16
29
44
45
52
99
key
4.折叠法将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为哈希地址 。
(1)边界 折叠法设表地址范围为 0～ 999
● k1=056439527
650 + 439 + 725 =1814
H(k1)=814
● k2=123486790
321 + 486 + 097 =907
H(k2)=907
● k3=300600007
003 + 600 + 700 =1303
H(k2)=303
300600007
056439527
123486790
0
1
303
814
907
999
HT[0.,999]
4.折叠法将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为哈希地址 。
(2)移位 折叠法 (移位 法 )
设表地址范围为 0～ 999
● k1=056439527
056 + 439 + 527 =1022
H(k1)=022
● k2=123486790
123 + 486 + 790 =1399
H(k2)=399
● k3=300600007
300 + 600 + 007 =907
H(k2)=907
056439527
123486790
300600007
0
1
22
399
907
999
HT[0.,999]
5.数字分析法设哈希表中可能出现的关键字都是事先知道的,则可取关键字的 若干分布均匀的位组成哈希地址 。
k H(k)
9020067 206
9044313 431
9013456 145
9044326 432
9053243 524
9061791 679
9013456
9020067
9044313
9044326
9053243
9061791
145
206
431
432
524
679
HT[0..999]
6.随机数法
H(key)=random(key)
random(key)为产生伪随机数的函数
7.灵活构造哈希函数例,设 哈希表为 HT[0..40],哈希函数为：
H(K)=取 k2的 中间 2位 数 *40/99
其中 40/99将其 00～ 99压缩到 00～ 40之内，
输入关键字序列,39,21,6,36,38,13,
用 线性探测再散列 法解决冲突。
K k2 H(K)
39 1521 52*40/99=21
21 0441 44*40/99=17
6 0036 03*40/99=1
77 5929 92*40/99=37
38 1444 44*40/99=17
13 0169 16*40/99=6
6
13
21
38
39
77
0
1
3
6
17
18
21
37
40
key
9.3.3 如何解决冲突
1.开放地址法 (开式寻址法 )
假定记录 Ri,RX的关键字 Ki,KX为同义词，散列地址为 q,Ri已存入 HT[0..m-1]中的 HT[q]中，则 RX 存入 HT中的某个空位上。
依次在地址 q+1,q+2,...,m-1,0,1,...,q-1中寻找一个空位，叫做线性探测再散列。
(1) 线性探测再散列
Ki,..
HT[0..m-1]
0
1
q-1
q
q+1
m-1
RiRX
课堂练习：设 H(k)=k的首字母在字母表中的序号,用线性探测再散列法解决冲突，依次用下列关键字，造哈希表 HT[0..28]。
k H(k)
A 1
DEC 4
ZMN 26
DAB 4
ZE 26
ANT 1
YY 25
ZOO 26
CAD 3
YES 25
ZY 26
LL 12
DE 4
0
1
2
3
4
5
6
7
12
13
25
26
27
28
HT[0..28]
1
2
3
4
5
6
7
8
9
10
11
12
13
例 设 H(k)=k的首字母在字母表中的序号,用线性探测再散列法解决冲突，依次用下列关键字，造哈希表 HT[0..28]。
YES
A
ANT
CAD
DEC
DAB
ZY
DE
LL
YY
ZMN
ZE
Z00
k H(k)
A 1
DEC 4
ZMN 26
DAB 4
ZE 26
ANT 1
YY 25
ZOO 26
CAD 3
YES 25
ZY 26
LL 12
DE 4
0
1
2
3
4
5
6
7
12
25
26
27
28
HT[0..28]
1
2
3
4
5
6
7
8
9
10
11
12
13
(2) 二次探测再散列假定记录 Ri和 Rj的关键字 Ki和 Kj为同义词，散列地址为 q,
Ri已存入 HT[0..m-1]中的 HT[q]中。
若依次在地址 q+12,q-12,q+22,q-22,...,q+i2,q-i2,...中寻找一个空位，叫做二次探测再散列。
例 设记录 X和 A为同义词，散列地址为 50,二次探测再散列的地址序列为,51,49,54,46,59,41,66,34,75,......
HT[0..99]
G E C A B D F
0 34 41 46 49 50 51 54 59 66 75 99
X X XXXXXX
HT[0..99]
G E C A B D F X
0 34 41 46 49 50 51 54 59 66 75 99
2.链地址法将关键字为同义词的所有记录存入同一链表中。
例 设 H(k)=k的首字母在字母表中的序号,用下列关键字造哈希表 HT[1..26]
k H(k)
A 1
DEC 4
ZMN 26
DAB 4
ZE 26
ANT 1
YY 25
ZOO 26
CAD 3
YES 25
ZY 26
LL 12
DE 4
1
2
3
4
5
6
7
8
9
10
11
12
13
∧
∧
∧
∧
HT[1..26]
ZEZOOZY ZMN ∧
DE
YES YY ∧
CAD ∧
ANT A ∧
DAB DEC ∧
LL ∧
1
2
3
4
12
25
26
2.链地址法将关键字为同义的所有记录存入同一链表中。
例 设 H(k)=k的首字母在字母表中的序号,用下列关键字造哈希表 HT[1..26]
k H(k)
A 1
DEC 4
ZMN 26
DAB 4
ZE 26
ANT 1
YY 25
ZOO 26
CAD 3
YES 25
ZY 26
LL 12
DE 4
1
2
3
4
5
6
7
8
9
10
11
12
13
HT[1..26]
ZOOZEZMN ZY ∧
DEC
YY YES ∧
CAD ∧
A ANT ∧
DAB DE ∧
LL ∧
∧
∧
∧
∧
1
2
3
4
12
25
26
3.建立公共溢出区将发生冲突的所有记录存入一个 公共溢出表 OT[0..v]中。
例 设 H(k)=k的首字母在字母表中的序号,用下列关键字生成基本表 HT[1..26]和溢出表 OT[0..50]
k H(k)
A 1
DEC 4
ZMN 26
DAB 4
ZE 26
ANT 1
YY 25
ZOO 26
CAD 3
YES 25
ZY 26
LL 12
DE 4
1
2
3
4
5
6
7
8
9
10
11
12
13
A
CAD
DEC
LL
YY
ZMN
HT[1..26]
1
2
3
4
12
25
26
DAB
ZE
ANT
ZOO
YES
ZY
DE
OT[0..50]
1
2
3
4
5
6
7
50
4.再哈希法发生冲突时，使用下一个哈希函数计算哈希地址,
j1=H1(K)； j2=H2(K)； j3=H3(K)；,.....
9.3.4 哈希表的查找及其分析
∧
∧
∧
∧
ZEZOOZY ZMN ∧
DE
YES YY ∧
CAD ∧
ANT A ∧
DAB DEC ∧
LL ∧
例 1 假定每个记录的查找概率相等，查找成功时的平均查找长度：
ASL=(1+2+1+1+2+3+1+1+2+
1+2+3+4)/13
= 24/13
≈ 1.85
例 2 假定每个记录的查找概率相等，
查找成功时的平均查找长度,
关键字 K H(K) 比较次数
YES 25 5
A 1 1
ANT 1 2
CAD 3 1
DEC 4 1
DAB 4 2
ZY 26 10
DE 4 4
LL 12 1
YY 25 1
ZMN 26 1
ZE 26 2
Z00 26 3
合计 34
ASL=34/13≈ 2.62
YES
A
ANT
CAD
DEC
DAB
ZY
DE
LL
YY
ZMN
ZE
Z00
HT[0..28]
0
1
2
3
4
5
6
7
12
13
25
26
27
28
家庭作业
1.顺序查找 1000个记录的顺序表,当使用监视哨时,若查找成功,比较关键字的 次数最少 是多少？最多是多少？
假定每个记录的查找概率相同,求查找成功时的平均查找长度 ASL。
2.折半查找 22个记录的有序表,若查找成功,比较关键字的次数最少 是多少？最多是多少？
假定每个记录的查找概率相同,求查找成功时的 ASL；
画出对应的判定树。
3.对长度为 800的表采用分块查找,最理想的块长是多少？
假定每个记录的查找概率相同,试求查找成功时的 ASL。
4.试按表 (13,06,04,12,20,05,02,26)中元素的排列次序,
生成一棵 二叉排序树,
(1)画出二叉排序树；
(2)对该树进行中序遍历,写出中序遍历序列；
(3)假定每个结点的查找概率相等,求查找成功时的 ASL。
5.设哈希 (Hash)函数为,H(k)=k%14,其中 k为关键字,%为取模运算，用线性探测再散列法处理冲突,在地址范围为 0～ 15的散列区 中,试用关键字序列 (19,27,26,28,29,40,64,21,15,12,
42,41)造一个哈希表,
(1)画出该哈希表的存储结构图；
(2)若查找关键字 40,必须依次与表中哪些关键字比较大小?
(3)假定每个关键字的查找概率相同,试求查找成功时的 ASL。
