吉林大学数据结构课件 第八章 查找

第八章查找,查找（亦称检索），简言之就是查表。一份表就是一个文件(表通常指小文件，文件一般指大表。一个大的文件通常被称为数据库)一份表包含N个记录，假定每个记录都对应一个关键词。一个查找算法查找或检索一张表的过程，就是对给定的变元K，去找出其关键词域之值等于K的那个记录；查找完成后有两种可能，或者查找成功，已确定出一个其关键词域之值为K的记录之所在，或者查找失败，即确定出关键词域之值为K的记录在表中已无处可寻。在查找失败后，有时还希望把一个关键词域之值为K的新记录插入到表中去，这样的过程被称为查找与插入操作,下面我们简要介绍一下查找方法研究中的代表性工作：1946年，JohnMauchly首先提出了对半查找（又称为二分查找，折半查找）的思想。随后人们又在20世纪六、七十年代对其进行了深入研究，提出了一致对半查找算法，费波那契查找算法和插值查找算法等。1952年，A.I.Dumey描述了树插入算法的原始形式。之后人们又研究了二叉查找树、最优二叉查找树、近似最优二叉查找树、平衡树、2-3树、2-3-4树、红黑树、B树及其变形树等树查找方法，并将其广泛应用于数据库、操作系统等领域中。1962年，两名俄国数学家G.M.Adelson-Velsky和E.M.Landis，对维持一株好的查找树的问题，发现了一个非常漂亮的解，即平衡树，许多学者也将其称之为AVL树，其中AV代表Adelson-Velsky，L代表Landis.,1953年，H.P.Luhn提出了散列（Hashing，也译成杂凑、哈希）的思想。从1953年至今，散列技术一直是研究的热点，并被广泛应于数据加密等领域。1980年，C.S.Ellis提出将AVL树并行的思想。之后，直到2004年，人们才分别提出了AVL树、2-3树、红黑树、B树的并行算法，使树的查找、插入和删除等操作，实现了从单处理机上的顺序执行到多处理机上的并行执行的跨越。从上面的发展历程可看出，自上世纪50年代起至今查找技术研究已经历了半个世纪，在这段时间里，人们陆续提出了线性表查找、树结构查找、基于检索结构的查找、数字查找和散列查找等方法。每种查找方法的提出都有其历史背景，且其目的都是要提高查找方法的效率。,一个查找算法，主要有以下四个方面的特性：内外有别分内查找和外查找。内查找系指内存能容纳一文件的全部N个记录的情形；外查找系指一文件所包含的记录总数N太大超出了内存的容量。静态动态静态查找时，表（或文件）的内容不变（即一个单纯的查找过程）；动态查找时，频繁地将新记录插入到表（或文件）中，或频繁地从表（或文件）中删除记录，即表（或文件）中的内容不断地变化。,8.1顺序查找无序表的顺序查找从起点开始顺着往下查，一直找到正确的关键词为止顺序查找方法从线性表的起始结点开始，逐个检查其后继结点，或者找到关键词KKi，或者iN（i为表中记录的下标，N为线性表的元素个数）查找以失败告终。,这个算法可以精确地阐述如下：算法S(N，R，K.i)/*给定包含N个记录R1，R2，RN，其对应的关键词分别为K1，K2，KN的一个表，S查找一个给定的变元K.这里假定N1.*/S1.初始化i1.S2.比较关键词如果KKi，则算法成功结束.S3.推进iii1.S4.iN?若iN，则返回步骤S2；否则此算法以失败告终.,查找成功的平均查找长度：SS顺序查找的时间复杂度:O(n),i,算法Q(N，R，K.i)/算法Q与S基本相同，区别在于Q之表（或文件）的末尾添加了一个“虚拟”记录RN1.Q1.初始化置i1，并置KN1K.Q2.比较关键词如果KKi，则转到步骤Q4.Q3.推进i置ii1，并返回步骤Q2.Q4.iN?如果iN，则算法成功结束；否则以失败告终./此时有iN1算法Q大约比算法S节省百分之二十的运行时间。算法Q还能更快吗？,算法Q(N，R，K.i)Q1.初始化置i1.KN1K.Q2.前进两步置ii2.Q3.Ki:K若KiK，则转到步骤Q5.Q4.Ki1:K若Ki1K/此时KiK，则返回步骤Q2；否则置ii1./此时Ki1K，找到了所需记录，其位置为i1Q5.iN?若iN，则算法成功结束；否则算法以失败告终./此时iN1算法Q的运行时间比算法S约减少了百分之三十。,把经常出现的元素（它的发生概率较大）自动向表的前端移动，把不经常出现的元素自动向表的后端移动，并称以该方式组织的表为自组织表.MOVE-AHEAD-ONEMOVE-TO-FRONT顺序查找优缺点:优点:算法简单,且适用面广,对表的结构无任何要求.缺点:平均查找长度较大,特别n很大查找效率低.,有序表的顺序查找算法T(N，R，K.i)/*设与表中记录R1，R2，RN对应的关键词满足K1K2KN，算法T查找给定变元K，假定有一虚拟记录RN1，其关键词为KN1，显然有KN1K.*/T1.初始化置i1.KN1.T2.比较若KKi，则转到步骤T4.T3.推进i置iil，并返回步骤T2.T4.KKi?若KKi，则算法成功结束；否则算法以失败告终.,对于成功查找，算法T的平均执行时间基本与算法Q相同；但当查找不成功时，它比算法Q大约快1倍，因为它能更快地确定一个记录不存在当然，如果只需对这个表查找一次，则进行顺序查找比对这个文件进行完整的排序要快K1K2KN.在这样的表中，比较K和Ki后，我们有:KKi，不必考虑子表Ri，Ri1，RNKKi，查找成功结束KKi，不必考虑子表R1，R2，Ri,使用不同的规则确定i，可得到不同的二分查找方法：对半查找、一致对半查找、斐波那契查找和插值查找等。从只考虑KKi和KKi两种情况，到考虑KKi，KKi和KKi等三种情况；每次比较K和当前被查之子表（文件）的中间记录的关键词Km,算法B(N，R，K.i)给定其关键词在递增次序下（即K1K2KN）包含N个记录R1,R2,RN的一个表（或曰文件，表（或文件）的一部分亦被称为表（或文件），本算法查找一个给定变元K.用两个指针s和e分别指出当前被查找之文件中最左边记录（或其关键词）的下标和最右边记录（或其关键词）的下标。,算法B(N，R，K.i)B1.初始化s1.eN.B2.取中点（此时，若知道K在此文件中，则它满足KsKKe）如果es，则该算法以失败告终；否则，置i(s+e)/2（i为此文件的近似中点）。B3.比较如果KKi，则转步骤B5；如果K=Ki，则算法成功结束。B4.调整eei1，并返回B2.B5.调整ssi1，并返回B2.,例假定有序表A中10元素的关键字序列为：12，23，26，37，54，60，68，75，82，96当给定值分别为96和58时进行对半查找。,查找k=96时对半查找过程(4次比较成功）,12345678910,查找k=58时对半查找过程(3次比较失败）,例T（1，10）的二叉判定树,每个圆圈结点表示关键词比较K:Ki,12232637546068758296,二叉判定树二叉判定树，T（s，e）的递归定义如下：(1)当e-s+10时，T（s，e）为空树；(2)当e-s+10时，二叉判定树的根结点是有序表中序号为(e+s)/2的记录，根结点的左子树是与有序表Rs，Rs+1，R(e+s)/2-1相对应的二叉判定树，根结点的右子树是与有序表R(e+s)/2+1，R(e+s)/2+2，Re相对应的二叉判定树.,外部结点：树中所有结点的空指针都指向一个方形结点，则称这些方形结点为查找树的外部结点。内部结点：树中原来那些圆形结点就叫做查找树的内部结点。增长的二叉树：当原二叉树中的结点没有左子树形和右子树形时，就增加特殊的结点（称外部结点，树中原来的那些结点称内结点），由此生成的二叉树称为增长的二叉树。,搜索K=96成功的情况：,搜索K=58失败的情况：,例T(1,10)查找成功的平均查找长度.,ASLSUCC(1*1+2*2+3*4+4*3)/1029/102.9,查找失败的平均查找长度：,ASLUNSUCCEn/(n+1)(3*5+4*6)/1139/11,引理8.1如果算法B对N个记录的成功查找是等概率的，且不成功查找也是等概率的，则成功查找关键词的平均比较次数为SN1IN/N，不成功查找关键词的平均比较次数为UNEN/(N1)(其中IN，EN为T(1,N)的内、外路径长)已知外路径长总是比内路径长大2NSN1IN/N，(SN-1)*NIN，UNEN/(N1)，UN*(N+1)EN=IN+2N=SN*N+NSN(11/N)UN1,引理8.1如果算法B对N个记录的成功查找是等概率的，且不成功查找也是等概率的，则成功查找关键词的平均比较次数为SN1IN/N，不成功查找关键词的平均比较次数为UNEN/(N1)(其中IN，EN为T(1,N)的内、外路径长)已知外路径长总是比内路径长大2N通过比较进行查找的一种“最好的”方式，是在所有具有N个内结点的二叉树中，具有极小外路径长的树。,引理8.1如果算法B对N个记录的成功查找是等概率的，且不成功查找也是等概率的，则成功查找关键词的平均比较次数为SN1IN/N，不成功查找关键词的平均比较次数为UNEN/(N1)(其中IN，EN为T(1,N)的内、外路径长)引理8.2对半查找二叉判定树T(s,e)的高度是log2(es2).引理8.3设T(1,N)是N个内结点的二叉查找判定树，如不考虑外结点T(1,N)之高度为k，则T(1,N)之外结点均属于k或k1层.,定理8.2在最坏情况下，算法B的关键词比较次数为log2(N1)，且其期望复杂性等于O(log2N).,一致对半查找就对半查找算法而言，能否将其所用的指针数量减少，譬如仅使用三个（s，i和e）中的两个使用当前的位置i和它的变化率；在每次不相等的比较之后，可以置ii/2（近似地）,算法U(N，R，K.i)/*给定包含N个记录R1，R2，RN，其诸关键词为递增次序K1K2KN的一张表，本算法查找变元K.若N为偶数，则算法有时将涉及一个虚拟关键词K0，K0被置成（或小于K的任意值）.我们假定N1.*/U1.初始化置iN/2，mN/2.U2.比较若KKi，转到U3；若KKi，转到U4；若KKi，则算法成功结束。,U3.减小i（我们已认准包含m或m1个记录的一个查找区间；i1恰指向该区间的右端）若m0，则算法以失败告终；否则置iim/2；然后置mm/2并返回U2.U4.增大i（我们已认准包含m或m1个记录的一个查找区间；i1恰指向该区间的左端）若m=0，则算法以失败告终；否则置iim/2；然后置mm/2并返回U2.,当查找失败时，该算法可能在结束前作一次冗余的比较，如图中阴影结点所示。算法U之所以被称为是一致的，是因为，在层L上的一个结点的编号与在层L-1上它父亲结点的编号之差的绝对值，对于层L的所有结点均一致为一常数对第1层均有一致的3，对第2层均有一致的1，对第3层均有一致的1下一个中间点是由iim/2来确定的,改进算法U.在算法运行期间，没有必要去计算诸m之值（在算法U中用于寻找中点）而是代之使用一张辅助表.,算法C的时间花费近似为:(8.5log2N-6)u对于一次成功的查找(8.5log2N+12)u对于一次不成功的这个速度相当于算法B的2倍多在均匀划分待查表（或曰文件）的前提下，对半查找算法还有一些改进方案,斐波那契查找(一致)对半查找方法对表的分划是均匀的，考虑其他的分划方法.Fibonacci序列向我们提供了一种对半查找的替代方案：这种序列可以定义为F0=0，F1=1，以及Fj=Fj-1+Fj-2，j2,假定表中元素的个数是某个Fibonacci数减1，即n=Fi-1.设m=Fi-1,Fibonacci查找是把关键词K与Km作首次比较，从而产生如下的结果：（a）KKm，这时查找从m+1到n的子表，且表的元素个数是(Fi-1)-Fi-1=Fi-Fi-1-1=Fi-2-1即一个Fibonacci数减1.,算法Fibonacci(R,K,m.found)/假定表中元素数n=Fm+1-1(m2)，且表中记录已排序Fib1初始化iFmpFm-1.qFm-2.foundfalse.Fib2WHILEi0DO（IFK1时，二叉判定树的根结点是有序表中序号为Fm的记录，根结点的左子树是与有序表R1，R2，RFm-1相对应的二叉判定树，根结点的右子树是与有序表RFm+1，RFm+2，RFm+1-1相对应的二叉判定树.,6阶的斐波那契树，即N12f71.阶数k的斐波那契树有fk11个内部结点和fk1个外部结点每个内结点的两个儿子结点的编号与其父亲结点的编号之差的绝对值相同，且这个差数的绝对值是一个斐波那契数。,(7.05log2N+1.08)u对于成功查找(7.05log2N+5.23)u对于不成功查找算法C的平均运行时间大约是算法F的1.2倍，算法B的平均运行时间大约是算法F的2.5倍。在最坏的情况下，算法F的运行时间约为8.6log2N，比算法C稍稍慢一点。,引理8.4设m3，Tm是m阶Fibonacci树形，则Tm的左子树形的高度等于右子树形的高度加1，且Tm的高度为m-1.,引理8.4设m3，Tm是m阶Fibonacci树形，则Tm的左子树形的高度等于右子树形的高度加1，且Tm的高度为m-1.引理8.5设n=Fm+1-1，则m阶Fibonacci树形的高度约等于1.44log2（n1）.,引理8.4设m3，Tm是m阶Fibonacci树形，则Tm的左子树形的高度等于右子树形的高度加1，且Tm的高度为m-1.引理8.5设n=Fm+1-1，则m阶Fibonacci树形的高度约等于1.44log2（n1）.定理8.2令n=Fm+1-1，则算法Fibonacci在最坏情况下的时间复杂性为O(log2n)，且期望复杂性亦为O(log2n).,前面讨论的几种查找算法是基于严格比较的，即假定我们对线性表中元素的分布一无所知（即无启发式信息）.然而实际中，很多查找问题所涉及的表都满足某些统计特点.例如，查字典（A-Z）我们是在所期望的地址（X,Y在词典的很靠后的地方）附近开始查找，称这样的查找为插值查找.,插值查找假定表中记录的关键词是数字类型，且K1K2Kn在(K0，Kn+1)区间上呈均匀分布.变元K给定，且K0K1ANDNOT（found）DO(ms+（e-s-1)(K-Ks）/（Ke-Ks）.IFKKmTHENem.IFKKmTHENsmIFK=KmTHENfoundtrue）,插值查找渐近地优于对半查找。当表中关键词随机分布时，对半查找的每一步将查找工作量从N降低到N/2，而插值查找则把N降到N1/2.,画出二叉判定树(算法BUCF)计算平均成功、失败查找的关键词比较次数123456789101112,8.2二叉查找（搜索）树二叉判定树有助于了解对半查找和斐波那契查找的特性。上一节的方法主要适用于固定长度的表，记录的顺序分配使得插入和删除相当费时如果这个表动态地变化，则我们花费的维护时间可能比在对半查找中(查找它们)所节省的时间还要多,8.2二叉查找（搜索）树定义和基本操作定义:二叉查找树(或称二叉搜索树、排序树)是一棵可能为空的二叉树形，一棵非空的二叉查找树中的所有结点在中根次序下按其关键词由小到大排序，并且关键词各不相同。,定义:就关键词的大小次序而言，TB的诸结点是按照中根次序排列的。换言之，若以中根次序遍历TB，将产生一个关于TB诸结点之关键词的递增序列。定义:一棵二叉查找树是一棵可能为空的二叉树形，并且关键词各不相同.二叉查找树任一非叶结点P，它的左子树中结点的关键词都小于KEY（P），而右子树中结点的关键词都大于KEY（P），并且结点P的左右子树也都是二叉查找树。,如何建立一棵二叉查找树。例有一种组数据集合53,78,65,17,87,09,81,45,23对包含N个记录的集合，其对应的关键词有N!种不同的排列，可构成棵不同的二叉查找树。,为讨论算法的方便性，我们设二叉查找树中结点的结构为（LLINK，KEY，DATA，RLINK），其中LLINK和RLINK是链接字段，KEY为该结点的关键词.,基本操作（1）Create()；创建一个空的二叉查找树。（2）Search(k，e)；将关键词为k的元素返回到e中，查找失败返回false，否则true。（3）Insert(k，e)；将关键词为k的元素e插入查找树中，如果k已存在，则不插入。（4）Delete(k，e)；删除关键词为k的元素并将其返回到e中。（5）Ascend()；按照关键词的升序排列输出所有元素。,二叉查找树基本操作算法查找算法算法BST(T,K.found)/二叉查找树查找算法/设指针T指向二叉查找树的根结点BST1由根结点开始PTfoundfalseBST2比较WHILEPANDNOT（found）DOCASEDO（KKEY（P）：PRLINK（P）.K=KEY（P）：foundtrue）,设表中元素的关键词K1K2Kn，则查找成功应该终止于Ri(内结点)，而查找失败应终止在n1个记录间隔(或者称外结点，即KiK树中结点数或k0*/.若MRANK(P)，则转到步骤B4/*向右*/；若MRANK(P)，则本算法成功地结束.B3左移置PLLINK(P)并返回步骤B2.B4右移置MMRANK(P)，PRLINK(P)并返回步骤B2.,8.7B树及其变形树前面介绍的树形查找方法，主要属于内查找方法，适用于被检索文件能完整地被放到计算机内存中的情形。如果文件很大，以至于计算机内存容纳不下时，则必须放在磁盘等外存储器上。当人们想从一个存放在磁盘上的大文件中查找某些信息时，则需要去研究一种新的查找方法外查找。,8.7.1多叉树,二叉树被分成许多包含7个结点的页，我们又称其为页结点。,8.7.1多叉树,每次从盘上存取一个页结点（而不是仅仅存取一个结点），即7个记录，从而使盘操作次数缩小到原来（没分页时）的三分之一，大大提高了查找速度。,1、基本概念1970年，拜尔(R.Bayer)和麦克瑞特(E.McCreight)提出一种新的外查找树，称为B树。这是一种多叉平衡树形，它在插入或删除操作中有简单的平衡算法。B树及它的一些改进形式已成为索引文件的有效结构，得到了广泛的应用。定义8.7一个m阶的B树满足下述条件：每个结点有m个儿子；除根和叶之外的每个结点有m/2个儿子；根结点至少要有两个儿子（除非它本身又是一个叶结点）；具有k个儿子的非叶结点包含k1个关键词；所有的叶结点都出现在同一层上，并且它们都不带有信息.,8.7.2B树,叶不带有信息，可以认为它们是外部结点，实际上它们不在树中，所以指向叶的指针为空。,在前面的7阶B树中，每个结点(除了根和叶)，有4（7/2）到7个儿子，故可有3，4，5或6个关键词。根结点允许有1至6个关键词，根结点包含两个关键词。这个B树的所有叶子都在第3层上。应强调指出的是：每个非叶结点中的关键词是按从左到右的递增顺序排列的；叶子的总数比关键词总数多1；和两点表明了B树是二叉查找树的一个自然推广。很自然，我们对1阶和2阶B树毫无兴趣，这里只考虑m3的情况。阶为3的B树，也叫做2-3树。,一个包含j个关键词和j+1个指针的B树结点如图所示。结点之关键词满足K1K2Kj，指针Pi指向一个其所有关键词都在Ki和Ki+1之间的子树形。因此，在B树中进行查找是十分简单的。,2、查找假定结点P已从磁盘读到内存中，可选择适当的内查找方法。当j比较大时，可选择对半查找算法；当j较小时可采用顺序查找方法。设查找一个给定的变元k，若k在NODE(P)中，则查找成功。否则必是下述三种情形之一：1)KikKi+1(1ij)，则继续到结点NODE(Pi)中去查找.2)kKj，查找将转NODE(Pj)继续查找。3)kK1，查找将转NODE(P0)继续查找。如果指向下一个要查找的结点的指针Pi=，则查找以失败告终，关键词为k的记录不在树中。,3、插入（1）若在一个包含jm1个关键词的结点中插入一个新关键词，则插入过程将局限于该结点自身（把新关键词直接插入该结点中即可）。如在下图中插入关键词337，只须改变一个结点即可。,插入（2）若把一个新关键词插入一个已包含m1个(m为B树的阶)关键词的结点(结点已满)，则插入将造成此结点“分裂”。如插入关键词071。此时，把m个关键词分成个数相等的两组，第一组从左向右数，包含m/2个关键词，第二组从右向左数，包含m/2个关键词，剩下的中间那个关键词将被提升到上一层结点中，去开始新的插入。“分裂”可能会向上传播，在极端情况下，分裂会一直波及到根结点，而这恰恰是B树长高的唯一方式。,4、删除先找到要删除的关键词Ki的位置，若它不在叶的上一层里，则要把删除Ki后的空位置用最接近Ki而又大于Ki的关键词K*来填充，同时从K*所在的结点中删除K*，这是因为在中间诸层的关键词还起指导向下查找的作用，故不能为空。例如删除353。,当删除关键词后，空位置已在B树之叶子的上一层结点中。要检查该结点目前包含的关键词个数是否小于m/2-1.(1)若不是，则直接删除空位置，即合并两个空指针。(2)若是，则要从相邻的兄弟结点中借关键词，最好使两个结点的大小一样（即包含相同数目的关键词）。如下图删除关键词379的情形。,若相邻（同父）结点的关键词个数都等于m/21，则一个与分裂相反的过程“合并”便发生了。所谓“合并”，即把两个兄弟结点的关键词连同在父结点中指向这两个结点的指针之间的关键词按递增顺序排列在一个新结点中。例如从上图中删去关键词431。若“合并”操作使上一层结点（父结点）所包含的关键词个数出现了m/21的情况，则又造成了上一层结点或要借关键词或要进行“合并”操作。“合并”可能会导致上一层发生“合并”，从而可能使“合并”不断向上传播，或许一直波及到根结点，从而有可能使整个B树减少一层。,5、讨论设有一个m阶B树，它包含N个关键词，它的N+1个叶子出现在第l层上。则：,这意味着，当N=1999998且m=199时，l最多是3.就是说，在最坏的情况下，一次查找至多需要存取3个结点。因此，B树上的查找操作是很快的。,8.7.3B+树由于B树的结点代表一个辅存页或者是一个辅存块，从一个结点到另一个结点需要费时的页切换。所以最好尽可能地少访问结点。如果请求以升序访问B树中的结点，如用中序遍历，但对非末端结点，一次只能显示一个关键词，然后就要访问其他的页。因此，希望增强B树，能以比中序遍历快的方式顺序访问数据。B+树提供了一个解决方案。,B+树是适应文件系统的需要而产生的一种B树的变形树，一棵m阶B+树须满足下列条件：1)每个分支结点至多有m棵子树；2)除根结点外，其它每个分支结点至少有m/2棵子树；3)根结点至少有两棵子树，至多有m棵子树；4)有n棵子树的结点有n个关键词；5)所有的叶子结点包含全部关键词及指向相应记录的指针，而且叶子结点按关键词自小而大的顺序链接；6)所有分支结点（可看成是索引的索引）中仅包含它的各个子结点（下级索引的索引块）中最大关键词及指向子结点的指针。,一棵2阶B+树,一棵m阶B+树和一棵m阶B树的差异在于:B树中，有n棵子树的结点中含有n个关键词；B树中，每个结点（根结点和叶结点除外）中的关键词个数n的取值范围是m/2nm，根结点关键词个数n的取值范围是2nm；而B树中，它们的取值范围分别是m/21nm1和1nm1；B树中，所有的叶结点中包含了全部关键词，即其它非叶结点中的关键词都包含在叶结点中；而在B树中，叶子结点包含的关键词与其它结点包含的关键词是不重复的；B树中，非叶结点仅起索引作用，即结点中每个索引项只含有对应子树的最大关键词和指向该子树的指针，不含有该关键词对应记录的存储地址。而B树中，每个关键词对应一个记录的存储地址；通常在B树上有两个头指针，一个指向根结点，另一个指向最小关键词的叶子结点，所有叶子结点链接成一个不定长的线性链表。,B+树进行两种查找运算：一种是从最小关键词开始进行顺序查找，另一种是从根结点开始进行随机查找。在B+树上进行随机查找、插入和删除操作的过程基本上与B树类似。只是在查找时，如果非叶结点上的关键词等于给定值，并不终止，而是继续向下直到叶结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶结点的路径。,我们所考虑的查找方法在找到以K为关键词的记录之前，都要检查若干数目的关键词.而散列技术则完全免去了上述方法所作的搜索.,8.9散列散列方法（或曰杂凑方法，哈希方法）：以给定变元K（关键词）为自变量，通过某种函数关系h(K)直接计算出函数值，这个值被解释为存放以K为关键词之记录的存储单元的地址。以关键词在地址集上的“映像”作为该记录在表中的存储位置，这种表称为散列表或者杂凑表.这种映射过程称为散列，所得到的存储位置称为散列地址.,8.9散列散列方法（或曰杂凑方法，哈希方法）：以给定变元K（关键词）为自变量，通过某种函数关系h(K)直接计算出函数值，这个值被解释为存放以K为关键词之记录的存储单元的地址。以关键词在地址集上的“映像”作为该记录在表中的存储位置，这种表称为散列表或者杂凑表.这种映射过程称为散列，所得到的存储位置称为散列地址.,这样的散列函数必须满足如下条件：便于快速计算；没有冲突（所谓“冲突”系指，对于K1K2，却有h(K1)=h(K2)）.但是，没有冲突的散列函数h是很不好找便于快速计算；极少出现冲突.冲突消解方法拉链法线性探查法伪随机探查法二次探查法双重散列法,散列方法不仅是一种快速的查找（检索）方法，而且也是一种重要的存储方式。按散列存储方式构造的存储结构被称为散列表，散列表中的一个位置被称为槽。散列方法的核心是散列函数及冲突消解方法。,散列函数为了获得一个好的杂凑函数，通常应使h与组成关键词K的所有符号有关.此外，如果K是从关键词集合中随机选取的一个，则我们希望h(K)以同等概率取区间0，M-1中的每一个值.如果一个杂凑函数满足这一性质，则被称为是均匀的.为了方便，我们把关键词都表示为二进制代码.,例A=00001,B=00010,C=00011,Z=11010THEh1(THE)=10100XOR01000XOR00101=1100125(10).异或运算满足交换律，即aXORbbXORa即有同样字母的单词有相同的杂凑地址。hl(STEAL)=h1(STALE)=h1(TALES)=h1(LEAST),杂凑函数压缩法除法散列函数乘法散列函数平方取中法抽取法,杂凑函数压缩法把关键词的二进制串分割成若干个子串，然后按某种方式把这些子串合并形成该关键词的地址。压缩法满足交换律；压缩技术最适合转换多个字母的单词为单个字母，并且它也很容易与除法及乘法散列函数联合使用。h(THE)=10100XOR01000XOR00101=110012510,杂凑函数除法杂凑函数只需使用模M的余数h(K)KmodM除法杂凑函数的优点是便于快速计算要使用这样的杂凑函数就要仔细地选择M的值即M的选择不仅要依赖整个关键词而且要打破一些自然的群集现象；M取小于或等于杂凑表容量的最大质数例：h(THE)=101000100000101mod31=2074110mod31=2,杂凑函数乘法杂凑函数给定一个实数，01，则我们可按如下的方式给出一个杂凑函数.：h(K)=M(Kmod1)显然h满足0h(K)M讨论参数的选择，我们不希望太接近0或1，因为这能导致小元素群集在表的两端.一般来说当0.6180339887或0.3819660113时杂凑函数能均匀地分布在0，M-1上.,杂凑函数平方取中法(middle-square)首先将K平方，然后取K2的中间部分作为h(K)的值。平方取中法可以避免除法运算。一般使用下列散列函数:其中W=2，M=2k都是2的幂，是计算机字长，M是散列表长，关键词是无符号整数。将K平方，取位；右移-k位。由于右移时左边补零，因此，结果总在0到M-1之间,设关键词用内部码表示，内码采用八进制表示。=18，k=9，M512.虽然只取了KK的中间几位，但这些位与乘数K的每一位都相关，故散列值还是比较均匀的。,杂凑函数抽取法最简单的杂凑函数，即从关键词相对的二进制串中抽取几个分散的代码，然后合并这几个代码而形成一个地址，这种方法容易出现“群集”现象；,冲突调节冲突调节也称为溢出处理技术.上面的讨论表明，一个再好的杂凑函数也不能完全避免冲突，因此寻求较好的解决冲突的方法是一个很重要的问题，下面我们给出解决冲突的几种技术.拉链方法（chaining）/开散列法（openinghashing）开地址法（openaddressing）/闭散列法（closedhashing）,1.拉链法/开散列法假定表T包含M个杂凑地址T0，Tl，TM-l，拉链就是令杂凑地址等于i的记录组成一个链表，且指针Ti是该单链表的头指针.,M=9，有一个包含7个关键词的序列EN,TO,TRE,FIRE,FEM,SEKS,SYV，散列函数h关于以上7个关键词分别(依序)有如下值:2，0，3，0，4，8，1,改进的方法是将每个Ti分成两个域，一个域存放真正的记录，另一个域存放指针，该指针指向和该记录具有相同杂凑地址的下一个记录。当插入关键词K时，如若发现Th(K)处已包含别的记录，则找到一个空的表地址Tfree，把K存储在Tfree处，并沿冲突位置的LINK一直找下去，直到一个表地址的LINK值为空然后最后一个空LINK域的值为free寻找空地址可由TM-l开始，向T0方向搜索,关键词序列为：,杂凑函数：h(k)=K%11,冲突调节：拉链法,算法C(TABLE，K，M.)/*对给定变元K，本算法检索M个结点的表。若K不在表中且表不满，则把K插入表中。本算法使用了一个散列函数h(K).R是一个辅助变量，用于找到空的空间；R有初始值，R=M+1.*/C1.散列置ih(K)+1（现在1iM，为检索K，取K的散列位置i=h(K)+1，去检索TABLEi).C2.有链表吗?若TABLEi为空，则转到步骤C6.C3.比较若K=KEYi，则本算法以成功告终.C4.查下一个若LINKi，则置iLINKi并返回步骤C3.,C5.找空结点(已查完由TABLEh(K)+1开始的链表，检索不成功，故应该插入K，所以需要在表中找一个空位置)令R减1（R初值为M+1），进行此操作一次或多次直到TABLER是空为止若R=0（表明已经没有剩余的空结点），则本算法以溢出告终；否则，置LINKiR，iR.C6.插入K标记TABLEi为已占用，置KEYiK，LINKi，算法以插入成功告终。,开地址法/闭散列法这类方法不建立链表线性探查插入关键词值为K的新元素的方法是：从h(K)开始，按照某种规定的次序探查允许插入新元素的空位置如果h(K)已经被占用，那么就需要有一种解决冲突的策略来确定如何探查下一个空位置不同的解决冲突的策略，可产生不同的被检查的位置序列，称为探查序列h(K)，h(K)+1,M-1，0，1,h(K)-1,关键词序列为：,杂凑函数：h(k)=K%11,冲突调节：线性探查,20,6,17,1,37,45,2,23,66,线性探查查找和插入算法L(TABLE，K，M.)/*在一个包含M个结点的表中查找一个给定的关键词K.如果K不在表中且表不满，则插入K变量N记录已占用的结点数*/L1.散列置ih(K)./有0iML2.比较若TABLEi为空，则转L4；/*去插入K*/否则，若KEYi=K，则本算法以检索成功结束.L3.查下一个置ii1；若i0,则置iiM返回L2.L4.插入K若N=M1，则本算法以溢出告终/*L在N=M1就认为表已经满了,这样做的结果使得表中永远有一个结点为空*/；否则,置NN+1,并置KEYiK./*注意在调用L的外层算法中，对变量N初始化*/,伪随机探查法线性探查法有一个明显的缺点，它容易使许多元素在散列表中连成一片理想的探查序列应当是散列表位置的一个随机排列可行的方法是使用伪随机探查:建立一个伪随机发生器，当发生冲突时，就利用伪随机数发生器计算出下一个探查的位置。y0h(key)yi1(yip)modM(i0,1,2,)y0为伪随机数发生器的初值，M为散列表的长度，p为与M接近的素数,现取p=7，构造伪随机探查散列表,现取p=7，构造伪随机探查散列表插入前三个关键词值12、24和9以后，接着：,现取p=7，构造伪随机探查散列表插入前三个关键词值12、24和9以后，接着：插入20，因y1=(4+7)mod8=3，位置3处空闲，故将20存入位置3处；,现取p=7，构造伪随机探查散列表插入前三个关键词值12、24和9以后，接着：插入20，因y1=(4+7)mod8=3，位置3处空闲，故将20存入位置3处；插入15，15可直接存入位置7；插入6，因y1=(6+7)mod8=5，位置5处空闲，故将6存入位置5处；,现取p=7，构造伪随机探查散列表插入前三个关键词值12、24和9以后，接着：插入20，因y1=(4+7)mod8=3，位置3处空闲，故将20存入位置3处；插入15，15可直接存入位置7；插入6，因y1=(6+7)mod8=5，位置5处空闲，故将6存入位置5处；插入5，因y1=(5+7)mod8=4,y2=(4+7)mod8=3,y3=(3+7)mod8=2，故可将5存入位置2处,二次探查法二次探查法使用下列探查序列：h(key),h1(key),h2i-1(key),h2i(key),h2i-1(key)=(h(key)+i2)modMh2i(key)=(h(key)i2)modM,双重散列法从h(K)开始，寻找空地址时，所前进的步长不是固定的，而与K有关，即用=(K)（(K)是另一个杂凑函数），lM（是K的函数），代替线性探查的前进步长1