第8章(查找表)

1、第八章第八章 查找表查找表 基本概念基本概念 靜態(tài)查找表靜態(tài)查找表 動態(tài)查找表動態(tài)查找表 Hash Hash法法 查找表：查找表：用于查找的數(shù)據(jù)元素集合稱為查找表。查找用于查找的數(shù)據(jù)元素集合稱為查找表。查找表由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成表由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成。 是一種以集合為邏輯結(jié)構(gòu)，以查找為核是一種以集合為邏輯結(jié)構(gòu)，以查找為核 心運算，同時包心運算，同時包括其他運算的數(shù)據(jù)結(jié)構(gòu)。括其他運算的數(shù)據(jù)結(jié)構(gòu)。 基本概念基本概念靜態(tài)查找表靜態(tài)查找表：若只對查找表進(jìn)行如下兩種操作：若只對查找表進(jìn)行如下兩種操作：（1）在查找表中查看某個特定的數(shù)據(jù)元素是否在查找表中，）在查找表中查看某個特

2、定的數(shù)據(jù)元素是否在查找表中，（2）檢索某個特定元素的各種屬性，）檢索某個特定元素的各種屬性，則稱這類查找表為靜態(tài)查找表。則稱這類查找表為靜態(tài)查找表。靜態(tài)查找表在查找過程中查找表本身不發(fā)生變化。靜態(tài)查找表在查找過程中查找表本身不發(fā)生變化。對靜態(tài)查找表進(jìn)行的查找操作稱為靜態(tài)查找。對靜態(tài)查找表進(jìn)行的查找操作稱為靜態(tài)查找。動態(tài)查找表動態(tài)查找表：若在查找過程中可以將查找表中不存在的：若在查找過程中可以將查找表中不存在的數(shù)據(jù)元素插入，或者從查找表中刪除某個數(shù)據(jù)元素，則稱這類數(shù)據(jù)元素插入，或者從查找表中刪除某個數(shù)據(jù)元素，則稱這類查找表為動態(tài)查找表。動態(tài)查找表在查找過程中查找表可能會查找表為動態(tài)查找表。動態(tài)查

3、找表在查找過程中查找表可能會發(fā)生變化。對動態(tài)查找表進(jìn)行的查找操作稱為動態(tài)查找。發(fā)生變化。對動態(tài)查找表進(jìn)行的查找操作稱為動態(tài)查找。 查找表查找表靜態(tài)查找表靜態(tài)查找表動態(tài)查找表動態(tài)查找表1.建表：建表：Create(st)2.查找：查找：Search(st,k)3.讀表元：讀表元：Get(st,pos)2.查找：查找：Search(st,k)3.讀表元：讀表元：Get(st,pos)1.初始化：初始化：Initiate(st)4.插入：插入：Insert(st,k)5.刪除：刪除：Delete(st,k)22121398334244382448605874471234567891011121314

4、15第一塊第一塊第二塊第二塊第三塊第三塊1611224474關(guān)鍵字表關(guān)鍵字表小小大大指針表指針表: :應(yīng)該指向各塊的第一個關(guān)鍵字。應(yīng)該指向各塊的第一個關(guān)鍵字。分成三塊分成三塊每塊每塊5 5個個關(guān)鍵字關(guān)鍵字分塊查找的方法分塊查找的方法: :1)1)由于索引表按關(guān)鍵字有序，則確定由于索引表按關(guān)鍵字有序，則確定k k在哪一塊的查找在哪一塊的查找 可以用順序查找，也可用折半查找?？梢杂庙樞虿檎遥部捎谜郯氩檎?。 (1)動態(tài)查找(2)ASL(3)二叉排序樹(4)平衡二叉樹例如，由關(guān)鍵字值序列（62,15,68,46,65,12,57,79,35）構(gòu)成的一棵二叉排序樹如圖7-4所示。如對上述二叉排序樹進(jìn)行

5、中根遍歷可以得到一個關(guān)鍵字有序序列如對上述二叉排序樹進(jìn)行中根遍歷可以得到一個關(guān)鍵字有序序列（12, 15, 35,46, 57,62,65,68,79），這是二叉排序樹的一個重要特征），這是二叉排序樹的一個重要特征，也正是由此將其稱為，也正是由此將其稱為二叉排序樹二叉排序樹 “二叉排序樹的構(gòu)造方法：二叉排序樹的構(gòu)造方法：設(shè)設(shè)R=R1,R2,Rn為一數(shù)列為一數(shù)列,按下面的原按下面的原則建立二叉樹：則建立二叉樹：1)令令R1為二叉樹的根；為二叉樹的根；2)若若R2R1，則令，則令R2為為R1的左子樹的根結(jié)的左子樹的根結(jié)點，否則令點，否則令R2為為 R1的右子樹的根結(jié)點；的右子樹的根結(jié)點；3)對對R

6、3,R4,Rn重復(fù)上述步驟重復(fù)上述步驟2)；例：給定例：給定R=10,18,3,8,12,2,7,3R=10,18,3,8,12,2,7,3按上面的原則構(gòu)造二按上面的原則構(gòu)造二 叉排序樹如下：叉排序樹如下：R2R1R310R1R1為根節(jié)點為根節(jié)點R3R1R3R1R2R2R2比比R1R1大大R4R4R1 R4R3 R4R3 右邊右邊R5R5R1 R5R1 右邊右邊R5R2 R5R2 左邊左邊R6R6R1 R6R1 左邊左邊R6R3 R6R3 左邊左邊R710181018310183810183812101838122101838122710183812273R8R7R1 R7R3 R7R3 右邊

7、右邊R&R4 R&R4 左邊左邊R8R1 R8R3 R8R3 右邊右邊R8R4 R8R4 左邊左邊R8R7 R8key != k )if (k key ) p = p - lchild;else p = p - rchild; return ( p); 已知46,57,84,32,73,36,15,48,90,20要求:(1)按鍵值排列次序構(gòu)造一棵二叉排序樹.(2)在等概率的情況下,該二叉排序樹查找成功的平均查找長度.(3)針對上述十個鍵值,對于不同的排列次序,構(gòu)造不同形態(tài)的二叉排序樹中,最好和最壞的情況下,二叉排序樹的高度各是多少?平衡二叉樹平衡二叉樹(balanced bi

8、nary tree)平衡二叉樹平衡二叉樹：或者是一棵空樹，或者是具有下列性質(zhì)的或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過樹和右子樹的深度之差的絕對值不超過1 1。平衡因子平衡因子：二叉樹中任一結(jié)點的左子樹的深度與它的右二叉樹中任一結(jié)點的左子樹的深度與它的右子樹的深度之差稱為平衡因子。子樹的深度之差稱為平衡因子。例例: :2-1=12-1=10-0=00-0=01-0=11-0=10-0=00-0=0平衡二叉樹平衡二叉樹2-3=-12-3=-1ABCDFG1-1=01-1=

9、00-0=00-0=00-2=-20-2=-21-0=11-0=10-0=00-0=00-0=00-0=0非平衡二叉樹非平衡二叉樹ABCDE二叉排序樹的平衡化二叉排序樹的平衡化 假設(shè)表中的關(guān)鍵字序列為假設(shè)表中的關(guān)鍵字序列為(13,24,37,90,53)(13,24,37,90,53)空樹和一個結(jié)點空樹和一個結(jié)點 的的二叉樹顯然是平衡二叉樹二叉樹顯然是平衡二叉樹 . .插入插入2424后仍平衡后仍平衡131324-10 插入插入 后結(jié)點后結(jié)點 的平衡因子為的平衡因子為0-2=-20-2=-2，不平衡，不平衡把把 從從 的右下側(cè)的右下側(cè)左轉(zhuǎn)到左轉(zhuǎn)到 的右上側(cè)的右上側(cè)原來原來 的左為的左為 的右的

10、右, ,新的新的 的左為的左為1324 24370-1-1-2-2RRRR型即逆時針旋轉(zhuǎn)型即逆時針旋轉(zhuǎn)371313243724131324132413 插入插入90,5390,53后后, ,又失去平衡又失去平衡, , 可經(jīng)過下列步驟轉(zhuǎn)化為平衡二叉樹可經(jīng)過下列步驟轉(zhuǎn)化為平衡二叉02_101324379053 第一次旋轉(zhuǎn)第一次旋轉(zhuǎn)( (順時針順時針) )以以 為軸心為軸心, ,把把 從從 的右上的右上, ,轉(zhuǎn)到轉(zhuǎn)到的右下的右下, , 的右是的右是 , , 的右為的右為 , ,原原 的右變成新的右變成新 的左。的左。RLRL型的第一次旋轉(zhuǎn)型的第一次旋轉(zhuǎn)( (順時針順時針)

11、)1324539037RLRL型的第二次旋轉(zhuǎn)型的第二次旋轉(zhuǎn)( (逆時針逆時針) ) 以以 為軸心為軸心, ,把把 從從 的左上轉(zhuǎn)到的左上轉(zhuǎn)到 的左下的左下, ,使得使得 的左的左是是 ; ;右是右是 ，原，原 的左變成了的左變成了 的右。的右。53905353375353905390533753535337905337 一般情況下，假設(shè)由于二叉排序樹上插入結(jié)點而失去一般情況下，假設(shè)由于二叉排序樹上插入結(jié)點而失去平衡的最小子樹的根結(jié)點指針為平衡的最小子樹的根結(jié)點指針為a a（即（即a a是離插入結(jié)點最是離插入結(jié)點最近近, ,且平衡因子絕對值超過且平衡因子絕對值超過1 1的祖先結(jié)點），則失去平衡的

12、祖先結(jié)點），則失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為下列四種情況后進(jìn)行調(diào)整的規(guī)律可歸納為下列四種情況: : RRRR型平衡旋轉(zhuǎn)型平衡旋轉(zhuǎn): :ba br a1 b1RRab a1 b1 br-2-1hh-1h-1插入節(jié)點插入節(jié)點 把結(jié)點把結(jié)點b b從從a a的右下側(cè)逆時針的右下側(cè)逆時針( (左轉(zhuǎn)左轉(zhuǎn)) )轉(zhuǎn)到轉(zhuǎn)到a a的右上側(cè)，的右上側(cè)，原原b b的左成為的左成為a a的右，新的右，新b b的左為的左為a a 0hh-10h-12.LL2.LL型平衡旋轉(zhuǎn)型平衡旋轉(zhuǎn): :LL21hh-1h-1ab ar br b1a b1 br ar00 把結(jié)點把結(jié)點b b從左下側(cè)順轉(zhuǎn)從左下側(cè)順轉(zhuǎn)( (右轉(zhuǎn)右轉(zhuǎn)) )

13、轉(zhuǎn)到轉(zhuǎn)到a a的左上側(cè)的左上側(cè), ,原原b b的右的右成為成為a a的左的左, ,新新b b的右為的右為a a。3.RL3.RL型平衡旋轉(zhuǎn)型平衡旋轉(zhuǎn): :-21h-11h-1 a1 c c1 cr brh-1h-2RL(RL(順時針順時針) ) c1 a1 cr brbabacb hh-1h-1h-2h-1h-1-1-1-2 以以c c為軸心，把為軸心，把b b從從c c的右上側(cè)順時針（右轉(zhuǎn)的右上側(cè)順時針（右轉(zhuǎn)) )到到c c的右的右下側(cè)，從而下側(cè)，從而a a的右是的右是c c，c c的右是的右是b b，原，原c c的右變成的右變成b b的左。的左。 以以c c為軸心，把為軸心，把a a從從c

14、 c的左上方，轉(zhuǎn)到的左上方，轉(zhuǎn)到c c的左下方，使的左下方，使得得c c的左是的左是a a，右是，右是b b，原，原c c的左子樹變成的左子樹變成a a的右。的右。RL(RL(逆時針逆時針) ) c1 a1 cr br4.LR4.LR型平衡旋轉(zhuǎn)型平衡旋轉(zhuǎn): :cab 以以c c為軸心把為軸心把b b從從c c的左上側(cè)，逆時針（左轉(zhuǎn)）到的左上側(cè)，逆時針（左轉(zhuǎn)）到c c的左的左下側(cè)，從而下側(cè)，從而a a的左是的左是c,cc,c的左是的左是b b，原，原c c的左變成新的左變成新b b的右。的右。 c1 a1 cr bracbh-1h-2h-1h-1-1-1-2h-1h-2h-1-100LR(LR(

15、逆時針逆時針) ) c1 ar cr bl2-11h-1h-1h-2 ar c1 cr b1h-1LR(LR(順時針順時針) ) c1 ar cr bl 再以再以c c為軸心，把為軸心，把a a從從c c的左上方轉(zhuǎn)到的左上方轉(zhuǎn)到c c的右下方，使得的右下方，使得c c的右是的右是a a，左是，左是b b，原，原c c的右子樹變成的右子樹變成a a的左。的左。abcacbcbah-1h-1h-2h-1022a c1 ar cr blcbh-1h-1h-2h-1022h-10h-2h-1-10將8,6,3,1,2,5,9,7,4中的數(shù)依次插入到時一棵空的平衡二叉排序樹中,求在等概率的情況下,查找成

16、功的平均檢索長度,查找失敗時對鍵值的最多 比較次數(shù).B-B-樹樹B-B-樹：一棵樹：一棵m m階的階的B-B-樹，或為空樹，或為具有下列性質(zhì)樹，或為空樹，或為具有下列性質(zhì) 的的m m叉樹：叉樹： 1)1)樹中每個結(jié)點有樹中每個結(jié)點有mm個兒子；個兒子； 2)2)除根和葉子結(jié)點之外的結(jié)點有除根和葉子結(jié)點之外的結(jié)點有Upper(m/2)Upper(m/2)個兒子；個兒子； 3)3)根結(jié)點至少要有兩個兒子根結(jié)點至少要有兩個兒子( (除非它本身又是一個除非它本身又是一個 葉子葉子) )； 4)4)所有的非終端結(jié)點中包含下列信息數(shù)據(jù)所有的非終端結(jié)點中包含下列信息數(shù)據(jù)(n,A(n,A0 0 , , k k

17、1 1 ,A ,A1 1 , , k k2 2 ,k,kn n ,A,An n) )； n n：本結(jié)點中關(guān)鍵字的個數(shù)：本結(jié)點中關(guān)鍵字的個數(shù)m-1m-1 k ki i ：關(guān)鍵字，從左到右其值按遞增次序排列：關(guān)鍵字，從左到右其值按遞增次序排列 A Ai i ：指向一個所有關(guān)鍵字都在：指向一個所有關(guān)鍵字都在k ki i和和k ki+1i+1間的子樹形間的子樹形 5)5)所有的葉子結(jié)點都在同一層次上，并且不帶信所有的葉子結(jié)點都在同一層次上，并且不帶信 息息( (可以看作是查找失敗的結(jié)點，實際上這些結(jié)可以看作是查找失敗的結(jié)點，實際上這些結(jié) 點不存在，指向這些結(jié)點的指針為空點不存在，指向這些結(jié)點的指針為空

18、) )；118111127135139199243783475364abcdefgh上圖中上圖中, ,結(jié)點形式為結(jié)點形式為: :n n 指針指針 關(guān)鍵字關(guān)鍵字 指針指針 關(guān)鍵字關(guān)鍵字.p0p0k1k1p1p1k2k2 每一個結(jié)點每一個結(jié)點( (除了根結(jié)點和葉子除了根結(jié)點和葉子),),有有Upper(4/2)Upper(4/2)到到4 4個兒子，個兒子，所以可以有所以可以有1 1，2 2或或3 3個關(guān)鍵字，根結(jié)點允許有個關(guān)鍵字，根結(jié)點允許有1 1至至3 3關(guān)鍵字，此時關(guān)鍵字，此時所有的所有的葉子都在第四層上。葉子都在第四層上。例：下圖所是為一棵例：下圖所是為一棵4階的階的B-樹，深度為樹，深度為

19、4在在B-B-樹上進(jìn)行查找所需時間的分析樹上進(jìn)行查找所需時間的分析 從上述過程可知，在從上述過程可知，在B-B-樹上進(jìn)行查找所需時間取決于兩個因樹上進(jìn)行查找所需時間取決于兩個因素：素： 等于給定值的關(guān)鍵字所在的層次數(shù)等于給定值的關(guān)鍵字所在的層次數(shù); ; 結(jié)點中關(guān)鍵字的數(shù)目。結(jié)點中關(guān)鍵字的數(shù)目。( (較大時可用折半查找較大時可用折半查找) ) 顯然，節(jié)點所在的最大層次數(shù)即為樹的深度。那么，含有顯然，節(jié)點所在的最大層次數(shù)即為樹的深度。那么，含有N N個個關(guān)鍵字的關(guān)鍵字的m m階階B-B-樹的最大深度是多少？樹的最大深度是多少？ 根據(jù)根據(jù)B-B-樹的定義樹的定義 第一層至少有第一層至少有1 1個結(jié)點

20、個結(jié)點 第二層至少有第二層至少有2 2個結(jié)點個結(jié)點 第三層至少有第三層至少有2 2* * m/2 m/2 個結(jié)點個結(jié)點 ( (因為除根之外的每個非終端結(jié)點至少有因為除根之外的每個非終端結(jié)點至少有 m/2 m/2 個個) ) 第四層至少有第四層至少有2 2* * m/2 m/2 2 2個結(jié)點個結(jié)點最末層最末層L+1L+1層有層有2 2* * m/2 m/2 L-1L-1個結(jié)點個結(jié)點 ( (因為最末層為葉子因為最末層為葉子,m,m階階B B樹中有樹中有N N個關(guān)鍵字個關(guān)鍵字, ,則葉子結(jié)點為則葉子結(jié)點為N+1N+1個個, ,由此有由此有 N+12N+12* *( m/2 )( m/2 )L-1L-

21、1 N+1N+12 2 ( m/2 )( m/2 )L-1L-1兩邊取對數(shù)兩邊取對數(shù)log( )log( )N+1N+12 2 (L-1)(L-1)log( m/2 )log( m/2 )L-1L-1log( )log( )N+1N+12 2log( m/2 )log( m/2 )換底換底= =log ( )log ( )m/2m/2N+1N+12 2loglogm/2m/22 2log ( )log ( )m/2m/2m/2m/2loglogm/2m/22 2= =log ( )log ( )m/2m/2N+1N+12 21 1log ( )log ( )m/2m/2N+1N+12 2LL

22、log ( )log ( )m/2m/2N+1N+12 2+1+1 這就是說，在含有這就是說，在含有N N個關(guān)鍵字的個關(guān)鍵字的B-B-樹上，進(jìn)行查找時，從根樹上，進(jìn)行查找時，從根j j結(jié)點到關(guān)鍵字所在結(jié)點的路徑上涉及的結(jié)點數(shù)不超過結(jié)點到關(guān)鍵字所在結(jié)點的路徑上涉及的結(jié)點數(shù)不超過log ( )log ( )m/2m/2N+1N+12 2+1+1 個個例如例如: :當(dāng)當(dāng)N=1999998N=1999998且且m=199m=199時時,L,L最多為最多為3 3。 這就是說，在最壞情況下，一次查找至多需要存取這就是說，在最壞情況下，一次查找至多需要存取3 3個結(jié)點。個結(jié)點。B-B-樹的插入：樹的插入：

23、B-B-樹的生成也是從空樹起，逐個插入關(guān)鍵字。但由樹的生成也是從空樹起，逐個插入關(guān)鍵字。但由于于B-B-樹結(jié)點中的關(guān)鍵字個數(shù)必須大于樹結(jié)點中的關(guān)鍵字個數(shù)必須大于Upper(m/2)-1Upper(m/2)-1，因，因此，每次插入一個關(guān)鍵字，不是在樹中添加一個葉子結(jié)此，每次插入一個關(guān)鍵字，不是在樹中添加一個葉子結(jié)點，而是首先在最底層的某個非終端結(jié)點中添加一個關(guān)點，而是首先在最底層的某個非終端結(jié)點中添加一個關(guān)鍵字，若該結(jié)點的關(guān)鍵字不超過鍵字，若該結(jié)點的關(guān)鍵字不超過m-1m-1，則插入完成，否，則插入完成，否則要產(chǎn)生結(jié)點則要產(chǎn)生結(jié)點“分裂分裂”。例例: :在如下的在如下的3 3階階B-B-樹上分別插

24、入樹上分別插入30,26,8530,26,85和和7 7454550501001002424373753 90 3 1261 70a ab bc cd de ef fg gh h( (圖一圖一) )插入插入303045455050100100242453 90 3 1261 70a ab bc cd de ef fg gh h( (圖二圖二) ) 30 37插入插入262645455050100100242453 90 3 1261 70a ab bd de ef fg g( (圖三圖三) ) 26 30 37c c將將2626插入插入d d后，由于后，由于d d中的關(guān)鍵字?jǐn)?shù)目超過中的關(guān)鍵字?jǐn)?shù)

25、目超過2 2，此時將，此時將d d分裂為兩個分裂為兩個結(jié)點結(jié)點, ,關(guān)鍵字關(guān)鍵字2626及其前后兩個指針留在及其前后兩個指針留在d d中，而中，而3737及其前后兩個指及其前后兩個指針存儲到新產(chǎn)生的結(jié)點針存儲到新產(chǎn)生的結(jié)點dd中，同時將中，同時將3030和指示結(jié)點和指示結(jié)點dd的指針插入的指針插入到雙親節(jié)點到雙親節(jié)點b b中。由于中。由于3030插入插入b b后沒超過后沒超過2,2,則插入完成。則插入完成。h h454550501001002653 90 3 1261 70a ab bc cd de ef fg gh h( (圖四圖四) ) 24 3037dd插入插入8585454550501

26、001002653 90 3 1261 70 85a ab bc cd de ef fg gh h( (圖五圖五) ) 24 3037dd8585插入插入g g后后, ,需分裂成兩個結(jié)點需分裂成兩個結(jié)點g,g,70g,g,70插入到插入到e e中中, ,由于由于e e中關(guān)鍵中關(guān)鍵字字22個個, ,所以所以,e,e又分裂為又分裂為e,ee,e，7070插入插入a a中。中。g,eg,e分裂后的圖分分裂后的圖分別見圖六、圖七：別見圖六、圖七：4550501001002653 70 90 3 12a ab bc cd de ef fg gh h( (圖六圖六) ) 24 3037dd61gg8550

27、501001002645 70 3 12a ab bc cd deef fg gh h( (圖七圖七) ) 24 3037dd61gg855390e e插入插入7 750501001002645 70 3 7 12a ab bc cd deef fg gh h( (圖八圖八) ) 24 3037dd61gg855390e e50501001002645 70a ab bc cd deef fg gh h( (圖九圖九) ) 7 24 3037dd61gg855390e e312cc50501001002624 45 70a ab bc cd deef fg gh h( (圖十圖十) )37dd

28、61gg855390e e312cc730505010010026a ab bc cd deef fg gh h( (圖十一圖十一) )37dd61gg855390e e312cc730bbbb247045aam m 一般情況，結(jié)點可如下實現(xiàn)一般情況，結(jié)點可如下實現(xiàn)“分裂分裂”。 假設(shè)假設(shè)p p節(jié)點中已有節(jié)點中已有m-1m-1個關(guān)鍵字，但插入一個關(guān)鍵字之后，結(jié)點中含有信息為：個關(guān)鍵字，但插入一個關(guān)鍵字之后，結(jié)點中含有信息為：此時此時, ,可將可將P P節(jié)點分裂為節(jié)點分裂為P P和和PP兩個節(jié)點兩個節(jié)點: P PP PPP 即把關(guān)鍵字即把關(guān)鍵字K K 插入到它的父親結(jié)點中，因此在父親結(jié)點中插入到

29、它的父親結(jié)點中，因此在父親結(jié)點中指針指針P P和和PP是按如下順序被放置的。是按如下順序被放置的。 .,P,K ,P.,P,K ,P.m/2 m/2 m/2 m/2 m m，A A0 0 ，K K1 1 ，A A1 1 ，K K2 2 ，A A2 2 ，. . ，K Km m A Am m，A A0 0 ，K K1 1 ，A A1 1 ，K K ，A Am/2 -1m/2 -1m/2 1m/2 1m/2 -1m/2 -1m- m/2 ,A ,K ,A ,.Km,Amm- m/2 ,A ,K ,A ,.Km,Amm/2 m/2 m/2 +1m/2 +1m/2 +1m/2 +1 縱觀以上兩節(jié)討論的

30、表示查找表的各種結(jié)構(gòu)，有一縱觀以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)，有一個共同點：記錄在表中的位置和它的關(guān)鍵字之間不存在個共同點：記錄在表中的位置和它的關(guān)鍵字之間不存在一個確定的關(guān)系，因此，查找的過程為給定值依次和關(guān)一個確定的關(guān)系，因此，查找的過程為給定值依次和關(guān)鍵字集合中各個關(guān)鍵字進(jìn)行比較，查找的效率取決于和鍵字集合中各個關(guān)鍵字進(jìn)行比較，查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個數(shù)。給定值進(jìn)行比較的關(guān)鍵字個數(shù)。 因此，用這類方法表示的查找表，其平均查找長度因此，用這類方法表示的查找表，其平均查找長度都不為零，不同表示方法的差別僅在于：和給定值進(jìn)行都不為零，不同表示方法的差別僅在于：和給定值進(jìn)行

31、比較的關(guān)鍵字的順序不同。比較的關(guān)鍵字的順序不同。 對于頻繁使用的查找表，希望對于頻繁使用的查找表，希望ASL=0ASL=0。即不需要從。即不需要從“比較比較”的結(jié)果來確定查找成功，只有一個辦法：預(yù)先知的結(jié)果來確定查找成功，只有一個辦法：預(yù)先知道所查關(guān)鍵字在表中的位置，也就是說，記錄在表中位道所查關(guān)鍵字在表中的位置，也就是說，記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系置和其關(guān)鍵字之間存在一種確定的關(guān)系。 Hash法法什么是什么是HashHash表表？例如：為每年招收的例如：為每年招收的10001000名新生建立一張查找表，其關(guān)名新生建立一張查找表，其關(guān)鍵字為鍵字為xx000-xx999(xx

32、000-xx999(前兩位為年份前兩位為年份) )。則可以下標(biāo)為。則可以下標(biāo)為000-999 000-999 的順序表表示之。由于關(guān)鍵字和記錄在表中的的順序表表示之。由于關(guān)鍵字和記錄在表中的序號相同，則不需要經(jīng)過比較即可確定待查關(guān)鍵字。序號相同，則不需要經(jīng)過比較即可確定待查關(guān)鍵字。但是，對于動態(tài)查找表而言，但是，對于動態(tài)查找表而言，1) 1) 表長不確定；表長不確定；2)2)在設(shè)計在設(shè)計查找表時，只知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵查找表時，只知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵字。因此，一般情況，需建立一個函數(shù)關(guān)系，以字。因此，一般情況，需建立一個函數(shù)關(guān)系，以f(key)f(key)作

33、作為關(guān)鍵字為為關(guān)鍵字為keykey的記錄在表中的位置，通常稱這個函數(shù)的記錄在表中的位置，通常稱這個函數(shù)f(key)f(key)為哈希函數(shù)。為哈希函數(shù)。( (注意：這個函數(shù)并不一定是數(shù)學(xué)函注意：這個函數(shù)并不一定是數(shù)學(xué)函數(shù)數(shù)) )簡單地說，簡單地說，哈希表是基于哈希函數(shù)建立的一種查找表。哈希表是基于哈希函數(shù)建立的一種查找表。例如：對于如下例如：對于如下9 9個關(guān)鍵字個關(guān)鍵字 Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei 13 896 1114122設(shè)設(shè) 從這個例子可見，從這個例子可見，哈希函數(shù)是一個映象，即：將關(guān)鍵字的集合映射到哈希函數(shù)是一個映象，即：將關(guān)鍵字的集合映射到

34、某個地址集合上，它的設(shè)置很靈活，只要這個地址某個地址集合上，它的設(shè)置很靈活，只要這個地址集合的大小不超出允許范圍即可集合的大小不超出允許范圍即可; ; 由于哈希函數(shù)是一個壓縮映象，因此，在一般情況由于哈希函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生下，很容易產(chǎn)生“沖突沖突”現(xiàn)象，即：現(xiàn)象，即：key1key2key1key2，而而 f(key1) = f(key2),f(key1) = f(key2),并且，改進(jìn)哈希函數(shù)只能減并且，改進(jìn)哈希函數(shù)只能減少沖突，而不能避免沖突。少沖突，而不能避免沖突。因此，在設(shè)計哈希函數(shù)時，一方面要考慮選擇一個因此，在設(shè)計哈希函數(shù)時，一方面要考慮選擇一個“好

35、好”的哈希函數(shù)的哈希函數(shù); ;另一方面要選擇一種處理沖突的方法。另一方面要選擇一種處理沖突的方法。所謂所謂“好好”的哈希函數(shù)，指的是，對于集合中的任意一個的哈希函數(shù)，指的是，對于集合中的任意一個關(guān)鍵字，經(jīng)哈希函數(shù)關(guān)鍵字，經(jīng)哈希函數(shù)“映象映象”到地址集合中任何一個地址到地址集合中任何一個地址的概率是相同的。稱這類哈希函數(shù)為的概率是相同的。稱這類哈希函數(shù)為“均勻的均勻的”哈希函數(shù)哈希函數(shù)。根據(jù)設(shè)定的哈希函數(shù)根據(jù)設(shè)定的哈希函數(shù)H(key)H(key)和所選中的處理沖突的方法，和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集( (區(qū)

36、區(qū)間間) )上，并以關(guān)鍵字在地址集中的上，并以關(guān)鍵字在地址集中的“象象”作為相應(yīng)記錄在作為相應(yīng)記錄在表中的存儲位置，這種表被稱為哈希表。表中的存儲位置，這種表被稱為哈希表。HashHash法的關(guān)鍵在于哈希表的構(gòu)造和沖突的處理法的關(guān)鍵在于哈希表的構(gòu)造和沖突的處理哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法對數(shù)字的關(guān)鍵字可有下列哈希函數(shù)的構(gòu)造方法，若對數(shù)字的關(guān)鍵字可有下列哈希函數(shù)的構(gòu)造方法，若是非數(shù)字關(guān)鍵字，則需先對其進(jìn)行數(shù)字化處理。是非數(shù)字關(guān)鍵字，則需先對其進(jìn)行數(shù)字化處理。1.1.直接定址法直接定址法 哈希函數(shù)為關(guān)鍵字的線性函數(shù)哈希函數(shù)為關(guān)鍵字的線性函數(shù)H(key) = key H(key) = key

37、 或者或者 H(key) = aH(key) = a* *key + bkey + b 僅限于：地址集合的大小僅限于：地址集合的大小 = = 關(guān)鍵字集合的大小關(guān)鍵字集合的大小 例例 有一個從有一個從1 1到到100100歲的人口數(shù)字統(tǒng)計表歲的人口數(shù)字統(tǒng)計表, ,用年齡做關(guān)鍵字，用年齡做關(guān)鍵字，它采用的它采用的hashhash函數(shù)是第一種函數(shù)是第一種H(K)=K,H(K)=K,即即j=kj=k。地址地址 01 02 03 25 26 27 28 10001 02 03 25 26 27 28 100年齡年齡 1 2 3 25 26 27 28 1001 2 3 25 26 27 28 100人數(shù)

38、人數(shù) 3000 2000 5000 1020 2070 7001 7200 103000 2000 5000 1020 2070 7001 7200 102.2.數(shù)字分析法數(shù)字分析法 例例 有七個有七個8 8位十進(jìn)制的關(guān)鍵字（有七個關(guān)鍵字，每個關(guān)鍵字位十進(jìn)制的關(guān)鍵字（有七個關(guān)鍵字，每個關(guān)鍵字都具有八位十進(jìn)制數(shù)），將其散列在地址為都具有八位十進(jìn)制數(shù)），將其散列在地址為10-9010-90的表中。的表中。 地址地址 k1k1：5 4 2 4 2 2 4 2 425 4 2 4 2 2 4 2 42 k2 k2：5 4 2 8 1 3 6 7 835 4 2 8 1 3 6 7 83 k3 k3：5

39、 4 2 2 2 8 1 7 285 4 2 2 2 8 1 7 28 k4 k4：5 4 2 3 8 9 6 7 395 4 2 3 8 9 6 7 39 k5 k5：5 4 2 5 4 1 5 7 515 4 2 5 4 1 5 7 51 k6 k6：5 4 2 6 8 5 3 7 655 4 2 6 8 5 3 7 65 k7 k7：5 4 2 1 9 3 5 5 135 4 2 1 9 3 5 5 13僅限于：能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字僅限于：能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。出現(xiàn)的頻度。假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是

40、由s s位數(shù)字組成位數(shù)字組成(k(k1 1, k, k2 2, , k, , kn n) )，分析關(guān)鍵字集中的全體，并從中，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。提取分布均勻的若干位或它們的組合作為地址。3.3.平方取中法平方取中法 若關(guān)鍵字的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的若關(guān)鍵字的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象，則先求關(guān)鍵字的平方值，以通過現(xiàn)象，則先求關(guān)鍵字的平方值，以通過“平方平方”擴大差別擴大差別，同時平方值的中間幾位受到整個關(guān)鍵字中各位的影響，同時平方值的中間幾位受到整個關(guān)鍵字中各位的影響. .4.4.折迭法折迭法 若關(guān)鍵字的位數(shù)特別多，

41、則可將其分割成幾部分，若關(guān)鍵字的位數(shù)特別多，則可將其分割成幾部分，然后取它們的疊加和為哈希地址。相加的方法有移位法然后取它們的疊加和為哈希地址。相加的方法有移位法和折疊法。和折疊法。折疊法：把一關(guān)鍵字看承一張紙條，從一端向另一端折疊法：把一關(guān)鍵字看承一張紙條，從一端向另一端沿邊界逐層折疊，再把相應(yīng)的位數(shù)加在一起。沿邊界逐層折疊，再把相應(yīng)的位數(shù)加在一起。移位法：將各部分的最后一位對齊，然后相加。移位法：將各部分的最后一位對齊，然后相加。假定關(guān)鍵字假定關(guān)鍵字:K=d1d2d3drdr+1d2rd2r+1d3r:K=d1d2d3drdr+1d2rd2r+1d3r允許允許有的存儲地址有有的存儲地址有r

42、 r位。位。 移位法移位法： d1 d2 drd1 d2 dr dr+1 dr+2 d2r dr+1 dr+2 d2r + d2r+1d2r+2d3r + d2r+1d2r+2d3r高進(jìn)位不要了高進(jìn)位不要了得到得到r r位的存儲地址位的存儲地址折疊法折疊法: d3r d3r-1d2r+1: d3r d3r-1d2r+1 dr+1dr+2 d2r dr+1dr+2 d2r + dr dr-1 d1 + dr dr-1 d1 d1 d2 dr d1 d2 dr高進(jìn)位不要了高進(jìn)位不要了得到得到r r位的存儲地址位的存儲地址例如：例如：K=32834872K=32834872，允許存儲地址為三位十進(jìn)制

43、數(shù)。，允許存儲地址為三位十進(jìn)制數(shù)。 位移法：位移法： 328 328 折疊法：折疊法： 2727 348 348 348 348 + 72 + 823 + 72 + 823 748 1198 748 1198 H(K)=748 H(K)=198 H(K)=748 H(K)=1985.5.除留余數(shù)法除留余數(shù)法 實際造表時，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集實際造表時，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況合的情況(包括關(guān)鍵字的范圍和形態(tài)包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。能性降到盡可能地小。設(shè)給出關(guān)鍵字設(shè)給出

44、關(guān)鍵字k k，存儲單元數(shù)為，存儲單元數(shù)為m,m,則可選一數(shù)則可選一數(shù)p(p=m)p(p=m)去去除除k k得到余數(shù)得到余數(shù)r(r(以以p p為模為模) )，再用一線性函數(shù)，再用一線性函數(shù)f f將將r r轉(zhuǎn)換為轉(zhuǎn)換為散列地址散列地址j,j,即即r=(k) mod p, j=f(r)r=(k) mod p, j=f(r)例例 有一組關(guān)鍵字從有一組關(guān)鍵字從000001-859999000001-859999，指定的存儲單元地址為，指定的存儲單元地址為1000000-1005999,1000000-1005999,即即m=6000m=6000。選。選p=5999 k=172148p=5999 k=17

45、2148 r=(172148) mod 5999=4176(mod 5999) r=(172148) mod 5999=4176(mod 5999) f=1000000+r=1004176 f=1000000+r=1004176在這里選擇在這里選擇p p是關(guān)鍵步驟，若是關(guān)鍵步驟，若P P為偶數(shù)，則凡是奇數(shù)的關(guān)鍵字，為偶數(shù)，則凡是奇數(shù)的關(guān)鍵字， 都轉(zhuǎn)換為奇數(shù)地址，則凡是偶數(shù)的關(guān)鍵字地都轉(zhuǎn)換為偶數(shù)地址，都轉(zhuǎn)換為奇數(shù)地址，則凡是偶數(shù)的關(guān)鍵字地都轉(zhuǎn)換為偶數(shù)地址， 顯然會出現(xiàn)沖突。一般情況：顯然會出現(xiàn)沖突。一般情況：(1)P(1)P盡量接近盡量接近m;(2)pm;(2)p為質(zhì)數(shù)。為質(zhì)數(shù)。8.3.2處理沖

46、突的方法處理沖突的方法 處理沖突的方法處理沖突的方法開放定址法開放定址法鏈地址法鏈地址法線性探測再散列線性探測再散列二次探測再散列二次探測再散列偽隨機探測再散列偽隨機探測再散列探測：探測：檢查關(guān)鍵字是否與檢查關(guān)鍵字是否與hashhash向量元素相匹配。向量元素相匹配。一、開放定址法一、開放定址法假設(shè)哈?？臻g為假設(shè)哈?？臻g為T(0:m-1),T(0:m-1),哈希函數(shù)為哈希函數(shù)為j=H(key)j=H(key)。為求得下一個哈希地址，可取為求得下一個哈希地址，可取j ji i=(j+d=(j+di i) MOD m) MOD m， i=1,2,3,.,s(s1),i=1,2,3,.,s(s1),

47、其中其中m m為哈希表的表長為哈希表的表長d di i為增量序列。為增量序列。1.1.當(dāng)取當(dāng)取d di i=1,2,3,.,s=1,2,3,.,s時稱為時稱為線性探測再散列線性探測再散列 例如：例如：有一個關(guān)鍵字序列有一個關(guān)鍵字序列19, 7019, 70，3333，已存入長度，已存入長度為為1616的哈希表中。的哈希表中。取哈希函數(shù)為除留余數(shù)法取哈希函數(shù)為除留余數(shù)法: j=k MOD 13: j=k MOD 13；01456781570193318現(xiàn)在要把關(guān)鍵字為現(xiàn)在要把關(guān)鍵字為1818的記錄填入表中：的記錄填入表中：j=18 MOD 13=5 j=18 MOD 13=5 沖突沖突 1 1次

48、次j j1 1=(5+1)MOD 16=6 =(5+1)MOD 16=6 沖突沖突j j2 2=(5+2)MOD 16=7 =(5+2)MOD 16=7 沖突沖突j j3 3=(5+3)MOD 16=8 =(5+3)MOD 16=8 不沖突不沖突 Hash地址地址 是否沖突是否沖突 沖突次數(shù)沖突次數(shù)2 2次次3 3次次j=19 MOD 13=6j=19 MOD 13=6；j=70 MOD 13=5j=70 MOD 13=5；j=33 MOD 13=7j=33 MOD 13=7 2.2.當(dāng)取當(dāng)取d di i=1=12 2 ,-1 ,-12 2 ,2 ,22 2,-2,-22 2,n,n2 2 ,

49、-n ,-n2 2 時稱為時稱為: : 二次探測再散列二次探測再散列仍以上例為例，仍以上例為例，7070，1919，3333已填入哈希表中，再已填入哈希表中，再填入關(guān)鍵字為填入關(guān)鍵字為1818的記錄的記錄: : j j1 1=(5+1) MOD 16=6=(5+1) MOD 16=601456781570193318j=18 MOD 13=5 j=18 MOD 13=5 沖突沖突 1 1次次Hash地址地址 是否沖突是否沖突 沖突次數(shù)沖突次數(shù)j j2 2=(5-1) MOD 16=4 =(5-1) MOD 16=4 不沖突不沖突2 2次次沖突沖突設(shè)散列表為HT13, 散列函數(shù)為 H (key)

50、 = key %13。用二次探測再散列二次探測再散列法解決沖突, 對下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1) 采用線性探查法尋找下一個空位, 畫出相應(yīng)的散列表, 并計算等概率下搜索成功的平均搜索長度和搜索不成功的平均搜索長度。(2) 采用雙散列法尋找下一個空位, 再散列函數(shù)為 RH (key) = (7*key) % 10 + 1, 尋找下一個空位的公式為 Hi = (Hi-1 + RH (key) % 13, H1 = H (key)。畫出相應(yīng)的散列表, 并計算等概率下搜索成功的平均搜索長度。說明：說明： 線性探測法可以探測到

51、哈希表中的各個位置，但線性探測法可以探測到哈希表中的各個位置，但它容易產(chǎn)生它容易產(chǎn)生“堆聚堆聚”現(xiàn)象。例如，關(guān)鍵字為現(xiàn)象。例如，關(guān)鍵字為2121的記錄，的記錄，由哈希函數(shù)得到哈希地址為由哈希函數(shù)得到哈希地址為8 8，則產(chǎn)生沖突。但是這，則產(chǎn)生沖突。但是這種沖突不是由同義詞所引起的，而是在解決同義詞沖種沖突不是由同義詞所引起的，而是在解決同義詞沖突的過程中又添加出的非同義詞沖突。這種現(xiàn)象會使突的過程中又添加出的非同義詞沖突。這種現(xiàn)象會使探測次數(shù)增加，對查找極為不利。探測次數(shù)增加，對查找極為不利。 二次探測法可減少二次探測法可減少“堆聚堆聚”，但由于它不能保證，但由于它不能保證探測到哈希表中的所有位置