第9章 查找 9.1 查找的基本概念 9.2 线性表的查找 9.3 树表的查找 9.4 哈希表查找

9.1 查找的基本概念 查找：在某种数据结构中找出满足给定条件的元素 查找表：用于查找的数据集合 由一组记录组成的表或文件； 9.1 查找的基本概念 查找：在某种数据结构中找出满足给定条件的元素 查找表：用于查找的数据集合 由一组记录组成的表或文件； 每个记录由若干个数据项组成,并假设每个记录都有一个能唯一标识该记录的关键字。 在这种条件下,查找的定义是： 给定一个值k,在含有n个记录的表中找出关键字等于k的记录。 若找到,则查找成功,返回该记录的信息或该记录在表中的位置；否则查找失败,返回相关的指示信息。

若在查找的同时对表做修改运算（如插入和删除），则相应的表称之为动态查找表。 否则称之为静态查找表。

关键字 关键字：查找表中的每个数据元素有若干属性，可以唯一标识某个数据元素的属性称为关键字。 查找结果不唯一 查找结果唯一 书号 书名 作者 出版社 定价 015010 C程序设计 谭浩强 清华大学出版社 26.00 015024 数据结构 严蔚敏 清华大学出版社 22.00 015025 离散数学 左孝凌 上海科学技术文献出版社 14.00 015080 计算机操作系统 汤子瀛 西安电子科技大学出版社 24.00 查找结果唯一

采用何种查找方法? (1) 使用哪种数据结构来表示“表”，即表中记录是按何种方式组织的。 (2) 表中关键字的次序。是对无序集合查找还是对有序集合查找?

平均查找长度（Average Search Length） 与给定值进行比较的关键字个数的期望值 衡量查找算法性能的主要依据 对于长度为n的查找表，查找成功时的平均查找长度为 ： 表中记录的个数 ( ) 查找第i个记录的概率 找到第i个记录时，需要进行的比较次数

9.2 线性表的查找 三种在线性表上进行查找的方法： (1) 顺序查找 (2) 二分查找 (3) 分块查找 以顺序表作为存储结构 9.2 线性表的查找 三种在线性表上进行查找的方法： (1) 顺序查找 (2) 二分查找 (3) 分块查找 以顺序表作为存储结构 #define MAXL <表中最多记录个数> typedef struct { KeyType key; //KeyType为关键字的数据类型 InfoType data; //其他数据 } NodeType; typedef NodeType SeqList[MAXL]; //顺序表类型

9.2.1 顺序查找 思路： 从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比较； 9.2.1 顺序查找 思路： 从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比较； 若当前扫描到的关键字与k相等，则查找成功，返回找到的记录的下标值； 若扫描结束后，仍未找到关键字等于k的记录，则查找失败返回-1 。 int SeqSearch(SeqList R,int n,KeyType k) { int i=0; while (i<n && R[i].key!=k) i++; if (i>=n) return -1; else return i; }

顺序查找的平均查找长度 关键字之间的比较次数取决于所查记录在表中的位置。 若查找表中第1个记录，仅需比较一次；而查找表中最后一个记录时，需比较n次。 查找成功时，顺序查找的平均查找长度为： 思考：不成功时的平均查找长度是多少？

顺序查找总结 优点： 缺点: 算法简单且适用面广。 对表的结构无任何要求，无论记录是否按关键字有序均可应用，而且上述所有讨论对线性链表也同样适用。 缺点: 平均查找长度较大，特别是当n很大时，查找效率低。

9.2.2 二分查找 也称为折半查找，要求线性表中的结点必须己按关键字值的递增或递减顺序排列。 有序表上的查找 思路： 首先用要查找的关键字k与中间位置的结点的关键字相比较，这个中间结点把线性表分成了两个子表，若比较结果相等则查找完成; 若不相等，再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表，这样递归进行下去，直到找到满足条件的结点或者该线性表中没有这样的结点。

例如: key = 64 的查找过程 05 13 19 21 37 56 64 75 80 88 92 low 指示查找区间的下界; 0 1 2 3 4 5 6 7 8 9 10 low low high high mid mid mid low 指示查找区间的下界; high 指示查找区间的上界; mid = (low+high)/2

查找关键字为18的数据元素 high low 03 10 15 19 25 28 40 55 83 ↑ ↑ ↑ low mid high 03 10 15 19 25 28 40 55 83 ↑ ↑ ↑ low mid high ↑ ↑ ↑ low mid high ↑↑ ↑ low mid high ↑↑↑ high low

折半查找算法 int BinSearch(SeqList R,int n,KeyType k) { int low=0,high=n-1,mid; while (low<=high) { mid=(low+high)/2; if (R[mid].key==k) //查找成功返回 return mid; if (R[mid].key>k)//继续在R[low..mid-1]查找 high=mid-1; else low=mid+1; //继续在R[mid+1..high]中查找 } return -1;

判定树（比较树） 二分查找过程可用二叉树来描述： 把当前查找区间的中间位置上的记录作为根； 左子表和右子表中的记录分别作为根的左子树和右子树。 R[0..10]的二分查找的判定树(n=11)

例9.1对于给定11个数据元素的有序表{2,3,10,15,20,25,28,29,30,35,40},采用二分查找,试问： (1)若查找给定值为20的元素，将依次与表中哪些元素比较？ (2)若查找给定值为26的元素，将依次与哪些元素比较？ (3)假设查找表中每个元素的概率相同，求查找成功时的平均查找长度和查找不成功时的平均查找长度。

(1)若查找给定值为20的元素,依次与表中25,10,15,20元素比较,共比较4次。 (2)若查找给定值为26的元素,依次与25,30,28元素比较,共比较3次。 (3)在查找成功时,会找到图中某个圆形结点,则成功时的平均查找长度： 在查找不成功时,会找到图中某个方形结点,则不成功时的平均查找长度：

折半查找总结 优点： 效率比顺序查找高 比较次数少，查找速度快，平均性能好 缺点： 要求查找表有序 仅限于顺序存储结构

9.2.3 索引存储结构和分块查找 1.索引存储结构 索引存储结构＝数据表+索引表 索引表中的每一项称为索引项 索引项的一般形式是： 9.2.3 索引存储结构和分块查找 1.索引存储结构 索引存储结构＝数据表+索引表 索引表中的每一项称为索引项 索引项的一般形式是： （关键字,地址） 指向该关键字对应结点的指针 唯一标识 一个结点

索引表 数据表 地址 关键字 城市名 区号 说明 300 010 100 Beijing 首都 310 021 130 Shanghai 直辖市 320 025 210 160 Wuhan 027 湖北省省会 330 190 Xian 029 陕西省省会 340 Nanjing 江苏省省会

2. 分块查找（顺序查找的改进） 性能：介于顺序查找和二分查找之间 思路： 　性能：介于顺序查找和二分查找之间 思路： （1）将数据表R[0..n-1]均分为b块，前b-1块中记录个数为s=n/b，最后一块即第b块的记录数小于等于s； （2）每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即要求表“分块有序”； （3）抽取各块中的最大关键字及其起始位置构成一个索引表。由于表R是分块有序的，所以索引表是一个递增有序表。

分块查找示例 索引表 步骤 ①确定待查记录所在的块：将待查关键字k与索引表中的关键字进行比较，可用顺序查找法或折半查找法进行。 最大关键字 25 56 89 起始地址 1 6 11 10 5 25 20 18 56 34 29 32 47 68 72 61 84 89 步骤 ①确定待查记录所在的块：将待查关键字k与索引表中的关键字进行比较，可用顺序查找法或折半查找法进行。 ②进一步用顺序查找法，在相应块内查找关键字为k的元素

若以二分查找来确定块,则分块查找成功时的平均查找长度为： 若以顺序查找确定块,则分块查找成功时的平均查找长度为： 当s= 时，ASL‘ blk取极小值 +1，即当采用顺序查找确定块时，应将各块中的记录数选定为 。

线性表的查找总结 顺序查找适用于任何线性表，但效率较低； 折半查找效率最高，但要求查找表有序且顺序存储，故插入删除时必须移动元素，这种由移动元素引起的额外时间开销，就会抵消折半查找的优点。也就是说，折半查找只适用于静态查找表。 分块查找不需要对全部的数据元素排序，它的插入删除在块内进行，由于不要求有序，操作比较容易，其主要代价是增加一个辅助数组的存储空间和将初始顺序表分块排序的操作； 若要对动态查找表进行高效率的查找，可采用下面介绍的几种特殊的二叉树或树作为表的组织形式 。

9.3 树表的查找 9.3.1 二叉排序树 二叉排序树(简称BST)，又称二叉查找(搜索)树 9.3 树表的查找 9.3.1 二叉排序树 二叉排序树(简称BST)，又称二叉查找(搜索)树 二叉排序树或者是空树，或者是满足如下性质的二叉树： (1) 若它的左子树非空，则左子树上所有记录的值均小于根记录的值； (2) 若它的右子树非空，则右子树上所有记录的值均大于根记录的值； (3) 左、右子树本身又各是一棵二叉排序树。 注意：二叉排序树中没有相同关键字的结点。

二叉排序树示例 中序遍历序列为：3，12，18，23，30，53，71，89，94 30 12 53 3 23 94 18 71 89

例如: 50 30 80 20 40 90 66 10 25 35 85 23 88 不 是二叉排序树。

在讨论二叉排序树上的运算之前，定义其结点的类型如下： typedef struct node //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据域 struct node *lchild,*rchild; //左右孩子指针 } BSTNode;

1. 二叉排序树上的查找 在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。 递归查找算法SearchBST()如下： BSTNode *SearchBST(BSTNode *bt,KeyType k) { if (bt==NULL || bt->key==k) //递归终结条件 return bt; if (k<bt->key) return SearchBST(bt->lchild,k); //在左子树中递归查找 else return SearchBST(bt->rchild,k); //在右子树中递归查找 }

50 30 80 20 90 85 40 35 88 32 50 50 50 50 50 30 80 40 90 35 查找关键字 50 , 35 , 90 , 95

最好情况：二叉排序树的深度与n个元素的二叉判定树的高度相同 二叉排序树的查找分析 4 2 5 1 3 6 最好情况：二叉排序树的深度与n个元素的二叉判定树的高度相同 1 2 3 4 5 6 最坏情况：二叉排序树为单支树，和顺序查找相同 二叉排序树的平均查找长度是O( )

2. 二叉排序树的插入和生成 插入过程： （1）若二叉排序树T为空，则创建一个key域为k的结点，将它作为根结点； 　（2）否则将k和根结点的关键字比较，若两者相等，则说明树中已有此关键字k，无须插入，直接返回0； 　（3）若k<T->key，则将k插入根结点的左子树中。 　（4）否则将它插入右子树中。

int InsertBST(BSTNode *&p,KeyType k) //在以*p为根结点的BST中插入一个关键字为k的结点。插入成功返回1,否则返回0 { if (p==NULL) //原树为空, 新插入的记录为根结点 { p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=k; p->lchild=p->rchild=NULL; return 1; } else if (k==p->key)//存在相同关键字的结点,返回0 return 0; else if (k<p->key) return InsertBST(p->lchild,k);//插入到左子树中 else return InsertBST(p->rchild,k);//插入到右子树中

二叉排序树的插入 35 15 45 50 40 25 10 20 30 插入新结点42 42 插入新结点28 28 插入在查找的基础上进行；每次结点的插入，都要从根结点出发搜索插入位置，然后把新结点作为叶子结点插入。

二叉排序树的生成 从一个空树开始，每输入一个关键字，就调用一次插入算法将它插入到当前已生成的二叉排序树中。 序列: 32,26,45,35,12,20,12 (a) ø (c) 32 26 (d) 32 26 45 (b) 32 32 26 45 35 (e) 32 26 45 12 35 (f) 12 35 32 26 45 20 (g)

例9.3 已知一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。 解：生成的二叉排序树如右图所示。

3. 二叉排序树的结点删除 50 30 80 20 40 90 35 85 32 88 （1）被删除的结点是叶子结点：直接删去该结点。 被删关键字 = 20 88 例如: 50 30 80 20 40 90 35 85 32 88 其双亲结点中相应指针域的值改为“空”

其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。 （2）被删除的结点只有左子树或者只有右子树，用其左子树或者右子树代替它。 被删关键字 = 40 80 50 30 80 20 40 90 35 85 32 88 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。

40 50 30 80 20 40 40 90 35 85 32 88 （3）被删除的结点既有左子树，也有右子树 被删关键字 = 50 前驱结点 被删结点 以其前驱替代之，然后再删除该前驱结点。前驱是左子树中最大的结点。

int DeleteBST(BSTNode *&bt,KeyType k) { if (bt==NULL) return 0; //空树删除失败 else { if (k<bt->key) return DeleteBST(bt->lchild,k); //递归在左子树中删除为k的结点 else if (k>bt->key) return DeleteBST(bt->rchild,k); //递归在右子树中删除为k的结点 { Delete(bt); //调用Delete(bt)函数删除*bt结点 return 1; }

void Delete(BSTNode *&p) //从二叉排序树中删除*p结点 { BSTNode *q; if (p->rchild==NULL) //*p结点没有右子树的情况 { q=p; p=p->lchild; //其右子树的根结点放在被删结点的位置上 free(q); } else if (p->lchild==NULL) //*p结点没有左子树 { q=p; p=p->rchild; //将*p结点的右子树作为双亲结点的相应子树/ else Delete1(p,p->lchild); //*p结点既没有左子树又没有右子树的情况

删除二叉排序树结点的算法DeleteBST()如下(指针变量p指向待删除的结点,指针变量q指向待删除结点*p的双亲结点)： void Delete1(BSTNode *p,BSTNode *&r) //当被删*p结点有左右子树时的删除过程 { BSTNode *q; if (r->rchild!=NULL) Delete1(p,r->rchild); //递归找最右下结点 else //找到了最右下结点*r { p->key=r->key; //将*r的关键字值赋给*p q=r; r=r->lchild; //将左子树的根结点放在被删结点的位置上 free(q); //释放原*r的空间 }

右子树为空树，则只需重接它的左子树 q = p; p = p->lchild; delete(q); q q p p

左子树为空树，只需重接它的右子树 q = p; p = p->rchild; delete(q); q q p p

左右子树均不空 q = p; r = p->lchild; while （!r->rchild） { q = r; r = r->rchild; } //r指向被删结点的前驱 p->data = r->data; if （q != p ） q->rchild = r->lchild; else q->lchild = r->lchild; //重接*q的左子树 delete（r）; q p r

9.3.2 平衡二叉树(AVL) 若一棵二叉树中每个结点的左、右子树的高度至多相差1，则称此二叉树为平衡二叉树。 在算法中，通过平衡因子(balancd factor，用bf表示)来具体实现上述平衡二叉树的定义。 平衡因子： 平衡二叉树中每个结点的平衡因子是该结点左子树的高度减去右子树的高度。 从平衡因子的角度可以说，若一棵二叉树中所有结点的平衡因子的绝对值小于或等于1，即平衡因子取值为1、0或-1，则该二叉树称为平衡二叉树。

平衡二叉树 不平衡二叉树

构造平衡二叉树 平衡二叉树中插入新结点方式与二叉排序树相似，只是插入后可能破坏了平衡性，解决方法是调整。 例如: 依次插入的关键字为5, 4, 2, 8, 6, 9 5 4 4 LL RL 4 2 5 2 6 2 8 5 8 向右旋转 一次 6 先向右旋转 再向左旋转

构造平衡二叉树 向左旋转一次 4 2 6 5 8 RR 6 8 9 9 4 2 继续插入关键字 9 5

9.3.3 B-树（略） B-树又称为多路平衡查找树,是一种组织和维护外存文件系统非常有效的数据结构。 B-树中所有结点的孩子结点最大值称为B-树的阶,通常用m表示,从查找效率考虑,要求m≥3。一棵m阶B-树或者是一棵空树,或者是满足下列要求的m叉树： (1) 树中每个结点至多有m个孩子结点(即至多有m-1个关键字)； (2) 除根结点外,其他结点至少有m/2个孩子结点(即至少有m/2-1=(m-1)/2个关键字)； (3) 若根结点不是叶子结点,则根结点至少有两个孩子结点；

(4) 每个结点的结构为： n p0 k1 p1 k2 p2 … kn pn 其中,n为该结点中的关键字个数,除根结点外,其他所有结点的n大于等于m/2-1,且小于等于m-1；ki(1≤i≤n)为该结点的关键字且满足ki＜ki+1；pi(0≤i≤n)为该结点的孩子结点指针且满足pi(0≤i≤n-1)结点上的关键字大于等于ki且小于ki+1,pn结点上的关键字大于kn。 (5) 所有叶子结点都在同一层上,即B-树是所有结点的平衡因子均等于0的多路查找树。

一棵5阶B-树

在B-树的存储结构中,各结点的类型定义如下： #define MAXM 10 //定义B-树的最大的阶数 typedef int KeyType; //KeyType为关键字类型 typedef struct node //B-树结点类型定义 { int keynum; //结点当前拥有的关键字的个数 KeyType key[MAXM]; //[1..keynum]存放关键字,[0]不用 struct node *parent; //双亲结点指针 struct node *ptr[MAXM]; //孩子结点指针数组[0..keynum] } BTNode;

B-树的查找 将k与根结点中的key[i]进行比较： (1) 若k=key[i],则查找成功； 在B-树中查找给定关键字的方法类似于二叉排序树上的查找，不同的是在每个记录上确定向下查找的路径不一定是二路(即二叉)的，而是n+1路的。因为记录内的关键字序列是有序的数量key[1..n]，故既可以用顺序查找，也可以用折半查找。在一棵B-树上顺序查找关键字为k的方法为： 将k与根结点中的key[i]进行比较： (1) 若k=key[i],则查找成功； (2) 若k＜key[1],则沿着指针ptr[0]所指的子树继续查找； (3) 若key[i]＜k＜key[i+1],则沿着指针ptr[i]所指的子树继续查找； (4) 若k＞key[n],则沿着指针ptr[n]所指的子树继续查找。

2. B-树的插入 将关键字k插入到B-树的过程分两步完成： (1) 利用前述的B-树的查找算法找出该关键字的插入结点(注意B-树的插入结点一定是叶子结点)。 (2) 判断该结点是否还有空位置,即判断该结点是否满足n＜m-1,若该结点满足n＜m-1,说明该结点还有空位置,直接把关键字k插入到该结点的合适位置上(即满足插入后结点上的关键字仍保持有序)；

若该结点有n=m-1,说明该结点已没有空位置,需要把结点分裂成两个。 分裂的做法是,取一新结点,把原结点上的关键字和k按升序排序后,从中间位置(即m/2=(m+1)/2之处)把关键字(不包括中间位置的关键字)分成两部分,左部分所含关键字放在旧结点中,右部分所含关键字放在新结点中,中间位置的关键字连同新结点的存储位置插入到父亲结点中。如果父结点的关键字个数也超过Max,则要再分裂,再往上插,直至这个过程传到根结点为止。

例，关键字序列为： {1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}。 创建一棵5阶B-树。

10 3 6 10 16 3 6 6 10 16 6 6 10 13 16 插入11 13 16 3 10 1 2 1 2 4 5 1 2 6 7 1 2 4 1 2 4 5 6 7 8 9 7 8 7 8 11 13 7 8 11 13 7 11 11 12 11 12 13 14 11 13 16 17 11 13 11 13 17 11 13 14 15 17 20 17 18 19 20 插入3 插入5 插入4 插入9 插入10 插入8,13 插入15 插入17 插入16 插入20 插入12,14,18,19

3. B-树的删除 B-树的删除过程与插入过程类似,只是稍为复杂一些。要使删除后的结点中的关键字个数≥m/2-1,将涉及到结点的“合并”问题。在B-树上删除关键字k的过程分两步完成： (1) 利用前述的B-树的查找算法找出该关键字所在的结点。 (2) 在结点上删除关键字k分两种情况：一种是在叶子结点上删除关键字；另一种是在非叶子结点上删除关键字。

(3) 在非叶子结点上删除关键字的过程： 　　假设要删除关键字key[i](1≤i≤n),在删去该关键字后,以该结点ptr[i]所指子树中的最小关键字key[min]来代替被删关键字key[i]所在的位置(注意ptr[i]所指子树中的最小关键字key[min]一定是在叶子结点上)。 　　然后再以指针ptr[i]所指结点为根结点查找并删除key[min](即再以ptr[i]所指结点为B-树的根结点,以key[min]为要删除的关键字,然后再次调用B-树上的删除算法)。 　　这样也就把在非叶子结点上删除关键字k的问题转化成了在叶子结点上删除关键字key[min]的问题。

(4) 在B-树的叶子结点上删除关键字有以下三种情况： ① 假如被删结点的关键字个数大于Min,说明删去该关键字后该结点仍满足B-树的定义,则可直接删去该关键字。 ② 假如被删结点的关键字个数等于Min,说明删去关键字后该结点将不满足B-树的定义。 此时若该结点的左(或右)兄弟结点中关键字个数大于Min,则把该结点的左(或右)兄弟结点中最大(或最小)的关键字上移到双亲结点中,同时把双亲结点中大于(或小于)上移关键字的关键字下移到要删除关键字的结点中,这样删去关键字k后该结点以及它的左(或右)兄弟结点都仍旧满足B-树的定义。

③ 假如被删结点的关键字个数等于Min,并且该结点的左和右兄弟结点(如果存在的话)中关键字个数均等于Min。

例如,对于上例生成的B-树,给出删除8,16,15,4等四个关键字的过程。

对于前例生成的B-树，给出删除8，16，15，4等四个关键字的过程。 10 删16 6 10 13 18 6 3 6 13 13 16 13 17 13 18 17 删8 1 2 3 5 1 2 4 5 5 7 8 9 7 9 11 12 14 15 14 17 14 17 17 18 19 20 18 19 20 19 20 18 （a） 初始5阶B-树 删4 删15

9.3.4 B+树 在索引文件组织中,经常使用B-树的一些变形,其中B+树是一种应用广泛的变形。一棵m阶B+树满足下列条件： (4) 有n棵子树的结点有n个关键字。

(5) 所有叶子结点包含全部(数据文件中记录) 关键字及指向相应记录的指针(或存放数据文件分块后每块的最大关键字及指向该块的指针),而且叶子结点按关键字大小顺序链接(可以把每个叶子结点看成是一个基本索引块,它的指针不再指向另一级索引块,而是直接指向数据文件中的记录)。 (6) 所有分支结点(可看成是索引的索引)中仅包含它的各个子结点(即下级索引的索引块)中最大关键字及指向子结点的指针。

一棵4阶的B+树

m阶的B+树和m阶的B-树,定义中的前三点是相同的,主要的差异是： (1) 在B+树中,具有n个关键字的结点含有n棵子树,即每个关键字对应一棵子树,而在B-树中,具有n个关键字的结点含有(n+1)棵子树。 (2) 在B+树中,每个结点(除根结点外)中的关键字个数n的取值范围是m/2≤n ≤m,根结点n的取值范围是1≤n≤m；而在B-树中,它们的取值范围分别是m/2-1≤n ≤m-1和1≤n≤m-1。 (3) B+树中的所有叶子结点包含了全部关键字,即其他非叶子结点中的关键字包含在叶子结点中,而在B-树中,叶子结点包含的关键字与其他结点包含的关键字是不重复的。

(4) B+树中所有非叶子结点仅起到索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址。而在B-树中,每个关键字对应一个记录的存储地址。

总 结 以上讨论的各种查找表的共同特点： 对于频繁使用的查找表，希望 ASL = 0 记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程为给定值依次和关键字集合中各个关键字进行比较 平均查找长度都不为零 对于频繁使用的查找表，希望 ASL = 0 只有一个办法：预先知道所查关键字在表中的位置，即要求：记录在表中位置和其关键字之间存在一种确定的关系。

9.4 哈希表查找 9.4.1 哈希表的基本概念 哈希表(Hash Table)又称散列表，是除顺序存储结构、链式存储结构和索引存储结构之外的又一种存储线性表的存储结构。 哈希表存储的基本思路 设要存储的对象个数为n，设置一个长度为m(m≥n)的连续内存单元，以线性表中每个对象的关键字ki(0≤i≤n-1)为自变量，通过一个称为哈希函数的函数h(ki)，把ki映射为内存单元的地址(或称下标)h(ki)，并把该对象存储在该内存单元中。 h(ki)也称为哈希地址(又称散列地址)。 如此构造的线性表存储结构称为哈希表。

冲突的概念 对于两个关键字ki和kj(i≠j),有ki≠kj(i≠j),但h(ki)=h(kj)。把这种现象叫做哈希冲突。 把具有不同关键字而具有相同哈希地址的对象称做“同义词”，由同义词引起的冲突称作同义词冲突。 同义词冲突是很难避免的

9.4.2 哈希函数构造方法 目标是使得到的哈希地址尽可能均匀地分布在n个连续内存单元地址上。 1. 直接定址法 9.4.2 哈希函数构造方法 目标是使得到的哈希地址尽可能均匀地分布在n个连续内存单元地址上。 1. 直接定址法 以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。 直接定址法的哈希函数h(k)为： h(k)=k+c 【例】：解放后每年出生人口的调查表 H(key)=key +(-1949) 地址 1 … 51 年份 1949 1950 2000 人数

直接定址法 特点： 计算简单，并且不可能有冲突发生。 当关键字的分布基本连续时，可用直接定址法的哈希函数；否则，若关键字分布不连续将造成内存单元的大量浪费。

2. 除留余数法 用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希地址 除留余数法的哈希函数h(k)为： h(k)=k mod p (mod为求余运算,p≤m) p最好取小于等于m的质数(素数) 【例】以城市名的值作为自变量k，哈希表长度m=8，选用哈希函数：H(k)=ASC(LEFT(k,1)) mod 8 来计算结点的存储地址。 key Beijing Shanghai Wuhan Xian Nanjing ASC(key) 66 83 87 88 78 H(key) 2 3 7 6

城市哈希表 地址 城市名 区号 说明 Xian 029 陕西省省会 1 2 Beijing 010 首都 3 Shanghai 021 Xian 029 陕西省省会 1 2 Beijing 010 首都 3 Shanghai 021 直辖市 4 5 6 Nanjing 025 江苏省省会 7 Wuhan 027 湖北省省会

3. 数字分析法 提取关键字中取值较均匀的数字位作为哈希地址。 适合于所有关键字值都已知的情况，并需要对关键字中每一位的取值分布情况进行分析。 【例】一组关键字： {92317602,92326875,92739628,92343634,92706816,92774638,92381262,92394220} 每个关键字的第1、2、3位和第6位取值较集中，不宜作为哈希函数，剩余的第4、5、7和8位取值较分散,可根据实际需要取其中的若干位作为哈希地址。 若取最后两位作为哈希地址,则哈希地址的集合为{2,75,28,34,16,38,62,20}。

9.4.3 哈希冲突解决方法 解决冲突的实际含义： 1、开放定址法 哈希表的空闲单元既向同义词关键字开放，也向发生冲突的非同义词关键字开放。 9.4.3 哈希冲突解决方法 解决冲突的实际含义： 为产生冲突的关键字寻找下一个哈希地址。 1、开放定址法 哈希表的空闲单元既向同义词关键字开放，也向发生冲突的非同义词关键字开放。 2、拉链法 把所有的同义词用单链表链接起来。

开放定址法 (1)线性探查法 从发生冲突的地址(设为d)开始，依次探查d的下一个地址(当到达下标为m-1的哈希表表尾时，下一个探查的地址是表首地址0)，直到找到一个空闲单元为止(当m≥n时一定能找到一个空闲单元)。 数学递推描述公式为： d0=h(k) di=(di-1+1) mod m (1≤i≤m-1)

(2)平方探查法 设发生冲突的地址为d，则平方探查法的探查序列为：d+12,d+22,…。 数学描述公式为： d0=h(k) di=(d0+i2) mod m (1≤i≤m-1)

线性探查法示例 关键字集合 { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 若采用线性探查法处理冲突 1 2 3 4 5 6 7 8 9 10 55 01 23 14 68 11 82 36 19 1 1 2 1 3 6 2 5 1 ASLsucc＝（1＋1+2+1＋3+6+2+5+1）/9=22/9 ASLunsucc＝（10＋9+8+7+6+5+4+3+2+1+1）/11=56/11

2. 拉链法 拉链法把所有的同义词用单链表链接起来。 哈希表每个单元中存放的不再是记录本身，而是相应同义词单链表的头指针。  1 2  { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 表长为 7， H(key)=key MOD 7 1 2 3 4 5 6  14 36  01  23 ASLsucc =(6×1+2×2+3)/9=13/9  ASLunsucc＝（2＋3+2+1+2+4+2）/7=16/7  11  19 82 68  55

本章小结 (1) 理解查找的基本概念，包括静态查找表和动态查找表、内查找和外查找之间的差异。 (2) 重点掌握线性表上各种查找算法，包括顺序查找、二分查找和分块查找的基本思路、算法实现和查找效率等。 (3) 掌握各种树表的查找算法，包括二叉排序树和AVL树的基本思路、算法实现和查找效率等。 (4) 掌握哈希表查找技术。 (5) 灵活运用各种查找算法解决一些综合应用问题。

作 业 教材P285 练习题9 习题9.1、9.2

上 机 上机实验题9 P286 9.1、9.2 9.4（1）（2）（3）递归 86