第八章查找.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）根据给定的某个值或某种条件，在查找表中确定一个或多个关键字等于给定值或满足给定条件的数据元素（或记录）的操作。若表中存在这样的一个记录，则称查找成功，否则称查找失败。,8.1查找的基本概念,4.静态查找 对查找表只查询特定数据元素是否在表中或查询特定元素的各种属性，不对查找表作任何修改。,5.动态查找修改查找表。表结构本身是在查找过程中动态生成的，通常是查找不成功则将该元素插入到查找表中；如果存在，可能需要从表中删除它。,8.1查找的基本概念,6.平均查找长度（衡量查找算法好坏的一个重要指标）查找过程中，和给定值进行比较的关键字个数的期望值。,其中，Pi为查找表中第i个记录的概率，且,Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。,对于含有n个记录的表，查找成功时的平均查找长度为,关键字类型说明typedeffloatKeyType；/实型typedefintKeyType；/整型typedefchar*KeyType；/字符串型数据元素类型定义typedefstructKeyTypekey；/关键字域；/其它域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.elem0.keykey；/哨兵for（iST.length；!EQ（ST.elemi.key，key）；i）；return i；/Search_Seq,8.2.1无序表的查找,特点：1）算法简单，适用面广2）平均查找长度较大3）在等概率情况下，ASL（n1）/24）若各结点被查找的概率不相同，应先查找概 率高的结点,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的数据元素。,513192137566475808892l m h,513192137566475808892l m h,513192137566475808892 l,m h,513192137566475808892l m h,513192137566475808892 l m h,513192137566475808892 l,m h,513192137566475808892 h l,8.2.2有序表的查找,特点：1）只适用于关键字有序的顺序存储结构2）平均查找长度为log2n（满二叉树P221）3）最大比较次数为：log2n+1或 log2（n+1）,判定树：描述查找过程的二叉树。,折半查找算法（P220算法9.2）,int Search_Bin（SSTable ST，KeyType key）low1；highST.length；while（lowhigh）mid（low+high）/2；ifEQ（key，ST.elemmid.key）return mid；elseif LT（key，ST.elemmid.key）highmid1；else lowmid+1；return 0；/Search_Bin,8.2.2有序表的查找,2.斐波那契查找,根据斐波那契序列的特点来对表进行划分：F0=0，F1=1，Fi=Fi-1+F i-2,斐波那契查找步骤：假设开始时，表中结点数目比某个斐波那契数小1，即n=Fu1。1）将ST.elemFu-1 与 key相比较2）若ST.elemFu-1=key，则查找成功。若ST.elemFu-1 key，则在 Fu-11，Fu1 内继续查找。若ST.elemFu-1 key，则在 1，Fu-1 1 内继续查找。若查找区间不存在，则查找失败。,特点：1）平均性能较好，但最坏情况比折半查找差2）算法中只有加、减运算,8.2.2有序表的查找,3.插值查找 用插值的方法计算出一个与给定值比较的元素下标,i=,其中，ST.eleml、ST.elemh 分别为有序表中具有最 小关键字和最大关键字的记录。,8.2.2有序表的查找,插值查找步骤：根据key与ST.elemi.key的比较结果，修改查找区间的上界、下界，重复进行，直到查找成功，或查找区间不存在，则查找失败。,特点：1）只适用于关键字均匀分布的表2）对表长较大的顺序表，其平均性能比折半查找好,8.2.3索引顺序表的查找,索引顺序表查找（也称分块查找）：,索引顺序表查找步骤：1.确定要查找的数据元素在表中的哪一块2.在确定的块中查找数据元素,1）表中的数据元素被分为若干块，每块中的数据元素可 以任意存放，但块与块之间的数据元素的关键字值是 有序的。,2）建立一个索引表，该索引表的数据元素个数等于查找 表被分割的块数，即查找表中的每一块对应索引表中 的一个索引项。在索引项中存放对应块的最大关键字 值和该块的起始位置。,8.2.3 索引顺序表的查找,例：在查找表中查找key65和key111的数据元素。,8.2.3索引顺序表的查找,索引表按关键字有序，可以利用顺序查找，也可用折半查找。块中数据元素是任意存放的，则在块中只能是顺序查找。,其中，n为查找表的长度，s为查找表分成的每一块中的数据元素个数。,当用顺序查找确定记录的所在块，则分块查找的平均查找长度（参考P226）：,当用折半查找确定记录的所在块（即索引表用折半查找），则：,8.3动态查找表,8.3.1二叉排序树(查找树或搜索树),1.二叉排序树（Binary Sort Tree）,对二叉排序树进行中序遍历，可以按从小到大的顺序，将各结点关键字排列起来。,二叉排序树是一棵空树或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树分别为二叉排序树。,8.3.1二叉排序树,二叉排序树的查找步骤：当二叉排序树T不空时，1）将给定值key与根结点的关键字T-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）；elsereturn（SearchBST（Trchild，key）；/SearchBST,如何将该算法转换成非递归？,8.3.1二叉排序树,例：在图示的二叉排序树中查找关键字等于100的记录。,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二叉排序树,同样的数据，输入顺序不同，建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达到最大，这样必然会降低搜索性能。,例:,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的右子树。,删除单链结点,8.3.1二叉排序树,（3）若*p结点的左子树和右子树均不空,2）令*p的右子树为*f的右子树，*p的左子树为H的左子树。,1）令*p的中序直接后继H（或直接前驱）替代*p，然后再从二叉排序树中删除*p的中序直接后继H（或直接前驱）。,删除结点80，令*p的中序直接后继H（或直接前驱）的值替代*p的值，然后再从二叉排序树中删除*p的中序直接后继H。,P,H,寻找左子树的最大结点或右子树中的最小结点。,删除结点80，令*p的右子树为*f的右子树，*p的左子树为H的左子树。,P,H,f,二叉排序树删除算法（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（顺序查找）最好情况下，平均查找长度与log2n成正比（折半情况）一般情况下，平均查找长度与logn等数量级,8.3.2平衡二叉树,一、平衡二叉树（Balanced Binary Tree，也称AVL树）,平衡因子BF：结点的左子树的深度减去它的右子树的 深度。,平衡二叉树上所有结点的平衡因子只可能是1、0、1。若有一个结点的平衡因子的绝对值大于1，则该二叉树是不平衡的。,平衡二叉树：一棵空树，或者它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差绝对值不超过1。,8.3.2平衡二叉树,8.3.2平衡二叉树,非平衡二叉树,平衡二叉树,平衡树的生成过程,013,关键字序列：1324379053,左旋转,右旋转,左旋转,8.3.2平衡二叉树,设在二叉排序树上插入新结点而失去平衡的最小子树根结点的指针为a，则二叉排序树调整的规律如下：1.单向右旋平衡处理（左倾斜）在*a的左子树根结点的左子树上插入结点，使*a的平衡因子由1增到2，则需进行一次向右的顺时针旋转操作。,0,1,8.3.2平衡二叉树,2.单向左旋平衡处理（右倾斜）在*a的右子树根结点的右子树上插入结点，使*a的平衡因子由1变为2，则需进行一次向左的逆时针旋转操作。,0,-1,8.3.2平衡二叉树,3.双向旋转（先左后右）平衡处理 在*a的左子树根结点的右子树上插入结点，使*a的平衡因子由1增为2，则需进行两次旋转操作（先左后右）。,0,0,1,8.3.2平衡二叉树,4.双向旋转（先右后左）平衡处理 在*a的右子树根结点的左子树上插入结点，使*a的平衡因子由1变为2，则需进行两次旋转操作（先右后左）。,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）Nh表示深度为h的平衡树中含有的最小结点数，有N00N11N22NhNh-1Nh-21,与斐波那契序列相似！在平衡树上进行查找的时间复杂度为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,A0,K1,A1,K2,Kn,An,）其中：Ki(i=1，n)为关键字，且KiKi+1(i=0，n-1);Ai(i=1，n)为指向子树根节点的指针，且指针Ai-1 所指子树中所有节点的关键字均小于Ki(i=1，n)，An 所指子树中所有节点的关键字均大于Kn，n(m/2-1nm-1)为关键字的个数（或n+1为子树个数）。（5）所有的叶子节点都出现在同一层次上，并且不带信息。,8.3.3 B-树和B+树,查找23,查找53,查找成功,查找失败,4阶B-树,8.3.3 B-树和B+树,2.B-树的存储结构B-树主要用作文件的索引，因此它的查找涉及外存的存取。const m=3;typedef struct BTNode int keynum;/结点中关键字的个数 struct BTNode*parent;KeyType keym+1;/关键字向量，0号单元未用 struct BTNode*ptrm+1;/子树指针向量 Record*recptrm+1;/记录指针向量，0号单元未用BTNode,*Btree;typedef struct BTNode*pt;/指向找到的结点 int i;/在结点中的关键字序号 int tag;/查找成功的标志Result;/查找结果类型,3.B-树的查找算法 Result SearchBTree(Btree T,KeyType K)p=T;q=NULL;found=FALSE;i=0;while(p,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 个关键字，并将Km/2提升到其父亲结点中。,插入关键字30,（a）,（b）,注：图（a）为一棵m=3的平衡二叉树,在图（b）上插入关键字26,分裂,插入26,（b）,（d）,（c）,（2）删除操作首先在B-中找到要删除的关键字，然后进行删除操作。在最下层的非终端结点中删除一个关键字有以下三种情况：若关键字所在的结点为最下层的非终端结点，且其中的关键字个数不少于 m/2，则删除完成，否则需要进行结点的合并。若被删除关键字结点中关键字个数等于m/2-1，而其相邻的右兄弟（或左兄弟）结点中的关键字个数大于m/2-1，则应将其兄弟结点中的最小（或最大）关键字上移至其双亲结点中，而将双亲结点中小于（或大于）且紧靠该该上移关键字的关键字下移至被删除关键字中。若被删除关键字结点和其相邻的兄弟结点中的关键字个数都等于m/2-1。假设该结点有右兄弟，且其指针由其双亲结点中的Ai指针指示，则删除该关键字后，它所在结点中剩余的关键字和指针与其双亲结点中的关键字Ki一起合并到其兄弟结点中（若没有右兄弟，则合并到左兄弟结点中）。若导致其双亲结点的关键字个数小于m/2-1，则需要继续合并。,8.3.3 B-树和B+树,删除12,第一种情况：,删除50,第二种情况：,第三种情况：,删除53,问题：如何删除非最下层的结点中的关键字呢？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+树,一棵三阶的B+树,2.B+树的 查找在B+树上进行随机查找、插入和删除的过程基本上与B-树类似，只是在查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点，因此，在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。m阶B+,8.3.3 B-树和B+树,8.4哈希表,8.4.1哈希表（散列表）,哈希（Hash）函数：在记录的存储位置和它的关键字之间建立的一个确定的对应关系f，使每个关键字和一个唯一的存储位置相对应。,例1：某储蓄所的储户帐号表。,H（k）储户帐号的最末4位数,1：30 H(k)=“将组成关键字k 的串 转换为一个130之 间的代码”,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位十进制数。假设哈希表的表长为10010，则可取两个十进制数字组成哈希地址。,813465328137224281387422813013678132281781338967813541578136853781419355,813465328137224281387422813013678132281781338967813541578136853781419355,8.4.2哈希函数的构造方法,3.平方取中法取关键字平方后的中间几位为哈希地址。取的位数由表长决定。,例：,8.4.2哈希函数的构造方法,4.折叠法将关键字分割成位数相同的几部分（最后一部分的位数可不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。,98765 4321 103086H（key）3086 移位叠加,98765 1234 99999 H（key）9999间界叠加,例：关键字key987654321，把它转换为一个4位的散列地址。,常用在关键字位数多，而每一位上数字的分布又基本均匀的情况下。,8.4.2哈希函数的构造方法,5.除留余数法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H（key）keyMODp其中，应该取p为不大于表长的最大素数。,例：,8.4.2哈希函数的构造方法,6.随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址。H（key）random（key），其中，random为随机函数。,选取哈希函数时考虑的因素：1）计算哈希函数所需时间2）关键字的长度3）哈希表的大小4）关键字的分布情况5）记录的查找频率,8.4.3冲突的处理方法,选择合适的哈希函数，使用较大的哈希表可减少冲突，但不能避免冲突。,处理冲突：为产生冲突的关键字对应的记录找到一个空的哈希地址Hi。,8.4.3冲突的处理方法,常用的处理冲突的方法：,1.开放地址法Hi（H（key）di）MODm其中，H（key）为哈希函数，m为哈希表表长，di为增量序列。,线性再散列：di1,2，m1二次探测再散列：di12，12，22，22，k2 k m/2 伪随机探测再散列：di伪随机数序列,例：关键字序列为17602938，哈希表长度为11，哈希函数为H（key）key MOD 11，用开放地址法处理冲突。,H（38）5,8.4.3冲突的处理方法,2.再哈希法HiRHi（key）i1，2，k RHi是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生为止。,3.链地址法将所有关键字为同义词的记录存储在同一线性链表中，另用一个数组存储各链表的链头指针。凡哈希地址为i的记录都插入到头指针为ChainHashi的链表中。,例：已知一组关键字为（191423016820842755111079），哈希表长为13，则按哈希函数H（key）key MOD 13和链地址法处理冲突构造哈希表。,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/不成功H.elemp.key=NULLKEY)/SearchHash,8.4.4哈希表的查找及分析,Status InsertHash(HashTable/重建哈希表/InsertHash,8.4.4哈希表的查找及分析,哈希表的查找性能分析平均查找长度ASL是衡量哈希表查找性能的重要指标。,8.4.4哈希表的查找及分析,平均查找长度取决于三个因素：哈希函数、处理冲突的方法和哈希表的装填因子。,8.4.4哈希表的查找及分析,一般情况下，处理冲突方法相同的哈希表，其平均查找长度主要依赖于哈希表的装填因子，不同冲突处理方法的平均查找长度如下表所示：,例：关键字序列（191423016820842755111079），哈希表长为13，哈希函数H（key）key MOD 13。,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,