第八章查找.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第八章查找,第八章 查找,8.1 静态查找表,8.1.1 顺序表的查找,8.1.2 有序表的查找,8.1.3 索引顺序表的查找,8.2 动态查找表,8.2.1 二叉树和平衡二叉树,8.2.2,B-,树和,B+,树的结构,8.3 哈希表,8.3.1 什么是哈希表,8.3.2 哈希函数的构造方法,8.3.3 冲突的处理方法,第八章查找,本章要点,掌握：静态搜索表的顺序搜索和折半搜索方法,掌握：二叉搜索树的表示、搜索、插入、删除算法及,性能分析,掌握：哈希表函数的构造方法,了解：哈希表冲突处理方法,“学生”表格,8.1查找的基本概念,1.查找表（,Search Table）,由,同一类型,的数据元素（或记录）构成的集合。,2.关键字（,Key）,数据元素（或记录）中某个数据项的值，用它可标识一,个数据元素（或记录）。,主,关键字（,Primary Key）：,可,唯一,标识一个记录的关键字。,次关键字（,Secondary Key）：,用以识别若干个记录的关键字。,3.查找（,Search）,根据给定的某个值或某种条件，在,查找表,中确定一个或多个,关键字,等于给定值或满足给定条件的数据元素（或记录）的操作。若表中存在这样的一个记录，则称查找成功，否则称查找失败。,关键字类型说明,typedeffloatKeyType；/,实型,typedefintKeyType；/,整型,typedefchar*KeyType；/,字符串型,数据元素类型定义,typedefstruct,KeyTypekey；/,关键字域,；/,其它域,ElemType；,两个关键字的比较约定,/,对数值型关键字,#defineEQ（a，b）（a）（b）,#defineLT（a，b）（a）（b）,#defineLQ（a，b）（a）（b）,/,对字符串型关键字,#defineEQ（a，b）（!,strcmp,（a），（b）,#defineLT（a，b）（,strcmp,（a），（b）0）,#defineLQ（a，b）（,strcmp,（a），（b）0）,8.2静态查找表,8.2.1无序表的查找,无序表：查找表中的结点是按关键字的,任意,顺序排列的。,顺序查找,（,Sequential Search）,：,从表中最后一个（或第一个）记录开始，逐个进行记录的关键字与给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直到第一个（或最后一个）记录，其关键字和给定值比较都不相等，则表明表中没有所查记录，查找失败。,顺序查找算法,（,P217,算法9.1,）,int Search_Seq（SSTable ST，KeyType,key,）,ST.elem,0,.key,key,；/,哨兵,for（iST.length；!EQ（ST.elemi.key，,key,）；,i）；,return i；,/Search_Seq,8.2.1无序表的查找,特点：,1）算法简单，适用面广,2）平均查找长度较大,3）在等概率情况下，,ASL（n1）/2,4）若各结点被查找的概率不相同，应先查找概,率高的结点,8.2.2有序表的查找,有序表,：查找表按,关键字有序,。,1.,折半查找（二分法查找）,设用,low,和,high,表示当前查找区间的,下界,和,上界,，,mid,为区间的,中间,位置。,折半查找步骤：,1）查找范围中间位置的数据元素的关键字,ST.elemmid,与给定值,key,相比较,2）若,ST.elemmidkey,，则查找成功。,若,ST.elemmidkey，,则在查找范围,low，mid-1,内继续查找,查找区间不存在时（即,lowhigh,），查找失败。,8.2.2有序表的查找,例,：在11个数据元素513192137566475808892中查找关键字为21和85的数据元素。,513192137566475808892,l m h,513192137566475808892,l m h,513192137566475808892,l,m h,513192137566475808892,l m h,513192137566475808892,l m h,513192137566475808892,l,m h,513192137566475808892,h l,8.2.2有序表的查找,特点：1）只适用于关键字有序的顺序存储结构,2）平均查找长度为,log,2,n（,满二叉树,P221）,3）最大比较次数为：,log,2,n,+1或,log,2,（n+1）,判定树：,描述查找过程的二叉树。,折半查找算法,（,P220,算法9.2,）,int Search_Bin（SSTable ST，KeyType,key,）,low1；highST.length；,while（low,data,比较,2）若,key=T-data，,则查找成功,若,keyT-data，,则继续在左子树中查找,若,keyT-data，,则继续在右子树中查找,二叉排序的查找（,P228,算法9.5（,a）,）,BiTree SearchBST（BiTree T，KeyType key）,if（!T）|（EQ（key，Tdata.key）return（T）；,elseifLT（key，Tdata.key）,return（SearchBST（Tlchild，key）；,else,return（SearchBST（Trchild，key）；,/SearchBST,如何将该算法转换成非递归？,8.3.1二叉排序树,例：,在图示的二叉排序树中查找关键字等于100的记录。,45,37,7,100,90,78,61,24,53,12,45,53,100,8.3.1二叉排序树,2.二叉排序树的插入,向二叉排序树中插入一个新元素，必须先检查这个元素是否在树中已经存在。,新插入的结点一定是一个新添加的,叶子,结点，并且是查,找不成功时查找路径上访问的最后一个结点的左孩子或,右孩子结点。,先使用查找算法在树中检查要插入元素是否存在。,查找成功:,树中已有这个元素，不再插入。,查找不成功:,树中原来没有关键字等于给定值的结点，把新元素加到查找操作停止的地方。,8.3.1二叉排序树,在二叉排序树中插入关键字为23和88的结点,二叉排序的查找（,P228,算法9.5（,b）,）,Status SearchBST（BiTree T，KeyType key，BiTree f，BiTree&p）,/,查找成功，,p,指向该数据元素结点，返回,TRUE，,否则,p,指向查找路径上访问,/的最后一个结点，返回,FALSE，f,指向,T,的双亲,if（!T）pf；return FALSE；,elseifEQ（key，Tdata.key）,pT；return TRUE；,elseifLT（key，Tdata.key）,return SearchBST（Tlchild，key，T，p）；,else,return SearchBST（Trchild，key，T，p）；,/SearchBST,二叉排序的插入（,P228,算法9.6,）,Status InsertBST（BiTree&T，ElemType e）,if（!,SearchBST,（T，e.key，NULL，p）,s（BiTree）malloc（sizeof（BiTNode）；,sdatae；slchildsrchildNULL；,if（!p）Ts；,elseifLT（e.key，pdata.key）,/p,指向查找路径上的最后一个结点。,plchilds；,elseprchilds；,return TRUE；,else return FALSE；,/InsertBST,输入数据，建立二叉排序树的过程,输入数据序列（8510169113724）,8.3.1二叉排序树,同样的数据，输入顺序不同，建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。,如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达到最大，这样必然会降低搜索性能。,例:,1,2,3,1,3,2,1,2,3,1,2,3,1,2,3,2,1,3,1,2,3 1,3,2 2,3,1 3,1,2 3,2,1,8.3.1二叉排序树,3.二叉排序树的删除,必须将因删除结点而断开的二叉链表重新链接起来，并确保仍是一棵二叉排序树。,防止重新链接后树的高度增加。,假设被删结点为*,p，,其双亲结点为*,f，,设*,p,是*,f,的右孩子。,8.3.1二叉排序树,（1）若*,p,结点为,叶结点,，只需修改其双亲结点的指针。,（2）若*,p,结点,只有左子树,（,或,右子树,）,H，,只需令,H,直接成为其双亲结点*,f,的右子树。,删除单链结点,F,P,8.3.1二叉排序树,（3）若*,p,结点的左子树和右子树均不空,2）令*,p,的右子树为*,f,的右子树，*,p,的左子树为,H,的左子树。,1）令*,p,的,中序,直接后继,H（,或直接前驱）替代*,p，,然后再从二叉排序树中删除*,p,的中序直接后继,H（,或直接前驱）。,删除结点80,，,令*,p,的,中序,直接后继,H（,或直接前驱）的值替代*,p,的值，然后再从二叉排序树中删除*,p,的中序直接后继,H,。,64,13,80,05,56,75,92,37,19,21,88,64,13,88,05,56,75,92,37,19,21,64,56,37,P,H,寻找左子树的最大结点或右子树中的最小结点。,删除结点80，,令*,p,的右子树为*,f,的右子树，*,p,的左子树为,H,的左子树。,64,13,80,05,56,75,92,37,19,88,P,H,f,75,64,13,92,05,56,37,19,21,64,56,37,88,21,二叉排序树删除算法（,P230,算法9.7,）,Status DeleteBST（BiTree&T，KeyType key）,if（!T）return FALSE；,else,ifEQ（key，Tdata.key）,return delete（T）；,elseifLT（key，Tdata.key）,return DeleteBST（Tlchild，key）；,elsereturn DeleteBST（Trchild，key）；,return TRUE；,/DeleteBST,二叉排序树删除算法（,P230,算法9.8,）,void Delete（BiTree&p）,if（!prchild）qp；pplchild；free（q）；,elseif（!plchild）,qp；pprchild；free（q）；,else,/,左右子树均不为空,qp；splchild；,while（srchild）qs；ssrchild；,/找,p,的直接前驱,pdatasdata；,/s,指向,p,的直接前驱,if（q!p）qrchildslchild；,/,重接*,q,的,右,子树,elseqlchildslchild；,/,当,p,的左孩子是其直接前驱时，,重接*,q,的,左,子树,free(s)；,/,教材上漏了，补上！,/Delete,8.3.1二叉排序树,4.二叉排序树的查找分析,两棵不同形态的二叉排序树,ASL(a)=（1+2*2+3*4）/7=17/7ASL(b)=（1+2+3+4+5+6+7）/7=28/7,8.3.1二叉排序树,设二叉排序树的深度为,n，,最差情况下，平均查找长度（,n1）/2,（,顺序查找）,最好情况下，平均查找长度与,log,2,n,成正比,（折半情况）,一般情况下，平均查找长度与,logn,等数量级,8.3.2平衡二叉树,一、平衡二叉树,（,Balanced Binary Tree，,也称,AVL,树）,平衡因子,BF,：,结点的左子树的深度减去它的右子树的,深度。,平衡二叉树上所有结点的平衡因子只可能是1、0、1。,若有一个结点的平衡因子的绝对值大于1，则该二叉树是不平衡的。,平衡二叉树：,一棵空树，或者它的,左,子树和,右,子树都是平衡二叉树，且左子树和右子树的深度之差,绝对值,不超过,1,。,8.3.2平衡二叉树,-1,0,0,1,0,-2,0,2,1,0,0,0,-1,1,0,0,1,8.3.2平衡二叉树,非平衡二叉树,平衡二叉树,平衡树的生成过程,0,13,0,24,-1,13,0,37,0,13,0,24,-1,24,-2,13,0,37,-2,37,0,13,-2,24,1,90,0,53,90,37,24,53,13,0,53,0,13,-1,24,0,90,0,37,关键字序列：1324379053,左旋转,右旋转,左旋转,8.3.2平衡二叉树,设在二叉排序树上插入新结点而失去平衡的,最小子树根结点,的指针为,a，,则二叉排序树调整的规律如下：,1.单向右旋平衡处理（左倾斜）,在*,a,的左子树根结点的左子树上插入结点，使*,a,的平衡因子由1增到2，则需进行一次向右的顺时针旋转操作。,1,B,2,A,B,L,h,B,R,h-1,A,R,h-1,0,A,0,B,A,R,h-1,B,R,h-1,B,L,h,0,1,8.3.2平衡二叉树,2.单向左旋平衡处理（右倾斜）,在*,a,的右子树根结点的右子树上插入结点，使*,a,的平衡因子由1变为2，则需进行一次向左的逆时针旋转操作。,0,A,0,B,A,L,h-1,B,L,h-1,B,R,h,-1,B,-2,A,B,R,h,B,L,h-1,A,L,h-1,0,-1,8.3.2平衡二叉树,3.双向旋转（先左后右）平衡处理,在*,a,的,左,子树根结点的,右,子树上插入结点，使*,a,的平衡因子由1增为2，则需进行两次旋转操作（先左后右）。,1,B,2,A,C,L,h-1,C,R,h-2,A,R,h-1,1,C,B,L,h-1,1,A,0,C,A,R,h-1,C,R,h-2,B,L,h-1,0,B,C,L,h-1,0,0,1,1,B,2,A,C,L,h-1,C,R,h-2,A,R,h-1,1,C,B,L,h-1,C,A,C,L,h-1,C,R,h-2,A,R,h-1,B,B,L,h-1,B,逆时针向左,1,A,0,C,A,R,h-1,C,R,h-2,B,L,h-1,0,B,C,L,h-1,A,顺时针向右,8.3.2平衡二叉树,4.双向旋转（先右后左）平衡处理,在*,a,的,右,子树根结点的,左,子树上插入结点，使*,a,的平衡因子由1变为2，则需进行两次旋转操作（先右后左）。,1,B,0,C,B,R,h-1,C,R,h-2,A,L,h-1,0,A,C,L,h-1,1,B,2,A,C,R,h-2,C,L,h-1,A,L,h-1,1,C,B,R,h-1,0,0,-1,B,顺时针向右,A,逆时针向左,1,B,2,A,C,R,h-2,A,L,h-1,1,C,B,R,h-1,C,L,h-1,A,L,h-1,C,C,R,h-2,B,B,L,h-1,C,L,h-1,A,1,B,0,C,B,R,h-1,C,R,h-2,A,L,h-1,0,A,C,L,h-1,8.3.2平衡二叉树,二、平衡二叉树的插入,1.若,BBST,为空，则插入一个数据元素为,e,的新结点作为根结点，树的深度增加1。,2.若,e,的关键字值与根结点的关键字相等，则不进行插入。,3.若,e,的关键字值小于根结点的关键字，且在,BBST,左子树中,无,与,e,的关键字值相等的结点，则将,e,插入在,BBST,的左子树上。,当插入后，左子树的深度增加1时,1）,BBST,的根结点的平衡因子为1，则将其改为0，,BBST,的深度不变,2）,BBST,的根结点的平衡因子为0，则将其改为1，,BBST,的深度加1,8.3.2平衡二叉树,3）,BBST,根结点的平衡因子为,1,，,若,BBST,左子树,根,结点的平衡因子为,1,，则进行右旋操,作。操作完成后，根结点和其右子树根结点的平衡因子,改为0，树的深度不变。,若,BBST,左子树,根,结点的平衡因子为,1,，则进行先左,后右的双向旋转操作。操作完成后，修改根结点及其左、,右子树根结点的平衡因子，树的深度不变。,4.若,e,的关键字值大于根结点的关键字，且在,BBST,的右子树中无与,e,的关键字值相等的结点，则将,e,插入在,BBST,的右子树上。,当插入后，右子树的深度增加1时,算法实现：,P236,算法9.9-9.12,8.3.2平衡二叉树,三、平衡树的查找分析（,P238）,N,h,表示深度为,h,的平衡树中含有的最小结点数，有,N,0,0N,1,1N,2,2,N,h,N,h-1,N,h-2,1,与斐波那契序列相似！,在平衡树上进行查找的时间复杂度为,O（logn）。,8.3.3,B-,树和,B+,树,8.3.3.1,B-,树及其查找,1.,B-,树的,定义,B-,树是一种平衡的,多路查找树,，它在文件系统中很有用。,一棵,m,阶的,B-,树，或为空树，或为满足下列特性的,m,叉树：,（,1,）树中每个结点,至多,有,m,棵子树；,（,2,）若根结点不是叶子结点，则,至少,有两棵子树；,（,3,）除,根,结点之外的所有非终端结点,至少,有,m/2,棵子树；,（,4,）所有的非终端点结点中包括下列信息数据,（,n,A,0,K,1,A,1,K,2,K,n,A,n,）,其中：,K,i,(i=1，n),为关键字，且,K,i,keynum;i=Search(p,k);,/,在,p-key1.n,中查找,/,使得,p-keyiK p-keyi+1,if(i0,else q=p;p=p-ptri;,if(found)return(p,i,l);,else return(q,i,0);,4.B-,树查找分析,B-,树上进行查找包含两种基本操作,:,（1）,在,B-,树中找结点；,（2,）在指定结点中找关键字。,由于,B-,树通常存储在,磁盘,上，则前一查找操作是在磁盘上进行的，而在指定结点中找关键字是在内存中进行的，即在磁盘上找到指针,p,所指结点后，先将结点中的信息读入内存，然后再利用顺序查找或折半查找查询等于,k,的关键字。显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多，因此，在磁盘上进行查找的次数、即待查关键字所在结点在,B-,树上的层次数，是决定,B-,树查找效率的首要因素。,8.3.3,B-,树和,B+,树,5.B-,树的插入与删除,（1）插入操作,若插入后结点的关键字个数,m-1,则插入操作完成，否则需要对该结点进行分裂。分裂的过程是一个从下向上对所有发生变化的、且不满足,B-,树条件的结点进行循环分解的过程。,若,p,结点已有,m-1,个关键字，在,p,中插入一个新的关键字时，需要对,P,进行分裂，假设分裂为,p,和*,p,两个结点，则分裂后的,p,结点中包含,p,结点中的前,m/2,-1,个关键字，而*,p,中包含分割点后 的,m-m/2,个关键字，并将,K,m/2,提升到其父亲结点中。,45,24,53 90,3 12,37,50,61 70,100,a,b,c,d,e,f,g,h,bt,插入关键字30,45,24,53 90,3 12,30 37,50,61 70,100,a,b,c,d,e,f,g,h,bt,（,a）,（,b）,注：图（,a）,为一棵,m=3,的平衡二叉树,在图（,b）,上插入关键字26,45,24,53 90,3 12,30 37,50,61 70,100,a,b,c,d,e,f,g,h,bt,45,24,53 90,26 30 37,53,61 70,100,a,b,c,d,e,f,g,h,bt,3 12,分裂,插入26,45,24 30,53 90,53,61 70,100,a,b,c,d,e,f,g,h,bt,3 12,26,37,d*,（,b）,（,d）,（,c）,（2）删除操作,首先在,B-,中找到要删除的关键字，然后进行删除操作。在最下层的非终端结点中删除一个关键字有以下三种情况,：,若关键字所在的结点为最下层的非终端结点，且其中的关键字个数不少于,m/2,，,则删除完成，否则需要进行结点的合并。,若被删除关键字结点中关键字个数等于,m/2,-1,，而其相邻的右兄弟（或左兄弟）结点中的关键字个数大于,m/2,-1,，则应将其兄弟结点中的最小（或最大）关键字,上,移至其双亲结点中，而将双亲结点中小于（或大于）且紧靠该该,上,移关键字的关键字,下,移至被删除关键字中。,若被删除关键字结点和其相邻的兄弟结点中的关键字个数都等于,m/2,-1,。假设,该结点有右兄弟，且其指针由其双亲结点中的,A,i,指针指示，则删除该关键字后，它所在结点中剩余的关键字和指针与其双亲结点中的关键字,K,i,一起合并到其兄弟结点中（若没有右兄弟，则合并到左兄弟结点中）。若导致其双亲结点的关键字个数小于,m/2,-1,，则需要继续合并。,8.3.3,B-,树和,B+,树,45,24,53 90,3,12,37,50,61 70,100,a,b,c,d,e,f,g,h,bt,删除12,45,24,53 90,3,37,50,61 70,100,a,b,c,d,e,f,g,h,bt,第一种情况：,删除50,45,24,53 90,3 12,37,50,61 70,100,a,b,c,d,e,f,g,h,bt,45,24,61 90,3 12,37,53,70,100,a,b,c,d,e,f,g,h,bt,第二种情况：,第三种情况：,45,24,61 90,3 12,37,53,70,100,a,b,c,d,e,f,g,h,bt,删除53,45,24,90,3 12,37,61 70,100,a,b,c,d,e,g,h,bt,问题：如何删除非最下层的结点中的关键字呢？,p245,8.3.3.2,B+,树,1.,B+,树的 定义,B,+,树是应,文件系统,所需而出的一种,B-,树的变型树。一棵,m,阶的,B,+,树是一棵的,m,路,平衡索引树。,m,阶的,B,+,树和,m,阶的,B-,树的差异在于：,（1）有,n,棵子树的结点中含有,n,个关键字；,（2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小,自小而大,的顺序链接；,（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的,最大,（或,最小,）关键字。,8.3.3 B-树和B+树,8.3.3,B-,树和,B+,树,10 15,59 97,21 37 44,51 59,63 72,85 91 97,15 44 59,72 97,root,sqt,一棵三阶的,B,+,树,2.,B,+,树的 查找,在,B,+,树上进行随机查找、插入和删除的过程基本上与,B-,树类似，只是在查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点，因此，在,B,+,树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。,m,阶,B+,8.3.3 B-树和B+树,8.4哈希表,8.4.1哈希表（散列表）,哈希（,Hash）,函数,：在记录的存储位置和它的关键字之,间建立的一个确定的对应关系,f，,使每个关键字和一个唯,一的存储位置相对应,。,例1,：,某储蓄所的储户帐号表。,存储地址,储户帐号,存款余额,9001,345-6978-549001,56，340.00,9002,345-6978-549002,6，789.00,9003,345-6978-549003,762，300.00,9004,345-6978-549004,2，300.00,9004,345-6978-549005,0,H（k）,储户帐号的最末4位数,99003,李 军 男 ,99002,王 民 男 ,99001,张 云 女 ,99004,汪 敏 女 ,99030,刘小春 男 ,学 号 姓名 性别,1,2,3,4,:,:,30,1：30,H(k)=“,将组成关键字,k,的串,转换为一个,1,30,之,间的代码”,H(,张云,)=2,H(,王民,)=4,H(,李军,)=1,H(,汪敏,)=,4,张 云,王 民,李 军,汪 敏,例2,8.4.1哈希表（散列表）,根据设定的,哈希函数,H（key）,和,处理冲突的方法,将一组关键字映象到一个,有限的连续的地址集,（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置。用这种方式所得到的查找表就称为,哈希表,。,散列,：映象过程(根据关键字确定存储位置的过程,)，,也称为哈希造表。,散列地址（哈希地址）,：由哈希函数所得到的存储位置。,冲突（,collision）,：,对不同的关键字可能得到同一哈希地址，即,key1key2，,而,H（key1）H（key2）。,同义词,：具有相同函数值的关键字。,8.4.2哈希函数的构造方法,一个好的哈希函数应该使得哈希函数的,值均匀地分布,在存储空间的有效地址范围内，从减少发生冲突的机会。,常用的构造哈希函数的方法：,1.直接定址法,取关键字或关键字的某个,线性,函数值为哈希地址，即,H（key）key,或,a*key+b,其中,a,和,b,为常数。,8.4.2哈希函数的构造方法,2.数字分析法,假设关键字是以,r,为基的数，并且哈希表中可能出现的关键字是已知的，则取关键字的若干数位组成哈希地址。,使用该方法，一般要求熟悉关键字各位的分布情况。,8.4.2哈希函数的构造方法,例,：有80个记录，其关键字为8位十进制数。假设哈希表的表长为100,10,，则可取两个十进制数字组成哈希地址。,81346532,81372242,81387422,81301367,81322817,81338967,81354157,81368537,81419355,81346532,81372242,81387422,81301367,81322817,81338967,81354157,81368537,81419355,8.4.2哈希函数的构造方法,3.平方取中法,取关键字平方后的中间几位为哈希地址。取的位数由,表长,决定。,key,key,2,H（key）,1101,1,212,201,212,1102,1,214,404,214,1200,1,440,000,440,2031,4,124,961,124,2134,4,553,956,553,例：,8.4.2哈希函数的构造方法,4.折叠法,将关键字分割成位数相同的几部分（最后一部分的位数可不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。,98765,4321,103086,H（key）3086,移位叠加,98765,1234,99999,H（key）9999,间界叠加,例,：关键字,key987654321，,把它转换为一个4位的散列地址。,常用在关键字位数多，而每一位上数字的分布又基本均匀的情况下。,8.4.2哈希函数的构造方法,5.除留余数法,取关键字被某个,不大于,哈希表,表长,m,的数,p,除后所得,余数,为哈希地址。,H（key）keyMODp,其中，应该取,p,为不大于表长的,最大素数,。,Key,H（key）keyMOD997,11052344,599,12051282,543,25341272,523,48765210,943,例：,8.4.2哈希函数的构造方法,6.,随机数法,选择一个随机函数，取关键字的随机函数值为它的哈希地址。,H（key）random（key），,其中，,random,为随机函数。,选取哈希函数时考虑的因素：,1）计算哈希函数所需时间,2）关键字的长度,3）哈希表的大小,4）关键字的分布情况,5）记录的查找频率,8.4.3冲突的处理方法,选择合适的哈希函数，使用较大的哈希表可减少冲突，但不能避免冲突。,处理冲突,：为产生冲突的关键字对应的记录找到一个,空,的哈希地址,H,i,。,8.4.3冲突的处理方法,常用的处理冲突的方法：,1.开放地址法,H,i,（,H（key）,d,i,）MODm,其中，,H（key）,为哈希函数，,m,为哈希表表长，,d,i,为增量序列。,线性再散列,：,d,i,1,2，,，,m1,二次探测再散列,：,d,i,1,2,，1,2,，2,2,，2,2,，,，,k,2,k,m/2,伪随机探测再散列,：,d,i,伪随机数序列,例,：关键字序列为17602938，哈希表长度为11，哈希函数为,H（key）key MOD 11，,用开放地址法处理冲突。,60,17,29,0,1,2,3,4,5,6,7,8,9,10,H,1,（51）MOD116,H,2,（52）MOD117,H,3,（53）MOD118,60,17,29,38,0,1,2,3,4,5,6,7,8,9,10,线性探测再散列法,38,60,17,29,0,1,2,3,4,5,6,7,8,9,10,二次探测再散列法,H,1,（51）MOD116,H,2,（51）MOD114,38,60,17,29,0,1,2,3,4,5,6,7,8,9,10,伪随机探测再散列法,H,1,（59）MOD113,H（38）5,8.4.3冲突的处理方法,2.再哈希法,H,i,RH,i,（key）i1，2，,，k,RH,i,是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生为止。,3.链地址法,将所有关键字为同义词的记录存储在同一线性链表中，另用一个数组存储各链表的链头指针。,凡哈希地址为,i,的记录都插入到头指针为,ChainHashi,的链表中。,例,：已知一组关键字为（191423016820842755111079），哈希表长为13，则按哈希函数,H（key）key MOD 13,和链地址法处理冲突构造哈希表。,0,1,2,3,4,5,6,7,8,9,10,11,12,14,01,27,79,68,55,19,84,20,23,10,11,8.4.3冲突的处理方法,4.溢出区法,另建一个溢出区专门用来存放同义词。所有关键字和基本表中关键字为同义词的记录，不管它们的哈希地址是什么，一旦发生冲突，都填入溢出区。,8.4.4哈希表的查找及分析,哈希表的查找步骤：,1）由哈希函数计算给定,Key,的哈希地址,H（key）,2）若哈希表中此位置上无记录，则查找失败,否则比较关键字，若和给定,Key,值相同，则查找成功,否则根据设定的冲突处理方法找下一,地址，直到哈希表中某个位置为,“空”或表中所填记录的关键字值,等于给定,key,值。,算法实现：,P259,算法9.179.18,哈希表的查找过程和建表过程是一致的。,假设哈希函数为,Hash(x)，,则查找过程为（开放地址法）：对给定值,kval，,求得哈希地址为,j=Hash(kval)，,若哈希表中下标为,j,的分量为空，则查找不成功，将关键字等于,kval,的记录填入，若表中该分量不空且所填记录的关键字等于,kval，,则查找成功，否则按散列方法计算新的哈希地址，直至表中相应分量为空或所填记录的关键字等于,kval。,若利用链地址法处理冲突,，则查找过程更简单，只要在和哈希地址对应的链表中进行顺序查找即可，若该链表为“空”或链表中不存在关健字等于给定值的结点，则查找不成功，否则找到该待查记录结点。,8.4.4哈希表的查找及分析,开放地址法的哈希表的存储结构,int,hashsize=997,;,typedef struct,ElemType*elem;,int,count;,int,sizeindex;,HashTable;,const,SUCCESS=1;,const,UNSUCCESS=0;,const,DUPLICATE=-1;,8.4.4哈希表的查找及分析,Status,SearchHash(HashTable H,KeyType kval,int,&p,int,&c),/,在开放定址哈希表,H,中查找关键码为,kval,的元素，若成功，/以,p,指示待查记录在表中位置，并返回,SUCCESS；/,否则，以,p,指示插入位置并返回/,UNSUCCESS ，c,用以计冲突次数，其初值置零，供建表插入时参考,p=Hash(kval);,/,求得哈希地址,while,(H.elemp.key!=NULLKEY&(H.elemp.key!=kval),/,该位置中填有记录,并且关键字不相等,collision(p,+c);,/,求得下一探查地址,p,if,(H.elemp.key=kval),return,SUCCESS;,/,查找成功，,p,返回待查记录位置,else,return,UNSUCCESS;,/,不成功,H.elemp.key=NULLKEY),/SearchHash,8.4.4哈希表的查找及分析,Status,InsertHash(HashTable&H,Elemtype e),/,若开放定址表,H,中不存在记录,e,时则进行插入，并返回,OK；,/,若在查找过程中发现冲突次数过大，则需重建哈希表,c=0;,if,(HashSearch(H,e.key,j,c)=SUCCESS),return,DUPLICATE;,/,表中已有与,e,有相同关键字的记录,else if,(chashsizeH.sizeindex/2),/,冲突次数,c,未达到上限，(阀值,c,可调),H.elemj=e;+H.count;,return,OK;,/,插入记录,e,else,RecreateHashTable(H);,/,重建哈希表,/,InsertHash,8.4.4哈希表的查找及分析,哈希表的查找性能分析,平均查找长度,ASL,是衡量哈希表查找性能的重要指标。,8.4.4哈希表的查找及分析,平均查找长度取决于三个因素：,哈希函数,、,处理冲突的方法,和哈希表的,装填因子,。,装填因子,表中填入的记录数,哈希表的长度,8.4.4哈希表的查找及分析,一般情况下，处理冲突方法相同的哈希表，其平均查找长度主要依赖于哈希表的,装填因子,，不同冲突处理方法的平均查找长度如下表所示：,处理冲突的方法,成功查找的平均查找长度,线性探测法,伪随机探测，二次探测和再哈希法,链地址法,例,：关键字序列（191423016820842755111079），哈希表长为13，哈希函数,H（key）key MOD 13。,0,1,2,3,4,5,6,7,8,9,10,11,12,14,01,27,79,68,55,19,84,20,23,10,11,链地址法处理冲突,ASL（162434）/121.75,55,19,20,84,79,23,11,10,0,1,2,3,4,5,6,7,8,9,10,14,01,68,27,11,12,13,14,15,线性探测再散列法处理冲突,ASL（162+3349）/122.5,1.假设按下述递归方法进行顺序表的查找：若表长10进行顺序查找，否则进行折半查找。试画出对表长,n=50,的顺序表进行查找时，描述该查找过程的判定树，并求出在等概率 的情况下查找成功的平均查找长度。,2.试从树开始，画出按以下次序向3阶,B-,树（2-3树）中插入关键码的建树过程：20，30，50，52，60，68，70.并画出删除50和68每一步执行后,B-,树的状态。,3.在地址空间为016的散列区中，根据给出的关键字序列构造两个哈希表(,Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）.,(1),用线性探测开放定址法处理冲突,(2)用链地址法处理冲突,哈希函数设为,H(x)=i/2,，,其中,i,为关键字中第,一,个字母在字母表中的序号。,4.（,选做题,）已知含有100个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。,作业8,