第7章查找科技学院计算机

••老Office:9栋楼9-206（网络教研室•: 课件：:第7章查哈希表教学内教学目

ASLASLn关关键字的平均比较次数，也称平均搜ASL(AverageSearchn：记录的个pi：查找第i个记录的常认为pi=1/nci：找到第i个记录所需一、顺序查找（线性查找顺序查找（线性查找）使用数組:若查找函数设计如下intseqSeach(inta[],intn,intelem){inti=0;while(i<n&&a[i]!=elem)i++;if(a[i]==elem)returni;elsereturn-}此查找函数正确顺序查找（线性查找）使用数組:若查找函数设计如下intseqSeach(inta[],intn,intelem){inti=0;while(i<n&&a[i]!=elem)i++;if(i<n)returni;elsereturn-}此查找函数才正顺序查 typedefstruct

顺序typedefstruct

//表基

第2章在顺序表L中查找值为e的数#defineMAXSIZEtypedefstructElemTypeint

//指向数据元素 //线性表的当前intLocateELem(SqListL,ElemType{for(i=0;i<if(L.elem[i]==e)returni+1;return0;}改进：把待查关键字key存入表头（“哨兵”），逐个比较，可免去查找过程中每一步都要检测是否查找完毕加快速typedefstruct

intSearch_Seq(SSTableST,KeyTypekey//若成功返回其位置信息，否则返回for(i=ST.length;ST.R[i].key!=key;--i//不用for(i=ni>0;ifor(i=1;i<=nreturn(3/*在顺序表ST中顺序查找关键字等于key的数据元素。若找到，则返该元素在表中的位置；否则返回-intSearch_Seq(SSTableST,KeyTypekey){for(i=0;ST.R[i].key!=key;++i从前往后找if(i<ST.length)returni;elsereturn-1;平均查找长度为确定记录在查找表中的位置，数的期望查找成 nST假定Pi11 nASL查找不成功

(ni1)n2n2ASL=n+平均查找长ASL

(ni1)

1(n1)

3(n2n 顺序查找的性能分 设表中各记录查找概率相ASLs(n)=(1+2+...+n)/n查找不成功时的平均查找长 ASLf顺序查找算法有特 算法简单，对表结构无任何要求（顺序和链式nA1nAS。查找概率查找概率相等时，ASL有序表的顺序个元后的元素的关键字均大于key，所以表 –在有序表中，取中间的记录作为比较对象，如果要查找记2.To10i，，i=T1e当lo<=i：计算中间记录的位置将待查记录的关键字key和R[mid].key进行a．若key=R[mid].key，查找成功，mid素b．若key>r[mid].key，说明若存在要查找的元素，查找表的后半部分。修改查找范围的下界：low=mid+1，转重复以上过程，当low>high时，表示查找失败折半找

若k>R[mid].key，则

51234567895 5lowmid折半

若k>R[mid].key，则

找 5

555

7

lowmid折半直至low>high时，查找失 5low 5high折半查找（非递归算法 初始时，令让k与mid指向的记录比较 –若k==R[mid].key，查找–若k<R[mid].key，则high=mid-–若k>R[mid].key，则重复上述操作，直至low>high折半【算法描述】-算法 elseif(key<ST.R[mid].key)high=mid-1;//前一子表查else //后一子表查}return //表中不存在待查元}Procedurebinsearch(A[],key,low, //第一项数据的索引值小{mid=(lowhigh)/

//计算中间{

//「键值」与「中间值」比较

Case"="return //Casereturnbinsearch(A,keylowmid-1);//递归调用找Casereturnbinsearch(A,keymid+1,high) //递归调用找Return-End

//搜寻失败，传回-折半查找（递归算法intSearch_Bin(SSTableST,KeyTypekey,intlow,int{if(low>high)return0; if(key==ST.elem[mid].key)returnmid;elseif(key<ST.elem[mid].key)Search_Bin(ST,key,low,mid-1);//递Search_Bin(STkey,mid+1,high//}折半查找的性能分析－判定 56

10

外结若所有结点的空指针域设置为一个指向一个方形结点方形结点为判定树的外部结点；对应的，圆形结点为内部结点:6

10内结--

Cost(levelT(ai)pi)((levelT(ei)1)qi

外结ASLASL＝1/11*(1*1＋2×2＋4×3+4*46

10--

外结查找成功时比较次数：为该结点在判定树上的层次数，不超过的深度d=log2n+1=查找不成功的过程就是走了一条从根结点到外部结点的路径dd-1性质4:具有性质4:具有n个结点的完全二叉树的深度必为log2nk-1 k-1k

2k12k2k−1−12k−1−1＜n≤2k−12k−1≤n＜2k所以k=log2n+1注log2n＋1折半查找的性能比顺序查找效率高,时间复杂度O(log2n)。 折半3.折半查找的性能分–假设有序表的长度n=2h-1（反之h=log2(n+1)），度 1 ASLp C

h2h1 ASLn1log(n1) –n>50分块分块分块索引表的类型定义如#definen4typedefstruct{ElemTypeinttypedefstruct{

indexItemint分块值为、、、，分为四个块和索引表，如8分块intSearch_Idx(SSTableST,indexTableID,ElemTypekey){intlow=1,high=ID.length,mid,s,t,found=0;if(k<ID.elem[mid].key)high=mid-1;elseif(k>ID.elem[mid].key)low=mid+1;elsefound=1;low=mid;}/*找到，确定下一步的查找块}//s=ID.elem[low].stadr;//下一步的查找范围定位在第low块else分块if(ST.elem[t].key==k)returnelse{ if(p!=(t+1))returnk;elsereturn分块–分块查找的平均查找长度为索引查找和块内查找的平均查ASLL

b1

s1

s22s –分块查找的优点是在表中插入或删除一个记录时，只要找的空间，以及将初始表分块排序的运算。分块分块查找（块间有序，块内无序。含每个子表的起始地址（即头指针）717189第1 第2 第3分块查找过

分块②确定了待查关键字所在的子表后，在子表内分块查找性能对索引表查找的 对块内查找的ASLbslog2(n1)s (log2nASLbsn1) S为每块内部的记录个数，n/s即块的Sb分块查找优

缺点：要增加一个索引表的空间并对初始索引键键若表中存在，则成功返否则插入关键字等于key的记二叉二叉排序树或是空树，或是满足如下性质的二叉树 其左 本身又各是一棵二叉排序二叉排序下列图形中，哪下列图形中，哪个不是二叉排序树二叉排序练练

得到一个得到一个关键字的递增二叉排序树的操作－查 若大于根结点，查其

在左 上的操作类

【算法思 2若二叉排序树非空，将给定值key与根结点的关键T->data.key②若key小于T->data.key，则进一步查找 ③若key大于T->data.key，则进一步查找 二叉排序树的–二叉排序树用二叉链表 typedefstruct

typedefstructElemType structBSTNode*lchild,*rchild二叉排elseif(key<T->data.key)returnSearchBST(T-//在 中继续查//在 中继续查}//二叉排二叉排序树的操 树中已有，不再树中没有，查找直至某个叶子结点的左或右 为空为止，则插入结点应为该叶子结插插入的元素一定在二叉排序树的操作插入结点

二叉排序树的操{10，18，3，8，12，2， 3 87二叉排二叉排序树不同插入次序的序列生成不同形态的二叉排

二叉排二叉排序树的操防止重 后树的高度增–删除叶结点，只需将其双亲结点指向它的指针清，再释放它即可 –被删结点左、 都存在，可以在它的。查找的性能分 nnpici1223252.2(左图npici1234553(右图n查找的性能分 平均查找长度和二叉树的形态有关，即最好：log2n（形态匀称，与二分查找的判定树相似（n+1)/2（单支树 n

pici(12232)/52.2( npici1234553(n院院练例:3个结点3

Exampleforoptimal

Cost(levelT(ai)pi)((levelT(ei)1)qi searchtreeswithequalWithequalprobabilitiespi=qi=1/7foralli,weCost(tree(a))3*13*13*12*12*11*11*1 Cost(tree(b))2*12*13*13*13*11*11*1 Cost(tree(c))2*12*12*11*12*12*12*1 Cost(tree(d))1*11*13*13*13*12*12*1 Cost(tree(e))1*11*12*12*13*13*13*1 q0 q1q0q1q2q1 ExampleExampleforoptimalbinarysearchtreeswithdifferent(levelT(ai)pi)((levelT(ei)1)qi 3210iCost(tree(a))3*.153*.53*.12*.12*.051*.051*.052.65Cost(tree(b))2*.152*.53*.13*.13*.051*.051*.052.05Cost(tree(c))2*.152*.52*.11*.12*.052*.052*.051.9Cost(tree(d))1*.151*.53*.13*.13*.052*.052*.051.6Cost(tree(e))1*.151*.52*.12*.13*.053*.053*.051.5q0 q1q0q1q2

Cost(levelT(ai)pi)((levelT(ei)1)qi OptimalForagivensetofprobabilities,ourgoalistoconstructabinarysearchtreewhoseexpectedsearchissmallest.Wecallsuchatreeanoptimalbinarysearchtree.平衡二(BalancedBinary是平是平衡二叉所有结点的左、 平衡二叉树(AVL树任一结点的平衡因子只能取：-1、01；如果对于一棵有n个结点的AVL树，其O(log2n)数量级，ASL也保持在O(log2n)量级平衡二叉树(AVL树练习：判断下列二叉树是否AVL- - 0

- 0(a)平衡 (b)不平衡平衡二叉树(AVL树LLRR平衡旋LR平衡旋LLRR平衡旋LR平衡旋RL平衡旋平衡二叉树(AVL树平衡二叉树（BalancedBinary最小不平 的调整方法 平衡二叉树(AVL树最小不平 的调整方法 平衡二叉树(AVL树最小不平 的调整方法 平衡二叉树(AVL树最小不平 的调整方法–双向旋转(先右后左)平衡处理(RL型)：在A的右 中插入新结点造成失衡，则先以C ，进行一次右旋平衡处理，将B作为C的 平衡二叉树(AVL树平衡二叉–在平衡二叉树上进行查找的过程和在二叉排若在A的的若在A的的结点，使A的平衡因子从12，需要进行一次顺时针旋转(以B为旋转轴LLB RR若在A的 的 上插结点，使A的平衡因子从-1增至-2，需要进行一次逆时针旋转 (以B为旋转轴 若在A的 的 上插(以插入的结点C为旋转轴4）RL平衡旋 (以插入的结点C为旋转轴

A A 平衡二叉树(AVL树【调整原LLLRRLRR标线牵涉到三个节点。而三个节点中，将中间键值(一)LL型(Left- (二)RR型(Right-大L中大L中LCAR中R大B B B 小(三)LR型(Left- (四)RL型(Right-大L大LBR中AR大LCCC 小調 中练习：请将下面序列构成一棵平衡二叉排（--需要RR平衡旋 (绕B逆转,B为根0

- 0

需要RL平衡旋(绕C先顺后逆0 0 ConstructanAVLtreeForeachofthefollowinglists,constructanAVLtreebyinsertingtheir a.1,2,3,4,5, b.6,5,4,3,2,c.3,6,5,1,2,a.1,2,3,4,5, b.6,5,4,3,2, c.3,6,5,1,2,a.1,2,3,4,5, b.6,5,4,3,2, c.3,6,5,1,2,B 。(有m/2~m m阶排序树及B树m阶B树符合下列条树根至少有2 ，除非它也是树叶除了树根和树叶之外，其余的内部节点，至少 m/2 所有的树叶都在同一均相同L0K1L1K2 4 f4

g3340

i6369 BBtreeofOrderBB树允许多个键值存放在一个节点。其每个节点内的键值是经过排序的，以方便搜寻。如果节点存放的键值数目达到上限，就成两个新节点，并将中间的键值向上插入其父节点。这种树状结构可保证所有叶节点都处于同一个高logm(n+1)≤ ≤注: BtreeofOrder4--InsertBtree假设输入的数据库为ASEAR,C,HI,NG,X,A,M,P,L,E}，第二个A加入{A,E,S}节点后，将会超过2-3-4树的限制。这时候便要将{AAES}予以，并将其中间值E取出成为父节点。Btree Btree m阶排序树及B树

L0K1L1K2

个可插入点（一定是树叶）412e1821f2427g3340h

i6369j

L0K1L1K2

树叶，同时将中间的键值（第2个）

4 f4

g3340

i6369

m阶排序树及B树abcef2427gabcef2427g3340i6369j74774dL0L0K1L1K2abcef2427hi6369j74774

m阶排序树及B树L0L0K1L1K2abcef2427hi6369j74774加入键值

L0K1L1K2xxabcd B树的方法主要是要应用在大型文件系统中。因为其内存有限，再加上数据量很大时，我们无法一次将整个树状结构加载内存来运算。所以，树状结构会存放在像硬盘这样的装置中，通常每个节点会配置一个单位以方便存取。当B树的节点数越少，高度越低，则存取磁B+在B+树中的节点通常被表示为一组有序的元素和子指针。如果此B+树的序数(order)是m，则除了根之外的每个节点都包含最少m/2个元素最多m-1个元素，对于任意的节点B+B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与B+树背后的想法是内部节点可以有在预定范围内的可变量目的子节点。因此，B+树不需要像其他自平衡二元搜索树B+2-3左子节点所存放数据右子节点所存放数据皆Ldata.keyRdata.key9 2-3log3(n+1)-1≤h≤log2(n+1)-98Constructionofa2-3A2-3treeisalwaysheight-Forthelist9,5,8,3,2,4,2-323树其实就是「3阶的B树」Btreeoforder3。因此在23树上的每个节具有1个键值（2个指标）的节点称为“2-node”（2-节点具有2个键值（3个指标）的节点称为”3-node（3-节点）2–3树的节点结构可 为typedefstruct {

KeyLeft,KeyRight *LinkLeft,*LinkMiddle,}232–3树的节点键值插入，原则如下（与B树同新键值的第一个可插如果树叶的数据字段如果树叶的数据字段已经额满没有空位，则树叶进行节 (split)每次插入最多可能使2–3树的高度h增加12加入22

2-3加入

17 ，键值17加入

78 78

27加入27

72c72148148

节点 72加入5,9, 72014589014589 加入

7 7

节点 013589 01358911 2-3-41左子节点所存放数据右子节点所存放数据皆大于(>)键值Ldata.keyRdata.key左子节点所存放数据皆小于(<)Ldata.key键值中子节点所存放数据皆大于(>)Ldata.key键值和小于Rdata.key键值右子节点所存放数据皆大于(>)Rdata.key12 2-3-42若为4节点类型，只包含三个键值(Ldata.keyMdata.key和Rdata.key)资料和左、、右子节Ldata.keyMdata.keyRdata.key左子节点所存放数据皆小于(<)Ldata.key键值左中子节点所存放数据皆大于(>)Ldata.key键值和小Mdata.key键值右中子节点所存放数据皆大于(>)Mdata.keyRdata.key键值右子节点所存放数据皆大于(>)Rdata.key键键树中所有的树叶节102-3-42-3-4 加入删除

删除插入和删除需要时间为Ologn2-3-4树 234树其实就是「4阶的B树」B-treeoforder4在234树上的每个节点最多有3个键值、4具有1个键值（2个指标）的节点称为“2-node”（2-节点）具有2个键值（3个指标）的节点称为“3-node”（3-节点）具有3个键值（4个指标）的节点称为“4-node（4-节点）。2–3–4树的节点结构 typedefstruct

}234每个节点有2个指标，并且每个指标有2在画出红－黑树时 一个2–node转成1个红－黑树节点，2个 标的Color均为Black 一个3node转成2个红－黑树节点，这2个红－黑树节点以1个Red

或

变种的AVL树 Red-Blacktree,简称RB-它是在1972年由·贝尔发明的，他称之为“对称二LeoJ.Guibas和RobertSedgewick于1978年写的一篇中获得的特点：利用对树中的结点“ 坏情况运行时间，它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目平衡的扩充二叉颜色特征：每个结点为“黑色”或“红色根特征：根结 是“黑色”外部特征：扩充外部叶结点都是空的“黑色”结 PropertiesofaRed-BlackTherootisEveryrednodehasablackAnychildrenofarednodeareblack;thatis,arednodecannothaveredchildren.Everypathfromtheroottoaleafcontainsthesamenumberofblacknodes.AddingEntriestoaRed-BlackAddinganentrytoared-blacktreeresultsinanewredleaf.Thecolorofthisleafcanchangelaterwhenotherentriesareaddedorremoved.Red-blacktree( 树)对树而言，只要所有从根节点到叶节点的路径其所经h≤2lgn 树结 B C和{B,D}互换颜 根节点C必须为黑树的插入与删除…为O(lgn)。也是O(lgn)。116Datastructureofred-black(RedorAred-blacktreewithninternalnodeshasheightatmostJAVA集合框架：TreeSet和 代码参Huffman内部路径长internalpathlength：由树根到每个内部节点的路径长度之总和外部路径长(externalpathlength：由树根到每个外部节点的路径长度之总和 E F G 此树的内部路径长I0A1B1C)2D)外部路径长E2E2F)3G外部路径长：由树根到每个外部节点的路径长乘上该节点 之总此图 外部路径长=2*8(E)+2*7(F)+3*9(G)=对具有相同外部节点同 也相同的不同二元树， 外部路径长也同。其 外部路径长最小的二元树称为Huffman树，或称最佳二元树算法：Huffman法建算法：Huffman法建立编码(编码字母表与频率 当串行中多于一个元素，重复循从串行新，将最小的两 生成一为两 树入串行适当位，使串行仍然维持由和Huffman算法：由已知的外部节点建构Huffman树 外部路长最小的树） 否 Huffman假设有ABCDEF六个树叶， 分别为15,8,30,27,5,将树叶按 ，由小到大排序好，成为一有序串行E/ B/ A/ F/ D/ C/ E B将节点NN/ A/ F/ D/ C/取最左边两个节点N和A，合成新节点 N AE BHuffman将节点P放入有序串行的适当位F/ D/ P/ C/取最左边两个节点F和D，合成新节点 N A FDEEB将节点R放入有序串行的适当位置，使串行保持次序P/ C/ R/取最左边两个节点P和C，合成新节点 FD CN AEEBHuffman将节点S放入有序串行的适当位R/ S/取最左边两个节点R和S，合成新节点T，只剩一个FF D30AEBHuffman６个字母需要编码，分别是A/15B/8C/30,D/27E/5,F/15，合起来刚好100%。我们依照前述Huffman算法建构Huffman树：010F1010F1D0011300E1BAB的编码右左左右=C的编码=右右D的编码=左右E的编码=右左左左=F的编码=左左编码一篇1000个字母的文章。根据字母出现的频率，它们的出现次数分是A出现的次1000*15B出现的次数1000*8C出现的次数=1000*30D出现的次数=1000*27E出现的次数1000*5F出现的次数1000*15因此总共需要的bit150*3+80*4+300*2+270*2+50*4+150*2=编码，每个字母用3个位表示，(8种组合)，共需3000压缩率＝(1 )*100%207.3哈希 哈希

优点：查找速度极快O(1),查找效率与元素个数n例2001120V02001120V0将2001011810231的所有信息存入V[31]单元查找2001011810216的信息，可直 例数数据元素序(14，23399251)若规定个k的 ），出 结。内9内9

232425

39如何内9内9

14

232425

39根据哈希函数 有关哈希方法(杂凑选取某个函数，依该函数按关键字计算元素 位置并按哈希函数(杂凑函数)：哈希方法中使用的转换有关哈希表(杂凑表)：按上述思想构造的地址 9 11 14 232425 39内9冲突：不同的关键码映射到同一个哈希key1key2，但同义词：具有相同函数值的两个关hashfunction:h:U{0,1,…,m-hashtable:T[0…m-khashstoslot:h(k)hashcollision:twokeyshashtothesame哈希函数：H(k)=kmod7

地址应该足够 同义如何

是不可能避制制定一个好的解 方哈希函数的根据元根据元素集合的特性构地址均折叠随机数DirectaddressingisasimpletechniquethatworkswellwhentheuniverseUofkeysisreasonablesmall.SupposethatanapplicationneedsadynamicsetinwhichanelementhasakeydrawnfromtheuniverseU={0,1,…,m-1}wheremisnottoolarge.Weshallassumethatnotwoelementshavethesamekey.Forexample:nnumbers,range:[1,k],usesA[1..k]andletA[i]=i.Disadvantage:Wastingtoomuchextra ysisofAlgorithms-Chapter直接寻址akey+ (a、b为常 缺点：要占用连续地址空间，空间效率低直接寻址哈希函数 除留余数法（最常用重点掌握Hash(key)=keymod (p是一个整数关键：如何选取合适的技巧：设表长为m，取p≤m且为质构造哈希函数考虑的①执行速度（即计算哈希函数所需时间的长的大键字的分 h(k1)=h(k2)thenthereisaGoodhashfunctionsresultinfewerCollisionscanneverbe yTwotypeshandlecollisionsOpenhashing-bucketpointstolinkedlistofallhashingtoClosedhashingonekeyperincaseofcollision,findanotherbucketforoneofthekeysCollisionresolutionlinearprobing:usenextdoublehashing:usesecondhashfunctiontocomputeHashingOpenhashing(separateInopenhashingkeysarestoredinlinkedlistsattachedtocellsofahashingtable.Closedhashing(openThesimplestone–calledlinearprobing,checksthecellfollowingtheonewherethecollision处 的方 1.1.开放寻2.2.链地开放寻址法（开地址法 线性线性二次伪随LinearCheckthecellfollowingtheonewherethecollisionItsufferstheprimaryclusteringh(k,i)(h'(k)i)mod线性探测法linearprobingHi=(Hash(key)+di)mod (1≤i<m其中：m为哈希表 为增量序列1，2，…m-1，且di=i， 一 ，就找下一个空地址存线性探测法linearprobing【作法】是指将哈希地址视为环状的空间，当溢位发生以探测法执行会

碰 345630mod 37mod 40mod②Hash(29)=7，11=8②Hash(29)=7，11=8，哈希地址8为空，因此将29，由H1=(Hash(29)+1)关键码集为{47，7，29，11，16，92，22，8，3}，哈希函数为Hash(key)=keymod 378 3连续移线性探测法的特 解决方案：二次(平方)探测法(quadraticprobingHash(3)=3，哈希地，H1=(Hash(3)+1Hash(3)=3，哈希地，H1=(Hash(3)+12)mod11=4，仍 H2=(Hash(3)-12)mod11=2，找到空的哈希地址，存入关键码集为{47，7，29，11，16，92，22，8，3}， 哈希函数为Hash(key)=keymod11HHi=(Hash(key)±di)mod其中：m为哈希表长度，m要求是某个4k+3 3 二次(平方)探测法(quadraticprobing)(有些【作法当f(x)的地址发生地址 f(xi2modbf(xi2modb的来找地址，而i是代表第i (碰撞)，并且1<=i<=(b-1)/2，b是质数。平方【范例】假设有一串数列15,29,52,80，并设b=13，其哈希函数H(X)=Xmodb，请利用平方探测法来解 的问题【解答H(80)=80mod13=2产生地 (第1次碰撞进行溢位处理：H(xi2mod第1次处理：(2+12)mod13=3又产 (第2次碰撞第2次处理：(2+22mod13=63434567XX80第2次碰80第1次碰伪随机探测 Hi=(Hash(key)+di)mod其中：m为哈di为随机

(1≤i<m开放地址法建立哈希表步 step1数据元素的关键字key，计算其哈 step2根据选择的 址仍被占用，则继续执行step2，直到找到 DoubleDoublehashingrepresentsanimprovementoverlinearandquadraticprobinginthatprobesequenceareused.Itsperformanceismoreclosedtouniformhashing.h(k,i)(1(k)ih2(k))modSomefunctions mendedintheliteratureare:h2(k)=(m-2)-kmod(m-2)forsmalltablesorh2(k)=8-(kmod8)h2(k)=kmod97+ forlargeDoubleh(k,i)(1(k)ih2(k))modh1(k)=kmodh2(k)=1+(kmodInserti=0,h1(14)=1,h2(14)=i=1,h(14,1)=(h1(14)+1h2(14))mod13=i=2,h(14,2)=(h1(14)+2h2(14))mod13=2.链地址法(拉链法链表的表头指针起来，形成一个动态的结构^^0^^^ ^^^3^^4^^^6^^^^^8^^^^

链地址法建立哈希表step1取数据元素的关键字key，计算其哈空，则将该元素插入此链表；否则执行step2解决。step2根据选择的处理方法，计算关键字key的下一个地址。若该地址对应的•••非同义词不，无链表上结点空间动态申请，更适合于表长不定的链地址法的哈希给定值给定值与关键字比给定k计算Y此地址查找查找Y关键字查找查找成按按处方法计算哈希哈希已已知一组关键字哈希函数为：H(key)=keyMOD13希表长为m=16，用线性探测再散列处 ，即Hi=(H(key)+di)MOD 11 1 311 9 1

，H1=(1+1)

哈希用链地址法处

关键字^^0^^^ ^^^3^^4^^^6^^7^^8^^^^^^思关键字无无序表查找有有序表折半查找Fortheinput30,20,56,75,31,19andhashfunctionh(K)=KmodConstructtheopenhashtable(separateFindthelargestnumberofkeycomparisonsinasuccessfulsearchinthisFindtheaveragenumberofkeycomparisonsinasuccessfulsearchinthisFortheinput30,20,56,75,31,19andhashfunctionh(K)=KmodConstructtheclosedhashtable(openaddressing,i.e.linearFindthelargestnumberofkeycomparisonsinasuccessfulsearchinthisFindtheaveragenumberofkeycomparisonsinasuccessfulsearchinthisysisofhashingwith slots load

m(theaveragenumberofelementsstoredina哈希表的查

使用平均查找长度ASL来衡量查找算法，ASL哈希函处 的方越大，表中记录数越多，说明表装得越满，发生的可能性就越大，查找哈希表的查找效率分 ASL与装填因子ASL与装填因子有关！既不是严格的O(1)，也不是ASL1 2ASL1 1ASL1ln(1)

）Inparticular,theaveragenumberofpointers(chainlinks)inspectedinsuccessfulsearch,1+/2,andanunsuccessfulsearch,.Ifahashtableinwhichcollisionareresolvedbychaining,asuccessfulsearchtakestime,(1+/2)ontheaverage,andunsuccessfulsearchtakestime,()ontheaverage,undertheassumptionofsimpleuniformhashing.1n

1n Xij

1 E[Xij j

ni j 1n 1

Totaltimerequiredasuccessful 1

n

ji1mn

(1 )(1 1 (nnm1 1 ninm i11

1n2n(n1) nm 1 ysisofopen-addressGivenanopen-addresshash-tablewithloadfactor=n/m<1,theexpectednumberofprobesinanunsuccessfulsearchisatmost1/(1-)assuminguniformhashing.

pi=Pr{exactlyiprobesaccessoccupiedslotsfor0in.Andpi=0ifi>Theexpectednumberofprobes

1

ipiiqi=Pr{atleastiprobesaccessoccupiedslots ipiqi E[X]iPr{Xi i(Pr{Xi}Pr{Xi iPr{Xi

i

nq1

mq n ni n

if0i ) ) m mi qi=0fori> 1ip1q1

... i

i

1Givenanopen-addresshashtablewithload,theexpectednumberofsuccessfulsearchis

1 1 assuminguniformhashingandassumingthateachkeyinthetableisequallylikelytobesearched>Asearchforkfollowsthesameprobesequenceasfollowedwhenkwasinserted.Ifkisthe(i+1)thkeyinsertedinthehashtable,theexpectednumberofprobesmadeinasearchforkisatmost 1i

miAveragingoverallnkeyinthehashtablegivesustheaveragenumberofprobesinasuccessfulsearch:1 m (HmHm1ni0m ni0m 1(lnm1ln(m(SincelniHilni1 11 m 1 0kSeth(k)=kmInterpretingkeysasnaturalASCII(p,t)=(112,116)=(112128+116)=几点链地址法除留余数法作哈希函数优于