??老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 –分塊查找的優(yōu)點是在表中插入或刪除一個記錄時，只要找的空間，以及將初始表分塊排序的運算。分塊分塊查找（塊間有序，塊內無序。含每個子表的起始地址（即頭指針）717189第1 第2 第3分塊查找過

分塊②確定了待查關鍵字所在的子表后，在子表內分塊查找性能對索引表查找的 對塊內查找的ASLbslog2(n1)s (log2nASLbsn1) S為每塊內部的記錄個數，n/s即塊的Sb分塊查找優(yōu)

缺點：要增加一個索引表的空間并對初始索引鍵鍵若表中存在，則成功返否則插入關鍵字等于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-//在 中繼續(xù)查//在 中繼續(xù)查}//二叉排二叉排序樹的操 樹中已有，不再樹中沒有，查找直至某個葉子結點的左或右 為空為止，則插入結點應為該葉子結插插入的元素一定在二叉排序樹的操作插入結點

二叉排序樹的操{10，18，3，8，12，2， 3 87二叉排二叉排序樹不同插入次序的序列生成不同形態(tài)的二叉排

二叉排二叉排序樹的操防止重 后樹的高度增–刪除葉結點，只需將其雙親結點指向它的指針清，再釋放它即可 –被刪結點左、 都存在，可以在它的。查找的性能分 nnpici1223252.2(左圖npici1234553(右圖n查找的性能分 平均查找長度和二叉樹的形態(tài)有關，即最好：log2n（形態(tài)勻稱，與二分查找的判定樹相似（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標線牽涉到三個節(jié)點。而三個節(jié)點中，將中間鍵值(一)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 ，除非它也是樹葉除了樹根和樹葉之外，其余的內部節(jié)點，至少 m/2 所有的樹葉都在同一均相同L0K1L1K2 4 f4

g3340

i6369 BBtreeofOrderBB樹允許多個鍵值存放在一個節(jié)點。其每個節(jié)點內的鍵值是經過排序的，以方便搜尋。如果節(jié)點存放的鍵值數目達到上限，就成兩個新節(jié)點，并將中間的鍵值向上插入其父節(jié)點。這種樹狀結構可保證所有葉節(jié)點都處于同一個高logm(n+1)≤ ≤注: BtreeofOrder4--InsertBtree假設輸入的數據庫為ASEAR,C,HI,NG,X,A,M,P,L,E}，第二個A加入{A,E,S}節(jié)點后，將會超過2-3-4樹的限制。這時候便要將{AAES}予以，并將其中間值E取出成為父節(jié)點。Btree Btree m階排序樹及B樹

L0K1L1K2

個可插入點（一定是樹葉）412e1821f2427g3340h

i6369j

L0K1L1K2

樹葉，同時將中間的鍵值（第2個）

4 f4

g3340

i6369

m階排序樹及B樹abcef2427gabcef2427g3340i6369j74774dL0L0K1L1K2abcef2427hi6369j74774

m階排序樹及B樹L0L0K1L1K2abcef2427hi6369j74774加入鍵值

L0K1L1K2xxabcd B樹的方法主要是要應用在大型文件系統中。因為其內存有限，再加上數據量很大時，我們無法一次將整個樹狀結構加載內存來運算。所以，樹狀結構會存放在像硬盤這樣的裝置中，通常每個節(jié)點會配置一個單位以方便存取。當B樹的節(jié)點數越少，高度越低，則存取磁B+在B+樹中的節(jié)點通常被表示為一組有序的元素和子指針。如果此B+樹的序數(order)是m，則除了根之外的每個節(jié)點都包含最少m/2個元素最多m-1個元素，對于任意的節(jié)點B+B+樹的特點是能夠保持數據穩(wěn)定有序，其插入與修改擁有較穩(wěn)定的對數時間復雜度。B+樹元素自底向上插入，這與B+樹背后的想法是內部節(jié)點可以有在預定范圍內的可變量目的子節(jié)點。因此，B+樹不需要像其他自平衡二元搜索樹B+2-3左子節(jié)點所存放數據右子節(jié)點所存放數據皆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樹上的每個節(jié)具有1個鍵值（2個指標）的節(jié)點稱為“2-node”（2-節(jié)點具有2個鍵值（3個指標）的節(jié)點稱為”3-node（3-節(jié)點）2–3樹的節(jié)點結構可 為typedefstruct {

KeyLeft,KeyRight *LinkLeft,*LinkMiddle,}232–3樹的節(jié)點鍵值插入，原則如下（與B樹同新鍵值的第一個可插如果樹葉的數據字段如果樹葉的數據字段已經額滿沒有空位，則樹葉進行節(jié) (split)每次插入最多可能使2–3樹的高度h增加12加入22

2-3加入

17 ，鍵值17加入

78 78

27加入27

72c72148148

節(jié)點 72加入5,9, 72014589014589 加入

7 7

節(jié)點 013589 01358911 2-3-41左子節(jié)點所存放數據右子節(jié)點所存放數據皆大于(>)鍵值Ldata.keyRdata.key左子節(jié)點所存放數據皆小于(<)Ldata.key鍵值中子節(jié)點所存放數據皆大于(>)Ldata.key鍵值和小于Rdata.key鍵值右子節(jié)點所存放數據皆大于(>)Rdata.key12 2-3-42若為4節(jié)點類型，只包含三個鍵值(Ldata.keyMdata.key和Rdata.key)資料和左、、右子節(jié)Ldata.keyMdata.keyRdata.key左子節(jié)點所存放數據皆小于(<)Ldata.key鍵值左中子節(jié)點所存放數據皆大于(>)Ldata.key鍵值和小Mdata.key鍵值右中子節(jié)點所存放數據皆大于(>)Mdata.keyRdata.key鍵值右子節(jié)點所存放數據皆大于(>)Rdata.key鍵鍵樹中所有的樹葉節(jié)102-3-42-3-4 加入刪除

刪除插入和刪除需要時間為Ologn2-3-4樹 234樹其實就是「4階的B樹」B-treeoforder4在234樹上的每個節(jié)點最多有3個鍵值、4具有1個鍵值（2個指標）的節(jié)點稱為“2-node”（2-節(jié)點）具有2個鍵值（3個指標）的節(jié)點稱為“3-node”（3-節(jié)點）具有3個鍵值（4個指標）的節(jié)點稱為“4-node（4-節(jié)點）。2–3–4樹的節(jié)點結構 typedefstruct

}234每個節(jié)點有2個指標，并且每個指標有2在畫出紅－黑樹時 一個2–node轉成1個紅－黑樹節(jié)點，2個 標的Color均為Black 一個3node轉成2個紅－黑樹節(jié)點，這2個紅－黑樹節(jié)點以1個Red

或

變種的AVL樹 Red-Blacktree,簡稱RB-它是在1972年由·貝爾發(fā)明的，他稱之為“對稱二LeoJ.Guibas和RobertSedgewick于1978年寫的一篇中獲得的特點：利用對樹中的結點“ 壞情況運行時間，它可以在O(logn)時間內做查找，插入和刪除，這里的n是樹中元素的數目平衡的擴充二叉顏色特征：每個結點為“黑色”或“紅色根特征：根結 是“黑色”外部特征：擴充外部葉結點都是空的“黑色”結 PropertiesofaRed-BlackTherootisEveryrednodehasablackAnychildrenofarednodeareblack;thatis,arednodecannothaveredchildren.Everypathfromtheroottoaleafcontainsthesamenumberofblacknodes.AddingEntriestoaRed-BlackAddinganentrytoared-blacktreeresultsinanewredleaf.Thecolorofthisleafcanchangelaterwhenotherentriesareaddedorremoved.Red-blacktree( 樹)對樹而言，只要所有從根節(jié)點到葉節(jié)點的路徑其所經h≤2lgn 樹結 B C和{B,D}互換顏 根節(jié)點C必須為黑樹的插入與刪除…為O(lgn)。也是O(lgn)。116Datastructureofred-black(RedorAred-blacktreewithninternalnodeshasheightatmostJAVA集合框架：TreeSet和 代碼參Huffman內部路徑長internalpathlength：由樹根到每個內部節(jié)點的路徑長度之總和外部路徑長(externalpathlength：由樹根到每個外部節(jié)點的路徑長度之總和 E F G 此樹的內部路徑長I0A1B1C)2D)外部路徑長E2E2F)3G外部路徑長：由樹根到每個外部節(jié)點的路徑長乘上該節(jié)點 之總此圖 外部路徑長=2*8(E)+2*7(F)+3*9(G)=對具有相同外部節(jié)點同 也相同的不同二元樹， 外部路徑長也同。其 外部路徑長最小的二元樹稱為Huffman樹，或稱最佳二元樹算法：Huffman法建算法：Huffman法建立編碼(編碼字母表與頻率 當串行中多于一個元素，重復循從串行新，將最小的兩 生成一為兩 樹入串行適當位，使串行仍然維持由和Huffman算法：由已知的外部節(jié)點建構Huffman樹 外部路長最小的樹） 否 Huffman假設有ABCDEF六個樹葉， 分別為15,8,30,27,5,將樹葉按 ，由小到大排序好，成為一有序串行E/ B/ A/ F/ D/ C/ E B將節(jié)點NN/ A/ F/ D/ C/取最左邊兩個節(jié)點N和A，合成新節(jié)點 N AE BHuffman將節(jié)點P放入有序串行的適當位F/ D/ P/ C/取最左邊兩個節(jié)點F和D，合成新節(jié)點 N A FDEEB將節(jié)點R放入有序串行的適當位置，使串行保持次序P/ C/ R/取最左邊兩個節(jié)點P和C，合成新節(jié)點 FD CN AEEBHuffman將節(jié)點S放入有序串行的適當位R/ S/取最左邊兩個節(jié)點R和S，合成新節(jié)點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哈希 哈希

優(yōu)點：查找速度極快O(1),查找效率與元素個數n例2001120V02001120V0將2001011810231的所有信息存入V[31]單元查找2001011810216的信息，可直 例數數據元素序(14，23399251)若規(guī)定個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為常 缺點：要占用連續(xù)地址空間，空間效率低直接尋址哈希函數 除留余數法（最常用重點掌握Hash(key)=keymod (p是一個整數關鍵：如何選取合適的技巧：設表長為m，取p≤m且為質構造哈希函數考慮的①執(zhí)行速度（即計算哈希函數所需時間的長的大鍵字的分 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【作法】是指將哈希地址視為環(huán)狀的空間，當溢位發(fā)生以探測法執(zhí)行會

碰 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連續(xù)移線性探測法的特 解決方案：二次(平方)探測法(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ā)生地址 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根據選擇的 址仍被占用，則繼續(xù)執(zhí)行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.鏈地址法(拉鏈法鏈表的表頭指針起來，形成一個動態(tài)的結構^^0^^^ ^^^3^^4^^^6^^^^^8^^^^

鏈地址法建立哈希表step1取數據元素的關鍵字key，計算其哈空，則將該元素插入此鏈表；否則執(zhí)行step2解決。step2根據選擇的處理方法，計算關鍵字key的下一個地址。若該地址對應的???非同義詞不，無鏈表上結點空間動態(tài)申請，更適合于表長不定的鏈地址法的哈希給定值給定值與關鍵字比給定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哈希函處 的方越大，表中記錄數越多，說明表裝得越滿，發(fā)生的可能性就越大，查找哈希表的查找效率分 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)=幾點鏈地址法除留余數法作哈希函數優(yōu)于