1
? 静态索引结构
? 动态索引结构
? 散列
2
静态索引结构
? 示例,有一个存放职工信息的数据表,每一
个职工对象有近 1k 字节的信息,正好占据一
个页块的存储空间 。
? 假设内存工作区仅能容纳 64k 字节的数据,
在某一时刻内存最多可容纳 64 个对象以供
搜索。
当数据对象个数 n 很大时,可采用索引方法
来实现存储和搜索。
线性索引 (Linear Index List)
3
0
1k
2k
3k
4k
5k
6k
7k
key addr
03 2k
08 1k
17 6k
24 4k
47 5k
51 7k
83 0
95 3k
职工号 姓名 性别 职务 婚否
83 张珊 女 教师 已婚 …
08 李斯 男 教师 已婚,..
03 王鲁 男 教务员 已婚,..
95 刘琪 女 实验员 未婚,..
24 岳跋 男 教师 已婚,..
47 周斌 男 教师 已婚,..
17 胡江 男 实验员 未婚,..
51 林青 女 教师 未婚,..
索引表 数据表
4
? 如果对象总数有 14400 个,不可能把所有对
象的数据一次都读入内存 。 无论是顺序搜
索或折半搜索,都需要多次读取外存记录 。
? 如果在索引表中每一个索引项占 4 个字节,
索引项给出一个职工对象的 关键码 及其 存
储地址,用以索引一个职工对象,则 14400
个索引项需要 56.25k 字节,在内存中可以容
纳所有的索引项 。
? 这样只需从外存中把索引表读入内存,经过
搜索索引后确定了职工对象的存储地址,再
经过 1 次读取对象操作就可以完成搜索 。
5
? 稠密索引,一个索引项对应数据表中一个对
象的索引结构 。 当对象在外存中 按加入顺序
存放而不是按关键码有序存放 时必须采用 稠
密索引 结构, 这时的索引结构叫做索引非顺
序结构 。
? 稀疏索引,当对象在外存中有序存放时, 可
以把所有 n 个对象分为 b 个子表 (块 )存放,
一个索引项对应数据表中一组对象 (子表 )。
? 第 i 个索引项是第 i 个子表的索引项,i = 0,
1,…,n-1。 这种索引结构叫做 索引顺序结构 。
6
? 对索引顺序结构进行搜索时，一般分为两级
搜索,
? 先在 索引表 ID 中搜索给定值 K,确定满足
ID[i-1].max_key < K ? ID[i].max_key
22 12 13 30 29 33
36 42 44 48 39 40
60 74 56 79 80 66
92 82 88 98 94
子表 1
子表 2
子表 3
子表 4
数据区
33
48
80
98
索引表
1
2
3
4
max_ max_
key addr
7
的 i 值,即待查对象可能在的子表的序号 。
? 然后再在第 i 个子表中按给定值搜索要求
的对象 。
? 索引表是按 max_key有序的,且长度也不大,
可以折半搜索, 也可以顺序搜索 。
? 各子表内各个对象如果也按对象关键码有序,
可以采用折半搜索或顺序搜索 ; 如果不是按
对象关键码有序,只能顺序搜索 。
8
? 索引顺序搜索的搜索成功时的平均搜索长度
ASLIndexSeq = ASLIndex + ASLSubList
? 其中,ASLIndex 是在索引表中搜索子表位臵的
平均搜索长度, ASLSubList 是在子表内搜索对
象位臵的搜索成功的平均搜索长度 。
? 设把长度为 n 的表分成均等的 b 个子表, 每
个子表 s 个对象, 则 b = ?n/s?。 又设表中每
个对象的搜索概率相等, 则每个子表的搜索
概率为 1/b,子表内各对象的搜索概率为 1/s。
? 若对 索引表 和 子表 都用 顺序搜索, 则索引顺
序搜索的搜索成功时的平均搜索长度为
ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1
9
? 索引顺序搜索的平均搜索长度与 表中的对象
个数 n 有关，与 每个子表中的对象个数 s 有
关。在给定 n 的情况下,s 应选择多大？
? 用数学方法可导出,当 s = 时,ASLIndexSeq
取极小值 +1。这个值比顺序搜索强，但
比折半搜索差。但如果子表存放在外存时，
还要受到页块大小的制约。
? 若采用折半搜索确定对象所在的子表,则搜
索成功时的平均搜索长度为
ASLIndexSeq = ASLIndex + ASLSubList
? log2 (b+1)-1 + (s+1)/2
? log2(1+n / s ) + s/2
n
n
10
m 路静态搜索树
? 当数据对象数目特别大，索引表本身很大，
在内存中放不下，需要分批多次读取外存才
能把索引表搜索一遍。
? 此时,可以建立索引的索引 (二级索引 )。二级
索引中一个索引项对应一个索引块，登记该
索引块的最大关键码及该索引块的存储地址。
? 如果二级索引在内存中也放不下，需要分为
许多块多次从外存读入。可以建立二级索引
的索引 (三级索引 )。这时，访问外存次数等
于读入索引次数再加上 1次读取对象。
11
? 必要时,还可以有 4级索引,5极索引,… 。
? 这种多级索引结构形成一种 m叉树。树中 每
一个分支结点表示一个索引块,每个索引项
给出各子树结点的 最大关键码 和 结点地址 。
02 06 11 15 18 23 29 32 38 41 45 49 52 60 77 95
(06,) (15,) (23,) (32,) (41,) (49,) (60,) (95,)
(23,) (49,) (95,)
root
head
12
? 树的叶结点中各索引项给出在数据表中存放
的对象的关键码和存放地址。这种 m叉树用
来作为多级索引，就是 m路搜索树。
? m路搜索树 可能是 静态索引结构,即结构在
初始创建，数据装入时就已经定型，在整个
运行期间，树的结构不发生变化。
? m路搜索树 还可能是 动态索引结构,即在整
个系统运行期间,树的结构随数据的增删及
时调整,以保持最佳的搜索效率。
13
多级索引结构形成 m 路搜索树
数据区
一级索引
二级索引
三级索引
四级索引
14
动态搜索结构
? 现在我们所讨论的 m 路搜索树多为可以动
态调整的多路搜索树, 它的一般定义为：
? 一棵 m 路搜索树,它或者是一棵空树,或者
是满足如下性质的树：
? 根最多有 m 棵子树,并具有如下的结构：
n,P0,K1,P1,K2,P2,……,Kn,Pn
其中,Pi 是指向子树的指针,0 ? i ? n < m; Ki
是关键码,1 ? i ? n < m。 Ki < Ki+1,1 ? i < n。
动态的 m 路搜索树
15
? 在子树 Pi 中所有的关键码都 小于 Ki+1,且
大于 Ki,0 < i < n。
? 在子树 Pn 中所有的关键码都 大于 Kn；
? 在子树 P0 中的所有关键码都 小于 K1。
? 子树 Pi 也是 m 路搜索树, 0 ? i ? n。
一棵 3路搜索树的示例
35
20 40a
b c d
e
25 3010 15 45 50
16
AVL树是 2路搜索树。若已知 m 路搜索树的
度 m 和它的 高度 h,则树中的 最大结点数 为
? ?1
1
1 1
0
?
?
? ?
?
? h
h
i
i m
m
m
(等比级数前 h 项求和 )
每个结点中 最多有 m-1 个关键码, 在一棵高
度为 h 的 m 路搜索树中关键码的最大个数为
mh+1-1。
? 高度 h=2 的二叉树,关键码最大个数为 7；
? 高度 h=3 的 3路搜索树,关键码最大个数为
34-1 = 80。
17
m 路搜索树上的搜索
? 在 m 路搜索树上的搜索过程是一个 在结点
内搜索 和 自根结点向下逐个结点搜索 的交
替的过程。
35
20 40a
b c d
e
25 3010 15 45 50
root
搜索 35
18
? 提高搜索树的路数 m,可以改善树的搜索
性能 。 对于给定的关键码数 n,如果搜索
树是平衡的, 可以使 m 路搜索树的性能接
近最佳 。 下面将讨论一种称之为 B 树的平
衡的 m 路搜索树 。
19
B 树
? 一棵 m 阶 B 树是一棵平衡的 m 路搜索树,它
或者是空树,或者是满足下列性质的树：
? 根结点至少有 2 个子女。
? 除根结点以外的所有结点 (不包括失败结
点 )至少有 ?m/2?个子女。
? 所有的失败结点都位于同一层。
? 在 B 树中的“失败”结点是当搜索值 x不在
树中时才能到达的结点。该层计入树的高度。
? 事实上，在 B 树的每个结点中还包含有一组
指针 D[m]，指向实际对象的存放地址。
20
30
? K[i]与 D[i] (1 ? i ? n < m) 形成一个 索引项
(K[i],D[i])，通过 K[i]可找到某个对象的存
储地址 D[i]。
? 一棵 B 树是平衡的 m 路搜索树，但一棵平
衡的 m 路搜索树不一定是 B 树。
35
20 40
25 3010 15 45 50
root
45 5035
4020
root
10 15 25
非 B 树 B 树
21
typedef int BTreeData;
typedef struct node { //B树结点的定义
int n; //结点中关键码个数
struct node *parent; //双亲指针
BTreeData key[m+1]; //关键码数组 1?m-1
struct node *ptr[m+1]; //子树指针数组 0?m-1
} BTreeNode;
typedef BTreeNode * BTree; //B树定义
B 树的定义和 B 树结点的定义
22
? B 树的搜索继承了 m 路搜索树的搜索 。
? B 树的搜索过程是一个在结点内搜索和循
某一条路径向下一层搜索交替进行的过程 。
? B 树的搜索时间与 B 树的阶数 m 和 B 树的
高度 h 直接有关。
? 在 B 树上进行搜索,搜索成功所需的时间取
决于关键码所在的层次 ; 搜索不成功所需的
时间取决于树的高度 。
B 树的搜索算法
23
? 设在 m 阶 B 树中每层结点个数达到最少,
则 B 树的高度可能达到最大。设树中关键
码个数为 N，从 B 树的定义知：
? 0层 1 个结点
? 1层 至少 2 个结点
? 2层 至少 2 ?m / 2?个结点
? 3层 至少 2 ?m / 2? 2 个结点
? 如此类推,??
? h-1 层 至少有 2 ?m / 2? h-2 个结点。所有
这些结点都不是失败结点。
高度 h与关键码个数 N之间的关系
24
? 若树中关键码有 N个,则失败结点数为 N+1。
这是因为失败数据一般与已有关键码交错
排列。因此，有
N +1 = 失败结点数 = 位于第 h 层结点数
? 2 ?m / 2? h-1
? N ? 2 ?m / 2? h-1-1
? h-1 ? log ?m / 2? ( (N +1) / 2 )
? 所有的非失败结点所在层次为 0 ? h-1。
? 示例：若 B 树的阶数 m = 199,关键码总数
N = 1999999，则 B 树的高度 h 不超过
log100 1000000 +1= 4
25
? 如果让 B 树每层结点个数达到最大，且设
关键码总数 为 N,则树的高度达到最小。
? 从高度为 h (根在第 0层 ) 的满 m叉树的性质
可知：
N +1 = 失败结点数 = 位于第 h 层结点数
? mh
h ? logm(N+1)
? 示例：若 B 树的阶数 m = 199,关键码总数
N = 1999999，则 B 树的高度 h 不低于
log199 2000000 = 2.74
26
B 树的插入
? B 树是从空树起,逐个插入关键码而生成的。
? 在 B 树，每个非失败结点的关键码个数都在
[ ?m/2?-1,m-1]
之间。
? 插入在 某个叶结点 开始。如果在关键码插入
后结点中的 关键码个数超出了上界 m-1，则
结点需要“分裂”，否则可以直接插入 。
? 实现结点“分裂”的原则是：
? 设结点 p 中已经有 m-1 个关键码，当再插
入一个关键码后结点中的状态为
27
( m,P0,K1,P1,K2,P2,……,Km,Pm)
其中 Ki < Ki+1,1 ? i < m
? 这时必须把结点 p 分裂成两个结点 p 和 q，
它们包含的信息分别为：
? 结点 p：
( ?m/2?-1,P0,K1,P1,……,K?m/2?-1,P?m/2?-1)
? 结点 q：
(m-?m/2?,P?m/2?,K?m/2?+1,P?m/2?+1,……,Km,Pm)
? 位于中间的关键码 K?m/2?与指向新结点 q 的
指针形成一个二元组 ( K?m/2?,q )，插入到这
两个结点的双亲结点中去。
28
结点“分裂”的示例
2 53 75
n P0 K1 P1 K2 P2
p
3 53 75 139
n P0 K1 P1 K2 P2 K3 P3
p
加入 139,
结点溢出
1 75
n P0 K1 P1
1 53
n P0 K1 P1
1 139
n P0 K1 P1
结点
分裂
P q
m = 3
29
49 75
示例,从空树开始加入关键码建立 3阶 B 树
n=1 加入 53
53
n=2 加入 75
53 75
n=3 加入 139
75
13953
n=5 加入 49,145
75
139 14549 53
n=6 加入 36
139 1455336
30
? 在插入新关键码时，需要自底向上分裂结
点，最坏情况下从被插关键码所在叶结点
到根的路径上的所有结点都要分裂。
若设 B 树的
高度为 h,那
么在 自顶向
下 搜索到 叶
结点 的过程
中需要进行
h 次读盘。
n=7 加入 101
49
5336
139
145101
75
31
B 树的删除
? 在 B 树上删除一个关键码时,首先需要找到
这个关键码所在的结点,从中删去这个关键
码。若该结点不是叶结点,且被删关键码为
Ki,1 ? i ? n,则在删去该关键码之后,应以该
结点 Pi 所指示子树中的最小关键码 x 来代
替被删关键码 Ki 所在的位臵,然后在 x 所在
的叶结点中删除 x。
? 在叶结点上的删除有 4 种情况。
① 被删关键码所在叶结点同时又是根结点且
删除前该结点中关键码个数 n ? 2，则直接
删去该关键码并将修改后的结点写回磁盘。
32
② 被删关键码所在叶结点不是根结点且删除前
该结点中关键码个数 n ??m/2?,则直接删去
该关键码并将修改后的结点写回磁盘,删除
结束。
③ 被删关键码所在叶结点删除前关键码个数 n
= ?m/2?-1,若这时与该结点相邻的右兄弟
(或左兄弟 )结点的关键码个数 n ??m/2?，则
可按以下步骤调整该结点、右兄弟 (或左兄
弟 ) 结点以及其双亲结点，以达到新的平衡。
36 49m = 3 删除 36 49
33
55 58
删除 55简单删除
75 80
m = 3
删除 55
10 40 65
60 7030
50a
cb
d e f g h
58 75 8010 40 65
60 7030
50a
cb
d e f g h
34
?将双亲结点中刚刚大于 (或小于 ) 该被删关
键码的关键码 Ki (1 ? i ? n) 下移；
?将右兄弟 (或左兄弟 ) 结点中的最小 (或最
大 )关键码上移到双亲结点的 Ki 位臵；
?将右兄弟 (或左兄弟 ) 结点中的最左 (或最
右 ) 子树指针平移到被删关键码所在结点
中最后 (或最前 ) 子树指针位臵；
?在右兄弟 (或左兄弟 ) 结点中，将被移走的
关键码和指针位臵用剩余的关键码和指针
填补、调整。再将结点中的关键码个数减
1。
35
结点联合调整
55 58 75 80
m = 3 删除 65
10 40 65
60 7030
50a
cb
d e f g h
55 58 8010 40 70
60 7530
50a
cb
d e f g h
调整 g,c,h
删除 65
36
70
删除 70
55 58 80
m = 3 删除 70
10 40
60 7530
50a
cb
d e f g h
55 8010 40 60
58 7530
50a
cb
d e f g h
调整 f,c,g
结点联合调整
37
④ 被删关键码所在叶结点删除前关键码个数
n = ?m/2?-1,若这时与该结点相邻的右兄弟
(或左兄弟 )结点的关键码个数 n = ?m/2?-1,
则必须按以下步骤合并这两个结点。
? 若要合并 p 中的子树指针 Pi 与 Pi+1 所指
的结点,且保留 Pi 所指结点,则把 p 中的关
键码 Ki+1下移到 Pi 所指的结点中。
? 把 p 中子树指针 Pi+1 所指结点中的全部
指针和关键码都照搬到 Pi 所指结点的后
面。删去 Pi+1 所指的结点。
38
? 在结点 p 中用后面剩余的关键码和指针填
补关键码 Ki+1 和指针 Pi+1。
? 修改结点 p 和选定保留结点的关键码个数。
? 在合并结点的过程中,双亲结点中的关键码个
数减少了。若双亲结点是根结点且结点关键
码个数减到 0,则将该双亲结点删去,合并后保
留的结点成为新的根结点 ; 否则将双亲结点与
合并后保留的结点都写回磁盘,删除处理结束。
? 若双亲结点不是根结点且关键码个数减到
?m/2?-2，又要与它自己的兄弟结点合并,重
复上面的合并步骤。最坏情况下这种结点合
并处理要自下向上直到根结点。
39
55
删除 55结点合并
80
m = 3 删除 55
10 40 60
58 7530
50a
cb
d e f g h
合并 f,g
58 60 8010 40
7530
50a
cb
d e f h
40
8055
删除 80结点合并
m = 3 删除 80
10 40 60
58 7530
50a
cb
d e f g h
合并 g,h
60 755510 40
5830
50a
cb
d e f g
41
55
非叶结点删除
删除 50
删除 55
55 58 75 80
m = 3 删除 50
10 40 65
60 7030
50a
cb
d e f g h
58 75 80
删除 55
10 40 65
60 7030
a
cb
d e f g h
用 55取代
用 58取代
42
58
75 8010 40 65
60 7030
a
cb
d e f g h
合并 f,g
58
75 8010 40 60 65
7030
a
cb
d e f h
结点合并与调整
删除 70
43
58
8010 40 60 65
7530
a
cb
d e f h
删除 70
用 75取代
删除 75
58
10 40 60 65
8030
a
cb
d e f h
删除 75
用 80取代
调整 f,c,h
44
58
8010 40 60
6530
a
cb
d e f h
删除 10
8030 40 60f h
58 65
d
b
45
散列 (Hashing)
? 散列方法在 表项存储位臵 与 其关键码 之间建
立一个 确定的对应函数关系 Hash( )，使每个
关键码与结构中一个唯一存储位臵相对应：
Address ＝ Hash ( Rec.key )
? 在搜索时,先对表项的关键码进行函数计算,
把函数值当做表项的存储位臵,在结构中按
此位臵取表项比较。若关键码相等,则搜索
成功。在存放表项时,依相同函数计算存储
位臵,并按此位臵存放。这种方法就是散列
方法。
46
? 在散列方法中使用的转换函数叫做 散列函数 。
按此方法构造出来的表或结构就叫做 散列表 。
? 使用散列方法进行搜索不必进行多次关键码
的比较,搜索速度比较快,可以直接到达或逼
近具有此关键码的表项的实际存放地址。
? 散列函数是一个压缩映象函数 。关键码集合
比散列表地址集合大得多。因此有可能经过
散列函数的计算，把不同的关键码映射到同
一个散列地址上，这就产生了 冲突 。
? 示例：有一组表项，其关键码分别是
12361,07251,03309,30976
47
采用的散列函数是
hash(x) = x % 73 + 13420
其中，,%” 是除法取余操作。
则有,hash(12361) = hash(07250) = hash(03309)
= hash(30976) = 13444。 就是说,对不同的关
键码,通过散列函数的计算,得到了同一散列
地址。 我们称这些产生冲突的散列地址相同
的不同关键码为 同义词 。
? 由于关键码集合比地址集合大得多,冲突很难
避免。 所以对于散列方法,需要讨论以下两个
问题：
48
构造散列函数时的几点要求：
? 散列函数应是简单的，能在较短的时间内计
算出结果。
? 散列函数的定义域必须包括需要存储的全部
关键码,如果散列表允许有 m 个地址时,其
值域必须在 0 到 m-1 之间。
散列函数
?对于给定的一个关键码集合,选择一个计算
简单且地址分布比较均匀的散列函数,避免
或尽量减少冲突；
? 拟订解决冲突的方案。
49
① 直接定址法
此类函数取关键码的某个线性函数值作为
散列地址：
Hash ( key ) ＝ a * key + b { a,b为常数 }
这类散列函数是一对一的映射，一般不会
产生冲突。但是，它要求散列地址空间的大
小与关键码集合的大小相同。
? 散列函数计算出来的 地址应能均匀分布在整
个地址空间中 。
50
示例：有一组关键码如下, { 942148,941269,
940527,941630,941805,941558,942047,
940001 }。 散列函数为
Hash (key) = key - 940000
Hash (942148) = 2148 Hash (941269) = 1269
Hash (940527) = 527 Hash (941630) = 1630
Hash (941805) = 1805 Hash (941558) = 1558
Hash (942047) = 2047 Hash (940001) = 1
可以按计算出的地址存放记录。
51
② 数字分析法
设有 n 个 d 位数,每一位可能有 r 种不同
的符号,它们在各位上出现的频率不一定相
同。可根据散列表的大小,选取其中各种符
号分布均匀的若干位作为散列地址。
数字分析法仅适用于事先明确知道表中所
有关键码每一位数值的分布情况,它完全依
赖于关键码集合。如果换一个关键码集合，
选择哪几位要重新决定。
52
9 4 2 1 4 8
9 4 1 2 6 9
9 4 0 5 2 7
9 4 1 6 3 0
9 4 1 8 0 5
9 4 1 5 5 8
9 4 2 0 4 7
9 4 0 0 0 1
① ② ③ ④ ⑤ ⑥
若散列表地址范围有 3
位数字,取各关键码的 ④
⑤⑥ 位做为记录的散列
地址。也可以把第 ①,
②,③ 和第 ⑤ 位相加,舍
去进位位,变成一位数,
与第 ④,⑥ 位合起来作为
散列地址。
53
③ 除留余数法
设散列表中允许地址数为 m,取一个不大
于 m,但最接近于或等于 m 的质数 p 作为除
数,利用以下函数把关键码转换成散列地址：
hash ( key ) = key % p p ? m
其中,“%” 是整数除法取余的运算，要求
这时的质数 p 不是接近 2的幂。
示例, 关键码 key = 962148,散列表大小 m
= 25,即 HT[25]。取质数 p= 23。散列函数
hash ( key ) = key % p。则散列地址为
hash ( 962148 ) = 962148 % 23 = 12。
54
可以按计算出的地址存放记录。需要注意
的是,使用上面的散列函数计算出来的地址
范围是 0到 22,因此,从 23到 24这几个散列地
址实际上在一开始是不可能用散列函数计算
出来的,只可能在处理溢出时达到这些地址。
④ 平方取中法
它先计算构成关键码的标识符的内码的平
方,然后按照散列表的大小取中间的若干位
作为散列地址。
? 因为内码平方数的中间几位一般是由标识符
所有字符决定,所以对不同的标识符计算出
的散列地址大多不相同。
55
标识符 内码 内码的平方 散列地址
A 01 01 001
A1 0134 20420 042
A9 0144 23420 342
B 02 4 004
DMAX 04150130 21526443617100 443
DMAX1 0415013034 5264473522151420 352
AMAX 01150130 135423617100 236
AMAX1 0115013034 3454246522151420 652
标识符的八进制内码表示及其平方值
56
⑤ 折叠法
? 此方法把关键码自左到右分成 位数相等 的几
部分,每一部分的位数应与散列表地址位数
相同,只有最后一部分的位数可以短一些。
? 把这些部分的数据叠加起来,就可以得到具
有该关键码的记录的散列地址。
? 有两种叠加方法：
? 移位法 —把各部分的最后一位对齐相加；
? 分界法 —各部分不折断,沿各部分的分界
来回折叠,然后对齐相加,将相加的结果当
做散列地址。
57
? 示例,设给定的关键码为 key = 23938587841,
若 存储空间限定 3 位,则划分结果为每段 3
位, 上述关键码可划分为 4段：
239 385 878 41
? 把超出地址位数的最高位删去,仅保留最低
的 3位，做为可用的散列地址。
移
位
法
分
界
法
58
? 一般当关键码的位数很多, 而且关键码每
一位上数字的分布大致比较均匀时, 可用
这种方法得到散列地址 。
? 以上介绍了几种常用的散列函数 。 在实际
工作中应根据关键码的特点, 选用适当的
方法 。
59
处理冲突的闭散列方法
? 因为任一种散列函数也不能避免产生冲突，
因此选择好的解决冲突的方法十分重要。
? 闭散列也叫做 开地址法 。若设散列表中各
散列地址的编址为 0 到 m-1,当要加入一
个表项 R2时,用它的关键码 R2.key,通过
散列函数 hash ( R2.key ) 的计算，得到它
的存放位臵 j。
? 但在存放时发现此位臵已被另一个表项 R1
占据,发生了冲突,必须处理冲突。为此,
需把 R2 存放到表中“下一个”空位中。
60
? 如果表未被装满,则在允许的范围内必定还
有空位。
(1) 线性探查法 (Linear Probing)
假设给出一组表项，它们的关键码为
Burke,Ekers,Broad,Blum,Attlee,Alton,
Hecht,Ederly。采用的散列函数是：取其第
一个字母在字母表中的位臵。
Hash (x) = ord (x) - ord (?A?)
//ord ( ) 是求字符内码的函数
61
? 可得 Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
? 设散列表 HT[26],m = 26。采用 线性探查法
处理冲突,则散列结果如图所示。
0 1 2 3 4
Attlee Burke Broad Blum Ekers
Alton Ederly Hecht
5 6 7 8 9
(1) (1) (2) (3) (1)
(6) (3) (1)
62
? 需要搜索或加入一个表项时,使用散列函数
计算散列地址：
H0 = hash ( key )
? 一旦发生冲突，在表中顺次向后寻找,下一
个”空位 Hi 的递推公式为：
Hi = ( Hi-1 +1 ) % m,i =1,2,…,m-1
即用以下的线性探查序列在表中寻找,下一
个”空位 的地址：
H0 +1,H0 +2,…,m-1,0,1,2,…,H0-1
亦可写成如下的通项公式：
Hi = ( H0 + i ) % m,i =1,2,…,m-1
63
? 当发生冲突时探查下一个空位。当循环 m-1
次后就会回到开始探查时的位臵,说明待查
关键码不在表内,而且表已满,不能再插入
新关键码。
? 用 平均搜索长度 ASL衡量散列方法的性能。
? 搜索成功的平均搜索长度 ASLsucc 是指 搜索
到表中已有表项的平均探查次数 。它是找到
表中各个已有表项的探查次数的平均值。
? 搜索不成功的平均搜索长度 ASLunsucc 是
指在表中搜索不到待查的表项，但找到插入
位臵的平均探查次数 。
64
? 它是表中所有可能散列到的位臵上要插入新元
素时为找到空位的探查次数的平均值。
? 在使用线性探查法对示例进行搜索时,搜索成
功的平均搜索长度为：
? 搜索不成功的平均搜索长度为,
?
?
??????????
8
1
.
8
181)361321(1
8
1
8
1
i
CiA S L s u c c
.266226 1823456789 ??????????A S L u n s u c c
65
? 散列表存放的表项不应有重复的关键码 。
在插入新表项时,如果发现表中已经有关键
码相同的表项,则不再插入 。
? 在闭散列情形下不能真正删除表中已有表
项 。 删除表项会影响其他表项的搜索 。 若
把关键码为 Broad的表项真正删除,以后在
搜索关键码为 Blum和 Alton的表项时就查
不下去,会错误地判断表中没有关键码为
Blum和 Alton的表项 。
? 若想删除一个表项,只能给它做一个删除标
记,进行逻辑删除,不能把它真正删去 。
66
? 逻辑删除的副作用 是：在执行多次删除后,
表面上看起来散列表很满,实际上有许多位
臵没有利用。
? 线性探查方法容易产生,堆积,,不同探查
序列的关键码占据可用的空位,为寻找某一
关键码需要经历不同的探查序列,导致搜索
时间增加。
67
(2) 二次探查法 (quadratic probing)
? 为改善“堆积”问题,减少为完成搜索所需
的平均探查次数,可使用二次探查法。
? 通过某一个散列函数对表项的关键码 x 进行
计算,得到散列地址,它是一个非负整数。
H0 = hash(x)
? 二次探查法在表中寻找“下一个”空位的公
式：
Hi = (H0 + i 2 ) % m,
Hi = (H0 - i 2 ) % m,i = 1,2,…,( m-1)/2
? 式中的 m 是表的大小，它应是一个值为
4k+3 的质数，其中 k 是一个整数。 如 3,7,
11,19,23,31,43,59,127,251,503,… 。
68
? 探查序列如 H0,H0+1,H0-1,H0+4,H0-4,… 。
? 在做 (H0- i2 ) % m 的运算时,当 H0- i2 < 0 时,
运算结果也是负数 。 实际算式可改为
j = (H0- i2 ) % m,if ( j < 0 ) j += m
? 示例：给出一组关键码 { Burke,Ekers,
Broad,Blum,Attlee,Alton,Hecht,Ederly }。
散列函数为,Hash (x)＝ ord (x)－ ord ('A')
? 用它计算可得
Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
69
? 因为可能位臵是 0 ? 25,取满足 4k+3 的质数，
表的长度为 m = 31，利用二次探查法得到的
散列结果如图所示。
0 1 2 3 4 5
Blum Burke Broad Ekers Ederly
Hecht
6 7 8 9 10 11
Alton Attlee
(3) (1) (2) (1) (2)
(1)
25 26 27 28 29 30
(5) (3)
利用二次探查法处理溢出
70
? 使用 二次探查法 处理冲突时的 搜索成功的平
均搜索长度 为：
? 搜索不成功的平均搜索长度 为：
.8183)512121(38181
8
1
?????????? ?
?i
CiA S L s u c c
26
402 0)22325(6
26
1 ????????A S L u n s u c c
可以证明,当 表的长度 m为质数 且 表的装填
因子 ? 不超过 0.5 时,新的表项 x 一定能够插
入,且任何一个位臵不会被探查两次。只要表
中至少有一半空，就不会有表满问题。
71
? 在搜索时可以不考虑表满的情况 ; 但在插入
时 必须确保表的装填因子 ?不超过 0.5。 如果
超出,必须将表长度扩充一倍,进行表的分
裂 。
? 在删除一个表项时, 为确保搜索链不致中
断, 也只能做表项的逻辑删除 。
(3) 双散列法
? 使用双散列方法时,需要两个散列函数 。
? 第一个散列函数 Hash( ) 按表项的关键码
key 计算表项所在地址 H0 = Hash(key)。
72
? 一旦冲突, 利用第二个散列函数 ReHash( )
计算该表项到达, 下一个, 空位的移位量 。
它的取值与 key 的值有关,要求它的取值应
是小于地址空间大小 m,且与 m互质的正整数 。
? 若设表的长度为 m,则在表中寻找, 下一个,
空位的公式为：
j = H0 = Hash(key),p = ReHash(key)；
j = ( j + p ) % m；
p是小于 m且与 m互质的整数
73
? 利用双散列法,按一定的距离,跳跃式地寻找
“下一个”空位,减少了“堆积”的机会。
? 双散列法的探查序列也可写成：
Hi = (H0 + i * ReHash(key) ) % m，
i =1,2,…,m-1
? 最多经过 m-1次探查,它会遍历表中所有位
臵,回到 H0 位臵。
? 示例：给出一组表项关键码 { 22,41,53,46,
30,13,01,67 }。散列函数为：
Hash(x)＝ (3x) % 11。
? 散列表为 HT[0..10],m = 11。因此，再散列
函数为 ReHash(x) = (7x) % 10 +1。
74
Hi = ( Hi-1 + (7x) % 10 +1 ) % 11,i = 1,2,?
? H0(22) = 0 H0(41) = 2 H0(53) = 5
H0(46) = 6 H0(30) = 2 冲突 H1 = (2+1) = 3
H0(13) = 6 冲突 H1 = (6+2) = 8
H0(01) = 3 冲突 H1 = (3+8) = 0 冲突 H2 =
(0+8) = 8 冲突 H3 = (8+8) = 5 冲突 H4 =
(5+8) = 2 冲突 H5 = (2+8) = 10
H0(67) = 3 冲突 H1 = (3+10) = 2 冲突 H2 =
(2+10) = 1
22 67 41 30 53 46 13 01
(1) (3) (1) (2) (1) (1) (2) (6)
0 1 2 3 4 5 6 7 8 9 10
1 8 2 5 3 4 6 7
75
? 搜索成功的平均搜索长度
? 搜索不成功的平均搜索长度
? 每一散列位臵的移位量有 10种,1,2,?,
10。先计算每一散列位臵各种移位量情形
下找到下一个空位的比较次数,求出平均
值；
? 再计算各个位臵的平均比较次数的总平均
值。
22 67 41 30 53 46 13 01
(1) (3) (1) (2) (1) (1) (2) (6)
0 1 2 3 4 5 6 7 8 9 10
8
176)211213(1
8
1 ?????????A S L s u c c
76
? Rehash( )的取法很多 。 例如,当 m是质数时,
可定义
? ReHash(key) = key % (m-2) +1
? ReHash(key) = ?key / m? % (m-2)+1
? 当 m 是 2 的方幂时,ReHash(key) 可取从 0
到 m-1 中的任意一个奇数。
77
处理冲突的开散列方法 — 链地址法
? 开散列方法首先对关键码集合用某一个散列
函数计算它们的存放位臵 。
? 若设散列表地址空间的所有位臵是从 0 到
m-1,则关键码集合中的所有关键码被划分
为 m个子集,具有相同地址的关键码归于同
一子集 。 我们称同一子集中的关键码互为同
义词 。 每一个子集称为一个桶 。
? 通常各个桶中的表项通过一个单链表链接起
来, 称之为同义词子表 。 所有桶号相同的表
项都链接在同一个同义词子表中, 各链表的
表头结点组成一个向量 。
78
? 向量的元素个数与桶数一致。桶号为 i 的同义
词子表的表头结点是向量中的第 i 个元素。
? 示例：给出一组表项关键码 { Burke,Ekers,
Broad,Blum,Attlee,Alton,Hecht,Ederly }。
散列函数为,Hash (x)＝ ord (x)－ ord ('A')。
? 用它计算可得：
Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
? 散列表为 HT[0..25],m = 26。
79
0
1
2
3
4
5
6
7
8
9
Attlee Alton
Burke Broad Blum
Ekers Ederly
Ekers 8
13
8
1*33*24*1 ????
s u c cA S L
26
34
18)*12
113114(3
26
1
???
????????u n s u c cA S L
80
? 通常, 每个桶中的同义词子表都很短, 设有
n 个关键码通过某一个散列函数, 存放到散
列表中的 m 个桶中 。 那么每一个桶中的同义
词子表的平均长度为 n / m。 以搜索平均长度
为 n / m 的同义词子表代替了搜索长度为 n
的顺序表, 搜索速度快得多 。
? 应用开散列法处理冲突,需要增设链接指针,
似乎增加了存储开销。事实上,由于闭散列
法必须保持大量的空闲空间以确保搜索效率，
如二次探查法要求装填因子 ?? 0.5，而表项
所占空间又比指针大得多，所以 使用开散列
法 反而 比闭散列法节省存储空间 。
81
散列表分析
? 散列表是一种直接计算记录存放地址的方
法，它在关键码与存储位臵之间直接建立
了映象。
? 当选择的散列函数能够得到均匀的地址分
布时,在搜索过程中可以不做多次探查。
? 由于很难避免冲突,增加了搜索时间。 冲
突的出现,与 散列函数的选取 (地址分布是
否均匀 ),处理冲突的方法 (是否产生堆积 )
有关。
? 下图给出一些实验结果。
82
? = n / m 0, 5 0 0, 7 5 0, 9 0 0, 9 5
散列函数
种类
开散
列法
闭散
列法
开散
列法
闭散
列法
开散
列法
闭散
列法
开散
列法
闭散
列法
平平 方方 取取 中中 11,,22 66 11,,77 33 11,,44 00 99,,77 55 11,,44 55 33 11 00,,11 44 11,,44 77 33 11 00,,55 33
除留余数 1, 1 9 4, 5 2 1, 3 1 1 0, 2 0 1, 3 8 2 2, 4 2 1, 4 1 2 5, 7 9
移位折叠 1, 3 3 2 1, 7 5 1, 4 8 6 5, 1 0 1, 4 0 7 1 0, 0 1 1, 5 1 1 1 8, 5 7
分界折叠 1, 3 9 2 2, 9 7 1, 5 7 4 8, 7 0 1, 5 5 6 9, 6 3 1, 5 1 9 1 0, 5 6
数字分析 1, 3 5 4, 5 5 1, 4 9 3 0, 6 2 1, 5 2 8 9, 2 0 1, 5 2 1 2 5, 5 9
理论值 1, 2 5 1, 5 0 1, 3 7 2, 5 0 1, 4 5 5, 5 0 1, 4 8 1 0, 5 0
搜索关键码时所需对桶的平均访问次数
从图中可以看出,开散列法优于闭散列法 ；
在散列函数中,用除留余数法作散列函数优于
其它类型的散列函数,最差的是折叠法。
83
? 当装填因子 ?较高时,选择的散列函数不
同,散列表的搜索性能差别很大。在一般情
况下多选用除留余数法,其中的除数在实用
上应选择不含有 20以下的质因数的质数。
? 对散列表技术进行的实验评估表明,它 具有
很好的平均性能,优于一些传统的技术,如
平衡树 。但散列表 在最坏情况下性能很不好 。
如果对一 个有 n 个关键码的散列表执行一
次搜索或插入操作，最坏情况下需要 O(n)
的时间。
? Knuth对不同的冲突处理方法进行了分析。
84
? 若设 ? 是散列表的装填因子：
? 用地址分布均匀的散列函数 Hash( )计算桶号。
? Sn 是搜索一个随机选择的关键码 xi (1 ? i ? n)
所需的关键码比较次数的期望值
? Un 是在长度为 m 的散列表中 n 个桶已装入表
项的情况下，装入第 n+1 项所需执行的关键
码比较次数期望值 。
? 前者称为在 ? = n / m 时的搜索成功的平均搜
索长度，后者称为在 ?= n / m时的搜索不成功
的平均搜索长度。
m
n??
表中预设的最大记录数
表中已装有记录数?
85
? 用不同的方法溢出处理冲突时散列表的平均
搜索长度如图所示。
平 均 搜 索 长 度 ASL
处 理 冲 突
的 方 法
搜索成功
Sn
搜索不成功 Un
( 登入新记录 )
闭
散
线性探查法
?
?
?
?
?
?
???
?
??
?
?
?
?
?
?
?
?
?
?
?
???
?
??
?
?
)(
列
法
伪随机探查法
二次探查法
双散列法
? ??
?
??
?
?
?
?
?
? 1l o g
1
e
???
?
开 散 列 法
( 同义词子表法 )
?
?
?? ????
??
e
86
? 散列表的装填因子 ? 表明了表中的装满程
度 。 越大,说明表越满,再插入新元素时发生
冲突的可能性就越大 。
? 散列表的搜索性能,即 平均搜索长度 依赖于
散列表的装填因子,不直接依赖于 n 或 m。
? 不论表的长度有多大,我们总能选择一个合
适的装填因子,以把平均搜索长度限制在一
定范围内 。
87
例 求散列表大小并设计散列函数
? 设有一个含 200个表项的散列表，用二次探查
法解决冲突，按关键码查询时找到一个新表
项插入位臵的平均探查次数不超过 1.5，则散
列表项应能够至少容纳多少个表项。再设计
散列函数 （设搜索不成功的平均搜索长度为
Un＝ 1 / (1 -α),其中 α为装填因子）
? 解答：设表中表项个数 n = 200，搜索不成功
的平均搜索长度
Un＝ 1 / (1 -α) ? 1.5 ??? 1/3
? n / m = 200 / m = ?? 1/3 m ? 600
? 静态索引结构
? 动态索引结构
? 散列
2
静态索引结构
? 示例,有一个存放职工信息的数据表,每一
个职工对象有近 1k 字节的信息,正好占据一
个页块的存储空间 。
? 假设内存工作区仅能容纳 64k 字节的数据,
在某一时刻内存最多可容纳 64 个对象以供
搜索。
当数据对象个数 n 很大时,可采用索引方法
来实现存储和搜索。
线性索引 (Linear Index List)
3
0
1k
2k
3k
4k
5k
6k
7k
key addr
03 2k
08 1k
17 6k
24 4k
47 5k
51 7k
83 0
95 3k
职工号 姓名 性别 职务 婚否
83 张珊 女 教师 已婚 …
08 李斯 男 教师 已婚,..
03 王鲁 男 教务员 已婚,..
95 刘琪 女 实验员 未婚,..
24 岳跋 男 教师 已婚,..
47 周斌 男 教师 已婚,..
17 胡江 男 实验员 未婚,..
51 林青 女 教师 未婚,..
索引表 数据表
4
? 如果对象总数有 14400 个,不可能把所有对
象的数据一次都读入内存 。 无论是顺序搜
索或折半搜索,都需要多次读取外存记录 。
? 如果在索引表中每一个索引项占 4 个字节,
索引项给出一个职工对象的 关键码 及其 存
储地址,用以索引一个职工对象,则 14400
个索引项需要 56.25k 字节,在内存中可以容
纳所有的索引项 。
? 这样只需从外存中把索引表读入内存,经过
搜索索引后确定了职工对象的存储地址,再
经过 1 次读取对象操作就可以完成搜索 。
5
? 稠密索引,一个索引项对应数据表中一个对
象的索引结构 。 当对象在外存中 按加入顺序
存放而不是按关键码有序存放 时必须采用 稠
密索引 结构, 这时的索引结构叫做索引非顺
序结构 。
? 稀疏索引,当对象在外存中有序存放时, 可
以把所有 n 个对象分为 b 个子表 (块 )存放,
一个索引项对应数据表中一组对象 (子表 )。
? 第 i 个索引项是第 i 个子表的索引项,i = 0,
1,…,n-1。 这种索引结构叫做 索引顺序结构 。
6
? 对索引顺序结构进行搜索时，一般分为两级
搜索,
? 先在 索引表 ID 中搜索给定值 K,确定满足
ID[i-1].max_key < K ? ID[i].max_key
22 12 13 30 29 33
36 42 44 48 39 40
60 74 56 79 80 66
92 82 88 98 94
子表 1
子表 2
子表 3
子表 4
数据区
33
48
80
98
索引表
1
2
3
4
max_ max_
key addr
7
的 i 值,即待查对象可能在的子表的序号 。
? 然后再在第 i 个子表中按给定值搜索要求
的对象 。
? 索引表是按 max_key有序的,且长度也不大,
可以折半搜索, 也可以顺序搜索 。
? 各子表内各个对象如果也按对象关键码有序,
可以采用折半搜索或顺序搜索 ; 如果不是按
对象关键码有序,只能顺序搜索 。
8
? 索引顺序搜索的搜索成功时的平均搜索长度
ASLIndexSeq = ASLIndex + ASLSubList
? 其中,ASLIndex 是在索引表中搜索子表位臵的
平均搜索长度, ASLSubList 是在子表内搜索对
象位臵的搜索成功的平均搜索长度 。
? 设把长度为 n 的表分成均等的 b 个子表, 每
个子表 s 个对象, 则 b = ?n/s?。 又设表中每
个对象的搜索概率相等, 则每个子表的搜索
概率为 1/b,子表内各对象的搜索概率为 1/s。
? 若对 索引表 和 子表 都用 顺序搜索, 则索引顺
序搜索的搜索成功时的平均搜索长度为
ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1
9
? 索引顺序搜索的平均搜索长度与 表中的对象
个数 n 有关，与 每个子表中的对象个数 s 有
关。在给定 n 的情况下,s 应选择多大？
? 用数学方法可导出,当 s = 时,ASLIndexSeq
取极小值 +1。这个值比顺序搜索强，但
比折半搜索差。但如果子表存放在外存时，
还要受到页块大小的制约。
? 若采用折半搜索确定对象所在的子表,则搜
索成功时的平均搜索长度为
ASLIndexSeq = ASLIndex + ASLSubList
? log2 (b+1)-1 + (s+1)/2
? log2(1+n / s ) + s/2
n
n
10
m 路静态搜索树
? 当数据对象数目特别大，索引表本身很大，
在内存中放不下，需要分批多次读取外存才
能把索引表搜索一遍。
? 此时,可以建立索引的索引 (二级索引 )。二级
索引中一个索引项对应一个索引块，登记该
索引块的最大关键码及该索引块的存储地址。
? 如果二级索引在内存中也放不下，需要分为
许多块多次从外存读入。可以建立二级索引
的索引 (三级索引 )。这时，访问外存次数等
于读入索引次数再加上 1次读取对象。
11
? 必要时,还可以有 4级索引,5极索引,… 。
? 这种多级索引结构形成一种 m叉树。树中 每
一个分支结点表示一个索引块,每个索引项
给出各子树结点的 最大关键码 和 结点地址 。
02 06 11 15 18 23 29 32 38 41 45 49 52 60 77 95
(06,) (15,) (23,) (32,) (41,) (49,) (60,) (95,)
(23,) (49,) (95,)
root
head
12
? 树的叶结点中各索引项给出在数据表中存放
的对象的关键码和存放地址。这种 m叉树用
来作为多级索引，就是 m路搜索树。
? m路搜索树 可能是 静态索引结构,即结构在
初始创建，数据装入时就已经定型，在整个
运行期间，树的结构不发生变化。
? m路搜索树 还可能是 动态索引结构,即在整
个系统运行期间,树的结构随数据的增删及
时调整,以保持最佳的搜索效率。
13
多级索引结构形成 m 路搜索树
数据区
一级索引
二级索引
三级索引
四级索引
14
动态搜索结构
? 现在我们所讨论的 m 路搜索树多为可以动
态调整的多路搜索树, 它的一般定义为：
? 一棵 m 路搜索树,它或者是一棵空树,或者
是满足如下性质的树：
? 根最多有 m 棵子树,并具有如下的结构：
n,P0,K1,P1,K2,P2,……,Kn,Pn
其中,Pi 是指向子树的指针,0 ? i ? n < m; Ki
是关键码,1 ? i ? n < m。 Ki < Ki+1,1 ? i < n。
动态的 m 路搜索树
15
? 在子树 Pi 中所有的关键码都 小于 Ki+1,且
大于 Ki,0 < i < n。
? 在子树 Pn 中所有的关键码都 大于 Kn；
? 在子树 P0 中的所有关键码都 小于 K1。
? 子树 Pi 也是 m 路搜索树, 0 ? i ? n。
一棵 3路搜索树的示例
35
20 40a
b c d
e
25 3010 15 45 50
16
AVL树是 2路搜索树。若已知 m 路搜索树的
度 m 和它的 高度 h,则树中的 最大结点数 为
? ?1
1
1 1
0
?
?
? ?
?
? h
h
i
i m
m
m
(等比级数前 h 项求和 )
每个结点中 最多有 m-1 个关键码, 在一棵高
度为 h 的 m 路搜索树中关键码的最大个数为
mh+1-1。
? 高度 h=2 的二叉树,关键码最大个数为 7；
? 高度 h=3 的 3路搜索树,关键码最大个数为
34-1 = 80。
17
m 路搜索树上的搜索
? 在 m 路搜索树上的搜索过程是一个 在结点
内搜索 和 自根结点向下逐个结点搜索 的交
替的过程。
35
20 40a
b c d
e
25 3010 15 45 50
root
搜索 35
18
? 提高搜索树的路数 m,可以改善树的搜索
性能 。 对于给定的关键码数 n,如果搜索
树是平衡的, 可以使 m 路搜索树的性能接
近最佳 。 下面将讨论一种称之为 B 树的平
衡的 m 路搜索树 。
19
B 树
? 一棵 m 阶 B 树是一棵平衡的 m 路搜索树,它
或者是空树,或者是满足下列性质的树：
? 根结点至少有 2 个子女。
? 除根结点以外的所有结点 (不包括失败结
点 )至少有 ?m/2?个子女。
? 所有的失败结点都位于同一层。
? 在 B 树中的“失败”结点是当搜索值 x不在
树中时才能到达的结点。该层计入树的高度。
? 事实上，在 B 树的每个结点中还包含有一组
指针 D[m]，指向实际对象的存放地址。
20
30
? K[i]与 D[i] (1 ? i ? n < m) 形成一个 索引项
(K[i],D[i])，通过 K[i]可找到某个对象的存
储地址 D[i]。
? 一棵 B 树是平衡的 m 路搜索树，但一棵平
衡的 m 路搜索树不一定是 B 树。
35
20 40
25 3010 15 45 50
root
45 5035
4020
root
10 15 25
非 B 树 B 树
21
typedef int BTreeData;
typedef struct node { //B树结点的定义
int n; //结点中关键码个数
struct node *parent; //双亲指针
BTreeData key[m+1]; //关键码数组 1?m-1
struct node *ptr[m+1]; //子树指针数组 0?m-1
} BTreeNode;
typedef BTreeNode * BTree; //B树定义
B 树的定义和 B 树结点的定义
22
? B 树的搜索继承了 m 路搜索树的搜索 。
? B 树的搜索过程是一个在结点内搜索和循
某一条路径向下一层搜索交替进行的过程 。
? B 树的搜索时间与 B 树的阶数 m 和 B 树的
高度 h 直接有关。
? 在 B 树上进行搜索,搜索成功所需的时间取
决于关键码所在的层次 ; 搜索不成功所需的
时间取决于树的高度 。
B 树的搜索算法
23
? 设在 m 阶 B 树中每层结点个数达到最少,
则 B 树的高度可能达到最大。设树中关键
码个数为 N，从 B 树的定义知：
? 0层 1 个结点
? 1层 至少 2 个结点
? 2层 至少 2 ?m / 2?个结点
? 3层 至少 2 ?m / 2? 2 个结点
? 如此类推,??
? h-1 层 至少有 2 ?m / 2? h-2 个结点。所有
这些结点都不是失败结点。
高度 h与关键码个数 N之间的关系
24
? 若树中关键码有 N个,则失败结点数为 N+1。
这是因为失败数据一般与已有关键码交错
排列。因此，有
N +1 = 失败结点数 = 位于第 h 层结点数
? 2 ?m / 2? h-1
? N ? 2 ?m / 2? h-1-1
? h-1 ? log ?m / 2? ( (N +1) / 2 )
? 所有的非失败结点所在层次为 0 ? h-1。
? 示例：若 B 树的阶数 m = 199,关键码总数
N = 1999999，则 B 树的高度 h 不超过
log100 1000000 +1= 4
25
? 如果让 B 树每层结点个数达到最大，且设
关键码总数 为 N,则树的高度达到最小。
? 从高度为 h (根在第 0层 ) 的满 m叉树的性质
可知：
N +1 = 失败结点数 = 位于第 h 层结点数
? mh
h ? logm(N+1)
? 示例：若 B 树的阶数 m = 199,关键码总数
N = 1999999，则 B 树的高度 h 不低于
log199 2000000 = 2.74
26
B 树的插入
? B 树是从空树起,逐个插入关键码而生成的。
? 在 B 树，每个非失败结点的关键码个数都在
[ ?m/2?-1,m-1]
之间。
? 插入在 某个叶结点 开始。如果在关键码插入
后结点中的 关键码个数超出了上界 m-1，则
结点需要“分裂”，否则可以直接插入 。
? 实现结点“分裂”的原则是：
? 设结点 p 中已经有 m-1 个关键码，当再插
入一个关键码后结点中的状态为
27
( m,P0,K1,P1,K2,P2,……,Km,Pm)
其中 Ki < Ki+1,1 ? i < m
? 这时必须把结点 p 分裂成两个结点 p 和 q，
它们包含的信息分别为：
? 结点 p：
( ?m/2?-1,P0,K1,P1,……,K?m/2?-1,P?m/2?-1)
? 结点 q：
(m-?m/2?,P?m/2?,K?m/2?+1,P?m/2?+1,……,Km,Pm)
? 位于中间的关键码 K?m/2?与指向新结点 q 的
指针形成一个二元组 ( K?m/2?,q )，插入到这
两个结点的双亲结点中去。
28
结点“分裂”的示例
2 53 75
n P0 K1 P1 K2 P2
p
3 53 75 139
n P0 K1 P1 K2 P2 K3 P3
p
加入 139,
结点溢出
1 75
n P0 K1 P1
1 53
n P0 K1 P1
1 139
n P0 K1 P1
结点
分裂
P q
m = 3
29
49 75
示例,从空树开始加入关键码建立 3阶 B 树
n=1 加入 53
53
n=2 加入 75
53 75
n=3 加入 139
75
13953
n=5 加入 49,145
75
139 14549 53
n=6 加入 36
139 1455336
30
? 在插入新关键码时，需要自底向上分裂结
点，最坏情况下从被插关键码所在叶结点
到根的路径上的所有结点都要分裂。
若设 B 树的
高度为 h,那
么在 自顶向
下 搜索到 叶
结点 的过程
中需要进行
h 次读盘。
n=7 加入 101
49
5336
139
145101
75
31
B 树的删除
? 在 B 树上删除一个关键码时,首先需要找到
这个关键码所在的结点,从中删去这个关键
码。若该结点不是叶结点,且被删关键码为
Ki,1 ? i ? n,则在删去该关键码之后,应以该
结点 Pi 所指示子树中的最小关键码 x 来代
替被删关键码 Ki 所在的位臵,然后在 x 所在
的叶结点中删除 x。
? 在叶结点上的删除有 4 种情况。
① 被删关键码所在叶结点同时又是根结点且
删除前该结点中关键码个数 n ? 2，则直接
删去该关键码并将修改后的结点写回磁盘。
32
② 被删关键码所在叶结点不是根结点且删除前
该结点中关键码个数 n ??m/2?,则直接删去
该关键码并将修改后的结点写回磁盘,删除
结束。
③ 被删关键码所在叶结点删除前关键码个数 n
= ?m/2?-1,若这时与该结点相邻的右兄弟
(或左兄弟 )结点的关键码个数 n ??m/2?，则
可按以下步骤调整该结点、右兄弟 (或左兄
弟 ) 结点以及其双亲结点，以达到新的平衡。
36 49m = 3 删除 36 49
33
55 58
删除 55简单删除
75 80
m = 3
删除 55
10 40 65
60 7030
50a
cb
d e f g h
58 75 8010 40 65
60 7030
50a
cb
d e f g h
34
?将双亲结点中刚刚大于 (或小于 ) 该被删关
键码的关键码 Ki (1 ? i ? n) 下移；
?将右兄弟 (或左兄弟 ) 结点中的最小 (或最
大 )关键码上移到双亲结点的 Ki 位臵；
?将右兄弟 (或左兄弟 ) 结点中的最左 (或最
右 ) 子树指针平移到被删关键码所在结点
中最后 (或最前 ) 子树指针位臵；
?在右兄弟 (或左兄弟 ) 结点中，将被移走的
关键码和指针位臵用剩余的关键码和指针
填补、调整。再将结点中的关键码个数减
1。
35
结点联合调整
55 58 75 80
m = 3 删除 65
10 40 65
60 7030
50a
cb
d e f g h
55 58 8010 40 70
60 7530
50a
cb
d e f g h
调整 g,c,h
删除 65
36
70
删除 70
55 58 80
m = 3 删除 70
10 40
60 7530
50a
cb
d e f g h
55 8010 40 60
58 7530
50a
cb
d e f g h
调整 f,c,g
结点联合调整
37
④ 被删关键码所在叶结点删除前关键码个数
n = ?m/2?-1,若这时与该结点相邻的右兄弟
(或左兄弟 )结点的关键码个数 n = ?m/2?-1,
则必须按以下步骤合并这两个结点。
? 若要合并 p 中的子树指针 Pi 与 Pi+1 所指
的结点,且保留 Pi 所指结点,则把 p 中的关
键码 Ki+1下移到 Pi 所指的结点中。
? 把 p 中子树指针 Pi+1 所指结点中的全部
指针和关键码都照搬到 Pi 所指结点的后
面。删去 Pi+1 所指的结点。
38
? 在结点 p 中用后面剩余的关键码和指针填
补关键码 Ki+1 和指针 Pi+1。
? 修改结点 p 和选定保留结点的关键码个数。
? 在合并结点的过程中,双亲结点中的关键码个
数减少了。若双亲结点是根结点且结点关键
码个数减到 0,则将该双亲结点删去,合并后保
留的结点成为新的根结点 ; 否则将双亲结点与
合并后保留的结点都写回磁盘,删除处理结束。
? 若双亲结点不是根结点且关键码个数减到
?m/2?-2，又要与它自己的兄弟结点合并,重
复上面的合并步骤。最坏情况下这种结点合
并处理要自下向上直到根结点。
39
55
删除 55结点合并
80
m = 3 删除 55
10 40 60
58 7530
50a
cb
d e f g h
合并 f,g
58 60 8010 40
7530
50a
cb
d e f h
40
8055
删除 80结点合并
m = 3 删除 80
10 40 60
58 7530
50a
cb
d e f g h
合并 g,h
60 755510 40
5830
50a
cb
d e f g
41
55
非叶结点删除
删除 50
删除 55
55 58 75 80
m = 3 删除 50
10 40 65
60 7030
50a
cb
d e f g h
58 75 80
删除 55
10 40 65
60 7030
a
cb
d e f g h
用 55取代
用 58取代
42
58
75 8010 40 65
60 7030
a
cb
d e f g h
合并 f,g
58
75 8010 40 60 65
7030
a
cb
d e f h
结点合并与调整
删除 70
43
58
8010 40 60 65
7530
a
cb
d e f h
删除 70
用 75取代
删除 75
58
10 40 60 65
8030
a
cb
d e f h
删除 75
用 80取代
调整 f,c,h
44
58
8010 40 60
6530
a
cb
d e f h
删除 10
8030 40 60f h
58 65
d
b
45
散列 (Hashing)
? 散列方法在 表项存储位臵 与 其关键码 之间建
立一个 确定的对应函数关系 Hash( )，使每个
关键码与结构中一个唯一存储位臵相对应：
Address ＝ Hash ( Rec.key )
? 在搜索时,先对表项的关键码进行函数计算,
把函数值当做表项的存储位臵,在结构中按
此位臵取表项比较。若关键码相等,则搜索
成功。在存放表项时,依相同函数计算存储
位臵,并按此位臵存放。这种方法就是散列
方法。
46
? 在散列方法中使用的转换函数叫做 散列函数 。
按此方法构造出来的表或结构就叫做 散列表 。
? 使用散列方法进行搜索不必进行多次关键码
的比较,搜索速度比较快,可以直接到达或逼
近具有此关键码的表项的实际存放地址。
? 散列函数是一个压缩映象函数 。关键码集合
比散列表地址集合大得多。因此有可能经过
散列函数的计算，把不同的关键码映射到同
一个散列地址上，这就产生了 冲突 。
? 示例：有一组表项，其关键码分别是
12361,07251,03309,30976
47
采用的散列函数是
hash(x) = x % 73 + 13420
其中，,%” 是除法取余操作。
则有,hash(12361) = hash(07250) = hash(03309)
= hash(30976) = 13444。 就是说,对不同的关
键码,通过散列函数的计算,得到了同一散列
地址。 我们称这些产生冲突的散列地址相同
的不同关键码为 同义词 。
? 由于关键码集合比地址集合大得多,冲突很难
避免。 所以对于散列方法,需要讨论以下两个
问题：
48
构造散列函数时的几点要求：
? 散列函数应是简单的，能在较短的时间内计
算出结果。
? 散列函数的定义域必须包括需要存储的全部
关键码,如果散列表允许有 m 个地址时,其
值域必须在 0 到 m-1 之间。
散列函数
?对于给定的一个关键码集合,选择一个计算
简单且地址分布比较均匀的散列函数,避免
或尽量减少冲突；
? 拟订解决冲突的方案。
49
① 直接定址法
此类函数取关键码的某个线性函数值作为
散列地址：
Hash ( key ) ＝ a * key + b { a,b为常数 }
这类散列函数是一对一的映射，一般不会
产生冲突。但是，它要求散列地址空间的大
小与关键码集合的大小相同。
? 散列函数计算出来的 地址应能均匀分布在整
个地址空间中 。
50
示例：有一组关键码如下, { 942148,941269,
940527,941630,941805,941558,942047,
940001 }。 散列函数为
Hash (key) = key - 940000
Hash (942148) = 2148 Hash (941269) = 1269
Hash (940527) = 527 Hash (941630) = 1630
Hash (941805) = 1805 Hash (941558) = 1558
Hash (942047) = 2047 Hash (940001) = 1
可以按计算出的地址存放记录。
51
② 数字分析法
设有 n 个 d 位数,每一位可能有 r 种不同
的符号,它们在各位上出现的频率不一定相
同。可根据散列表的大小,选取其中各种符
号分布均匀的若干位作为散列地址。
数字分析法仅适用于事先明确知道表中所
有关键码每一位数值的分布情况,它完全依
赖于关键码集合。如果换一个关键码集合，
选择哪几位要重新决定。
52
9 4 2 1 4 8
9 4 1 2 6 9
9 4 0 5 2 7
9 4 1 6 3 0
9 4 1 8 0 5
9 4 1 5 5 8
9 4 2 0 4 7
9 4 0 0 0 1
① ② ③ ④ ⑤ ⑥
若散列表地址范围有 3
位数字,取各关键码的 ④
⑤⑥ 位做为记录的散列
地址。也可以把第 ①,
②,③ 和第 ⑤ 位相加,舍
去进位位,变成一位数,
与第 ④,⑥ 位合起来作为
散列地址。
53
③ 除留余数法
设散列表中允许地址数为 m,取一个不大
于 m,但最接近于或等于 m 的质数 p 作为除
数,利用以下函数把关键码转换成散列地址：
hash ( key ) = key % p p ? m
其中,“%” 是整数除法取余的运算，要求
这时的质数 p 不是接近 2的幂。
示例, 关键码 key = 962148,散列表大小 m
= 25,即 HT[25]。取质数 p= 23。散列函数
hash ( key ) = key % p。则散列地址为
hash ( 962148 ) = 962148 % 23 = 12。
54
可以按计算出的地址存放记录。需要注意
的是,使用上面的散列函数计算出来的地址
范围是 0到 22,因此,从 23到 24这几个散列地
址实际上在一开始是不可能用散列函数计算
出来的,只可能在处理溢出时达到这些地址。
④ 平方取中法
它先计算构成关键码的标识符的内码的平
方,然后按照散列表的大小取中间的若干位
作为散列地址。
? 因为内码平方数的中间几位一般是由标识符
所有字符决定,所以对不同的标识符计算出
的散列地址大多不相同。
55
标识符 内码 内码的平方 散列地址
A 01 01 001
A1 0134 20420 042
A9 0144 23420 342
B 02 4 004
DMAX 04150130 21526443617100 443
DMAX1 0415013034 5264473522151420 352
AMAX 01150130 135423617100 236
AMAX1 0115013034 3454246522151420 652
标识符的八进制内码表示及其平方值
56
⑤ 折叠法
? 此方法把关键码自左到右分成 位数相等 的几
部分,每一部分的位数应与散列表地址位数
相同,只有最后一部分的位数可以短一些。
? 把这些部分的数据叠加起来,就可以得到具
有该关键码的记录的散列地址。
? 有两种叠加方法：
? 移位法 —把各部分的最后一位对齐相加；
? 分界法 —各部分不折断,沿各部分的分界
来回折叠,然后对齐相加,将相加的结果当
做散列地址。
57
? 示例,设给定的关键码为 key = 23938587841,
若 存储空间限定 3 位,则划分结果为每段 3
位, 上述关键码可划分为 4段：
239 385 878 41
? 把超出地址位数的最高位删去,仅保留最低
的 3位，做为可用的散列地址。
移
位
法
分
界
法
58
? 一般当关键码的位数很多, 而且关键码每
一位上数字的分布大致比较均匀时, 可用
这种方法得到散列地址 。
? 以上介绍了几种常用的散列函数 。 在实际
工作中应根据关键码的特点, 选用适当的
方法 。
59
处理冲突的闭散列方法
? 因为任一种散列函数也不能避免产生冲突，
因此选择好的解决冲突的方法十分重要。
? 闭散列也叫做 开地址法 。若设散列表中各
散列地址的编址为 0 到 m-1,当要加入一
个表项 R2时,用它的关键码 R2.key,通过
散列函数 hash ( R2.key ) 的计算，得到它
的存放位臵 j。
? 但在存放时发现此位臵已被另一个表项 R1
占据,发生了冲突,必须处理冲突。为此,
需把 R2 存放到表中“下一个”空位中。
60
? 如果表未被装满,则在允许的范围内必定还
有空位。
(1) 线性探查法 (Linear Probing)
假设给出一组表项，它们的关键码为
Burke,Ekers,Broad,Blum,Attlee,Alton,
Hecht,Ederly。采用的散列函数是：取其第
一个字母在字母表中的位臵。
Hash (x) = ord (x) - ord (?A?)
//ord ( ) 是求字符内码的函数
61
? 可得 Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
? 设散列表 HT[26],m = 26。采用 线性探查法
处理冲突,则散列结果如图所示。
0 1 2 3 4
Attlee Burke Broad Blum Ekers
Alton Ederly Hecht
5 6 7 8 9
(1) (1) (2) (3) (1)
(6) (3) (1)
62
? 需要搜索或加入一个表项时,使用散列函数
计算散列地址：
H0 = hash ( key )
? 一旦发生冲突，在表中顺次向后寻找,下一
个”空位 Hi 的递推公式为：
Hi = ( Hi-1 +1 ) % m,i =1,2,…,m-1
即用以下的线性探查序列在表中寻找,下一
个”空位 的地址：
H0 +1,H0 +2,…,m-1,0,1,2,…,H0-1
亦可写成如下的通项公式：
Hi = ( H0 + i ) % m,i =1,2,…,m-1
63
? 当发生冲突时探查下一个空位。当循环 m-1
次后就会回到开始探查时的位臵,说明待查
关键码不在表内,而且表已满,不能再插入
新关键码。
? 用 平均搜索长度 ASL衡量散列方法的性能。
? 搜索成功的平均搜索长度 ASLsucc 是指 搜索
到表中已有表项的平均探查次数 。它是找到
表中各个已有表项的探查次数的平均值。
? 搜索不成功的平均搜索长度 ASLunsucc 是
指在表中搜索不到待查的表项，但找到插入
位臵的平均探查次数 。
64
? 它是表中所有可能散列到的位臵上要插入新元
素时为找到空位的探查次数的平均值。
? 在使用线性探查法对示例进行搜索时,搜索成
功的平均搜索长度为：
? 搜索不成功的平均搜索长度为,
?
?
??????????
8
1
.
8
181)361321(1
8
1
8
1
i
CiA S L s u c c
.266226 1823456789 ??????????A S L u n s u c c
65
? 散列表存放的表项不应有重复的关键码 。
在插入新表项时,如果发现表中已经有关键
码相同的表项,则不再插入 。
? 在闭散列情形下不能真正删除表中已有表
项 。 删除表项会影响其他表项的搜索 。 若
把关键码为 Broad的表项真正删除,以后在
搜索关键码为 Blum和 Alton的表项时就查
不下去,会错误地判断表中没有关键码为
Blum和 Alton的表项 。
? 若想删除一个表项,只能给它做一个删除标
记,进行逻辑删除,不能把它真正删去 。
66
? 逻辑删除的副作用 是：在执行多次删除后,
表面上看起来散列表很满,实际上有许多位
臵没有利用。
? 线性探查方法容易产生,堆积,,不同探查
序列的关键码占据可用的空位,为寻找某一
关键码需要经历不同的探查序列,导致搜索
时间增加。
67
(2) 二次探查法 (quadratic probing)
? 为改善“堆积”问题,减少为完成搜索所需
的平均探查次数,可使用二次探查法。
? 通过某一个散列函数对表项的关键码 x 进行
计算,得到散列地址,它是一个非负整数。
H0 = hash(x)
? 二次探查法在表中寻找“下一个”空位的公
式：
Hi = (H0 + i 2 ) % m,
Hi = (H0 - i 2 ) % m,i = 1,2,…,( m-1)/2
? 式中的 m 是表的大小，它应是一个值为
4k+3 的质数，其中 k 是一个整数。 如 3,7,
11,19,23,31,43,59,127,251,503,… 。
68
? 探查序列如 H0,H0+1,H0-1,H0+4,H0-4,… 。
? 在做 (H0- i2 ) % m 的运算时,当 H0- i2 < 0 时,
运算结果也是负数 。 实际算式可改为
j = (H0- i2 ) % m,if ( j < 0 ) j += m
? 示例：给出一组关键码 { Burke,Ekers,
Broad,Blum,Attlee,Alton,Hecht,Ederly }。
散列函数为,Hash (x)＝ ord (x)－ ord ('A')
? 用它计算可得
Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
69
? 因为可能位臵是 0 ? 25,取满足 4k+3 的质数，
表的长度为 m = 31，利用二次探查法得到的
散列结果如图所示。
0 1 2 3 4 5
Blum Burke Broad Ekers Ederly
Hecht
6 7 8 9 10 11
Alton Attlee
(3) (1) (2) (1) (2)
(1)
25 26 27 28 29 30
(5) (3)
利用二次探查法处理溢出
70
? 使用 二次探查法 处理冲突时的 搜索成功的平
均搜索长度 为：
? 搜索不成功的平均搜索长度 为：
.8183)512121(38181
8
1
?????????? ?
?i
CiA S L s u c c
26
402 0)22325(6
26
1 ????????A S L u n s u c c
可以证明,当 表的长度 m为质数 且 表的装填
因子 ? 不超过 0.5 时,新的表项 x 一定能够插
入,且任何一个位臵不会被探查两次。只要表
中至少有一半空，就不会有表满问题。
71
? 在搜索时可以不考虑表满的情况 ; 但在插入
时 必须确保表的装填因子 ?不超过 0.5。 如果
超出,必须将表长度扩充一倍,进行表的分
裂 。
? 在删除一个表项时, 为确保搜索链不致中
断, 也只能做表项的逻辑删除 。
(3) 双散列法
? 使用双散列方法时,需要两个散列函数 。
? 第一个散列函数 Hash( ) 按表项的关键码
key 计算表项所在地址 H0 = Hash(key)。
72
? 一旦冲突, 利用第二个散列函数 ReHash( )
计算该表项到达, 下一个, 空位的移位量 。
它的取值与 key 的值有关,要求它的取值应
是小于地址空间大小 m,且与 m互质的正整数 。
? 若设表的长度为 m,则在表中寻找, 下一个,
空位的公式为：
j = H0 = Hash(key),p = ReHash(key)；
j = ( j + p ) % m；
p是小于 m且与 m互质的整数
73
? 利用双散列法,按一定的距离,跳跃式地寻找
“下一个”空位,减少了“堆积”的机会。
? 双散列法的探查序列也可写成：
Hi = (H0 + i * ReHash(key) ) % m，
i =1,2,…,m-1
? 最多经过 m-1次探查,它会遍历表中所有位
臵,回到 H0 位臵。
? 示例：给出一组表项关键码 { 22,41,53,46,
30,13,01,67 }。散列函数为：
Hash(x)＝ (3x) % 11。
? 散列表为 HT[0..10],m = 11。因此，再散列
函数为 ReHash(x) = (7x) % 10 +1。
74
Hi = ( Hi-1 + (7x) % 10 +1 ) % 11,i = 1,2,?
? H0(22) = 0 H0(41) = 2 H0(53) = 5
H0(46) = 6 H0(30) = 2 冲突 H1 = (2+1) = 3
H0(13) = 6 冲突 H1 = (6+2) = 8
H0(01) = 3 冲突 H1 = (3+8) = 0 冲突 H2 =
(0+8) = 8 冲突 H3 = (8+8) = 5 冲突 H4 =
(5+8) = 2 冲突 H5 = (2+8) = 10
H0(67) = 3 冲突 H1 = (3+10) = 2 冲突 H2 =
(2+10) = 1
22 67 41 30 53 46 13 01
(1) (3) (1) (2) (1) (1) (2) (6)
0 1 2 3 4 5 6 7 8 9 10
1 8 2 5 3 4 6 7
75
? 搜索成功的平均搜索长度
? 搜索不成功的平均搜索长度
? 每一散列位臵的移位量有 10种,1,2,?,
10。先计算每一散列位臵各种移位量情形
下找到下一个空位的比较次数,求出平均
值；
? 再计算各个位臵的平均比较次数的总平均
值。
22 67 41 30 53 46 13 01
(1) (3) (1) (2) (1) (1) (2) (6)
0 1 2 3 4 5 6 7 8 9 10
8
176)211213(1
8
1 ?????????A S L s u c c
76
? Rehash( )的取法很多 。 例如,当 m是质数时,
可定义
? ReHash(key) = key % (m-2) +1
? ReHash(key) = ?key / m? % (m-2)+1
? 当 m 是 2 的方幂时,ReHash(key) 可取从 0
到 m-1 中的任意一个奇数。
77
处理冲突的开散列方法 — 链地址法
? 开散列方法首先对关键码集合用某一个散列
函数计算它们的存放位臵 。
? 若设散列表地址空间的所有位臵是从 0 到
m-1,则关键码集合中的所有关键码被划分
为 m个子集,具有相同地址的关键码归于同
一子集 。 我们称同一子集中的关键码互为同
义词 。 每一个子集称为一个桶 。
? 通常各个桶中的表项通过一个单链表链接起
来, 称之为同义词子表 。 所有桶号相同的表
项都链接在同一个同义词子表中, 各链表的
表头结点组成一个向量 。
78
? 向量的元素个数与桶数一致。桶号为 i 的同义
词子表的表头结点是向量中的第 i 个元素。
? 示例：给出一组表项关键码 { Burke,Ekers,
Broad,Blum,Attlee,Alton,Hecht,Ederly }。
散列函数为,Hash (x)＝ ord (x)－ ord ('A')。
? 用它计算可得：
Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
? 散列表为 HT[0..25],m = 26。
79
0
1
2
3
4
5
6
7
8
9
Attlee Alton
Burke Broad Blum
Ekers Ederly
Ekers 8
13
8
1*33*24*1 ????
s u c cA S L
26
34
18)*12
113114(3
26
1
???
????????u n s u c cA S L
80
? 通常, 每个桶中的同义词子表都很短, 设有
n 个关键码通过某一个散列函数, 存放到散
列表中的 m 个桶中 。 那么每一个桶中的同义
词子表的平均长度为 n / m。 以搜索平均长度
为 n / m 的同义词子表代替了搜索长度为 n
的顺序表, 搜索速度快得多 。
? 应用开散列法处理冲突,需要增设链接指针,
似乎增加了存储开销。事实上,由于闭散列
法必须保持大量的空闲空间以确保搜索效率，
如二次探查法要求装填因子 ?? 0.5，而表项
所占空间又比指针大得多，所以 使用开散列
法 反而 比闭散列法节省存储空间 。
81
散列表分析
? 散列表是一种直接计算记录存放地址的方
法，它在关键码与存储位臵之间直接建立
了映象。
? 当选择的散列函数能够得到均匀的地址分
布时,在搜索过程中可以不做多次探查。
? 由于很难避免冲突,增加了搜索时间。 冲
突的出现,与 散列函数的选取 (地址分布是
否均匀 ),处理冲突的方法 (是否产生堆积 )
有关。
? 下图给出一些实验结果。
82
? = n / m 0, 5 0 0, 7 5 0, 9 0 0, 9 5
散列函数
种类
开散
列法
闭散
列法
开散
列法
闭散
列法
开散
列法
闭散
列法
开散
列法
闭散
列法
平平 方方 取取 中中 11,,22 66 11,,77 33 11,,44 00 99,,77 55 11,,44 55 33 11 00,,11 44 11,,44 77 33 11 00,,55 33
除留余数 1, 1 9 4, 5 2 1, 3 1 1 0, 2 0 1, 3 8 2 2, 4 2 1, 4 1 2 5, 7 9
移位折叠 1, 3 3 2 1, 7 5 1, 4 8 6 5, 1 0 1, 4 0 7 1 0, 0 1 1, 5 1 1 1 8, 5 7
分界折叠 1, 3 9 2 2, 9 7 1, 5 7 4 8, 7 0 1, 5 5 6 9, 6 3 1, 5 1 9 1 0, 5 6
数字分析 1, 3 5 4, 5 5 1, 4 9 3 0, 6 2 1, 5 2 8 9, 2 0 1, 5 2 1 2 5, 5 9
理论值 1, 2 5 1, 5 0 1, 3 7 2, 5 0 1, 4 5 5, 5 0 1, 4 8 1 0, 5 0
搜索关键码时所需对桶的平均访问次数
从图中可以看出,开散列法优于闭散列法 ；
在散列函数中,用除留余数法作散列函数优于
其它类型的散列函数,最差的是折叠法。
83
? 当装填因子 ?较高时,选择的散列函数不
同,散列表的搜索性能差别很大。在一般情
况下多选用除留余数法,其中的除数在实用
上应选择不含有 20以下的质因数的质数。
? 对散列表技术进行的实验评估表明,它 具有
很好的平均性能,优于一些传统的技术,如
平衡树 。但散列表 在最坏情况下性能很不好 。
如果对一 个有 n 个关键码的散列表执行一
次搜索或插入操作，最坏情况下需要 O(n)
的时间。
? Knuth对不同的冲突处理方法进行了分析。
84
? 若设 ? 是散列表的装填因子：
? 用地址分布均匀的散列函数 Hash( )计算桶号。
? Sn 是搜索一个随机选择的关键码 xi (1 ? i ? n)
所需的关键码比较次数的期望值
? Un 是在长度为 m 的散列表中 n 个桶已装入表
项的情况下，装入第 n+1 项所需执行的关键
码比较次数期望值 。
? 前者称为在 ? = n / m 时的搜索成功的平均搜
索长度，后者称为在 ?= n / m时的搜索不成功
的平均搜索长度。
m
n??
表中预设的最大记录数
表中已装有记录数?
85
? 用不同的方法溢出处理冲突时散列表的平均
搜索长度如图所示。
平 均 搜 索 长 度 ASL
处 理 冲 突
的 方 法
搜索成功
Sn
搜索不成功 Un
( 登入新记录 )
闭
散
线性探查法
?
?
?
?
?
?
???
?
??
?
?
?
?
?
?
?
?
?
?
?
???
?
??
?
?
)(
列
法
伪随机探查法
二次探查法
双散列法
? ??
?
??
?
?
?
?
?
? 1l o g
1
e
???
?
开 散 列 法
( 同义词子表法 )
?
?
?? ????
??
e
86
? 散列表的装填因子 ? 表明了表中的装满程
度 。 越大,说明表越满,再插入新元素时发生
冲突的可能性就越大 。
? 散列表的搜索性能,即 平均搜索长度 依赖于
散列表的装填因子,不直接依赖于 n 或 m。
? 不论表的长度有多大,我们总能选择一个合
适的装填因子,以把平均搜索长度限制在一
定范围内 。
87
例 求散列表大小并设计散列函数
? 设有一个含 200个表项的散列表，用二次探查
法解决冲突，按关键码查询时找到一个新表
项插入位臵的平均探查次数不超过 1.5，则散
列表项应能够至少容纳多少个表项。再设计
散列函数 （设搜索不成功的平均搜索长度为
Un＝ 1 / (1 -α),其中 α为装填因子）
? 解答：设表中表项个数 n = 200，搜索不成功
的平均搜索长度
Un＝ 1 / (1 -α) ? 1.5 ??? 1/3
? n / m = 200 / m = ?? 1/3 m ? 600
