数据结构(第九章 查找)PPT学习课件

数据结构,第9章查找,基本概念,若表中存在特定元素，称查找成功，应输出该记录；否则，称查找不成功（也应输出失败标志或失败位置）,查找表查找查找成功查找不成功静态查找动态查找关键字主关键字次关键字,由同一类型的数据元素（或记录）构成的集合。,查询(Searching)特定元素是否在表中。,只查找，不改变集合内的数据元素。既查找，又改变（增减）集合内的数据元素。记录中某个数据项的值，可用来识别一个记录(预先确定的记录的某种标志)可以唯一标识一个记录的关键字,例如“学号”,例如“女”,是一种数据结构,识别若干记录的关键字,基本概念,（2）对查找表常用的操作有哪些？查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。,（3）有哪些查找方法？,讨论：,（1）查找的过程是怎样的？给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。,例如查字典,“特定的”=关键字,查找的基本方法可以分为两大类，即比较式查找法和计算式查找法。其中比较式查找法又可以分为静态查找表和动态查找表，而计算式查找法也称为HASH（哈希）查找法。静态查找表：只作前两种操作。动态查找表：查找过程中同时插入不存在或删除已存在的某个元素。,基本概念,（4）如何评估查找方法的优劣？,明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：averagesearchlength）。,其中：n是文件记录个数；Pi是查找第i个记录的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i个记录时所经历的比较次数。,统计意义上的数学期望值,物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。,显然，ASL值越小，时间效率越高。,主要内容,9.1静态查找表9.2动态查找表9.3哈希表,9.1静态查找表,静态查找表的抽象数据类型,抽象数据类型静态查找表的定义:ADTStaticSearchTable,D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。,数据关系R：数据元素同属一个集合。,数据对象D:,Create(/按某种次序对ST的每个元素调用函数Visit()一次且仅一次。ADTStaticSearchTable,基本操作P：,针对静态查找表的查找算法主要有：,一、顺序查找（线性查找）二、折半查找（二分或对分查找）三、静态树表的查找四、分块查找（索引顺序查找）,9.1静态查找表,顺序表的机内存储结构：,typedefstructElemType*elem;/表基址，0号单元留空。表容量为全部元素intlength;/表长，即表中数据元素个数SSTable;,顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。对顺序结构如何线性查找？对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”；对非线性树结构如何顺序查找?可借助各种遍历操作！,9.1静态查找表,顺序查找,以顺序表表示静态查找表，则Search函数可用顺序查找来实现。其顺序存储结构如下：,01234567891011,513192137566475808892,找64,64,监视哨,比较次数=5,比较次数：查找第n个元素：1查找第n-1个元素：2.查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1,查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。例如：,9.1静态查找表,顺序查找,9.1静态查找表,顺序查找,算法的实现：,技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。,例：,若将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！,intSearch_Seq(SSTableST,KeyTypekey)/在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0ST.elem0.key=key;/设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n1000时，查找时间将减少一半。for(i=ST.length;ST.elemi.key!=key;-i);/不要用for(i=n;i0;-i)或for(i=1;ihigh时，查找失败。,9.1静态查找表,折半查找,折半查找算法实现,9.1静态查找表,折半查找,1234567891011,例如key=21的查找过程,low指示查找区间的下界;high指示查找区间的上界;mid=(low+high)/2。,例key=70的查找过程,9.1静态查找表,折半查找,当下界low大于上界high时，则说明表中没有关键字等于Key的元素，查找不成功。,9.1静态查找表,折半查找,intcount=0;/记录查找次数intSearch_Bin(SSTableST,KeyTypekval)/在顺序表ST中顺序查找其关键字等于key的数据元素intlow=1,mid,high=ST.length;/置区间初值while(lowdata.key)else,p=f;returnFALSE;/查找不成功,p=T;returnTRUE;/查找成功,SearchBST(T-lchild,key,T,p);/在左子树中继续查找,SearchBST(T-rchild,key,T,p);/在右子树中继续查找,9.2动态查找表,二叉排序树,T,设key=48,f,T,f,T,22,p,T,f,T,T,T,T,f,f,f,p,9.2动态查找表,二叉排序树,根据动态查找表的定义，“插入”操作在查找不成功时才进行;若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。,二叉排序树的插入算法,9.2动态查找表,二叉排序树,intInsertBST(BiTree/InsertBST,9.2动态查找表,二叉排序树,一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列每次插入的新结点都是二叉排序树上新的叶子结点插入时不必移动其它结点，仅需修改某个结点的指针,结论,9.2动态查找表,二叉排序树,二叉排序树的删除算法,和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：被删除的结点是叶子；被删除的结点只有左子树或者只有右子树；被删除的结点既有左子树，也有右子树。,9.2动态查找表,二叉排序树,（1）被删除的结点是叶子结点,例如:,被删关键字=20,88,其双亲结点中相应指针域的值改为“空”,9.2动态查找表,二叉排序树,（2）被删除的结点只有左子树或者只有右子树,其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。,被删关键字=40,80,9.2动态查找表,二叉排序树,（3）被删除的结点既有左子树，也有右子树,40,40,以其（中序遍历）前驱替代之，然后再删除该前驱结点,被删结点,前驱结点,被删关键字=50,9.2动态查找表,二叉排序树,StatusDeleteBST(BiTree/不存在关键字等于key的数据元素else/DeleteBST,算法描述如下：,见下页,9.2动态查找表,二叉排序树,if(EQ(key,T-data.key)/找到关键字等于key的数据元素elseif(LT(key,T-data.key)else,Delete(T);returnTRUE;,DeleteBST(T-lchild,key);/继续在左子树中进行查找,DeleteBST(T-rchild,key);/继续在右子树中进行查找,上页else中内容,9.2动态查找表,二叉排序树,voidDelete(BiTreep=p-lchild;delete(q);,q,q,9.2动态查找表,二叉排序树,9.2动态查找表,二叉排序树,/左子树为空树只需重接它的右子树,q=p;p=p-rchild;delete(q);,p,p,q,q,9.2动态查找表,二叉排序树,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;elseq-lchild=s-lchild;/重接*q的左子树delete(s);,9.2动态查找表,二叉排序树,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;/重接*q的右子树elseq-lchild=s-lchild;/重接*q的左子树delete(s);,9.2动态查找表,二叉排序树,二叉排序树查找性能的分析,对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。,9.2动态查找表,二叉排序树,由关键字序列3，1，2，5，4构造而得的二叉排序树,由关键字序列1，2，3，4，5构造而得的二叉排序树，,例如：,ASL=（1+2+3+4+5）/5=3,ASL=（1+2+3+2+3）/5=2.2,9.2动态查找表,平衡二叉树,平衡二叉树又称AVL树，是具有如下性质的二叉树：,为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子balance。这样，可以得到AVL树的其它性质：,即|左子树深度-右子树深度|1,左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值1,任一结点的平衡因子只能取：-1、0或1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；,对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。,9.2动态查找表,平衡二叉树,(a)平衡树(b)不平衡树,例：判断下列二叉树是否AVL树？,1,1,-1,-1,2,1,-1,9.2动态查找表,平衡二叉树,如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。,现分别介绍这四种平衡旋转。,平衡旋转可以归纳为四类：LL平衡旋转RR平衡旋转LR平衡旋转RL平衡旋转,9.2动态查找表,平衡二叉树,若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）,1）LL平衡旋转：,9.2动态查找表,平衡二叉树,在一般二叉排序树的结点中增加一个存放平衡因子的域bf，就可以用来表示平衡二叉排序树。在下面的讨论中，我们约定：用来表示结点的字母，同时也用来表示指向该结点的指针。因此，LL型失衡的特点是：A-bf=2，B-bf=1。相应调整操作可用如下语句完成：,B=A-lchild；A-lchild=B-rchild；B-rchild=A；A-bf=0；B-bf=0；,9.2动态查找表,平衡二叉树,最后，将调整后二叉树的根结点B“接到”原A处。令A原来的父指针为FA，如果FA非空，则用B代替A做FA的左子或右子；否则原来A就是根结点，此时应令根指针t指向B：if(FA=NULL)t=B;elseif(A=FA-lchild)FA-lchild=B;elseFA-rchild=B；,9.2动态查找表,平衡二叉树,若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）,2）RR平衡旋转：,RR型失衡的特点是：A-bf=-2，B-bf=-1。相应调整操作可用如下语句完成：B=A-rchild；A-rchild=B-lchild；B-lchild=A；A-bf=0；B-bf=0；,9.2动态查找表,平衡二叉树,9.2动态查找表,平衡二叉树,最后，将调整后二叉树的根结点B“接到”原A处。令A原来的父指针为FA，如果FA非空，则用B代替A做FA的左子或右子；否则，原来A就是根结点，此时应令根指针t指向B：if(FA=NULL)t=B;elseif(A=FA-lchild)FA-lchild=B;elseFA-rchild=B；,9.2动态查找表,平衡二叉树,若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）,3）LR平衡旋转：,9.2动态查找表,平衡二叉树,LR型失衡的特点是：A-bf=2，B-bf=-1。相应调整操作可用如下语句完成：B=A-lchild；C=B-rchild；B-rchild=C-lchild；A-lchild=C-rchild；C-lchild=B；C-rchild=A；,9.2动态查找表,平衡二叉树,然后针对上述三种不同情况，修改A、B、C的平衡因子：if(S-keykey)/*在CL下插入S*/A-bf=-1；B-bf=0；C-bf=0；if(S-keyC-key)/*在CR下插入S*/A-bf=0；B-bf=1；C-bf=0；if(S-key=C-key)/*C本身就是插入的新结点S*/A-bf=0；B-bf=0；,9.2动态查找表,平衡二叉树,最后，将调整后的二叉树的根结点C“接到”原A处。令A原来的父指针为FA，如果FA非空，则用C代替A做FA的左子或右子；否则，原来A就是根结点，此时应令根指针t指向C：if(FA=NULL)t=C;elseif(A=FA-lchild)FA-lchild=C;elseFA-rchild=C；,9.2动态查找表,平衡二叉树,若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）,4）RL平衡旋转：,9.2动态查找表,平衡二叉树,RL型失衡的特点是：A-bf=-2，B-bf=1。相应调整操作可用如下语句完成：B=A-rchild；C=B-lchild；B-lchild=C-rchild；A-rchild=C-lchild；C-lchild=A；C-rchild=B；,然后针对上述三种不同情况，修改A、B、C的平衡因子：if(S-keykey)/*在CL下插入S*/A-bf=0；B-bf=-1；C-bf=0；if(S-keyC-key)/*在CR下插入S*/A-bf=1；B-bf=0；C-bf=0；if(S-key=C-key)/*C本身就是插入的新结点S*/A-bf=0；B-bf=0；,9.2动态查找表,平衡二叉树,最后，将调整后的二叉树的根结点C“接到”原A处。令A原来的父指针为FA，如果FA非空，则用C代替A做FA的左子或右子；否则，原来A就是根结点，此时应令根指针t指向C：if(FA=NULL)t=C;elseif(A=FA-lchild)FA-lchild=C;elseFA-rchild=C；,9.2动态查找表,平衡二叉树,综上所述，在一个平衡二叉排序树上插入一个新结点S时，主要包括以下三步：（1）查找应插位置，同时记录离插入位置最近的可能失衡结点A（A的平衡因子不等于0）。（2）插入新结点S，并修改从A到S路径上各结点的平衡因子。（3）根据A、B的平衡因子，判断是否失衡以及失衡类型，并做相应处理。,9.2动态查找表,平衡二叉树,9.2动态查找表,平衡二叉树,例：请将下面序列构成一棵平衡二叉排序树：（13，24，37，90，53）,013,-113,-124,-213,需要RR平衡旋转(绕B逆转,B为根）,-124,-137,190,-237,需要RL平衡旋转(绕C先顺后逆）,9.2动态查找表,B树,B树的定义空树或m叉树每个结点至多有m棵子树，如根结点不是叶，至少有两棵子树，除根之外，所有非终端结点至少有m/2棵子树。所有的非终端结点含有信息(n,A0,K1,A1,K2,Kn,An)5)所有叶结点都在同一层次，叫做失败结点。,9.2动态查找表,B树,所有的非终端结点含有信息,n:有n+1棵子树，K1K2Kn关键字有序序列,指针Ai指向子树中结点的关键字小于Ki,9.2动态查找表,B树,F,F,F,F,F,F,F,F,F,F,F,在B树中的“失败”结点(F)是当搜索值x不在树中时才能到达的结点。,根据m阶B_树的定义，结点的类型定义如下：#defineM5/*根据实际需要定义B_树的阶数*/typedefstructBTNodeintkeynum;/*结点中关键字的个数*/structBTNode*parent;/*指向父结点的指针*/KeyTypekeyM+1;/*关键字向量,key0未用*/structBTNode*ptrM+1;/*子树指针向量*/RecType*recptrM+1;/*记录指针向量,recptr0未用*/BTNode;,9.2动态查找表,B树,9.2动态查找表,B树,F,F,F,F,F,F,F,F,F,F,F,B树的搜索过程检索结点53,B树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程。,9.2动态查找表,B树,30,一棵B树是平衡的m路搜索树，但一棵平衡的m路搜索树不一定是B树。,35,2040,2530,1015,4550,root,4550,35,40,20,root,1015,25,非B树B树,9.2动态查找表,B树,设在m阶B树中每层结点个数达到最少,则B树的高度可能达到最大。设树中关键字个数为N，从B树的定义知：1层1个结点2层至少2个结点3层至少2m/2个结点4层至少2m/22个结点如此类推，h层至少有2m/2h-2个结点。所有这些结点都不是失败结点。h+1层至少有2m/2h-1个结点。这一层是叶子结点，不是失败结点。,高度h与关键字个数N之间的关系,9.2动态查找表,B树,若树中关键码有N个,则失败结点数为N+1。这是因为失败数据一般与已有关键码交错排列。因此，有N+1=失败结点数=位于第h层的结点数2m/2h-1N2m/2h-1-1h-1logm/2(N+1)/2)hlogm/2(N+1)/2)+1所有的非失败结点所在层次为1h。示例：若B树的阶数m=199,关键码总数N=1999999，则B树的高度h不超过log1001000000+1=4,查找的比较次数与树的深度有关,9.2动态查找表,B树,m值的选择,如果提高B树的阶数m,可以减少树的高度,从而减少读入结点的次数,因而可减少读磁盘的次数。事实上，m受到内存可使用空间的限制。当m很大超出内存工作区容量时,结点不能一次读入到内存,增加了读盘次数,也增加了结点内搜索的难度。,B树的插入,B树是从空树起,逐个插入关键码而生成的。在B树，每个非失败结点的关键码个数都在m/2-1,m-1之间。插入在某个叶结点开始。如果在关键码插入后结点中的关键码个数超出了上界m-1，则结点需要“分裂”，否则可以直接插入。,9.2动态查找表,B树,实现结点“分裂”的原则是：设结点p中已经有m-1个关键码，当再插入一个关键码后结点中的状态为(m,P0,K1,P1,K2,P2,Km,Pm)其中Kim/2-1，则将结点N的左(或右)兄弟结点中的最大(或最小)关键字上移到其父结点中，而父结点中大于(或小于)且紧靠上移关键字的关键字下移到结点N，如后图(a)。若结点N和其兄弟结点中的关键字数=m/2-1：删除结点N中的关键字，再将结点N中的关键字、指针与其兄弟结点以及分割二者的父结点中的某个关键字Ki，合并为一个结点，若因此使父结点中的关键字个数m/2-1，则依此类推，如后图(d)。,9.2动态查找表,B树,9.2动态查找表,B+树,B-树的变形根结点(非叶时)至少有两个结点除根外，非叶结点至少有m/2棵子树,最多有m棵子树,非叶结点都是索引，含有子树中的最大或最小关键字含有n个关键字的非叶结点有n棵子树所有的叶子结点都在同一个层次上，叶子结点中包含全部关键字，以及指向这些关键字的指针所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字,9.2动态查找表,B+树,根,叶,B+树两种查找：从根开始，从叶起始,9.2动态查找表,B+树,B树(上图)与B+树（下图）比较,B树与B+树的随机查找、插入、删除的过程基本上与B树类似。只是在查找时，若非终端结点的关键字等于给定值，并不终止，而是继续向下直到叶子结点。,9.3哈希表,哈希表的相关定义,哈希查找:又叫散列查找，利用哈希函数进行查找的过程。基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。哈希函数:在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。可写成，addr(ai)=H(ki)其中：ai是表中的一个元素addr(ai)是ai的存储地址ki是ai的关键字,9.3哈希表,哈希表的相关定义,哈希表根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。,9.3哈希表,哈希表的相关定义,98,例30个地区的各民族人口统计表,以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2,以地区名作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19,9.3哈希表,哈希表的相关定义,从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。冲突：key1key2，但H(key1)=H(key2)的现象,9.3哈希表,哈希函数构造的方法,哈希函数构造的方法,直接定址法数字分析法平方取中法折叠法除留余数法随机数法,9.3哈希表,哈希函数构造的方法,哈希函数为关键字的线性函数H(key)=key或者H(key)=akey+b此法仅适合于：地址集合的大小=关键字集合的大小其中a和b为常数,直接定址法,优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.缺点：要占用连续地址空间，空间效率低。,例：关键码集合为100，300，500，700，800，900，选取哈希函数为Hash(key)=key/100，则存储结构（哈希表）如下：,9.3哈希表,哈希函数构造的方法,数字分析法,假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。此法适于能预先估计出全体关键字的每一位上各种数字出现的频度。,例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数,分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址,9.3哈希表,哈希函数构造的方法,9.3哈希表,哈希函数构造的方法,以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。,平方取中法,9.3哈希表,哈希函数构造的方法,将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：移位叠加:将分割后的几部分低位对齐相加间界叠加:从一端沿分割界来回折送，然后对齐相加(此法适于关键字的数字位数特别多),折叠法,除留余数法,设定哈希函数为:H(key)=keyMODp(pm)其中，m为表长p为不大于m的质数或是不含20以下的质因子,9.3哈希表,哈希函数构造的方法,9.3哈希表,哈希函数构造的方法,给定一组关键字为:12,39,18,24,33,21，若取p=9,则他们对应的哈希函数值将为:3,3,0,6,6,3可见，若p中含质因子3,则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能,例如：,为什么要对p加限制？,9.3哈希表,哈希函数构造的方法,随机数法,设定哈希函数为:H(key)=Random(key)其中，Random为伪随机函数此法用于构造关键字长度不等的哈希函数。选取哈希函数考虑的因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率,9.3哈希表,处理冲突的方法,处理冲突的方法,“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。开放定址法链地址法,为产生冲突的地址H(key)求得一个地址序列：H0,H1,H2,Hs1sm-1Hi=(H(key)+di)MODm其中：i=1,2,sH(key)为哈希函数;m为哈希表长;di为增量序列,有下列三种取法:,开放定址法,9.3哈希表,处理冲突的方法,对增量di的三种取法：,1)线性探测再散列di=ci最简单的情况c=12)二次探测再散列di=12,-12,22,-22,3)随机探测再散列di是一组伪随机数列或者di=iH2(key)(又称双散列函数探测),9.3哈希表,处理冲突的方法,注意：增量di应具有“完备性”即：产生的Hi均不相同，且所产生的s(m-1)个Hi值能覆盖哈希表中所有地址。则要求：平方探测时的表长m必为形如4j+3的素数（如:7,11,19,23,等）；随机探测时的m和di没有公因子。,9.3哈希表,处理冲突的方法,9.3哈希表,处理冲突的方法,例表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=keyMOD11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中,(1)H(38)=38MOD11=5冲突H1=(5+1)MOD11=6冲突H2=(5+2)MOD11=7冲突H3=(5+3)MOD11=8不冲突,(2)H(38)=38MOD11=5冲突H1=(5+1)MOD11=6冲突H2=(5-1)MOD11=4不冲突,(3)H(38)=38MOD11=5冲突设伪随机数序列为9，则：H1=(5+9)MOD11=3不冲突,012345678910,601729,38,38,38,9.3哈希表,处理冲突的方法,例如:给定关键字集合构造哈希表19,01,23,14,55,68,11,82,36设定哈希函数H(key)=keyMOD11(表长=11),19,01,23,14,55,68,19,01,23,14,68,若采用线性探测再散列处理冲突,若采用二次探测再散列处理冲突,11,82,36,55,11,82,36,112136251,将所有哈希地址相同的记录都链接在同一链表中。例:给定关键字19,01,23,14,55,68,11,82,36哈希函数为H(key)=keyMOD7,链地址法,9.3哈希表,处理冲突