Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 1页第 8章 查找表
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 2页基本概念
查找表 是由 同一类型 的数据元素 (或记录 )构成的集合。
由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。
对查找表经常进行的操作,
1） 查询某个,特定的,数据元素是否在查找表中；
2） 检索某个,特定的,数据元素的各种属性；
3） 在查找表中 插入 一个数据元素；
4） 从查找表中 删去 某个数据元素 。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 3页查找表可分为两类
静态查找表仅作 查询 和 检索 操作的查找表。
动态查找表有时在查询之后，还需要将,查询,结果为,不在查找表中,的数据元素 插入 到查找表中；或者，从查找表中 删除 其,查询,结果为,在查找表中,的数据元素。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 4页
关键字 是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。
若此关键字可以识别唯一的一个记录，则称之谓,主关键字,。若此关键字能识别若干记录，则称之谓
,次关键字,。
查找 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
– 若查找表中存在这样一个记录，则称,查找成功,。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；
否则称,查找不成功,。查找结果给出,空记录,或,空指针,。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 5页如何进行查找？
查找的方法取决于查找表的结构。
由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。
为了提高查找的效率,需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说,用另外一种结构来表示查找表
– 静态查找表
– 动态查找树表
– 哈希表
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 6页
8.1 静态查找表抽象数据类型
ADT StaticSearchTable {
数据对象 D：
D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素数据关系 R：
数据元素同属一个集合。
基本操作 P：
Create(&ST,n);
Destroy(&ST);
Search(ST,key);
Traverse(ST,Visit());
} ADT StaticSearchTable
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 7页静态查找表的存储
静态查找表基本上不采用插入和删除操作，因此通常以顺序存储结构的线形表或有序表存储假设静态查找表的顺序存储结构为
typedef struct {
ElemType *elem;
// 数据元素存储空间基址，建表时按实际
// 长度分配,0号单元留空
int length; // 表的长度
} SSTable;
数据元素类型的定义为,
typedef struct {
keyType key; // 关键字域
… … // 其它属性域
} ElemType
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 8页
8.1.1 顺序查找表
以顺序表或线性链表表示静态查找表
回顾顺序表的查找过程：
算法 2.5
int LocateElem_Sq( SqList L,ElemType e)
{
// 在顺序线性表 L 中查找第 1 个值与 e 相等的数据元素，
// 若找到，则返回其在 L 中的位序，否则返回 0
i = 1; // i 的初值为第 1 个元素的位序
p = L.elem; // p 的初值为第 1 个元素的存储位置
while (i <= L.length && *p++ != e ) ++i; // 依次进行判定
if (i <= L.length) return i; // 找到满足判定的数据元素为第 i 个元素
else return 0; // 该线性表中不存在满足判定的数据元素
} // LocateElem_Sq
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 9页
以顺序表或线性链表表示静态查找表
假设给定值 e=64,
要求 ST.elem[k] = e,问,k =?
21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 11
ST.Length
ST.elem
k k
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 10页设置“哨兵” 21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 1 1
S T,L e ngt h
ST.elem i
21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 1 1
S T,L e ngt h
ST.elem
i
60
i
key=64
key=60
i
64
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 11页算法 8.1
int Search_Seq (SSTable ST,KeyType kval)
{
// 在顺序表 ST中顺序查找其关键字等于 kval的数据元素。
// 若找到，则函数值为该元素在表中的位置，
否则为 0。
ST.elem[0].key = kval; // 设置 "哨兵 "
for (i=ST.length; ST.elem[i].key != kval; --i);
// 从后往前查找
return i; // 找不到时,i为 0
} // Search_Seq
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 12页分析顺序查找的时间性能
定义,查找算法的 平均查找长度 (Average Search Length)
为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值其中,n 为表长,Pi 为查找表中第 i个记录的概率，且,
Ci为找到该记录时，曾和给定值比较过的关键字的个数。
n
i
iiCPA S L
1
1
1
n
i
iP
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 13页对顺序表而言,Ci = n-i+1
ASL = nP1 +(n-1)P2 +…… +2P n-1+Pn
在等概率查找的情况下，
nPi
1?
顺序表查找的平均查找长度 为：
2
111
1
n)i(n
nA S L
n
i
ss
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 14页
8.1.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时，查找失败
05 13 19 21 37 56 64 75 80 88 92
0 1 2 3 4 5 6 7 8 9 10 1 1
ST.elem
ST.length
例如,key=64 的查找过程如下：
low high
mid
low
mid
high
mid
low 指示查找区间的下界
high 指示查找区间的上界
mid = (low+high)/2
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 16页算法 8.2
int Search_Bin ( SSTable ST,KeyType kval )
{
// 在有序表 ST中折半查找其关键字等于 kval的数据元素。若找到，则函
// 数值 为该元素在表中的位置，否则为 0。
low = 1; high = ST.length; // 置区间初值
while (low <= high) {
mid = (low + high) / 2;
if （ kval == ST.elem[mid].key )
return mid; // 找到待查元素
else
if ( kval < ST.elem[mid].key )
high = mid - 1; // 继续在前半区间内进行查找
else
low = mid + 1; // 继续在后半区间内进行查找
} //while
return 0; // 顺序表中不存在待查元素
} // Search_Bin
先看一个具体的情况，假设,n=11
分析 折半查找 的平均查找长度
6
3 9
1 4
2 5
7
8
10
11
判定树
i 1 2 3 4 5 6 7 8 9 10 11
Ci
12 23 3 3 34 4 4 4
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 18页
一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。
假设 n=2h-1 并且查找概率相等则在 n>50时，可得近似结果
1)1(l o g1211 2
1
1
1
nnnjnCnA S L
h
j
j
n
i
ibs
1)1(l o g 2 nA S L bs
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 19页
8.1.3 分块查找
查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找
适用条件：分块有序表
算法实现
– 用数组存放待查记录,每个数据元素至少含有关键字域
– 建立索引表，每个索引表结点含有最大关键字域和指向本块第 1
个结点的指针
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
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 20页分块查找方法评价
ASL(n)=ASL(b)+ASL(n/b)
其中：
ASL(b)查找索引表确定所在块的平均查找长度
ASL(n/b)在块中查找元素的平均查找长度
ASL(n)=ASL(b)+ASL(n/b)≈Log2(b+1) -1+(n/b+1)/2
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 21页
8.2 动态查找表抽象数据类型动态查找表的定义如下：
ADT DynamicSearchTable{
数据对象 D：
D是具有相同特性的数据元素的集合。
每个数据元素含有类型相同的关键字,可唯一标识数据元素。
数据关系 R：
数据元素同属一个集合。
基本操作 P：
InitDSTable(&DT)
DestroyDSTable(&DT)
SearchDSTable(DT,key);
InsertDSTable(&DT,e);
DeleteDSTable(&T,key);
TraverseDSTable(DT,Visit());
}ADT DynamicSearchTable
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 22页二叉查找树
回顾,
定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉排序树
10
183
8 122
7
3
中序遍历二叉排序树可得到一个关键字的有序序列
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 23页
50
30 80
20 90
85
40
35
8832
例如,二叉排序树查找关键字
== 50,35,90,95,
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 24页查找树和二叉查找树
通过和根结点关键字的比较可将继续查找的范围缩小到某一棵子树中,具有该特性的二叉树和树均称为查找树
二叉排序树称为二叉查找树
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 25页算法 8.4
bool Search_BST (BiTree T,KeyType kval,BiTree &p,BiTree &f )
{
// 在根指针 T所指二叉查找树中查找其关键字等于 kval的数据元素，
// 若查找成功，则指针 p指向该数据元素结点，并返回 TRUE，
// 否则指针 p指向查找路径上访问的最后一个结点，并返回 FALSE,
// 无论查找成功与否,f 总是指向 p 所指结点的双亲，其初始调用值为 NULL
p = T; // p 指向树中某个结点,f指向其双亲结点
while (p) {
if ( kval == p->data.key)
return TRUE; // 查找成功
else if ( kval < p->data.key)
{ f = p ; p = p->lchild; } // 在左子树中继续查找
else { f = p; p = p->rchild; } // 在右子树中继续查找
} // while
return FALSE; // 查找不成功
} // SearchBST
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 26页假设 kval = 48
f p
30
20
10
40
3525
23
52
48
43
Tf
pf
pf
p
kval=24
f p
f
pf
pf
pf
p
return TRUEreturn FALSE
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 27页算法 8.5
bool Insert_BST(BiTree &T,ElemType e ) {
// 当二叉查找树 T中不存在关键字等于 e.key的数据元素时，
// 插入 e并返回 TRUE，否则不再插入并返回 FALSE
f = NULL;
if (Search_BST ( T,e.key,p,f )) return FALSE;
// 树中已有关键字相同的结点，不再插入
else { // 查找不成功，插入结点
s = new BiTNode;
s->data = e; s->lchild = s->rchild = NULL;
if ( !f ) T = s; // T为空树，插入的 s 结点为新的根结点
else if( e.key < f->data.key) f->lchild = s; //插入 s 结点为左孩子
else f->rchild = s; // 插入 s 结点为右孩子
return TRUE;
}//else
} // Insert_BST
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 28页
T=NULL
kval=50,
T
50
30,
30
40,
40
80,
80
20,
20
36,
36
90,
90
40,
38
38,
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 29页二叉查找树中删除结点
三种情况
– 删除叶子结点
– 删除只有一个子树的结点
– 删除有左右子树的结点
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 30页
（ 1）被删除的结点是 叶子结点
50
30 80
20 90
85
40
35
8832
例如,被删关键字 = 2088
其双亲结点中相应指针域的值改为“空”
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 31页
50
30 80
20 90
85
40
35
8832
（ 2）被删除的结点 只有左子树 或者 只有右子树其双亲结点的相应指针域的值改为
“指向被删除结点的左子树或右子树”。
被删关键字 = 4080
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 32页
50
30 80
20 90
85
40
35
8832
（ 3）被删除的结点 既有左子树，也有右子树
40
以其前驱替代之，然后再删除该前驱结点被删结点前驱结点被删关键字 = 50
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 33页算法 8.6
void Delete_BST (BiTree &T,KeyType kval ) {
// 若二叉查找树 T中存在关键字等于 kval的数据元素，则删除之。
f = NULL;
if (Search_BST(T,kval,p,f)) { // 找到其关键字等于 kval的数据元素
if (p->lchild && p->rchild) { // 左右子树均不空
q = p; s = p->lchild;
while (s->rchild) { q = s; s = s->rchild; }
p->data = s->data; // s指向左子树中关键字最大的结点
if (q != p ) q->rchild = s->lchild;
else q->lchild = s->lchild; // s结点即为 p结点的左子树根
delete s;
}// if
else {
if (!p->rchild) { // 右子树空则只需挂接它的左子树
q = p; p = p->lchild;
}//if
else { // 左子树空，只需挂接它的右子树
q = p; p = p->rchild;
}
// 将指针 p所指子树挂接到被删结点的双亲 (指针 f所指的 )结点上
if (!f) T = p; // 被删结点为根结点
else if (q == f->lchild) f->lchild = p;
else f->rchild = p; // 完成子树的挂接
delete q; // 释放被删结点空间
}//else
}//if
}//Delete_BST
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 34页查找性能的分析
对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 35页例如：
由关键字序列 1,2,3,4,5构造而得的二叉排序树，
ASL =（ 1+2+3+4+5） / 5 = 3
由关键字序列 3,1,2,5,4构造而得的二叉排序树，
ASL =（ 1+2+3+2+3） / 5 = 2.2
2
1
3
4
5
3
5
4
1
2
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 36页二叉平衡树
二叉平衡树 是二叉查找树的另一种形式，其特点为：
树中每个结点的 左、右子树深度之差的绝对值不大于 1。
5
4 8
2
5
4 8
2
1是平衡树 不是平衡树
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 37页
8.2.2 键树
1,键树的结构特点：
关键字中的各个符号分布在从根结点到叶的路径上，
叶结点内的符号为“结束”的标志符。因此,键树的深度和关键字集合的大小无关 ；
键树被约定为是一棵 有序树,即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符 ‘ $’小于任何其它符号。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 38页
H
A
D
$
S
$
V
E
$
E
$ R
$ E
$
I
G
H
$
S
$
例如,
表示关键字集合
{HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS }
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 39页
2,双链树
— 以二叉链表作存储结构实现的键树
typedef enum { LEAF,BRANCH }NodeKind;
// 两种结点,{叶子 和 分支 }
结点结构,
first symbol next
分支结点
infoptr symbol next
叶子结点指向孩子结点的指针 指向兄弟结点 的指针 指向记录 的指针
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 40页
H?
A
D
$
HAD
E
$
R
$
$
E
S
$
G
H
$
I?
HE
HER
HERE
HIGH HIS
…
T
叶子结点分支结点含关键字的记录
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 41页
8.3 哈希表及其查找
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 42页
8.3.1 什么是哈希表
以上两节讨论的表示查找表的各种结构的共同特点：
记录在表中的位置和它的关键字之间不存在一个确定的关系
查找的过程 为给定值依次和关键字集合中各个关键字进行比较
查找的效率 取决于和给定值进行比较的关键字个数。
用这类方法表示的查找表，其平均查找长度都不为零。
不同的表示方法，其差别仅在于：
关键字和给定值进行比较的顺序不同。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 43页
对于频繁使用的查找表，希望 ASL = 0。
只有一个办法：预先知道所查关键字在表中的位置，即要求：记录在表中位置和其关键字之间存在一种确定的关系。
例如,为每年招收的 1000 名新生建立一张查找表，
其关键字为学号，其值的范围为 xx000 ~ xx999 (前两位为年份 )。
若以下标为 000 ~ 999 的顺序表表示之。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 44页
因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字为
key 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 45页
{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}
例如,对于如下 9 个关键字设 哈希函数 f(key) =
(Ord(第一个字母 ) -Ord('A')+1)/2?
0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3
Chen ZhaoQian SunLi WuHan YeDei
问题,若添加关键字 Zhou,怎么办？
能否找到 另一个哈希函数？
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 46页从这个例子可见：
1) 哈希函数是一个 映象,即,将关键字的集合映射到某个地址集合上,它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；
2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生,冲突,现象，即,key1=key2，而 f(key1) = f(key2)。
3) 很难找到一个不产生冲突的哈希函数。
一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。
因此，在构造这种特殊的“查找表” 时，除了需要选择一个
“好” (尽可能少产生冲突 )的哈希函数之外；还需要找到一种“处理冲突” 的方法。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 47页哈希表的定义：
根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间 ) 上，并以关键字在地址集中的“象”
作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。
一般情况下，所设哈希表的空间较记录集合大，随浪费了空间，但提高了查找效率。假设哈希表的空间大小为 m，在表中添入的记录数为 n，定义
a=n/m
为装填系数，一般取为 0.65— 0.85
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 48页
8.3.2 构造哈希函数的方法
除留余数法设定哈希函数为,H(key) = key MOD p
其中,p≤m ( 表长 ) 并且 p 应为不大于 m 的素数
平方取中法以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。此方法适合于,关键字中的每一位都有某些数字重复出现频度很高的现象。
折叠法将关键字分割成若干部分，然后取它们的叠加和为哈希地址。
有两种叠加处理的方法：移位叠加和间界叠加。 此方法适合于,
关键字的数字位数特别多
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 49页
8.3.3 处理冲突的方法
,处理冲突” 的实际含义是：为产生冲突的地址寻找下一个哈希地址。
1,开放定址法
2,链地址法
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 50页
1,开放定址法为产生冲突的地址 H(key) 求得一个地址序列：
H0,H1,H2,…,Hk 1≤ k≤m-1其中,H0 = H(key)
Hi = ( H(key) + di ) MOD m
i=1,2,…,k k<=m -1
对增量 di 有三种取法：
1) 线性探测再散列
di = c? i 最简单的情况 c=1
2) 二次 (平方 )探测再散列
di = 12,-12,22,-22,…,
3) 随机探测再散列
di 是一组伪随机数列
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 51页注意：
增量 di 应具有“完备性” 即：
产生的 Hi 均不相同，且所产生的 k(<=m-1)个 Hi 值能覆盖哈希表中所有 地址。则要求：
– 平方探测时的表长 m 必为形如 4j+3 的素数（如,7,
11,19,23,… 等）；
– 随机探测时需要一个伪随机函数来生成伪随机数。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 52页例如,关键字集合
{ 19,01,23,14,55,68,11,82,36 }
设定 哈希函数 H(key) = key MOD 11 ( 表长 =11 )
0 1 2 3 4 5 6 7 8 9 1 0
0 1 2 3 4 5 6 7 8 9 1 0
1901 23 1455 68
1901 23 14 68
若采用 线性探测再散列 处理冲突若采用 二次探测再散列 处理冲突
11 82 36
55 118236
1 1 2 1 3 6 2 5 1
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 53页将所有哈希地址相同的记录都链接在同一链表中。
2,链地址法
0
1
2
3
4
5
6
14
01 36
19 82
23
11
68
55
ASL=(6× 1+2× 2+3)/9=13/9
例如,同前例的关键字，哈希函数为
H(key)=key MOD 7
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 54页
8.3.4 哈希表的查找及性能分析
对于给定值 K,计算哈希地址 i = H(K)
若 r[i] = NULL 则查找不成功
若 r[i].key = K 则查找成功
否则,求下一地址 Hi”,直至
r[Hi] = NULL (查找不成功 )
或 r[Hi].key = K (查找成功 ) 为止。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 55页哈希表查找的分析,
从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。
决定哈希表查找的 ASL的因素,
1) 选用的 哈希函数 ；
2) 选用的 处理冲突的方法 ；
3) 哈希表饱和的程度,装载因子 α =n/m 值的 大小 （ n— 记录数,m— 表的长度）
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 56页线性探测再散列链地址法随机探测再散列
)
1
1
1(
2
1
nlS
)1l n (
1
nr
S
2
1
nc
S
可以证明,查找成功 时有下列结果：
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 57页从以上结果可见：
哈希表的平均查找长度是? 的函数
，而不是 n 的函数。
这说明，用哈希表构造查找表时，
可以选择一个适当的装填因子?,使得 平均查找长度限定在某个范围内 。
—— 这是哈希表所特有的特点。
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 1页第 8章 查找表
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 2页基本概念
查找表 是由 同一类型 的数据元素 (或记录 )构成的集合。
由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。
对查找表经常进行的操作,
1） 查询某个,特定的,数据元素是否在查找表中；
2） 检索某个,特定的,数据元素的各种属性；
3） 在查找表中 插入 一个数据元素；
4） 从查找表中 删去 某个数据元素 。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 3页查找表可分为两类
静态查找表仅作 查询 和 检索 操作的查找表。
动态查找表有时在查询之后，还需要将,查询,结果为,不在查找表中,的数据元素 插入 到查找表中；或者，从查找表中 删除 其,查询,结果为,在查找表中,的数据元素。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 4页
关键字 是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。
若此关键字可以识别唯一的一个记录，则称之谓,主关键字,。若此关键字能识别若干记录，则称之谓
,次关键字,。
查找 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
– 若查找表中存在这样一个记录，则称,查找成功,。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；
否则称,查找不成功,。查找结果给出,空记录,或,空指针,。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 5页如何进行查找？
查找的方法取决于查找表的结构。
由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。
为了提高查找的效率,需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说,用另外一种结构来表示查找表
– 静态查找表
– 动态查找树表
– 哈希表
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 6页
8.1 静态查找表抽象数据类型
ADT StaticSearchTable {
数据对象 D：
D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素数据关系 R：
数据元素同属一个集合。
基本操作 P：
Create(&ST,n);
Destroy(&ST);
Search(ST,key);
Traverse(ST,Visit());
} ADT StaticSearchTable
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 7页静态查找表的存储
静态查找表基本上不采用插入和删除操作，因此通常以顺序存储结构的线形表或有序表存储假设静态查找表的顺序存储结构为
typedef struct {
ElemType *elem;
// 数据元素存储空间基址，建表时按实际
// 长度分配,0号单元留空
int length; // 表的长度
} SSTable;
数据元素类型的定义为,
typedef struct {
keyType key; // 关键字域
… … // 其它属性域
} ElemType
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 8页
8.1.1 顺序查找表
以顺序表或线性链表表示静态查找表
回顾顺序表的查找过程：
算法 2.5
int LocateElem_Sq( SqList L,ElemType e)
{
// 在顺序线性表 L 中查找第 1 个值与 e 相等的数据元素，
// 若找到，则返回其在 L 中的位序，否则返回 0
i = 1; // i 的初值为第 1 个元素的位序
p = L.elem; // p 的初值为第 1 个元素的存储位置
while (i <= L.length && *p++ != e ) ++i; // 依次进行判定
if (i <= L.length) return i; // 找到满足判定的数据元素为第 i 个元素
else return 0; // 该线性表中不存在满足判定的数据元素
} // LocateElem_Sq
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 9页
以顺序表或线性链表表示静态查找表
假设给定值 e=64,
要求 ST.elem[k] = e,问,k =?
21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 11
ST.Length
ST.elem
k k
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 10页设置“哨兵” 21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 1 1
S T,L e ngt h
ST.elem i
21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 1 1
S T,L e ngt h
ST.elem
i
60
i
key=64
key=60
i
64
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 11页算法 8.1
int Search_Seq (SSTable ST,KeyType kval)
{
// 在顺序表 ST中顺序查找其关键字等于 kval的数据元素。
// 若找到，则函数值为该元素在表中的位置，
否则为 0。
ST.elem[0].key = kval; // 设置 "哨兵 "
for (i=ST.length; ST.elem[i].key != kval; --i);
// 从后往前查找
return i; // 找不到时,i为 0
} // Search_Seq
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 12页分析顺序查找的时间性能
定义,查找算法的 平均查找长度 (Average Search Length)
为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值其中,n 为表长,Pi 为查找表中第 i个记录的概率，且,
Ci为找到该记录时，曾和给定值比较过的关键字的个数。
n
i
iiCPA S L
1
1
1
n
i
iP
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 13页对顺序表而言,Ci = n-i+1
ASL = nP1 +(n-1)P2 +…… +2P n-1+Pn
在等概率查找的情况下，
nPi
1?
顺序表查找的平均查找长度 为：
2
111
1
n)i(n
nA S L
n
i
ss
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 14页
8.1.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时，查找失败
05 13 19 21 37 56 64 75 80 88 92
0 1 2 3 4 5 6 7 8 9 10 1 1
ST.elem
ST.length
例如,key=64 的查找过程如下：
low high
mid
low
mid
high
mid
low 指示查找区间的下界
high 指示查找区间的上界
mid = (low+high)/2
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 16页算法 8.2
int Search_Bin ( SSTable ST,KeyType kval )
{
// 在有序表 ST中折半查找其关键字等于 kval的数据元素。若找到，则函
// 数值 为该元素在表中的位置，否则为 0。
low = 1; high = ST.length; // 置区间初值
while (low <= high) {
mid = (low + high) / 2;
if （ kval == ST.elem[mid].key )
return mid; // 找到待查元素
else
if ( kval < ST.elem[mid].key )
high = mid - 1; // 继续在前半区间内进行查找
else
low = mid + 1; // 继续在后半区间内进行查找
} //while
return 0; // 顺序表中不存在待查元素
} // Search_Bin
先看一个具体的情况，假设,n=11
分析 折半查找 的平均查找长度
6
3 9
1 4
2 5
7
8
10
11
判定树
i 1 2 3 4 5 6 7 8 9 10 11
Ci
12 23 3 3 34 4 4 4
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 18页
一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。
假设 n=2h-1 并且查找概率相等则在 n>50时，可得近似结果
1)1(l o g1211 2
1
1
1
nnnjnCnA S L
h
j
j
n
i
ibs
1)1(l o g 2 nA S L bs
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 19页
8.1.3 分块查找
查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找
适用条件：分块有序表
算法实现
– 用数组存放待查记录,每个数据元素至少含有关键字域
– 建立索引表，每个索引表结点含有最大关键字域和指向本块第 1
个结点的指针
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
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 20页分块查找方法评价
ASL(n)=ASL(b)+ASL(n/b)
其中：
ASL(b)查找索引表确定所在块的平均查找长度
ASL(n/b)在块中查找元素的平均查找长度
ASL(n)=ASL(b)+ASL(n/b)≈Log2(b+1) -1+(n/b+1)/2
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 21页
8.2 动态查找表抽象数据类型动态查找表的定义如下：
ADT DynamicSearchTable{
数据对象 D：
D是具有相同特性的数据元素的集合。
每个数据元素含有类型相同的关键字,可唯一标识数据元素。
数据关系 R：
数据元素同属一个集合。
基本操作 P：
InitDSTable(&DT)
DestroyDSTable(&DT)
SearchDSTable(DT,key);
InsertDSTable(&DT,e);
DeleteDSTable(&T,key);
TraverseDSTable(DT,Visit());
}ADT DynamicSearchTable
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 22页二叉查找树
回顾,
定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉排序树
10
183
8 122
7
3
中序遍历二叉排序树可得到一个关键字的有序序列
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 23页
50
30 80
20 90
85
40
35
8832
例如,二叉排序树查找关键字
== 50,35,90,95,
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 24页查找树和二叉查找树
通过和根结点关键字的比较可将继续查找的范围缩小到某一棵子树中,具有该特性的二叉树和树均称为查找树
二叉排序树称为二叉查找树
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 25页算法 8.4
bool Search_BST (BiTree T,KeyType kval,BiTree &p,BiTree &f )
{
// 在根指针 T所指二叉查找树中查找其关键字等于 kval的数据元素，
// 若查找成功，则指针 p指向该数据元素结点，并返回 TRUE，
// 否则指针 p指向查找路径上访问的最后一个结点，并返回 FALSE,
// 无论查找成功与否,f 总是指向 p 所指结点的双亲，其初始调用值为 NULL
p = T; // p 指向树中某个结点,f指向其双亲结点
while (p) {
if ( kval == p->data.key)
return TRUE; // 查找成功
else if ( kval < p->data.key)
{ f = p ; p = p->lchild; } // 在左子树中继续查找
else { f = p; p = p->rchild; } // 在右子树中继续查找
} // while
return FALSE; // 查找不成功
} // SearchBST
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 26页假设 kval = 48
f p
30
20
10
40
3525
23
52
48
43
Tf
pf
pf
p
kval=24
f p
f
pf
pf
pf
p
return TRUEreturn FALSE
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 27页算法 8.5
bool Insert_BST(BiTree &T,ElemType e ) {
// 当二叉查找树 T中不存在关键字等于 e.key的数据元素时，
// 插入 e并返回 TRUE，否则不再插入并返回 FALSE
f = NULL;
if (Search_BST ( T,e.key,p,f )) return FALSE;
// 树中已有关键字相同的结点，不再插入
else { // 查找不成功，插入结点
s = new BiTNode;
s->data = e; s->lchild = s->rchild = NULL;
if ( !f ) T = s; // T为空树，插入的 s 结点为新的根结点
else if( e.key < f->data.key) f->lchild = s; //插入 s 结点为左孩子
else f->rchild = s; // 插入 s 结点为右孩子
return TRUE;
}//else
} // Insert_BST
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 28页
T=NULL
kval=50,
T
50
30,
30
40,
40
80,
80
20,
20
36,
36
90,
90
40,
38
38,
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 29页二叉查找树中删除结点
三种情况
– 删除叶子结点
– 删除只有一个子树的结点
– 删除有左右子树的结点
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 30页
（ 1）被删除的结点是 叶子结点
50
30 80
20 90
85
40
35
8832
例如,被删关键字 = 2088
其双亲结点中相应指针域的值改为“空”
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 31页
50
30 80
20 90
85
40
35
8832
（ 2）被删除的结点 只有左子树 或者 只有右子树其双亲结点的相应指针域的值改为
“指向被删除结点的左子树或右子树”。
被删关键字 = 4080
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 32页
50
30 80
20 90
85
40
35
8832
（ 3）被删除的结点 既有左子树，也有右子树
40
以其前驱替代之，然后再删除该前驱结点被删结点前驱结点被删关键字 = 50
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 33页算法 8.6
void Delete_BST (BiTree &T,KeyType kval ) {
// 若二叉查找树 T中存在关键字等于 kval的数据元素，则删除之。
f = NULL;
if (Search_BST(T,kval,p,f)) { // 找到其关键字等于 kval的数据元素
if (p->lchild && p->rchild) { // 左右子树均不空
q = p; s = p->lchild;
while (s->rchild) { q = s; s = s->rchild; }
p->data = s->data; // s指向左子树中关键字最大的结点
if (q != p ) q->rchild = s->lchild;
else q->lchild = s->lchild; // s结点即为 p结点的左子树根
delete s;
}// if
else {
if (!p->rchild) { // 右子树空则只需挂接它的左子树
q = p; p = p->lchild;
}//if
else { // 左子树空，只需挂接它的右子树
q = p; p = p->rchild;
}
// 将指针 p所指子树挂接到被删结点的双亲 (指针 f所指的 )结点上
if (!f) T = p; // 被删结点为根结点
else if (q == f->lchild) f->lchild = p;
else f->rchild = p; // 完成子树的挂接
delete q; // 释放被删结点空间
}//else
}//if
}//Delete_BST
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 34页查找性能的分析
对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 35页例如：
由关键字序列 1,2,3,4,5构造而得的二叉排序树，
ASL =（ 1+2+3+4+5） / 5 = 3
由关键字序列 3,1,2,5,4构造而得的二叉排序树，
ASL =（ 1+2+3+2+3） / 5 = 2.2
2
1
3
4
5
3
5
4
1
2
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 36页二叉平衡树
二叉平衡树 是二叉查找树的另一种形式，其特点为：
树中每个结点的 左、右子树深度之差的绝对值不大于 1。
5
4 8
2
5
4 8
2
1是平衡树 不是平衡树
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 37页
8.2.2 键树
1,键树的结构特点：
关键字中的各个符号分布在从根结点到叶的路径上，
叶结点内的符号为“结束”的标志符。因此,键树的深度和关键字集合的大小无关 ；
键树被约定为是一棵 有序树,即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符 ‘ $’小于任何其它符号。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 38页
H
A
D
$
S
$
V
E
$
E
$ R
$ E
$
I
G
H
$
S
$
例如,
表示关键字集合
{HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS }
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 39页
2,双链树
— 以二叉链表作存储结构实现的键树
typedef enum { LEAF,BRANCH }NodeKind;
// 两种结点,{叶子 和 分支 }
结点结构,
first symbol next
分支结点
infoptr symbol next
叶子结点指向孩子结点的指针 指向兄弟结点 的指针 指向记录 的指针
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 40页
H?
A
D
$
HAD
E
$
R
$
$
E
S
$
G
H
$
I?
HE
HER
HERE
HIGH HIS
…
T
叶子结点分支结点含关键字的记录
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 41页
8.3 哈希表及其查找
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 42页
8.3.1 什么是哈希表
以上两节讨论的表示查找表的各种结构的共同特点：
记录在表中的位置和它的关键字之间不存在一个确定的关系
查找的过程 为给定值依次和关键字集合中各个关键字进行比较
查找的效率 取决于和给定值进行比较的关键字个数。
用这类方法表示的查找表，其平均查找长度都不为零。
不同的表示方法，其差别仅在于：
关键字和给定值进行比较的顺序不同。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 43页
对于频繁使用的查找表，希望 ASL = 0。
只有一个办法：预先知道所查关键字在表中的位置，即要求：记录在表中位置和其关键字之间存在一种确定的关系。
例如,为每年招收的 1000 名新生建立一张查找表，
其关键字为学号，其值的范围为 xx000 ~ xx999 (前两位为年份 )。
若以下标为 000 ~ 999 的顺序表表示之。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 44页
因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字为
key 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 45页
{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}
例如,对于如下 9 个关键字设 哈希函数 f(key) =
(Ord(第一个字母 ) -Ord('A')+1)/2?
0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3
Chen ZhaoQian SunLi WuHan YeDei
问题,若添加关键字 Zhou,怎么办？
能否找到 另一个哈希函数？
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 46页从这个例子可见：
1) 哈希函数是一个 映象,即,将关键字的集合映射到某个地址集合上,它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；
2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生,冲突,现象，即,key1=key2，而 f(key1) = f(key2)。
3) 很难找到一个不产生冲突的哈希函数。
一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。
因此，在构造这种特殊的“查找表” 时，除了需要选择一个
“好” (尽可能少产生冲突 )的哈希函数之外；还需要找到一种“处理冲突” 的方法。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 47页哈希表的定义：
根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间 ) 上，并以关键字在地址集中的“象”
作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。
一般情况下，所设哈希表的空间较记录集合大，随浪费了空间，但提高了查找效率。假设哈希表的空间大小为 m，在表中添入的记录数为 n，定义
a=n/m
为装填系数，一般取为 0.65— 0.85
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 48页
8.3.2 构造哈希函数的方法
除留余数法设定哈希函数为,H(key) = key MOD p
其中,p≤m ( 表长 ) 并且 p 应为不大于 m 的素数
平方取中法以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。此方法适合于,关键字中的每一位都有某些数字重复出现频度很高的现象。
折叠法将关键字分割成若干部分，然后取它们的叠加和为哈希地址。
有两种叠加处理的方法：移位叠加和间界叠加。 此方法适合于,
关键字的数字位数特别多
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 49页
8.3.3 处理冲突的方法
,处理冲突” 的实际含义是：为产生冲突的地址寻找下一个哈希地址。
1,开放定址法
2,链地址法
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 50页
1,开放定址法为产生冲突的地址 H(key) 求得一个地址序列：
H0,H1,H2,…,Hk 1≤ k≤m-1其中,H0 = H(key)
Hi = ( H(key) + di ) MOD m
i=1,2,…,k k<=m -1
对增量 di 有三种取法：
1) 线性探测再散列
di = c? i 最简单的情况 c=1
2) 二次 (平方 )探测再散列
di = 12,-12,22,-22,…,
3) 随机探测再散列
di 是一组伪随机数列
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 51页注意：
增量 di 应具有“完备性” 即：
产生的 Hi 均不相同，且所产生的 k(<=m-1)个 Hi 值能覆盖哈希表中所有 地址。则要求：
– 平方探测时的表长 m 必为形如 4j+3 的素数（如,7,
11,19,23,… 等）；
– 随机探测时需要一个伪随机函数来生成伪随机数。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 52页例如,关键字集合
{ 19,01,23,14,55,68,11,82,36 }
设定 哈希函数 H(key) = key MOD 11 ( 表长 =11 )
0 1 2 3 4 5 6 7 8 9 1 0
0 1 2 3 4 5 6 7 8 9 1 0
1901 23 1455 68
1901 23 14 68
若采用 线性探测再散列 处理冲突若采用 二次探测再散列 处理冲突
11 82 36
55 118236
1 1 2 1 3 6 2 5 1
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 53页将所有哈希地址相同的记录都链接在同一链表中。
2,链地址法
0
1
2
3
4
5
6
14
01 36
19 82
23
11
68
55
ASL=(6× 1+2× 2+3)/9=13/9
例如,同前例的关键字，哈希函数为
H(key)=key MOD 7
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 54页
8.3.4 哈希表的查找及性能分析
对于给定值 K,计算哈希地址 i = H(K)
若 r[i] = NULL 则查找不成功
若 r[i].key = K 则查找成功
否则,求下一地址 Hi”,直至
r[Hi] = NULL (查找不成功 )
或 r[Hi].key = K (查找成功 ) 为止。
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 55页哈希表查找的分析,
从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。
决定哈希表查找的 ASL的因素,
1) 选用的 哈希函数 ；
2) 选用的 处理冲突的方法 ；
3) 哈希表饱和的程度,装载因子 α =n/m 值的 大小 （ n— 记录数,m— 表的长度）
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 56页线性探测再散列链地址法随机探测再散列
)
1
1
1(
2
1
nlS
)1l n (
1
nr
S
2
1
nc
S
可以证明,查找成功 时有下列结果：
Da
ta
St
ruc
tur
e
数据结构——
第
8
章查找表胡建华 2009-7-24
计算机教研室第 57页从以上结果可见：
哈希表的平均查找长度是? 的函数
，而不是 n 的函数。
这说明，用哈希表构造查找表时，
可以选择一个适当的装填因子?,使得 平均查找长度限定在某个范围内 。
—— 这是哈希表所特有的特点。
