第九章 查找
查找的概念
静态查找表
动态查找表
哈希表查找表 是由同一类型的数据元素 (或记录 )
构成的集合,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数据结构。 对查找表的操作,
查询某个“特定的”数据元素是否在查找表中；
检索某个,特定的,数据元素的各种属性；
在查找表中插入一个数据元素；
从查找表中删去某个数据元素查找的概念静态查找表仅作查询和检索操作的查找表。
动态查找表在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。
查找表的分类：
关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素
（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。
若查找表中存在这样一个记录，则称,查找成功,，查找结果,给出整个记录的信息，或指示该记录在查找表中的位置 ；
否则称,查找不成功,，查找结果,给出
“空记录”或“空指针”。
查找如何进行查找？
查找的方法取决于查找表的结构。
由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。
为了提高查找的效率,需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说,用另外一种结构来表示查找表。
查找方法评价
查找速度
占用存储空间多少
算法本身复杂程度
平均查找长度 ASL(Average Search Length)：
为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的 ~
个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：
个记录的表，对含有
ic
pip
cpA S Ln
i
n
i
ii
n
i
ii
1
1
1
抽象数据类型静态查找表的定义,
ADT StaticSearchTable {
D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。
数据关系 R：数据元素同属一个集合。
静 态 查 找 表数据对象 D:
Create(&ST,n); //构造一个含 n 个数据元素的静态查找表 ST。
Destroy(&ST); //销毁表 ST。
Search(ST,key); //查找 ST 中其关键字等于 kval 的数据元素。
Traverse(ST,Visit()); //按某种次序对
ST的每个元素调用函数
Visit()一次且仅一次，
} ADT StaticSearchTable
基本操作 P：
顺序表的查找
typedef struct {
ElemType *elem; // 数据元素存储空间基址，建表时按实际长度分配,0号单元留空
int length; // 表的长度
} SSTable;
以顺序表表示静态查找表，则 Search函数可用顺序查找来实现。 其顺序存储结构如下：
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
查找过程,从表的一端开始逐个进行记录的关键字和给定值的比较。
例如：
int Search_Seq(SSTable ST,
KeyType kval) {
// 在顺序表 ST中顺序查找其关键字等于
// key的数据元素。若找到，则函数值为
// 该元素在表中的位置，否则为 0。
ST.elem[0].key = kval; // 设置“哨兵”
for (i=ST.length; ST.elem[i].key!=kval; --i);
// 从后往前找
return i; // 找不到时,i为 0
} // Search_Seq
算法描述：
顺序查找性能分析查找算法的平均查找长度 (Average Search Length)：
为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。
n
i
iiCPA S L
1其中,n 为表长
Pi 为查找表中第 i个记录的概率
Ci为找到该记录时，曾和给定值比较过的关键字的个数
1
1
n
i
iP
顺序表查找的平均查找长度为：
对顺序表而言,Ci = n-i+1
2
111
1
n)i(n
n
A S L
n
i
ss
ASL = nP1 +(n-1)P2 + +2Pn-1+Pn
n
Pi
1
在等概率查找的情况下，
在不等概率查找的情况下,ASLss 在
Pn≥ Pn-1≥ ··≥ P2≥ P1
时取极小值。表中记录按查找概率由小到达重新排列,以提高查找效率。
若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，
将刚刚查找到的记录直接移至表尾的位置上。
顺序表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找表。
若以有序表表示静态查找表，则查找过程可以基于“折半”进行。
有序表的查找折半查找查找过程,每次将待查记录所在区间缩小一半。
适用条件,采用顺序存储结构的有序表。
1.设表长为 n,low,high和 mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。
2.初始时，令
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
3.重复上述操作，直至 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
例如 key =21 的查找过程
low 指示查找区间的下界 ;
high 指示查找区间的上界 ;
mid = (low+high)/2。
例 key =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
找 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
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
当下界 low大于上界 high时，则说明表中没有关键字等于 Key的元素，查找不成功。
int Search_Bin ( SSTable ST,KeyType kval ) {
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; // 继续在后半区间进行查找
}
return 0; // 顺序表中不存在待查元素
} // Search_Bin
折半查找算法先看一个有 11个元素的表的例子,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
折半查找的性能分析
判定树：描述查找过程的二叉树。
有 n个结点的判定树的深度为?log2n?+1
折半查找法在查找过程中进行的比较次数最多不超过?log2n?+1
假设 有序表的长度 n=2h-1（反之 h=log2(n+1) ）,
则描述折半查找的判定树是深度为 h的满二叉树。
树中层次为 1的结点有 1个，层次为 2的结点有 2
个，层次为 h的结点有 2 h-1个。假设表中每个记录的查找概率相等则查找成功时折半查找的平均查找长度
1)1(lo g1211 2
1
1
1
n
n
nj
n
C
n
A S L
h
j
j
n
i
ibs
在 n>50 时，可得近似结果
1)1(l o g 2 nA S L bs
可见，
折半查找的效率比顺序查找高。
折半查找只能适用于有序表，并且以顺序存储结构存储。
顺序表 有序表表的特性 无序 有序存储结构 顺序 或 链式 顺序插删操作 易于进行 需移动元素
ASL的值 大 小顺序表和有序表的比较
索引顺序表在建立顺序表的同时，建立一个索引项，包括两项：关键字项和指针项。索引表按关键字有序，
表则为分块有序
0 1 2 3 4 5 6 7 8 9 10 11 12 13 ……
17 08 21 19 14 31 33 22 25 40 52 61 78 46 ……
21 0 40 5 78 10 ……
索引顺序表 = 索引 + 顺序表顺序表索引表索引顺序查找又称分块查找查找过程,将表分成几块，块内无序，块间有序；
先确定待查记录所在块，再在块内查找适用条件,分块有序表算法实现：
用数组存放待查记录,每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针
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
1
11
)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 最大 最小 两者之间表结构 有序表、无序表 有序表 分块有序表存储结构 顺序存储结构线性链表顺序存储结构 顺序存储结构线性链表顺序查找 折半查找 分块查找
(n)
(1)
(n)
(1)
(nlogn)
几种查找表的特性查找 插入 删除无序顺序表无序线性链表有序顺序表有序线性链表静态查找树表
(n)
(n)
(logn)
(n)
(logn)
(1)
(1)
(n)
(1)
(nlogn)
从查找性能看，最好情况能达?(logn)，
此时要求表有序；
从插入和删除的性能看，最好情况能达
(1)，此时要求存储结构是链表。
结论：
ADT DynamicSearchTable {
抽象数据类型动态查找表的定义：
数据对象 D：
数据关系 R,数据元素同属一个集合。
D是具有相同特性的数据元素的集合。
每个数据元素含有类型相同的关键字,可唯一标识数据元素。
动态查找表动态查找表的特点,表结构本身是在查找过程中动态生成。若表中存在其关键字等于给定值 key的记录,表明查找成功；否则插入关键字等于 key的记录。
InitDSTable(&DT)//构造一个空的动态查找表 DT。
DestroyDSTable(&DT)//销毁动态查找表 DT。
SearchDSTable(DT,key);//查找 DT 中与关键字
key等值的元素。
InsertDSTable(&DT,e);//若 DT 中不存在其关键字等于 e.key 的 数据元素，则插入 e 到 DT。
DeleteDSTable(&T,key);//删除 DT中关键字等于
key的数据元素。
TraverseDSTable(DT,Visit());//按某种次序对
DT的每个结点调用函数 Visit() 一次且至多一次。
基本操作：
next
}ADT DynamicSearchTable
二叉排序树（二叉查找树）
定义二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
它的左、右子树也都分别是二叉排序树。
50
30 80
20 90
10 85
40
3525
23 88
66
不是二叉排序树。
以二叉链表形式存储
typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild,*rchild; // 左右指针
} BiTNode,*BiTree;
二叉排序树的存储结构二叉排序树的查找算法若二叉排序树为空，则查找不成功；
否则
1）若给定值等于根结点的关键字，则查找成功；
2）若给定值小于根结点的关键字，则继续在左子树上进行查找；
3）若给定值大于根结点的关键字，则继续在右子树上进行查找。
在二叉排序树中查找关键字值等于 50,35,90,95
50
30 80
20 90
85
40
35
8832
if (!T)
{ p = f; return FALSE; } // 查找不成功
else if ( EQ(kval,T->data.key) )
{ p = T; return TRUE; } // 查找成功
else if ( LT(kval,T->data.key) )
return SearchBST (T->lchild,kval,T,p ); // 在左子树中继续查找
else
return SearchBST (T->rchild,kval,T,p );
// 在右子树中继续查找
Status SearchBST (BiTree T,KeyType kval,BiTree f,
BiTree &p ) {
} // SearchBST
根据动态查找表的定义，“插入”操作在查找不成功时才进行 ;
若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。
二叉排序树的插入算法
Status Insert BST(BiTree &T,ElemType e ) {
if (!SearchBST ( T,e.key,NULL,p ))
{ s = new BiTNode; // 为新结点分配空间
s->data = e;
s->lchild = s->rchild = NULL;
if ( !p ) T = s; // 插入 s 为新的根结点
else if ( LT(e.key,p->data.key) )
p->lchild = s; // 插入 *s 为 *p 的左孩子
else p->rchild = s; // 插入 *s 为 *p 的右孩子
return TRUE; // 插入成功
}
else return FALSE;
} // Insert BST
一个无序序列可以通过构造一棵二叉排序树二而变成一个有序序列
每次插入的新结点都是二叉排序树上新的叶子结点
插入时不必移动其它结点，仅需修改某个结点的指针结论二叉排序树的删除算法和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。
可分三种情况讨论：
被删除的结点是叶子；
被删除的结点只有左子树或者只有右子树；
被删除的结点既有左子树，也有右子树 。
被删除的结点是叶子结点,如 Key = 88
结果,其双亲结点中相应指针域的值改为空
50
30 80
20 90
85
40
35
8832
50
30 80
20 90
85
40
35
32
被删除的结点只有左子树或者只有右子树如
key=80
结果,其双亲结点的相应指针域的值改为,指向被删除结点的左子树或右子树”。
50
30
20 40
35
90
85
88
32
50
30 80
20 90
85
40
35
8832
被删除的结点既有左子树，也有右子树如被删关键字 key = 50
结果,以其前驱替代之，然后再删除该前驱结点
40
40
30
20 35
90
85
88
32
50
30 80
20 90
85
40
35
8832
Status DeleteBST (BiTree &T,KeyType kval ) {
if (!T) return FALSE;
// 不存在关键字等于 kval的数据元素
else {if ( EQ (kval,T->data.key) )
{ Delete (T); return TRUE; }
// 找到关键字等于 key的数据元素
else if ( LT (kval,T->data.key) )
return DeleteBST ( T->lchild,kval );
// 继续在左子树中进行查找
else
return DeleteBST ( T->rchild,kval );
// 继续在右子树中进行查找
}
} // DeleteBST
算法其中删除操作过程如下：
void Delete ( BiTree &p ){
// 从 二叉排序树中删除结点 p，
// 并重接它的左子树或右子树
if (!p->rchild) { }
else if (!p->lchild) { }
else { }
} // Delete
… …
… …
… …
右子树为空树则只需重接它的左子树
q = p; p = p->lchild; delete(q);
P
PL
p
F
f
P
PL
q
F
f
p
左子树为空树只需重接它的右子树
q = p; p = p->rchild; delete(q);
P
p
F
PR
f
P
F
PR
fq
p
P
C
p F
PR
f
CL Q
SL
QL S
q
s
f
C
p F
PR
S
CL Q
QL SL
q
s
左右子树均不空
q = p; s = p->lchild;
while (s->rchild)
{ q = s; s = s->rchild; }
// s 指向被删结点的前驱
p->data = s->data;
if (q != p ) q->rchild = s->lchild;
else q->lchild = s->lchild;
// 重接 *q的左子树
delete(s);
f
L
p F
PR
P
CL
q
s
C
F
PR
CL Q
SL
QL S
s
f
二叉排序树查找性能的分析对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，
由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，
甚至可能差别很大。
由关键字序列 3,1,2,5,4构造而得的二叉排序树由关键字序列 1,2,3,4,5构造而得的二叉排序树，
例如：
2
1
3
4
5
3
5
4
1
2
ASL =（ 1+2+3+4+5） / 5
= 3
ASL =（ 1+2+3+2+3） / 5
= 2.2
下面讨论平均情况,
不失一般性，假设长度为 n 的序列中有 k 个关键字小于第一个关键字，则必有 n-k-1 个关键字大于第一个关键字,由它构造的二叉排序树
n-k-1k
的平均查找长度是 n 和 k 的函数
P(n,k) ( 0? k? n-1 )
假设 n 个关键字可能出现的 n! 种排列的可能性相同，则含 n 个关键字的二叉排序树的平均查找长度
1
0
),(
1
)(
n
k
knP
n
nPA S L
n
i
i
n
i
ii CnCpknP
11
1),(在等概率查找的情况下，
R
i
L
ir o o t
n
i
i CCCnCnknP
11),(
1
)1)1()(1()1)((11 knPknkPkn
)1()1()(11 knPknkPkn
由此可类似于解差分方程，此递归方程有解：
Cn
n
nnP l og12)(
1
0
)1()1()(111)( n
k
knPknkPknnnP
1
12
)(21 n
k
kPkn
二叉平衡树是二叉查找树的另一种形式，其特点为：树中每个结点的左、右子树深度之差的绝对值不大于 1。 1
RL hh
例如,5
4 8
2
5
4 8
2
1是平衡树 不是平衡树平衡二叉树
构造二叉平衡（查找）树的方法,
在插入过程中，采用平衡旋转技术。
例如,依次插入的关键字为 5,4,2,8,6,9
5
4
2
4
2 5
8
6
6
5 8
4
2
向右旋转一次先向右旋转再向左旋转
4
2 6
5 8
9
4
2
6
8
95
向左旋转一次继续插入关键字 9
哈希表的相关定义哈希函数的构造方法处理冲突的方法哈希表的查找哈希表的插入哈希查找分析哈 希 表哈希查找又叫散列查找，利用哈希函数进行查找的过程。
基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。
哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。
可写成,addr(ai)=H(ki)
其中,ai是表中的一个元素
addr(ai)是 ai的存储地址
ki是 ai的关键字哈希表的相关定义哈希表根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间 ) 上，
并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。
例 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
此法仅适合于：
地址集合的大小 = = 关键字集合的大小其中 a和 b为常数直接定址法数字分析法假设关键字集合中的每个关键字都是由 s 位数字组成 (u1,
u2,…,u s)，分析关键字集中的全体,并从中提取分布均匀的若干位或它们的组合作为地址。此法适于能预先估计出全体关键字的每一位上各种数字出现的频度。
例 有 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
数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别”,同时平方值的中间各位又能受到整个关键字中各位的影响。
此方法适合于,
关键字中的每一位都有某些数字重复出现频度很高的现象。
平方取中法将关键字分割成若干部分，然后取它们的叠加和为哈希地址。 两种叠加处理的方法,
移位叠加,将分割后的几部分低位对齐相加间界叠加,从一端沿分割界来回折送，然后对齐相加此法适于关键字的数字位数特别多。
折叠法例 关键字为,0442205864，哈希地址位数为 4
5 8 6 4
4 2 2 0
0 4
1 0 0 8 8
H(key)=0088
移位叠加
5 8 6 4
0 2 2 4
0 4
6 0 9 2
H(key)=6092
间界叠加除留余数法设定哈希函数为,
H(key) = key MOD p ( p≤m )
其中,m为 表长
p 为不大于 m 的素数或是不含 20 以下的质因子给定一组关键字为,12,39,18,24,33,21，
若取 p=9,则他们对应的哈希函数值将为,
3,3,0,6,6,3
可见，若 p 中含质因子 3,则所有含质因子 3 的关键字均映射到,3 的倍数”的地址上，从而增加了“冲突”的可能例如：
为什么要对 p 加限制？
随机数法设定哈希函数为,
H(key) = Random(key)
其中,Random 为伪随机函数此法用于对长度不等的关键字构造哈希函数。
选取哈希函数考虑的因素：
计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）
关键字分布情况记录的查找频率处理冲突的方法
“处理冲突” 的实际含义是：
为产生冲突的地址寻找下一个哈希地址。
开放定址法
再哈希法
链地址法为产生冲突的地址 H(key) 求得一个地址序列,H0,H1,H2,…,Hs 1≤s≤m-1
Hi = ( H(key) + di ) MOD m
其中,i=1,2,…,s
H(key)为哈希函数 ;m为哈希表长 ;
di为增量序列,有下列三种取法,
开放定址法对增量 di 的三种取法：
1) 线性探测再散列
di = c? i 最简单的情况 c=1
2) 二次探测再散列
di = 12,-12,22,-22,…,
3) 随机探测再散列
di 是一组伪随机数列 或者
di=i× H2(key) (又称双散列函数探测 )
注意：增量 di 应具有“完备性”
即：产生的 Hi 均不相同，且所产生的
s(m-1)个 Hi 值能覆盖哈希表中所有地址。则要求：
※ 平方探测时的表长 m 必为形如 4j+3
的素数（如,7,11,19,23,… 等）；
※ 随机探测时的 m 和 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 冲突
H1=(5+12) MOD 11=6 冲突
H2=(5-12) MOD 11=4 不冲突
38
(3) H(38)=38 MOD 11=5 冲突设伪随机数序列为 9，则：
H1=(5+9) MOD 11=3 不冲突
38
例如,给定关键字集合构造哈希表
{ 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
将所有哈希地址相同的记录都链接在同一链表中。
例,给定关键字 { 19,01,23,14,55,68,11,82,36 }
哈希函数为 H(key)=key MOD 7
链地址法
0
1
2
3
4
5
6
11
19 8268
55
14
36?01
23
例 已知一组关键字 (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
^
^
^
^
^
^
^
^
^
^
^
^
再哈希法方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，
直到冲突不再发生。
即,Hi=Rhi(key) i=1,2,……k
其中,Rhi——不同的哈希函数特点：计算时间增加哈希查找过程给定 k值计算 H(k)
此地址为空关键字 ==k
查找失败查找成功按处理冲突方法计算 Hi
Y
N
Y
N
哈希表的查找对于给定值 K,
计算哈希地址 i = H(K)
若 r[i] = NULL 则查找不成功若 r[i].key = K 则查找成功否则,求下一地址 Hi”,
直至 r[Hi] = NULL (查找不成功 )
或 r[Hi].key = K (查找成功 ) 为止。
int hashsize[] = { 997,..,};
typedef struct {
ElemType *elem;
int count; // 当前数据元素个数
int sizeindex;
// hashsize[sizeindex]为当前容量
} HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
开放定址哈希表的存储结构
Status SearchHash (HashTable H,KeyType K,
int &p,int &c) {
// 在开放定址哈希表 H中查找关键码为 K的记录
p = Hash(K); // 求得哈希地址
while ( H.elem[p].key != NULLKEY &&
!EQ(K,H.elem[p].key)）
collision(p,++c); // 求得下一探查地址 p
if (EQ(K,H.elem[p].key)) return SUCCESS;
// 查找成功，返回待查数据元素位置 p
else return UNSUCCESS; // 查找不成功
} // SearchHash
查找算法
Status InsertHash (HashTable &H,Elemtype e){
if ( HashSearch ( H,e.key,p,c ) == SUCCESS )
return DUPLICATE;
// 表中已有与 e 有相同关键字的元素
elseif ( c < hashsize[H.sizeindex]/2 ) {
// 冲突次数 c 未达到上限，（阀值 c 可调）
H.elem[p] = e; ++H.count; return OK;
// 查找不成功时，返回 p为插入位置
}
else RecreateHashTable(H); // 重建哈希表
} // InsertHash
哈希表的插入例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为 H(key)=key MOD 13,哈希表长为 m=16，
用线性探测再散列处理冲突得哈希表给定值 K=38的查找过程为,
H(38)=12 不空且不等于 38,冲突
H1=(12+1)MOD16=13空记录表中不存在关键字等于 38 的记录,查找不成功。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 1 68 27 55 19 20 84 79 23 11 10
给定值 K=84的查找过程为,
H(84)=6 不空且不等于 84,冲突
H1=(6+1)MOD16=7不空且不等于 84,冲突
H2=(6+2)MOD16=8不空且等于 84,查找成功,
返回记录在表中的序号。
哈希表查找的分析从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。
决定哈希表查找的 ASL的因素：
1) 选用的哈希函数 ;
2) 选用的处理冲突的方法 ;
3) 哈希表饱和的程度，装载因子
α =n/m 值的大小（ n—表中填入的记录数,m—表的长度）
一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论 ASL时，可以不考虑它的因素。
因此，哈希表的 ASL是处理冲突方法和装载因子的函数。
例如：前述例子线性探测处理冲突时,ASL = 22/9
双散列探测处理冲突时,ASL =14/9
链地址法处理冲突时,ASL = 13/9
线性探测再散列链地址法随机探测再散列
)
1
1
1(
2
1
nlS
)1l n (
1
nr
S
2
1
nc
S
可以证明：查找成功时有下列结果：
从以上结果可见，
哈希表的平均查找长度是?的函数,
而不是 n 的函数。
这说明，用哈希表构造查找表时，
可以选择一个适当的装填因子?,
使得 平均查找长度限定在某个范围内。
——这是哈希表所特有的特点。
查找的概念
静态查找表
动态查找表
哈希表查找表 是由同一类型的数据元素 (或记录 )
构成的集合,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数据结构。 对查找表的操作,
查询某个“特定的”数据元素是否在查找表中；
检索某个,特定的,数据元素的各种属性；
在查找表中插入一个数据元素；
从查找表中删去某个数据元素查找的概念静态查找表仅作查询和检索操作的查找表。
动态查找表在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。
查找表的分类：
关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素
（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。
若查找表中存在这样一个记录，则称,查找成功,，查找结果,给出整个记录的信息，或指示该记录在查找表中的位置 ；
否则称,查找不成功,，查找结果,给出
“空记录”或“空指针”。
查找如何进行查找？
查找的方法取决于查找表的结构。
由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。
为了提高查找的效率,需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说,用另外一种结构来表示查找表。
查找方法评价
查找速度
占用存储空间多少
算法本身复杂程度
平均查找长度 ASL(Average Search Length)：
为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的 ~
个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：
个记录的表，对含有
ic
pip
cpA S Ln
i
n
i
ii
n
i
ii
1
1
1
抽象数据类型静态查找表的定义,
ADT StaticSearchTable {
D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。
数据关系 R：数据元素同属一个集合。
静 态 查 找 表数据对象 D:
Create(&ST,n); //构造一个含 n 个数据元素的静态查找表 ST。
Destroy(&ST); //销毁表 ST。
Search(ST,key); //查找 ST 中其关键字等于 kval 的数据元素。
Traverse(ST,Visit()); //按某种次序对
ST的每个元素调用函数
Visit()一次且仅一次，
} ADT StaticSearchTable
基本操作 P：
顺序表的查找
typedef struct {
ElemType *elem; // 数据元素存储空间基址，建表时按实际长度分配,0号单元留空
int length; // 表的长度
} SSTable;
以顺序表表示静态查找表，则 Search函数可用顺序查找来实现。 其顺序存储结构如下：
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
查找过程,从表的一端开始逐个进行记录的关键字和给定值的比较。
例如：
int Search_Seq(SSTable ST,
KeyType kval) {
// 在顺序表 ST中顺序查找其关键字等于
// key的数据元素。若找到，则函数值为
// 该元素在表中的位置，否则为 0。
ST.elem[0].key = kval; // 设置“哨兵”
for (i=ST.length; ST.elem[i].key!=kval; --i);
// 从后往前找
return i; // 找不到时,i为 0
} // Search_Seq
算法描述：
顺序查找性能分析查找算法的平均查找长度 (Average Search Length)：
为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。
n
i
iiCPA S L
1其中,n 为表长
Pi 为查找表中第 i个记录的概率
Ci为找到该记录时，曾和给定值比较过的关键字的个数
1
1
n
i
iP
顺序表查找的平均查找长度为：
对顺序表而言,Ci = n-i+1
2
111
1
n)i(n
n
A S L
n
i
ss
ASL = nP1 +(n-1)P2 + +2Pn-1+Pn
n
Pi
1
在等概率查找的情况下，
在不等概率查找的情况下,ASLss 在
Pn≥ Pn-1≥ ··≥ P2≥ P1
时取极小值。表中记录按查找概率由小到达重新排列,以提高查找效率。
若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，
将刚刚查找到的记录直接移至表尾的位置上。
顺序表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找表。
若以有序表表示静态查找表，则查找过程可以基于“折半”进行。
有序表的查找折半查找查找过程,每次将待查记录所在区间缩小一半。
适用条件,采用顺序存储结构的有序表。
1.设表长为 n,low,high和 mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。
2.初始时，令
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
3.重复上述操作，直至 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
例如 key =21 的查找过程
low 指示查找区间的下界 ;
high 指示查找区间的上界 ;
mid = (low+high)/2。
例 key =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
找 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
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
当下界 low大于上界 high时，则说明表中没有关键字等于 Key的元素，查找不成功。
int Search_Bin ( SSTable ST,KeyType kval ) {
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; // 继续在后半区间进行查找
}
return 0; // 顺序表中不存在待查元素
} // Search_Bin
折半查找算法先看一个有 11个元素的表的例子,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
折半查找的性能分析
判定树：描述查找过程的二叉树。
有 n个结点的判定树的深度为?log2n?+1
折半查找法在查找过程中进行的比较次数最多不超过?log2n?+1
假设 有序表的长度 n=2h-1（反之 h=log2(n+1) ）,
则描述折半查找的判定树是深度为 h的满二叉树。
树中层次为 1的结点有 1个，层次为 2的结点有 2
个，层次为 h的结点有 2 h-1个。假设表中每个记录的查找概率相等则查找成功时折半查找的平均查找长度
1)1(lo g1211 2
1
1
1
n
n
nj
n
C
n
A S L
h
j
j
n
i
ibs
在 n>50 时，可得近似结果
1)1(l o g 2 nA S L bs
可见，
折半查找的效率比顺序查找高。
折半查找只能适用于有序表，并且以顺序存储结构存储。
顺序表 有序表表的特性 无序 有序存储结构 顺序 或 链式 顺序插删操作 易于进行 需移动元素
ASL的值 大 小顺序表和有序表的比较
索引顺序表在建立顺序表的同时，建立一个索引项，包括两项：关键字项和指针项。索引表按关键字有序，
表则为分块有序
0 1 2 3 4 5 6 7 8 9 10 11 12 13 ……
17 08 21 19 14 31 33 22 25 40 52 61 78 46 ……
21 0 40 5 78 10 ……
索引顺序表 = 索引 + 顺序表顺序表索引表索引顺序查找又称分块查找查找过程,将表分成几块，块内无序，块间有序；
先确定待查记录所在块，再在块内查找适用条件,分块有序表算法实现：
用数组存放待查记录,每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针
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
1
11
)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 最大 最小 两者之间表结构 有序表、无序表 有序表 分块有序表存储结构 顺序存储结构线性链表顺序存储结构 顺序存储结构线性链表顺序查找 折半查找 分块查找
(n)
(1)
(n)
(1)
(nlogn)
几种查找表的特性查找 插入 删除无序顺序表无序线性链表有序顺序表有序线性链表静态查找树表
(n)
(n)
(logn)
(n)
(logn)
(1)
(1)
(n)
(1)
(nlogn)
从查找性能看，最好情况能达?(logn)，
此时要求表有序；
从插入和删除的性能看，最好情况能达
(1)，此时要求存储结构是链表。
结论：
ADT DynamicSearchTable {
抽象数据类型动态查找表的定义：
数据对象 D：
数据关系 R,数据元素同属一个集合。
D是具有相同特性的数据元素的集合。
每个数据元素含有类型相同的关键字,可唯一标识数据元素。
动态查找表动态查找表的特点,表结构本身是在查找过程中动态生成。若表中存在其关键字等于给定值 key的记录,表明查找成功；否则插入关键字等于 key的记录。
InitDSTable(&DT)//构造一个空的动态查找表 DT。
DestroyDSTable(&DT)//销毁动态查找表 DT。
SearchDSTable(DT,key);//查找 DT 中与关键字
key等值的元素。
InsertDSTable(&DT,e);//若 DT 中不存在其关键字等于 e.key 的 数据元素，则插入 e 到 DT。
DeleteDSTable(&T,key);//删除 DT中关键字等于
key的数据元素。
TraverseDSTable(DT,Visit());//按某种次序对
DT的每个结点调用函数 Visit() 一次且至多一次。
基本操作：
next
}ADT DynamicSearchTable
二叉排序树（二叉查找树）
定义二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
它的左、右子树也都分别是二叉排序树。
50
30 80
20 90
10 85
40
3525
23 88
66
不是二叉排序树。
以二叉链表形式存储
typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild,*rchild; // 左右指针
} BiTNode,*BiTree;
二叉排序树的存储结构二叉排序树的查找算法若二叉排序树为空，则查找不成功；
否则
1）若给定值等于根结点的关键字，则查找成功；
2）若给定值小于根结点的关键字，则继续在左子树上进行查找；
3）若给定值大于根结点的关键字，则继续在右子树上进行查找。
在二叉排序树中查找关键字值等于 50,35,90,95
50
30 80
20 90
85
40
35
8832
if (!T)
{ p = f; return FALSE; } // 查找不成功
else if ( EQ(kval,T->data.key) )
{ p = T; return TRUE; } // 查找成功
else if ( LT(kval,T->data.key) )
return SearchBST (T->lchild,kval,T,p ); // 在左子树中继续查找
else
return SearchBST (T->rchild,kval,T,p );
// 在右子树中继续查找
Status SearchBST (BiTree T,KeyType kval,BiTree f,
BiTree &p ) {
} // SearchBST
根据动态查找表的定义，“插入”操作在查找不成功时才进行 ;
若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。
二叉排序树的插入算法
Status Insert BST(BiTree &T,ElemType e ) {
if (!SearchBST ( T,e.key,NULL,p ))
{ s = new BiTNode; // 为新结点分配空间
s->data = e;
s->lchild = s->rchild = NULL;
if ( !p ) T = s; // 插入 s 为新的根结点
else if ( LT(e.key,p->data.key) )
p->lchild = s; // 插入 *s 为 *p 的左孩子
else p->rchild = s; // 插入 *s 为 *p 的右孩子
return TRUE; // 插入成功
}
else return FALSE;
} // Insert BST
一个无序序列可以通过构造一棵二叉排序树二而变成一个有序序列
每次插入的新结点都是二叉排序树上新的叶子结点
插入时不必移动其它结点，仅需修改某个结点的指针结论二叉排序树的删除算法和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。
可分三种情况讨论：
被删除的结点是叶子；
被删除的结点只有左子树或者只有右子树；
被删除的结点既有左子树，也有右子树 。
被删除的结点是叶子结点,如 Key = 88
结果,其双亲结点中相应指针域的值改为空
50
30 80
20 90
85
40
35
8832
50
30 80
20 90
85
40
35
32
被删除的结点只有左子树或者只有右子树如
key=80
结果,其双亲结点的相应指针域的值改为,指向被删除结点的左子树或右子树”。
50
30
20 40
35
90
85
88
32
50
30 80
20 90
85
40
35
8832
被删除的结点既有左子树，也有右子树如被删关键字 key = 50
结果,以其前驱替代之，然后再删除该前驱结点
40
40
30
20 35
90
85
88
32
50
30 80
20 90
85
40
35
8832
Status DeleteBST (BiTree &T,KeyType kval ) {
if (!T) return FALSE;
// 不存在关键字等于 kval的数据元素
else {if ( EQ (kval,T->data.key) )
{ Delete (T); return TRUE; }
// 找到关键字等于 key的数据元素
else if ( LT (kval,T->data.key) )
return DeleteBST ( T->lchild,kval );
// 继续在左子树中进行查找
else
return DeleteBST ( T->rchild,kval );
// 继续在右子树中进行查找
}
} // DeleteBST
算法其中删除操作过程如下：
void Delete ( BiTree &p ){
// 从 二叉排序树中删除结点 p，
// 并重接它的左子树或右子树
if (!p->rchild) { }
else if (!p->lchild) { }
else { }
} // Delete
… …
… …
… …
右子树为空树则只需重接它的左子树
q = p; p = p->lchild; delete(q);
P
PL
p
F
f
P
PL
q
F
f
p
左子树为空树只需重接它的右子树
q = p; p = p->rchild; delete(q);
P
p
F
PR
f
P
F
PR
fq
p
P
C
p F
PR
f
CL Q
SL
QL S
q
s
f
C
p F
PR
S
CL Q
QL SL
q
s
左右子树均不空
q = p; s = p->lchild;
while (s->rchild)
{ q = s; s = s->rchild; }
// s 指向被删结点的前驱
p->data = s->data;
if (q != p ) q->rchild = s->lchild;
else q->lchild = s->lchild;
// 重接 *q的左子树
delete(s);
f
L
p F
PR
P
CL
q
s
C
F
PR
CL Q
SL
QL S
s
f
二叉排序树查找性能的分析对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，
由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，
甚至可能差别很大。
由关键字序列 3,1,2,5,4构造而得的二叉排序树由关键字序列 1,2,3,4,5构造而得的二叉排序树，
例如：
2
1
3
4
5
3
5
4
1
2
ASL =（ 1+2+3+4+5） / 5
= 3
ASL =（ 1+2+3+2+3） / 5
= 2.2
下面讨论平均情况,
不失一般性，假设长度为 n 的序列中有 k 个关键字小于第一个关键字，则必有 n-k-1 个关键字大于第一个关键字,由它构造的二叉排序树
n-k-1k
的平均查找长度是 n 和 k 的函数
P(n,k) ( 0? k? n-1 )
假设 n 个关键字可能出现的 n! 种排列的可能性相同，则含 n 个关键字的二叉排序树的平均查找长度
1
0
),(
1
)(
n
k
knP
n
nPA S L
n
i
i
n
i
ii CnCpknP
11
1),(在等概率查找的情况下，
R
i
L
ir o o t
n
i
i CCCnCnknP
11),(
1
)1)1()(1()1)((11 knPknkPkn
)1()1()(11 knPknkPkn
由此可类似于解差分方程，此递归方程有解：
Cn
n
nnP l og12)(
1
0
)1()1()(111)( n
k
knPknkPknnnP
1
12
)(21 n
k
kPkn
二叉平衡树是二叉查找树的另一种形式，其特点为：树中每个结点的左、右子树深度之差的绝对值不大于 1。 1
RL hh
例如,5
4 8
2
5
4 8
2
1是平衡树 不是平衡树平衡二叉树
构造二叉平衡（查找）树的方法,
在插入过程中，采用平衡旋转技术。
例如,依次插入的关键字为 5,4,2,8,6,9
5
4
2
4
2 5
8
6
6
5 8
4
2
向右旋转一次先向右旋转再向左旋转
4
2 6
5 8
9
4
2
6
8
95
向左旋转一次继续插入关键字 9
哈希表的相关定义哈希函数的构造方法处理冲突的方法哈希表的查找哈希表的插入哈希查找分析哈 希 表哈希查找又叫散列查找，利用哈希函数进行查找的过程。
基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。
哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。
可写成,addr(ai)=H(ki)
其中,ai是表中的一个元素
addr(ai)是 ai的存储地址
ki是 ai的关键字哈希表的相关定义哈希表根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间 ) 上，
并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。
例 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
此法仅适合于：
地址集合的大小 = = 关键字集合的大小其中 a和 b为常数直接定址法数字分析法假设关键字集合中的每个关键字都是由 s 位数字组成 (u1,
u2,…,u s)，分析关键字集中的全体,并从中提取分布均匀的若干位或它们的组合作为地址。此法适于能预先估计出全体关键字的每一位上各种数字出现的频度。
例 有 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
数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别”,同时平方值的中间各位又能受到整个关键字中各位的影响。
此方法适合于,
关键字中的每一位都有某些数字重复出现频度很高的现象。
平方取中法将关键字分割成若干部分，然后取它们的叠加和为哈希地址。 两种叠加处理的方法,
移位叠加,将分割后的几部分低位对齐相加间界叠加,从一端沿分割界来回折送，然后对齐相加此法适于关键字的数字位数特别多。
折叠法例 关键字为,0442205864，哈希地址位数为 4
5 8 6 4
4 2 2 0
0 4
1 0 0 8 8
H(key)=0088
移位叠加
5 8 6 4
0 2 2 4
0 4
6 0 9 2
H(key)=6092
间界叠加除留余数法设定哈希函数为,
H(key) = key MOD p ( p≤m )
其中,m为 表长
p 为不大于 m 的素数或是不含 20 以下的质因子给定一组关键字为,12,39,18,24,33,21，
若取 p=9,则他们对应的哈希函数值将为,
3,3,0,6,6,3
可见，若 p 中含质因子 3,则所有含质因子 3 的关键字均映射到,3 的倍数”的地址上，从而增加了“冲突”的可能例如：
为什么要对 p 加限制？
随机数法设定哈希函数为,
H(key) = Random(key)
其中,Random 为伪随机函数此法用于对长度不等的关键字构造哈希函数。
选取哈希函数考虑的因素：
计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）
关键字分布情况记录的查找频率处理冲突的方法
“处理冲突” 的实际含义是：
为产生冲突的地址寻找下一个哈希地址。
开放定址法
再哈希法
链地址法为产生冲突的地址 H(key) 求得一个地址序列,H0,H1,H2,…,Hs 1≤s≤m-1
Hi = ( H(key) + di ) MOD m
其中,i=1,2,…,s
H(key)为哈希函数 ;m为哈希表长 ;
di为增量序列,有下列三种取法,
开放定址法对增量 di 的三种取法：
1) 线性探测再散列
di = c? i 最简单的情况 c=1
2) 二次探测再散列
di = 12,-12,22,-22,…,
3) 随机探测再散列
di 是一组伪随机数列 或者
di=i× H2(key) (又称双散列函数探测 )
注意：增量 di 应具有“完备性”
即：产生的 Hi 均不相同，且所产生的
s(m-1)个 Hi 值能覆盖哈希表中所有地址。则要求：
※ 平方探测时的表长 m 必为形如 4j+3
的素数（如,7,11,19,23,… 等）；
※ 随机探测时的 m 和 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 冲突
H1=(5+12) MOD 11=6 冲突
H2=(5-12) MOD 11=4 不冲突
38
(3) H(38)=38 MOD 11=5 冲突设伪随机数序列为 9，则：
H1=(5+9) MOD 11=3 不冲突
38
例如,给定关键字集合构造哈希表
{ 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
将所有哈希地址相同的记录都链接在同一链表中。
例,给定关键字 { 19,01,23,14,55,68,11,82,36 }
哈希函数为 H(key)=key MOD 7
链地址法
0
1
2
3
4
5
6
11
19 8268
55
14
36?01
23
例 已知一组关键字 (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
^
^
^
^
^
^
^
^
^
^
^
^
再哈希法方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，
直到冲突不再发生。
即,Hi=Rhi(key) i=1,2,……k
其中,Rhi——不同的哈希函数特点：计算时间增加哈希查找过程给定 k值计算 H(k)
此地址为空关键字 ==k
查找失败查找成功按处理冲突方法计算 Hi
Y
N
Y
N
哈希表的查找对于给定值 K,
计算哈希地址 i = H(K)
若 r[i] = NULL 则查找不成功若 r[i].key = K 则查找成功否则,求下一地址 Hi”,
直至 r[Hi] = NULL (查找不成功 )
或 r[Hi].key = K (查找成功 ) 为止。
int hashsize[] = { 997,..,};
typedef struct {
ElemType *elem;
int count; // 当前数据元素个数
int sizeindex;
// hashsize[sizeindex]为当前容量
} HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
开放定址哈希表的存储结构
Status SearchHash (HashTable H,KeyType K,
int &p,int &c) {
// 在开放定址哈希表 H中查找关键码为 K的记录
p = Hash(K); // 求得哈希地址
while ( H.elem[p].key != NULLKEY &&
!EQ(K,H.elem[p].key)）
collision(p,++c); // 求得下一探查地址 p
if (EQ(K,H.elem[p].key)) return SUCCESS;
// 查找成功，返回待查数据元素位置 p
else return UNSUCCESS; // 查找不成功
} // SearchHash
查找算法
Status InsertHash (HashTable &H,Elemtype e){
if ( HashSearch ( H,e.key,p,c ) == SUCCESS )
return DUPLICATE;
// 表中已有与 e 有相同关键字的元素
elseif ( c < hashsize[H.sizeindex]/2 ) {
// 冲突次数 c 未达到上限，（阀值 c 可调）
H.elem[p] = e; ++H.count; return OK;
// 查找不成功时，返回 p为插入位置
}
else RecreateHashTable(H); // 重建哈希表
} // InsertHash
哈希表的插入例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为 H(key)=key MOD 13,哈希表长为 m=16，
用线性探测再散列处理冲突得哈希表给定值 K=38的查找过程为,
H(38)=12 不空且不等于 38,冲突
H1=(12+1)MOD16=13空记录表中不存在关键字等于 38 的记录,查找不成功。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 1 68 27 55 19 20 84 79 23 11 10
给定值 K=84的查找过程为,
H(84)=6 不空且不等于 84,冲突
H1=(6+1)MOD16=7不空且不等于 84,冲突
H2=(6+2)MOD16=8不空且等于 84,查找成功,
返回记录在表中的序号。
哈希表查找的分析从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。
决定哈希表查找的 ASL的因素：
1) 选用的哈希函数 ;
2) 选用的处理冲突的方法 ;
3) 哈希表饱和的程度，装载因子
α =n/m 值的大小（ n—表中填入的记录数,m—表的长度）
一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论 ASL时，可以不考虑它的因素。
因此，哈希表的 ASL是处理冲突方法和装载因子的函数。
例如：前述例子线性探测处理冲突时,ASL = 22/9
双散列探测处理冲突时,ASL =14/9
链地址法处理冲突时,ASL = 13/9
线性探测再散列链地址法随机探测再散列
)
1
1
1(
2
1
nlS
)1l n (
1
nr
S
2
1
nc
S
可以证明：查找成功时有下列结果：
从以上结果可见，
哈希表的平均查找长度是?的函数,
而不是 n 的函数。
这说明，用哈希表构造查找表时，
可以选择一个适当的装填因子?,
使得 平均查找长度限定在某个范围内。
——这是哈希表所特有的特点。
