數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：Chapter Eight Search

1、數(shù)據(jù)結(jié)構(gòu)Chapter Eight Search引基本概念以及術(shù)語(yǔ)靜態(tài)查找表動(dòng)態(tài)查找樹表哈希表查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。1、查找表基本概念及術(shù)語(yǔ)概念可以根據(jù)實(shí)際應(yīng)用和查找的具體要求來(lái)組織查找表，以獲得最高效率。若查找表的操作不包括對(duì)表的修改，稱為靜態(tài)查找表；否則稱為動(dòng)態(tài)查找表。關(guān)鍵碼：關(guān)鍵碼是數(shù)據(jù)元素（記錄）中某個(gè)項(xiàng)或組合項(xiàng)的值，用它可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（記錄）。1、查找表基本概念及術(shù)語(yǔ)術(shù)語(yǔ)查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄） 。若查找表中存在這樣一個(gè)記錄，則稱“查找成功”，查找結(jié)果：給出整個(gè)記錄的信息，或指示該記錄在查找

2、表中的位置；否則稱“查找不成功”，查找結(jié)果：給出“空記錄”或 “空指針”。1、查找表基本概念及術(shù)語(yǔ)術(shù)語(yǔ)平均查找長(zhǎng)度(ASL)：查找成功時(shí)，為確定數(shù)據(jù)元素在表中位置所進(jìn)行的關(guān)鍵碼比較次數(shù)的期望值其中: n 為表長(zhǎng)，Pi 為查找表中第i個(gè)記錄的概率， 且 ，Ci為找到該記錄時(shí)，曾和給定值 比較過(guò)的關(guān)鍵字的個(gè)數(shù)對(duì)順序表而言，Ci = n-i+11、查找表基本概念及術(shù)語(yǔ)ASL 舉例順序表查找的平均查找長(zhǎng)度為：ASL = nP1 +(n-1)P2 +. +2Pn-1+Pn在等概率查找的情況下，斐波那契查找順序查找表2、靜態(tài)查找表介紹如下幾種：有序查找表索引順序表2、靜態(tài)查找表：順序查找表定義:以順序表或

3、線性鏈表表示靜態(tài)查找表思路:從表的一端開始，向另一端逐個(gè)按給定值X與關(guān)鍵碼進(jìn)行比較，若找到，查找成功，并給出數(shù)據(jù)元素在表中的位置；若整個(gè)表檢測(cè)完，仍未找到與kx相同的關(guān)鍵碼，則查找失敗，給出失敗信息 。2、靜態(tài)查找表：順序查找表算法示例：ST.elem假設(shè)給定值 e = 64,要求 ST.elemi = e, 問(wèn): i = ?ii66ii2、靜態(tài)查找表：順序查找表算法： /*在表中查找關(guān)鍵碼為kx的數(shù)據(jù)元素，若找到返回該元素在數(shù)組中的下標(biāo)，否則返回0 */ int s_search(S_TBL tbl，KeyType kx) /* 存放監(jiān)測(cè)，從后向前查找失敗時(shí)，不必判表是否檢測(cè)完， 從而達(dá)到算

4、法統(tǒng)一*/tbl.elem0.key = kx；/* 從標(biāo)尾端向前找 */ for( i = tbl.length ; tbl.elemi.key kx ；i- )；return i； /*浪費(fèi)一個(gè)數(shù)據(jù)元素空間為代價(jià)*/2、靜態(tài)查找表：順序查找表ST.elemiST.elemi60ikval = 64kval = 60i64算法示例：2、靜態(tài)查找表： 有序查找表定義:所查找的表的數(shù)據(jù)是有序的包括:折半查找插值查找斐波那契查找2、靜態(tài)查找表：折半查找表思路： （又稱為二分查找）在遞增有序表中，取中間元素作為比較對(duì)象，若給定值與中間元素的關(guān)鍵碼相等，則查找成功；若給定值小于中間元素的關(guān)鍵碼，則在中

5、間元素的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間元素的關(guān)鍵碼，則在中間元素的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述查找過(guò)程，直到查找成功，或所查找的區(qū)域無(wú)數(shù)據(jù)元素，查找失敗 。2、靜態(tài)查找表：折半查找表算法演示：ST.elemST.length例如: key = 64 的查找過(guò)程如下lowhighmidlow mid high midlow ：指示查找區(qū)間的下界; high： 指示查找區(qū)間的上界;mid = (low+high)/2。2、靜態(tài)查找表：折半查找表算法實(shí)現(xiàn)：/* 在表tbl中查找關(guān)鍵碼為kx的數(shù)據(jù)元素，若找到返回該元素在表中的位置，否則，返回0 */int Binary_Search(S_TBL t

6、bl，KEY kx) /* 設(shè)置初始區(qū)間 */int mid，flag=0；low=1；high=length；while(low=high) /* 表空測(cè)試 */ /* 非空，進(jìn)行比較測(cè)試 */ mid=(low+high)/2； /* 得到中點(diǎn) */* 調(diào)整到左半?yún)^(qū) */if(kxtbl.elemmid.key) low=mid+1； /* 查找成功，元素位置設(shè)置到flag中 */else flag=mid；break；return flag;搜索成功的情形 搜索不成功的情形從有序表構(gòu)造出的二叉搜索樹(判定樹) 若設(shè) n = 2h-1，則描述對(duì)分搜索的二叉搜索樹是高度為 h-1 的滿二叉樹

7、。2h = n+1, h = log2(n+1)。 第0層結(jié)點(diǎn)有1個(gè)，搜索第0層結(jié)點(diǎn)要比較1次；第1層結(jié)點(diǎn)有2個(gè)，搜索第1層結(jié)點(diǎn)要比較2次；，可以用歸納法證明這樣第 i (0 i h) 層結(jié)點(diǎn)有 2i 個(gè)，搜索第 i 層結(jié)點(diǎn)要比較 i+1次，。假定每個(gè)結(jié)點(diǎn)的搜索概率相等，即pi = 1/n，則搜索成功的平均搜索長(zhǎng)度為2、靜態(tài)查找表：插值查找表思路：和折半查找類似，只不過(guò)mid不是首尾之和的一半，而是通過(guò)如下公式求得： (斜率)求取中點(diǎn)，其中l(wèi)ow和high分別為表的兩個(gè)端點(diǎn)下標(biāo)，kx為給定。 若 kxtbl.elemmid.key，則low=mid+1，繼續(xù)右半?yún)^(qū)查找； 若 kx=tbl.el

8、emmid.key，查找成功。 插值查找是平均性能最好的查找方法，但只適合于關(guān)鍵碼均勻分布的表。2、靜態(tài)查找表：斐波那契查找表思路：和折半查找類似，只不過(guò)mid不是首尾之和的一半，而是通過(guò)斐波那契公式求得：斐波那契查找分割的思想為：對(duì)于表長(zhǎng)為F(i)-1的有序表，以相對(duì)low偏移量F(i-1)-1取mid點(diǎn)，即mid = low + F(i-1) - 1，對(duì)表進(jìn)行分割，則左子表表長(zhǎng)為F(i-1)-1，右子表表長(zhǎng)為F(i)-1-F(i-1)-1-1=F(i-2)-1?？梢?jiàn)，兩個(gè)子表表長(zhǎng)也都是某個(gè)斐波那契數(shù)-1，因而，可以對(duì)子表繼續(xù)分割。2、靜態(tài)查找表：斐波那契查找表算法實(shí)現(xiàn)： 當(dāng)n很大時(shí)，該查找

9、方法稱為黃金分割法，其平均性能比折半查找好，但其時(shí)間效率仍為O(log2n)，而且，在最壞情況下比折半查找差。2、靜態(tài)查找表：索引順序表查找算法思路：又稱:分塊查找。要求將查找表分成若干個(gè)子表，并對(duì)子表建立索引表。查找表的每一個(gè)子表由索引表中的索引項(xiàng)確定。索引項(xiàng)包括兩個(gè)字段：關(guān)鍵碼字段 (存放對(duì)應(yīng)子表中的最大關(guān)鍵碼值) ；指針字段 (存放指向?qū)?yīng)子表的指針) ，并且要求索引項(xiàng)按關(guān)鍵碼字段有序。查找時(shí)，先用給定值X在索引表中檢測(cè)索引項(xiàng)，以確定所要進(jìn)行的查找在查找表中的查找分塊 (由于索引項(xiàng)按關(guān)鍵碼字段有序，可用順序查找或折半查找) ，然后，再對(duì)該分塊進(jìn)行順序查找。2、靜態(tài)查找表：索引順序表查找算

10、法演示：012345678910111213170821191431332225405261784621 040 578 10例如：索引順序表 = 索引 + 順序表順序表索引2、靜態(tài)查找表：索引順序表查找總結(jié)(n)(1)(n)(1)(nlogn)查找 插入 刪除無(wú)序順序表 無(wú)序線性鏈表有序順序表 有序線性鏈表 靜態(tài)查找樹表*(n)(n)(logn)(n)(logn)(1)(1)(n)(1)(nlogn)B+樹二叉排序樹3、動(dòng)態(tài)查找表介紹如下幾種：平衡二叉樹(AVL樹)B- 樹 二叉排序樹（Binary Sort Tree）或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹： 若左子樹不空，則左子樹上所

11、有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。 左右子樹也都是二叉排序樹。3、動(dòng)態(tài)查找表：二叉排序樹定義3、動(dòng)態(tài)查找表：二叉排序樹示例：3、動(dòng)態(tài)查找表：二叉排序樹建立過(guò)程序列為：63，90，70，55，67，42，98，83，10，45，58 中序序列是升序3、動(dòng)態(tài)查找表：二叉排序樹插入過(guò)程為了向二叉搜索樹中插入一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒(méi)有。 搜索成功: 樹中已有這個(gè)元素，不再插入。 搜索不成功: 樹中原來(lái)沒(méi)有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。3、動(dòng)態(tài)查找表：

12、二叉排序樹刪除過(guò)程：需要考慮3種情況：(1) 刪除結(jié)點(diǎn)為葉結(jié)點(diǎn)，只需將被刪結(jié)點(diǎn)的雙親結(jié)點(diǎn)相應(yīng)指針域改為空指針。如圖:3、動(dòng)態(tài)查找表：二叉排序樹刪除過(guò)程：需要考慮3種情況：(2)刪除結(jié)點(diǎn)只有右子樹pr或只有左子樹pl，此時(shí)只需將pr或pl替換*f結(jié)點(diǎn)的*p子樹即可。如圖:3、動(dòng)態(tài)查找表：二叉排序樹刪除過(guò)程：需要考慮3種情況：(3)刪除結(jié)點(diǎn)有右子樹pr也有左子樹pl，此時(shí)只需將刪除節(jié)點(diǎn)中序中刪除節(jié)點(diǎn)后的直接后繼補(bǔ)上即可。如圖:Pr要么是葉子節(jié)點(diǎn)，要么是只有右子樹。因?yàn)?條件3)規(guī)定有右子樹，故此Pr必然大于刪除節(jié)點(diǎn)P，而如果Pr有左葉節(jié)點(diǎn)，則Pr就左葉節(jié)點(diǎn)。如果有右葉節(jié)點(diǎn)，沒(méi)有左節(jié)點(diǎn)則按(條件2)

13、可得到。3、動(dòng)態(tài)查找表：二叉排序樹刪除過(guò)程舉例3、動(dòng)態(tài)查找表：二叉排序樹分析 同樣 3 個(gè)數(shù)據(jù) 1, 2, 3 ，輸入順序不同，建立起來(lái)的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。 如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大，這樣必然會(huì)降低搜索性能。如： 1, 2, 3 、 1, 3, 2、2, 3, 1、3, 1, 2、3, 2, 1 。1311113222332323、動(dòng)態(tài)查找表：平衡二叉樹(AVL樹)定義二叉平衡樹是二叉查找樹的另一種形式，其特點(diǎn)為：樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值不大于1 。例如:548254821是平衡樹不是平衡樹3

14、、動(dòng)態(tài)查找表：平衡二叉樹(AVL樹)如何構(gòu)造平衡二叉樹構(gòu)造過(guò)程等同于插入過(guò)程，在平衡二叉樹中，隨著節(jié)點(diǎn)的變化，將導(dǎo)致深度之差的絕對(duì)值大于1 ，故此需要調(diào)整，采用的方法是平衡旋轉(zhuǎn)技術(shù)。分4種情況考慮：左單旋轉(zhuǎn) (RR型)右單旋轉(zhuǎn)(LL型)先左后右雙向旋轉(zhuǎn)(RL型)先右后左雙向旋轉(zhuǎn)(LL型)平衡化旋轉(zhuǎn)方法：如果在一棵平衡的二叉搜索樹中插入一個(gè)新結(jié)點(diǎn)，造成了不平衡。此時(shí)必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。平衡化旋轉(zhuǎn)有兩類： 單旋轉(zhuǎn) (左旋和右旋) 雙旋轉(zhuǎn) (左平衡和右平衡)每插入一個(gè)新結(jié)點(diǎn)時(shí)，AVL樹中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會(huì)發(fā)生改變。因此，在插入一個(gè)新結(jié)點(diǎn)后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點(diǎn)的平

15、衡因子(左、右子樹的高度差)。如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn)，其中一個(gè)是另一個(gè)的鏡像，其方向與不平衡的形狀相關(guān)。如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。右單旋轉(zhuǎn)左單旋轉(zhuǎn) 左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)左單旋轉(zhuǎn) (RotateLeft )hhhACEBD(a) (b) (c)hhh+1BACEDhhh+1CEABD如果在子樹E中插入一個(gè)新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成+2，出現(xiàn)不平衡。沿

16、插入路徑檢查三個(gè)結(jié)點(diǎn)A、C和E。它們處于一條方向?yàn)椤啊钡闹本€上，需要做左單旋轉(zhuǎn)。以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)。+1+20+100右單旋轉(zhuǎn) (RotateRight )hhhACEBD(a) (b) (c)hh+1BACEDhhh+1CEABD在左子樹D上插入新結(jié)點(diǎn)使其高度增1，導(dǎo)致結(jié)點(diǎn)A的平衡因子增到 -2，造成了不平衡。為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個(gè)結(jié)點(diǎn)A、B和D，它們處于一條方向?yàn)椤?”的直線上，需要做右單旋轉(zhuǎn)。以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。h000-1-1-2先左后右雙旋轉(zhuǎn) (RotationLeftRight)在子樹F或G中插入新結(jié)點(diǎn)，該子樹的高度增1。結(jié)點(diǎn)A

17、的平衡因子變?yōu)?-2，發(fā)生了不平衡。從結(jié)點(diǎn)A起沿插入路徑選取3個(gè)結(jié)點(diǎn)A、B和E，它們位于一條形如“”的折線上，因此需要進(jìn)行先左后右的雙旋轉(zhuǎn)。首先以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)B反時(shí)針旋轉(zhuǎn)，以E代替原來(lái)B的位置，做左單旋轉(zhuǎn)。再以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)，做右單旋轉(zhuǎn)。使之平衡化。插入左單旋轉(zhuǎn)右單旋轉(zhuǎn)00-1-2+1-100+1先右后左雙旋轉(zhuǎn) (RotationRightLeft)右左雙旋轉(zhuǎn)是左右雙旋轉(zhuǎn)的鏡像。在子樹F或G中插入新結(jié)點(diǎn)，該子樹高度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?，發(fā)生了不平衡。 從結(jié)點(diǎn)A起沿插入路徑選取3個(gè)結(jié)點(diǎn)A、C和D，它們位于一條形如“”的折線上，需要進(jìn)行先右后左的雙旋轉(zhuǎn)。首先做

18、右單旋轉(zhuǎn)：以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)C順時(shí)針旋轉(zhuǎn)，以D代替原來(lái)C的位置。再做左單旋轉(zhuǎn)：以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)，恢復(fù)樹的平衡。左單旋轉(zhuǎn)插入右單旋轉(zhuǎn)+10000-1-1+1+2例，輸入關(guān)鍵碼序列為 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和調(diào)整過(guò)程如下。160163-10163701-2左右雙旋731600073110-1116右單旋37169000111371126916011273161190-1-22右左雙旋左單旋18160007326119003160917112627390182611-1161183-1-1716140269111左右雙旋152

19、31816-20714911261-218730011-116150126149從空樹開始的建樹過(guò)程3、動(dòng)態(tài)查找表：B- 樹定義一棵m階的B-樹，或者為空樹，或?yàn)闈M足下列特性的m叉樹：(1) 樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹；(2) 根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；(3) 除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有m/2棵子樹；(4) 所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）。3、動(dòng)態(tài)查找表：B- 樹定義(5) 所有的非終端結(jié)點(diǎn)中包含以下信息數(shù)據(jù)：(n，A0，K1，A1，K2，Kn，An)。其中：Ki（i=1,2

20、,n）為關(guān)鍵碼，且KiKi+1，Ai為指向子樹根結(jié)點(diǎn)的指針(i=0,1,n)，且指針Ai-1所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均小于Ki (i=1,2,n)，An所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均大于Kn， m/2 1nm 1 ，n為關(guān)鍵碼的個(gè)數(shù)。3、動(dòng)態(tài)查找表：B- 樹示例：3、動(dòng)態(tài)查找表：B- 樹B-樹的插入示例：例如:下列為 3 階B-樹50 20 40 80 插入關(guān)鍵字 = 60, 60 80 90,60809090 50 806030, 40 20 30 50 808030 503、動(dòng)態(tài)查找表：B+ 樹定義B+樹是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B-樹的變形樹。一棵m階的B+樹和m階的B-樹的差異在于：

21、(1) 有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵碼；(2) 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵碼的信息，及指向含有這些關(guān)鍵碼記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵碼的大小自小而大的順序鏈接。(3) 所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大（或最?。╆P(guān)鍵碼。3、動(dòng)態(tài)查找表：B+ 樹示例選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵碼計(jì)算元素的存儲(chǔ)位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值kx計(jì)算地址，將kx與地址單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功，這就是哈希方法(雜湊法)；哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù))；按這個(gè)思想構(gòu)造的表稱為哈希表(雜湊表)。4、哈希表定義：選取關(guān)鍵碼與元素位置

22、間的函數(shù)為 f(key)=key mod 111. 通過(guò)這個(gè)函數(shù)對(duì)11個(gè)元素建立查找表如下：4、哈希表例如：11個(gè)元素的關(guān)鍵碼分別為 18，27，1，20，22，6，10，13，41，15，25。2. 查找時(shí)，對(duì)給定值kx依然通過(guò)這個(gè)函數(shù)計(jì)算出地址，再將kx與該地址單元中元素的關(guān)鍵碼比較，若相等，查找成功。不可能對(duì)所有的數(shù)都一一對(duì)應(yīng)存放，故此必須設(shè)計(jì)函數(shù)進(jìn)行多少的映射。 4、哈希表思路因?yàn)槭嵌嗌伲员厝挥兄貜?fù)，稱為沖突。 故此，設(shè)計(jì)有兩個(gè)考慮的問(wèn)題：哈希函數(shù)的設(shè)計(jì)哈希函數(shù)的沖突解決4、哈希表常用的哈希函數(shù)常用的哈希函數(shù)1. 直接定址法3.乘余取整法5.平方取中法4.數(shù)字分析法6. 折疊法2.

23、 除留余數(shù)法*若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理，才可以使用以上方法。4、哈希表常用的哈希函數(shù)直接定址法即取關(guān)鍵碼的某個(gè)線性函數(shù)值為哈希地址，這類函數(shù)是一一對(duì)應(yīng)函數(shù)，不會(huì)產(chǎn)生沖突，但要求地址集合與關(guān)鍵碼集合大小相同，因此，對(duì)于較大的關(guān)鍵碼集合不適用。 Hash(key)=akey+b (a、b為常數(shù))4、哈希表常用的哈希函數(shù)直接定址法舉例關(guān)鍵碼集合為100，300，500，700，800，900，選取哈希函數(shù)為:Hash(key)=key/100，則存放如下：4、哈希表常用的哈希函數(shù)除留余數(shù)法即取關(guān)鍵碼除以p的余數(shù)作為哈希地址。使用除留余數(shù)法，選取合適的p很重要，若哈希表表長(zhǎng)為m，則要

24、求pm，且接近m或等于m。p一般選取質(zhì)數(shù)，也可以是不包含小于20質(zhì)因子的合數(shù)。 Hash(key)=key mod p (p是一個(gè)整數(shù))*pm (表長(zhǎng)) 并且 p 應(yīng)為不大于 m 的素?cái)?shù) 或是 不含 20 以下的質(zhì)因子以關(guān)鍵碼key乘以A，取其小數(shù)部分(A*key mod 1就是取A*key的小數(shù)部分)，之后再用整數(shù)B乘以這個(gè)值，取結(jié)果的整數(shù)部分作為哈希地址。 該方法B取什么值并不關(guān)鍵，但A的選擇卻很重要，最佳的選擇依賴于關(guān)鍵碼集合的特征。一般取A= ( -1)=0.6180339較為理想4、哈希表常用的哈希函數(shù)乘余取整法Hash(key)= B*(A*key mod 1) (A、B均為常數(shù)，

25、且0A1，B為整數(shù)) 數(shù)字分析法根據(jù)r種不同的符號(hào)，在各位上的分布情況，選取某幾位，組合成哈希地址。所選的位應(yīng)是各種符號(hào)在該位上出現(xiàn)的頻率大致相同。4、哈希表常用的哈希函數(shù)數(shù)字分析法此方法適合于: 能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值” 的目的是“擴(kuò)大差別” ，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。4、哈希表常用的哈希函數(shù)平方取中法此方法適合于: 關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。4、哈希表常用

26、的哈希函數(shù)折疊法移位疊加法： 將各部分的最后一位對(duì)齊相加。 間界疊加法：從一端向另一端沿各部分分界來(lái)回折疊后，最后一位對(duì)齊相加。此方法適合于: 關(guān)鍵字的數(shù)字位數(shù)特別多。關(guān)鍵碼為 key=2534658705，設(shè)哈希表長(zhǎng)為三位數(shù)，則可對(duì)關(guān)鍵碼每三位一部分來(lái)分割。4、哈希表常用的哈希函數(shù)折疊法舉例由關(guān)鍵碼得到的哈希地址一旦產(chǎn)生了沖突，也就是說(shuō)，該地址已經(jīng)存放了數(shù)據(jù)元素，就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。4、哈希表處理沖突的方法開放地址法常用的如下三種：(1) 線性探測(cè)法(2) 二次探測(cè)法(3) 雙哈希函數(shù)探測(cè)法 Hi=(Hash(key)+di)

27、 mod m ( 1i m ) 其中： Hash(key)為哈希函數(shù) m為哈希表長(zhǎng)度 di 為增量序列 1，2，m-1，且di=i4、哈希表處理沖度的方法線性探測(cè)法關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，哈希表表長(zhǎng)為11，Hash(key)=key mod 11，用線性探測(cè)法處理沖突，建表如下：4、哈希表處理沖度的方法線性探測(cè)法舉例47、7、11、16、92均是由哈希函數(shù)得到的沒(méi)有沖突的哈希地址而直接存入的；4、哈希表處理沖度的方法線性探測(cè)法舉例 Hash(29)=7，哈希地址上沖突，需尋找下一個(gè)空的哈希地址：由H1=(Hash(29)+1) mod 11=8，哈希地址8為

28、空，將29存入。另外，22、8同樣在哈希地址上有沖突，也是由H1找到空的哈希地址的； 而Hash(3)=3，哈希地址上沖突，由 H1=(Hash(3)+1) mod 11=4 仍然沖突； H2=(Hash(3)+2) mod 11=5 仍然沖突； H3=(Hash(3)+3) mod 11=6 找到空的哈希地址，存入。4、哈希表處理沖度的方法線性探測(cè)法缺點(diǎn)：可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來(lái)，大大降低了查找效率。為此，可采用二次探測(cè)法，或雙哈希函數(shù)探測(cè)法，以改善“堆積”問(wèn)題。4、哈希表處理沖度的方法二次探測(cè)法Hi=(Hash(key)di) mod m其中：Hash(key)為哈希函數(shù), m為哈希表長(zhǎng)度，m要求是某個(gè)4k+3的質(zhì)