第 7章 查找技术
查找 —— 也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素
关键字 —— 是数据元素中某个数据项的值，它可以标识一个数据元素
查找方法评价
查找速度
占用存储空间多少
算法本身复杂程度
平均查找长度 ASL(Average Search Length),为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的 ~
个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：
个记录的表，对含有
ic
pip
cpA S Ln
i
n
i
ii
n
i
ii
1
1
1
§ 7.1 顺序查找
查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较
算法描述
Ch7_1.c
i
例 0 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找 64
64
i i i i
比较次数 =5比较次数：
查找第 n个元素,1
查找第 n-1个元素,2
……….
查找第 1个元素,n
查找第 i个元素,n+1-i
查找失败,n+1
顺序查找方法的 ASL
2
1
2
)1(11
1
11
nnn
n
i
n
cpA SL
n
p
n
i
n
i
ii
i
则概率相等设表中每个元素的查找
n
i
ii cpA S Ln
1
个记录的表，对含有
§ 7.2 折半查找
查找过程：每次将待查记录所在区间缩小一半
适用条件：采用顺序存储结构的有序表
算法实现
设表长为 n,low,high和 mid分别指向待查元素所在区间的上界、下界和中点,k为给定值
初始时，令 low=1,high=n,mid=?(low+high)/2?
让 k与 mid指向的记录比较
若 k==r[mid].key,查找成功
若 k<r[mid].key,则 high=mid-1
若 k>r[mid].key,则 low=mid+1
重复上述操作，直至 low>high时，查找失败
算法描述
low highmid
例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
找 21
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
Ch7_2.c
例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
找 70
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low high
mid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
lowhigh
11852
10741
93
6判定树：
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
算法评价
判定树：描述查找过程的二叉树叫 ~
有 n个结点的判定树的深度为?log2n?+1
折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度
折半查找的 ASL
1)1(l o g1)1(l o g
1
2
11
1
),1(l o g,12
22
1
1
11
2
nn
n
n
j
n
c
n
cpA S L
n
p
hnhn
h
j
j
n
i
i
n
i
ii
i
h
则：
概率相等设表中每个记录的查找的满二叉树即判定树是深度为设表长
§ 7.3 分块查找
查找过程：将表分成几块，块内无序，块间有序；
先确定待查记录所在块，再在块内查找
适用条件：分块有序表
算法实现
用数组存放待查记录,每个数据元素至少含有关键字域
建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针
算法描述
Ch7_3.c
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53
22 48 86
1 7 13
索引表查 38
分块查找方法评价
2
)1(l o g)2(
1)(
2
1
2
1
2
111
)1(
2
11
s
s
n
A S L
s
s
nsb
i
s
j
b
A S L
sbn
L
L
LLA S L
bs
s
i
b
j
bs
w
b
wbbs
：用折半查找确定所在块
：用顺序查找确定所在块查找概率相等，则：
记录的个记录，并设表中每个块，每块含的表平均分成若将表长为均查找长度—在块中查找元素的平—
块的平均查找长度—查找索引表确定所在—其中：
ASL 最大 最小 两者之间表结构 有序表、无序表 有序表 分块有序表存储结构 顺序存储结构线性链表顺序存储结构 顺序存储结构线性链表查找方法比较顺序查找 折半查找 分块查找
二叉排序树
定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉排序树
二叉排序树的插入
插入原则：若二叉排序树为空，则插入结点应为新的根结点；
否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
插入算法例 {10,18,3,8,12,2,7,3}
10 10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
中序遍历二叉排序树可得到一个关键字的有序序列Ch5_9.c
二叉排序树的删除要删除二叉排序树中的 p结点，分三种情况：
p为叶子结点，只需修改 p双亲 f的指针 f->lchild=NULL
f->rchild=NULL
p只有左子树或右子树
p只有左子树，用 p的左孩子代替 p (1)(2)
p只有右子树，用 p的右孩子代替 p (3)(4)
p左、右子树均非空
沿 p左子树的根 C的右子树分支找到 S,S的右子树为空，
将 S的左子树成为 S的双亲 Q的右子树，用 S取代 p (5)
若 C无右子树，用 C取代 p (6)
S
Q
PL
P
中序遍历,Q S PL P
S
Q PL
中序遍历,Q S PL
(2)
S
P
PL
Q
中序遍历,PL P S Q
S
PL Q
中序遍历,PL S Q
(1)
中序遍历,P PR S Q
S
PR Q
中序遍历,PR S Q
(3)
S
P
PR
Q
中序遍历,Q S P PR
S
Q PR
中序遍历,Q S PR
(4)
S
Q
PR
P
F
P
C PR
CL Q
QL S
SL
中序遍历,CL C ……Q L Q SL S P PR F
F
S
C PR
CL Q
QL SL
中序遍历,CL C ……Q L Q SL S PR F(5)
F
P
C PR
CL
中序遍历,CL C P PR F
F
C
PRCL
中序遍历,CL C PR F
(6)
删除算法例 80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
Ch5_10.c
§ 7.4 哈希查找
基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，
一次存取就能得到所查元素的查找方法
定义
哈希函数 —— 在记录的关键字与记录的存储地址之间建立的一种对应关系叫 ~
哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象
哈希函数可写成,addr(ai)=H(ki)
ai是表中的一个元素
addr(ai)是 ai的存储地址
ki是 ai的关键字 关键字集合存储地址集合
hash
哈希表 —— 应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫 ~
哈希查找 —— 又叫散列查找，利用哈希函数进行查找的过程叫 ~
例 30个地区的各民族人口统计表编号 地区别 总人口 汉族 回族 …...
1 北京
2 上海
…..,…...
以编号作关键字，
构造 哈希函数,H(key)=key
H(1)=1
H(2)=2
以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数,H(Beijing)=2
H(Shanghai)=19
H(Shenyang)=19
从例子可见：
哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可
冲突,key1?key2,但 H(key1)=H(key2)的现象叫 ~
同义词：具有相同函数值的两个关键字，叫该哈希函数的 ~
哈希函数通常是一种压缩映象，所以冲突不可避免,只能尽量减少；同时，冲突发生后，应该有处理冲突的方法
哈希函数的构造方法
直接定址法
构造：取关键字或关键字的某个线性函数作哈希地址，即
H(key)=key 或 H(key)=a·key+b
特点
直接定址法所得地址集合与关键字集合大小相等，不会发生冲突
实际中能用这种哈希函数的情况很少
数字分析法
构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址
适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况例 有 80个记录，关键字为 8位十进制数，哈希地址为 2位十进制数
8 1 3 4 6 5 3 2
8 1 3 7 2 2 4 2
8 1 3 8 7 4 2 2
8 1 3 0 1 3 6 7
8 1 3 2 2 8 1 7
8 1 3 3 8 9 6 7
8 1 3 6 8 5 3 7
8 1 4 1 9 3 5 5
…..
…..
分析,?只取 8
只取 1
只取 3,4
只取 2,7,5
数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址
除留余数法
构造：取关键字被某个不大于哈希表表长 m的数 p除后所得余数作哈希地址，即 H(key)=key MOD p,p?m
特点
简单、常用，可与上述几种方法结合使用
p的选取很重要； p选的不好，容易产生同义词
随机数法
构造：取关键字的随机函数值作哈希地址，即
H(key)=random(key)
适于关键字长度不等的情况
选取哈希函数，考虑以下因素：
计算哈希函数所需时间
关键字长度
哈希表长度（哈希地址范围）
关键字分布情况
记录的查找频率
处理冲突的方法
开放定址法
方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即 Hi=(H(key)+di)MOD m，
i=1,2,……k(k?m-1)
其中,H(key)—— 哈希函数
m—— 哈希表表长
di—— 增量序列
分类
线性探测再散列,di=1,2,3,……m -1
伪随机探测再散列,di=伪随机数序列例 表长为 11的哈希表中已填有关键字为 17,60,29的记录，
H(key)=key MOD 11,现有第 4个记录，其关键字为 38，
按处理冲突的方法，将它填入表中
0 1 2 3 4 5 6 7 8 9 10
60 17 29
(1) H(38)=38 MOD 11=5 冲突
H1=(5+1) MOD 11=6 冲突
H2=(5+2) MOD 11=7 冲突
H3=(5+3) MOD 11=8 不冲突
38
(2) H(38)=38 MOD 11=5 冲突设伪随机数序列为 9，则：
H1=(5+9) MOD 11=3 不冲突
38
链地址法
方法：将所有关键字为同义词的记录存储在一个单链表中，
并用一维数组存放头指针例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为,H(key)=key MOD 13,
用链地址法处理冲突
0
1
2
3
4
5
6
7
8
9
10
11
12
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
哈希查找过程给定 k值计算 H(k)
此地址为空关键字 ==k
查找失败查找成功按处理冲突方法计算 Hi
Y
N
Y
N
哈希查找过程仍是一个给定值与关键字进行比较的过程
评价哈希查找效率仍要用 ASL
哈希查找过程与给定值进行比较的关键字的个数取决于：
哈希函数
处理冲突的方法
哈希表的填满因子?=表中填入的记录数 /哈希表长度
1.线性探查法的性能分析由于线性探查法解决冲突是线性地查找空闲位置的,平均查找长度与表的大小 m无关,只与所选取的散列函数 H及装填因子 α 的值和该处理方法有关,这时的成功的平均查找长度为 ASL=1/2 (1+1/(1- α))
2.拉链法查找的性能分析由于拉链法查找就是在单链表上查找，查找单链表中第一个结点的次数为 1，第二个结点次数为 2，其余依次类推。它的平均查找长度 ASL=1+α/2
例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为,H(key)=key MOD 13,哈希表长为 m=16，
设每个记录的查找概率相等
(1) 用线性探测再散列处理冲突，即 Hi=(H(key)+di) MOD m
H(55)=3 冲突,H1=(3+1)MOD16=4
冲突,H2=(3+2)MOD16=5
H(79)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
冲突,H4=(1+4)MOD16=5
冲突,H5=(1+5)MOD16=6
冲突,H6=(1+6)MOD16=7
冲突,H7=(1+7)MOD16=8
冲突,H8=(1+8)MOD16=9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ASL=(1*6+2+3*3+4+9)/12=2.5
14 1 68 27 55 19 20 84 79 23 11 10
H(19)=6
H(14)=1
H(23)=10
H(1)=1 冲突,H1=(1+1) MOD16=2
H(68)=3
H(20)=7
H(84)=6 冲突,H1=(6+1)MOD16=7
冲突,H2=(6+2)MOD16=8
H(27)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
H(11)=11
H(10)=10 冲突,H1=(10+1)MOD16=11
冲突,H2=(10+2)MOD16=12
(2) 用链地址法处理冲突
0
1
2
3
4
5
6
7
8
9
10
11
12
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
ASL=(1*6+2*4+3+4)/12=1.75
关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希查找算法实现
用线性探测再散列法处理冲突
实现
查找过程：同前
删除：只能作标记，不能真正删除
插入：遇到空位置或有删除标记的位置就可以插入
算法描述：
用外链表处理冲突算法
Ch7_4.c
Ch7_5.c
例给定关键字序列 11,78,10,1,3,2,4,21，
试分别用顺序查找,二分查找,二叉排序树查找,、
散列查找 (用线性探查法和拉链法 )来实现查找,试画出它们的对应存储形式 (顺序查找的顺序表,二分查找的判定树,二叉排序树查找的二叉排序树,两种散列查找的散列表 ),并求出每一种查找的成功平均查找长度 。 散列函数 H(k)=k%11。
顺序查找的顺序表（一维数组）如图 1所示,
1 1 7 8 1 0 1 3 2 4 2 1
0 1 2 3 4 5 6 7 8 9 10
图 1 顺序存储的顺序表从图 1可以得到顺序查找的成功平均查找长度为：
ASL=(1+2+3+4+5+6+7+8)/8=4.5；
二分查找的判定树（中序序列为从小到大排列的有序序列）如图 2所示，
4
2
1 3
1 1
10 21
78
图 2 二分查找的判定树从图 2可以得到二分查找的成功平均查找长度为：
ASL=(1+2*2+3*4+4)/8=2.625；
二叉排序树（关键字顺序已确定，该二叉排序树应唯一）
如图 8-3所示，
1 1
10 78
1
21
3
2 4
图 3 二叉排序树及平衡二叉树从图 3可以得到二叉排序树查找的成功平均查找长度为：
ASL=(1+2*2+3*2+4+5*2)=3.125；
线性探查法解决冲突的散列表如图 4所示，
1 1 78 1 3 2 4 21 10
0 1 2 3 4 5 6 7 8 9 10
图 4 线性探查的散列表从图 4可以得到线性探查法的成功平均查找长度为：
ASL=（ 1+1+2+1+3+2+1+8） /8=2.375；
拉链法解决冲突的散列表如图 5所示 。
0
1
2
3
4
5
6
7
8
9
10
^
^
^
^
^
1
^ 78
11
^
1
^ 78
2
^
3
^
4
^
图 5 拉链法的散列表从图 5可以得到拉链法的成功平均查找长度为：
ASL=(1*6+2*2)/8=1.25。
查找 —— 也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素
关键字 —— 是数据元素中某个数据项的值，它可以标识一个数据元素
查找方法评价
查找速度
占用存储空间多少
算法本身复杂程度
平均查找长度 ASL(Average Search Length),为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的 ~
个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：
个记录的表，对含有
ic
pip
cpA S Ln
i
n
i
ii
n
i
ii
1
1
1
§ 7.1 顺序查找
查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较
算法描述
Ch7_1.c
i
例 0 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找 64
64
i i i i
比较次数 =5比较次数：
查找第 n个元素,1
查找第 n-1个元素,2
……….
查找第 1个元素,n
查找第 i个元素,n+1-i
查找失败,n+1
顺序查找方法的 ASL
2
1
2
)1(11
1
11
nnn
n
i
n
cpA SL
n
p
n
i
n
i
ii
i
则概率相等设表中每个元素的查找
n
i
ii cpA S Ln
1
个记录的表，对含有
§ 7.2 折半查找
查找过程：每次将待查记录所在区间缩小一半
适用条件：采用顺序存储结构的有序表
算法实现
设表长为 n,low,high和 mid分别指向待查元素所在区间的上界、下界和中点,k为给定值
初始时，令 low=1,high=n,mid=?(low+high)/2?
让 k与 mid指向的记录比较
若 k==r[mid].key,查找成功
若 k<r[mid].key,则 high=mid-1
若 k>r[mid].key,则 low=mid+1
重复上述操作，直至 low>high时，查找失败
算法描述
low highmid
例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
找 21
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
Ch7_2.c
例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
找 70
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low high
mid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
lowhigh
11852
10741
93
6判定树：
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
算法评价
判定树：描述查找过程的二叉树叫 ~
有 n个结点的判定树的深度为?log2n?+1
折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度
折半查找的 ASL
1)1(l o g1)1(l o g
1
2
11
1
),1(l o g,12
22
1
1
11
2
nn
n
n
j
n
c
n
cpA S L
n
p
hnhn
h
j
j
n
i
i
n
i
ii
i
h
则：
概率相等设表中每个记录的查找的满二叉树即判定树是深度为设表长
§ 7.3 分块查找
查找过程：将表分成几块，块内无序，块间有序；
先确定待查记录所在块，再在块内查找
适用条件：分块有序表
算法实现
用数组存放待查记录,每个数据元素至少含有关键字域
建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针
算法描述
Ch7_3.c
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53
22 48 86
1 7 13
索引表查 38
分块查找方法评价
2
)1(l o g)2(
1)(
2
1
2
1
2
111
)1(
2
11
s
s
n
A S L
s
s
nsb
i
s
j
b
A S L
sbn
L
L
LLA S L
bs
s
i
b
j
bs
w
b
wbbs
：用折半查找确定所在块
：用顺序查找确定所在块查找概率相等，则：
记录的个记录，并设表中每个块，每块含的表平均分成若将表长为均查找长度—在块中查找元素的平—
块的平均查找长度—查找索引表确定所在—其中：
ASL 最大 最小 两者之间表结构 有序表、无序表 有序表 分块有序表存储结构 顺序存储结构线性链表顺序存储结构 顺序存储结构线性链表查找方法比较顺序查找 折半查找 分块查找
二叉排序树
定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉排序树
二叉排序树的插入
插入原则：若二叉排序树为空，则插入结点应为新的根结点；
否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
插入算法例 {10,18,3,8,12,2,7,3}
10 10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
中序遍历二叉排序树可得到一个关键字的有序序列Ch5_9.c
二叉排序树的删除要删除二叉排序树中的 p结点，分三种情况：
p为叶子结点，只需修改 p双亲 f的指针 f->lchild=NULL
f->rchild=NULL
p只有左子树或右子树
p只有左子树，用 p的左孩子代替 p (1)(2)
p只有右子树，用 p的右孩子代替 p (3)(4)
p左、右子树均非空
沿 p左子树的根 C的右子树分支找到 S,S的右子树为空，
将 S的左子树成为 S的双亲 Q的右子树，用 S取代 p (5)
若 C无右子树，用 C取代 p (6)
S
Q
PL
P
中序遍历,Q S PL P
S
Q PL
中序遍历,Q S PL
(2)
S
P
PL
Q
中序遍历,PL P S Q
S
PL Q
中序遍历,PL S Q
(1)
中序遍历,P PR S Q
S
PR Q
中序遍历,PR S Q
(3)
S
P
PR
Q
中序遍历,Q S P PR
S
Q PR
中序遍历,Q S PR
(4)
S
Q
PR
P
F
P
C PR
CL Q
QL S
SL
中序遍历,CL C ……Q L Q SL S P PR F
F
S
C PR
CL Q
QL SL
中序遍历,CL C ……Q L Q SL S PR F(5)
F
P
C PR
CL
中序遍历,CL C P PR F
F
C
PRCL
中序遍历,CL C PR F
(6)
删除算法例 80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
Ch5_10.c
§ 7.4 哈希查找
基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，
一次存取就能得到所查元素的查找方法
定义
哈希函数 —— 在记录的关键字与记录的存储地址之间建立的一种对应关系叫 ~
哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象
哈希函数可写成,addr(ai)=H(ki)
ai是表中的一个元素
addr(ai)是 ai的存储地址
ki是 ai的关键字 关键字集合存储地址集合
hash
哈希表 —— 应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫 ~
哈希查找 —— 又叫散列查找，利用哈希函数进行查找的过程叫 ~
例 30个地区的各民族人口统计表编号 地区别 总人口 汉族 回族 …...
1 北京
2 上海
…..,…...
以编号作关键字，
构造 哈希函数,H(key)=key
H(1)=1
H(2)=2
以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数,H(Beijing)=2
H(Shanghai)=19
H(Shenyang)=19
从例子可见：
哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可
冲突,key1?key2,但 H(key1)=H(key2)的现象叫 ~
同义词：具有相同函数值的两个关键字，叫该哈希函数的 ~
哈希函数通常是一种压缩映象，所以冲突不可避免,只能尽量减少；同时，冲突发生后，应该有处理冲突的方法
哈希函数的构造方法
直接定址法
构造：取关键字或关键字的某个线性函数作哈希地址，即
H(key)=key 或 H(key)=a·key+b
特点
直接定址法所得地址集合与关键字集合大小相等，不会发生冲突
实际中能用这种哈希函数的情况很少
数字分析法
构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址
适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况例 有 80个记录，关键字为 8位十进制数，哈希地址为 2位十进制数
8 1 3 4 6 5 3 2
8 1 3 7 2 2 4 2
8 1 3 8 7 4 2 2
8 1 3 0 1 3 6 7
8 1 3 2 2 8 1 7
8 1 3 3 8 9 6 7
8 1 3 6 8 5 3 7
8 1 4 1 9 3 5 5
…..
…..
分析,?只取 8
只取 1
只取 3,4
只取 2,7,5
数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址
除留余数法
构造：取关键字被某个不大于哈希表表长 m的数 p除后所得余数作哈希地址，即 H(key)=key MOD p,p?m
特点
简单、常用，可与上述几种方法结合使用
p的选取很重要； p选的不好，容易产生同义词
随机数法
构造：取关键字的随机函数值作哈希地址，即
H(key)=random(key)
适于关键字长度不等的情况
选取哈希函数，考虑以下因素：
计算哈希函数所需时间
关键字长度
哈希表长度（哈希地址范围）
关键字分布情况
记录的查找频率
处理冲突的方法
开放定址法
方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即 Hi=(H(key)+di)MOD m，
i=1,2,……k(k?m-1)
其中,H(key)—— 哈希函数
m—— 哈希表表长
di—— 增量序列
分类
线性探测再散列,di=1,2,3,……m -1
伪随机探测再散列,di=伪随机数序列例 表长为 11的哈希表中已填有关键字为 17,60,29的记录，
H(key)=key MOD 11,现有第 4个记录，其关键字为 38，
按处理冲突的方法，将它填入表中
0 1 2 3 4 5 6 7 8 9 10
60 17 29
(1) H(38)=38 MOD 11=5 冲突
H1=(5+1) MOD 11=6 冲突
H2=(5+2) MOD 11=7 冲突
H3=(5+3) MOD 11=8 不冲突
38
(2) H(38)=38 MOD 11=5 冲突设伪随机数序列为 9，则：
H1=(5+9) MOD 11=3 不冲突
38
链地址法
方法：将所有关键字为同义词的记录存储在一个单链表中，
并用一维数组存放头指针例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为,H(key)=key MOD 13,
用链地址法处理冲突
0
1
2
3
4
5
6
7
8
9
10
11
12
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
哈希查找过程给定 k值计算 H(k)
此地址为空关键字 ==k
查找失败查找成功按处理冲突方法计算 Hi
Y
N
Y
N
哈希查找过程仍是一个给定值与关键字进行比较的过程
评价哈希查找效率仍要用 ASL
哈希查找过程与给定值进行比较的关键字的个数取决于：
哈希函数
处理冲突的方法
哈希表的填满因子?=表中填入的记录数 /哈希表长度
1.线性探查法的性能分析由于线性探查法解决冲突是线性地查找空闲位置的,平均查找长度与表的大小 m无关,只与所选取的散列函数 H及装填因子 α 的值和该处理方法有关,这时的成功的平均查找长度为 ASL=1/2 (1+1/(1- α))
2.拉链法查找的性能分析由于拉链法查找就是在单链表上查找，查找单链表中第一个结点的次数为 1，第二个结点次数为 2，其余依次类推。它的平均查找长度 ASL=1+α/2
例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为,H(key)=key MOD 13,哈希表长为 m=16，
设每个记录的查找概率相等
(1) 用线性探测再散列处理冲突，即 Hi=(H(key)+di) MOD m
H(55)=3 冲突,H1=(3+1)MOD16=4
冲突,H2=(3+2)MOD16=5
H(79)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
冲突,H4=(1+4)MOD16=5
冲突,H5=(1+5)MOD16=6
冲突,H6=(1+6)MOD16=7
冲突,H7=(1+7)MOD16=8
冲突,H8=(1+8)MOD16=9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ASL=(1*6+2+3*3+4+9)/12=2.5
14 1 68 27 55 19 20 84 79 23 11 10
H(19)=6
H(14)=1
H(23)=10
H(1)=1 冲突,H1=(1+1) MOD16=2
H(68)=3
H(20)=7
H(84)=6 冲突,H1=(6+1)MOD16=7
冲突,H2=(6+2)MOD16=8
H(27)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
H(11)=11
H(10)=10 冲突,H1=(10+1)MOD16=11
冲突,H2=(10+2)MOD16=12
(2) 用链地址法处理冲突
0
1
2
3
4
5
6
7
8
9
10
11
12
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
ASL=(1*6+2*4+3+4)/12=1.75
关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希查找算法实现
用线性探测再散列法处理冲突
实现
查找过程：同前
删除：只能作标记，不能真正删除
插入：遇到空位置或有删除标记的位置就可以插入
算法描述：
用外链表处理冲突算法
Ch7_4.c
Ch7_5.c
例给定关键字序列 11,78,10,1,3,2,4,21，
试分别用顺序查找,二分查找,二叉排序树查找,、
散列查找 (用线性探查法和拉链法 )来实现查找,试画出它们的对应存储形式 (顺序查找的顺序表,二分查找的判定树,二叉排序树查找的二叉排序树,两种散列查找的散列表 ),并求出每一种查找的成功平均查找长度 。 散列函数 H(k)=k%11。
顺序查找的顺序表（一维数组）如图 1所示,
1 1 7 8 1 0 1 3 2 4 2 1
0 1 2 3 4 5 6 7 8 9 10
图 1 顺序存储的顺序表从图 1可以得到顺序查找的成功平均查找长度为：
ASL=(1+2+3+4+5+6+7+8)/8=4.5；
二分查找的判定树（中序序列为从小到大排列的有序序列）如图 2所示，
4
2
1 3
1 1
10 21
78
图 2 二分查找的判定树从图 2可以得到二分查找的成功平均查找长度为：
ASL=(1+2*2+3*4+4)/8=2.625；
二叉排序树（关键字顺序已确定，该二叉排序树应唯一）
如图 8-3所示，
1 1
10 78
1
21
3
2 4
图 3 二叉排序树及平衡二叉树从图 3可以得到二叉排序树查找的成功平均查找长度为：
ASL=(1+2*2+3*2+4+5*2)=3.125；
线性探查法解决冲突的散列表如图 4所示，
1 1 78 1 3 2 4 21 10
0 1 2 3 4 5 6 7 8 9 10
图 4 线性探查的散列表从图 4可以得到线性探查法的成功平均查找长度为：
ASL=（ 1+1+2+1+3+2+1+8） /8=2.375；
拉链法解决冲突的散列表如图 5所示 。
0
1
2
3
4
5
6
7
8
9
10
^
^
^
^
^
1
^ 78
11
^
1
^ 78
2
^
3
^
4
^
图 5 拉链法的散列表从图 5可以得到拉链法的成功平均查找长度为：
ASL=(1*6+2*2)/8=1.25。
