1、第九章第九章 查找查找 9.1 靜態(tài)查找表靜態(tài)查找表 9.2 動態(tài)查找表動態(tài)查找表 9.3 哈希表哈希表一、查找表一、查找表( (Search Table)Search Table)查找的概念查找的概念 查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合 對查找表的操作:1.查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2.檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3.在查找表中插入一個數(shù)據(jù)元素；4.從查找表中刪去某個數(shù)據(jù)元素。 靜態(tài)查找表:僅作查詢和檢索操作的查找表。 動態(tài)查找表:在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個數(shù)據(jù)元素二、關(guān)鍵字二、關(guān)鍵字( (Key)Ke

2、y) 關(guān)鍵字是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標識（識別）一個數(shù)據(jù)元素（或記錄） 主關(guān)鍵字：可以識別唯一的一個記錄的關(guān)鍵字 次關(guān)鍵字：能識別若干記錄的關(guān)鍵字三、查找三、查找( (Searching)Searching) 查找是根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）。 查找成功：在查找表中查找到指定的記錄;查找不成功：在查找表中沒有找到指定記錄 由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。規(guī)律，因此不便于查找。 為了提高查找的效率，為了提高查找的效率， 需要在查找表中的元素需要在查找表中的元

3、素之間人為地附加某種確定的關(guān)系，換句話說，用另之間人為地附加某種確定的關(guān)系，換句話說，用另外一種結(jié)構(gòu)來表示查找表。外一種結(jié)構(gòu)來表示查找表。如何進行查找？如何進行查找？查找的方法取決于查找表的結(jié)構(gòu)。查找的方法取決于查找表的結(jié)構(gòu)。9.1 靜態(tài)查找表靜態(tài)查找表typedef struct ElemType *elem; int length; / 表的長度 SSTable;假設(shè)靜態(tài)查找表靜態(tài)查找表的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)為n 順序查找順序查找( (算法算法) )9.1.1 順序查找表順序查找表1.從表中最后一個記錄開始 2.逐個進行記錄的關(guān)鍵字和給定值的比較 3.若某個記錄比較相等，則查找成功 4

4、.若直到第1個記錄都比較不等，則查找不成功 以順序表或線性鏈表表示靜態(tài)查找表以順序表或線性鏈表表示靜態(tài)查找表21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Lengthn順序查找順序查找( (算法實現(xiàn)算法實現(xiàn)) )int Search_Seq(SSTable ST, KeyType key) / 若查找成功，返回位置若查找成功，返回位置ST.elem0.key = key; / “哨兵哨兵”，for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找從后往前找return i;

5、/ 找不到時找不到時,i=0 / Search_Seq設(shè)置設(shè)置“哨兵哨兵”的目的是省略對下標越界的檢查，提高算法執(zhí)行速度的目的是省略對下標越界的檢查，提高算法執(zhí)行速度n順序查找順序查找( (舉例舉例) )i=11找找64監(jiān)視哨監(jiān)視哨i=7i=8i=9i=10比較次數(shù)比較次數(shù)=5比較次數(shù)：比較次數(shù)：查找第查找第n個元素：個元素： 1查找第查找第n-1個元素：個元素：2.查找第查找第1個元素：個元素： n查找第查找第i個元素：個元素： n+1-i查找失敗查找失敗： n+1 0 1 2 3 4 5 6 7 8 9 10 1164513192137566475808892 平均查找長度定義為確定記錄在

6、表中的位置所進行的和關(guān)鍵字比較的次數(shù)的平均值 n ASL = PiCi i=1n為查找表的長度，即表中所含元素的個數(shù)Pi為查找第i個元素的概率(Pi=1)Ci是查找第i個元素時同給定值K比較的次數(shù)n 衡量查找算法的標準衡量查找算法的標準: : 時間復(fù)雜度、空間復(fù)雜度 平均查找長度ASLn順序查找順序查找( (算法性能分析算法性能分析) ) 對順序表而言，Ci=n-i+1 在等概率查找的情況下，Pi=1/n ASL=n*P1 +(n-1)P2 + 2Pn-1+ Pn = (n+1)/2n 順序查找順序查找( (特點特點) ) 優(yōu)點：1.簡單2.適應(yīng)面廣(對表的結(jié)構(gòu)無任何要求) 缺點：1.平均查找

7、長度較大2.特別是當n很大時，查找效率很低9.1.2 有序表的查找有序表的查找 折半查找的原理是：1.先確定待查記錄所在的范圍(前部分或后部分)2.逐步縮小(一半)范圍直到找(不)到該記錄為止若以若以有序表有序表表示靜態(tài)查找表，則查找過程可以表示靜態(tài)查找表，則查找過程可以基于基于“折半折半”進行。進行。折半查找折半查找( (舉例成功舉例成功) )找找641 2 3 4 5 6 7 8 9 10 11513192137566475808892Low=1High=11mid=61 2 3 4 5 6 7 8 9 10 11513192137566475808892Low=7High=11mid=9

8、1 2 3 4 5 6 7 8 9 10 11513192137566475808892Low=7mid=7High=8折半查找折半查找( (舉例不成功舉例不成功) ) 當下界low大于上界high時，說明有序表中沒有關(guān)鍵字等于K的元素，查找不成功1 2 3 4 5 6 7 8 9 10 11513192137566475808892High=6 Low=7找找59int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值置區(qū)間初值 found=false; while (low 50n50時，可得

9、近似結(jié)果時，可得近似結(jié)果1) 1(log2nASLbs折半查找折半查找( (特點特點) )折半查找的效率比順序查找高(特別是在靜態(tài)查找表的長度很長時)折半查找只能適用于有序表，并且以順序存儲結(jié)構(gòu)存儲9.1.4 分塊查找分塊查找 分塊查找是一種索引順序表(分塊有序表)查找方法，是折半查找和順序查找的簡單結(jié)合 索引順序表(分塊有序表)將整個表分成幾塊，塊內(nèi)無序，塊間有序 所謂塊間有序是指后一塊表中所有記錄的關(guān)鍵字均大于前一塊表中的最大關(guān)鍵字分塊查找分塊查找( (分塊有序表分塊有序表) ) 主表：用數(shù)組存放待查記錄,每個數(shù)據(jù)元素至少含有關(guān)鍵字域 索引表：每個結(jié)點含有最大關(guān)鍵字域和指向本塊第一個結(jié)點的

10、指針1 2 3 4 5 6 7 8 9 10 11519132175566437888092主表主表211755929索引表索引表找找64分塊查找分塊查找( (性能分析性能分析) ) 若將長度為n的表分成b塊，每塊含s個記錄，并設(shè)表中每個記錄查找概率相等 用折半查找方法在索引表中查找索引塊，ASL塊間log2(n/s+1) 用順序查找方法在主表對應(yīng)塊中查找記錄，ASL塊內(nèi)=s/2 ASLlog2(n/s+1) + s/2第九章第九章 查找查找 9.1 靜態(tài)查找表靜態(tài)查找表 9.2 動態(tài)查找表動態(tài)查找表 9.3 哈希表哈希表9.2.1 二叉排序樹和平衡二叉樹二叉排序樹和平衡二叉樹 空樹或者是具有

11、如下特性的二叉樹：.若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；.若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；.它的左、右子樹也都分別是二叉排序樹。566459237881980211375二叉排序樹二叉排序樹( (查找查找) ) 二叉排序樹又稱二叉查找樹 查找算法： 給定值與根結(jié)點比較：1.若相等，查找成功2.若小于，查找左子樹3.若大于，查找右子樹在二叉排序樹中查找關(guān)在二叉排序樹中查找關(guān)鍵字值等于鍵字值等于3737, ,8888, ,949456645923788198021137594二叉排序樹二叉排序樹( (插入插入) )二叉排序樹是一種動態(tài)樹表當樹中不存在

12、查找的結(jié)點時，作插入操作新插入的結(jié)點一定是葉子結(jié)點（只需改動一個結(jié)點的指針）該葉子結(jié)點是查找不成功時路徑上訪問的最后一個結(jié)點左孩子或右孩子(新結(jié)點值小于或大于該結(jié)點值)56645923788198021137594二叉排序樹二叉排序樹( (生成舉例生成舉例) ) 畫出在初始為空的二叉排序樹中依次插入56,64,92,80,88,75時該樹的生長全過程566492888075n 中序遍歷二叉排序樹，可得到一個關(guān)中序遍歷二叉排序樹，可得到一個關(guān)鍵字的有序序列鍵字的有序序列,如如5,13,19,21,37,56,64,92,75,80,88二叉排序樹二叉排序樹( (中序遍歷中序遍歷) )bool S

13、earchBST (BSTree T, KeyType kval, BSTree f, BSTree &p )/ 根指針根指針T所指二叉查找樹中遞歸查找關(guān)鍵字等于所指二叉查找樹中遞歸查找關(guān)鍵字等于kval的數(shù)據(jù)元素的數(shù)據(jù)元素,若若查找成查找成 功功,則指針則指針p指向該數(shù)據(jù)元素結(jié)點指向該數(shù)據(jù)元素結(jié)點,并返回并返回TRUE,否則指針否則指針p指向指向查找路徑上訪問的最后一個結(jié)點并返回查找路徑上訪問的最后一個結(jié)點并返回FALSE,指針指針f指向指向T的雙親的雙親,其其初始調(diào)用值為初始調(diào)用值為NULLif (!T) p = f; return FALSE; / 查找不成功查找不成功else if (

14、 key = T-data.key ) p = T; return TRUE; / 查找成功查找成功else if ( key data.key )return SearchBST (T-lchild, key, T, p ); / 返回在左子樹中繼續(xù)查找所得結(jié)果返回在左子樹中繼續(xù)查找所得結(jié)果else return SearchBST (T-rchild, key, T, p ); / 返回在右子樹中繼續(xù)查找所得結(jié)果返回在右子樹中繼續(xù)查找所得結(jié)果 / SearchBST 二叉排序樹二叉排序樹( (查找查找) ) bool Insert BST(BiTree &T, ElemType e ) /

15、當二叉查找樹T中不存在關(guān)鍵字等于 e.key 的數(shù)據(jù)元素時，/ 插入 e 并返回 TRUE，否則返回 FALSEif (!SearchBST ( T, e.key, NULL, p ) / 查找不成功查找不成功s = new BiTNode;if (!s) exit(1); / 存儲分配失敗存儲分配失敗s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入插入 *s 為新的根結(jié)點為新的根結(jié)點else if ( e.key data.key ) p-lchild = s;/ 插入插入 *s 為為 *p 的左孩子的左孩子else

16、p-rchild = s; / 插入插入 *s 為為 *p 的右孩子的右孩子return TRUE; / ifelse return FALSE; / Insert BST 二叉排序樹二叉排序樹( (刪除刪除) ) 刪除二叉排序樹中的一個結(jié)點后，必須保持二叉排序樹的特性（左子樹的所有結(jié)點值小于根結(jié)點，右子樹的所有結(jié)點值大于根結(jié)點） 也即保持中序遍歷后，輸出為有序序列 被刪除結(jié)點具有以下三種情況：1.是葉子結(jié)點2.只有左子樹或右子樹3.同時有左、右子樹二叉排序樹二叉排序樹( (刪除刪除) )1.被刪除結(jié)點是葉子結(jié)點 直接刪除結(jié)點，并讓其父結(jié)點指向該結(jié)點的指針變?yōu)榭?664592378819802

17、11375刪除結(jié)點刪除結(jié)點88二叉排序樹二叉排序樹( (刪除刪除) )2.被刪除結(jié)點只有左子樹或右子樹 刪除結(jié)點,讓其父結(jié)點指向該結(jié)點的指針指向其左子樹(或右子樹),即用孩子結(jié)點替代被刪除結(jié)點即可56645928819802113755659237881980211375刪除結(jié)點刪除結(jié)點64(只有右子樹只有右子樹)刪除結(jié)點刪除結(jié)點37(只有左子樹只有左子樹)566459237881980211375原圖原圖二叉排序樹二叉排序樹( (刪除刪除) )3.被刪除結(jié)點p既有左子樹，又有右子樹 以中序遍歷時的直接前驅(qū)s替代被刪除結(jié)點p，然后再刪除該直接前驅(qū)（只可能有左孩子）PCpFPRfCLQSLQLS

18、qs二叉排序樹二叉排序樹( (刪除刪除) )3.被刪除結(jié)點既有左子樹，又有右子樹(舉例)56645923788198021137556649237881980215753764592218880191375原圖刪除結(jié)點13刪除結(jié)點56二叉排序樹二叉排序樹( (性能分析性能分析) ) 在最好的情況下，二叉排序樹為一近似完全二叉樹時，其查找深度為log2n量級，即其時間復(fù)雜性為O(log2n)755619645372180138892 在最壞的情況下，二叉排序樹為近似線性表時(如以升序或降序輸入結(jié)點時)，其查找深度為n量級，即其時間復(fù)雜性為O(n)808892647521191356375二叉排序

19、樹二叉排序樹( (特性特性) ) 一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列（通過中序遍歷） 插入新記錄時，只需改變一個結(jié)點的指針，相當于在有序序列中插入一個記錄而不需要移動其它記錄 二叉排序樹既擁有類似于折半查找的特性，又采用了鏈表作存儲結(jié)構(gòu) 但當插入記錄的次序不當時(如升序或降序)，則二叉排序樹深度很深(11)，增加了查找的時間平衡二叉樹平衡二叉樹 AVL(AVL(定義定義) ) 平衡二叉樹是二叉排序(查找)樹的另一種形式 平衡二叉樹又稱AVL樹(Adelsen-Velskii and Landis) 其特點為：樹中每個結(jié)點的左、右子樹深度之差的絕對值不大于1，即|hL-hR

20、|1566459237881980211375AVL樹非AVL樹565641913753780928821平衡二叉樹平衡二叉樹 AVLAVL( (平衡因子平衡因子) ) 每個結(jié)點附加一個數(shù)字, 給出該結(jié)點左子樹的高度減去右子樹的高度所得的高度差,這個數(shù)字即為結(jié)點的平衡因子balance AVL樹任一結(jié)點平衡因子只能取 -1, 0, 156564191375378092882100-10-1000100平衡二叉樹平衡二叉樹 AVLAVL( (平衡化旋轉(zhuǎn)平衡化旋轉(zhuǎn)) ) 如果在一棵平衡的二叉查找樹中插入一個新結(jié)點，造成了不平衡。此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。 平衡化旋轉(zhuǎn)(處理)有兩類：1.單向

21、旋轉(zhuǎn) (單向右旋和單向左旋)2.雙向旋轉(zhuǎn) (先左后右旋轉(zhuǎn)和先右后左旋轉(zhuǎn))平衡二叉樹平衡二叉樹 AVLAVL( (平衡化單向旋轉(zhuǎn)平衡化單向旋轉(zhuǎn)) ) 如果這三個結(jié)點處于一條直線上(“/”型或“”型)，則采用單向旋轉(zhuǎn)進行平衡化 單向旋轉(zhuǎn)分為單向右旋(“/”型)和單向左旋(“”型)ACBCBA單向左旋單向左旋ACBABC單向右旋單向右旋平衡二叉樹平衡二叉樹 AVLAVL( (平衡化雙向旋轉(zhuǎn)平衡化雙向旋轉(zhuǎn)) ) 如果這三個結(jié)點處于一條折線上(“”型)，則采用雙向旋轉(zhuǎn)進行平衡化。 雙旋轉(zhuǎn)分為先左后右(“”型)ACB先左后右旋轉(zhuǎn)先左后右旋轉(zhuǎn)ACBABCBCA先右后左旋轉(zhuǎn)先右后左旋轉(zhuǎn)ACBABC平衡二叉樹平

22、衡二叉樹 AVLAVL( (單向右旋單向右旋) ) 在B左子樹BL上插入新結(jié)點使其高度增1，導(dǎo)致結(jié)點A的平衡因子增到 +2，造成不平衡。hhhAARBRBBLhh+1BAARBRBLhhh+1ARBRABBLh 為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個結(jié)點A、B和BL(“/”型) 以結(jié)點B為旋轉(zhuǎn)軸，將結(jié)點A順時針(右)旋轉(zhuǎn)。平衡二叉樹平衡二叉樹 AVLAVL( (單向左旋單向左旋) ) 在B右子樹BR中插入新結(jié)點，該子樹高度增1導(dǎo)致結(jié)點A的平衡因子變成-2，出現(xiàn)不平衡。hhhABBRALBLhhh+1ALABBRBLhhh+1BBRAALBL 沿插入路徑檢查三個結(jié)點A、B和BR(“”型) 以結(jié)

23、點B為旋轉(zhuǎn)軸，讓結(jié)點A反時針(左)旋轉(zhuǎn)平衡二叉樹平衡二叉樹 AVLAVL( (先左后右雙向旋轉(zhuǎn)先左后右雙向旋轉(zhuǎn)) ) 在C的子樹CL或CR中插入新結(jié)點，該子樹的高度增1。結(jié)點A的平衡因子變?yōu)?2，發(fā)生了不平衡hhAARCBLh-1h-1BCLCRhhAh-1hARCBLBCLCR平衡二叉樹平衡二叉樹 AVLAVL( (先左后右雙向旋轉(zhuǎn)先左后右雙向旋轉(zhuǎn)) ) 再以結(jié)點C為旋轉(zhuǎn)軸，做單向右旋hhAARCBLh-1hBCLCRhhAh-1hARCBLBCLCR 從結(jié)點A起沿插入路徑選取3個結(jié)點A、B和C(“”型) 以結(jié)點B為旋轉(zhuǎn)軸，作單向右旋hhABBRh-1hALCLCRC 再以結(jié)點C為旋轉(zhuǎn)軸，作

24、單向左旋hhAh-1hBBRCALCLCRhhABhALCLCRh-1CBR平衡二叉樹平衡二叉樹 AVLAVL( (舉例舉例) ) 畫出在初始為空的AVL樹中依次插入64,5,13,21,19,80,75,37,56時該樹的生長過程，并在有旋轉(zhuǎn)時說出旋轉(zhuǎn)的類型。64645645左右雙旋564521641234第九章第九章 查找查找 9.1 靜態(tài)查找表靜態(tài)查找表 9.2 動態(tài)查找表動態(tài)查找表 9.3 哈希表哈希表9.3.1 哈希表哈希表(散列表散列表)9.3哈希表哈希表 哈希(Hash)表又稱散列表 散列表是一種直接計算記錄存放地址的方法，它在關(guān)鍵碼與存儲位置之間直接建立了映象。 哈希函數(shù)是從關(guān)

25、鍵字空間到存儲地址空間的一種映象 哈希函數(shù)在記錄的關(guān)鍵字與記錄的存儲地址之間建立起一種對應(yīng)關(guān)系。可寫成：addr(ai)= H(keyi)H(H() )為哈希函數(shù)為哈希函數(shù)keyikeyi是表中元素是表中元素aiai關(guān)鍵字關(guān)鍵字, ,addr(aiaddr(ai) )是存儲地址是存儲地址哈希表哈希表( (查找查找) ) 哈希查找也叫散列查找，是利用哈希函數(shù)進行查找的過程。 首先利用哈希函數(shù)及記錄的關(guān)鍵字計算出記錄的存儲地址 然后直接到指定地址進行查找 不需要經(jīng)過比較，一次存取就能得到所查元素哈希表哈希表( (沖突沖突) ) 不同的記錄，其關(guān)鍵字通過哈希函數(shù)的計算，可能得到相同的地址 把不同的記

26、錄映射到同一個散列地址上，這種現(xiàn)象稱為沖突哈希表哈希表( (定義定義) ) 根據(jù)設(shè)定的哈希函數(shù) H(key) 和所選中的處理沖突的方法 將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集 (區(qū)間) 上 并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲位置 如此構(gòu)造所得的查找表稱之為“哈希表”哈希函數(shù)哈希函數(shù)( (要求要求) )哈希函數(shù)實現(xiàn)的一般是從一個大的集合（部分元素，空間位置上一般不連續(xù)）到一個小的集合（空間連續(xù)）的映射一個好的哈希函數(shù)，對于記錄中的任何關(guān)鍵字，將其映射到地址集合中任何一個地址的概率應(yīng)該是相等的即關(guān)鍵字經(jīng)過哈希函數(shù)得到一個“隨機的地址”哈希函數(shù)應(yīng)是簡單的，能在較短的時間內(nèi)計

27、算出結(jié)果。哈希函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵字，如果散列表允許有 m 個地址時，其值域必須在 0 到 m-1 之間。 散列函數(shù)計算出來的地址應(yīng)能均勻分布在整個地址空間中9.3.2 哈希函數(shù)哈希函數(shù)(直接定址法直接定址法) 直接定址法中，哈希函數(shù)取關(guān)鍵字的線性函數(shù) H(key) = a x key + b其中其中a a和和b b為常數(shù)為常數(shù)哈希函數(shù)哈希函數(shù)( (直接定址法舉例直接定址法舉例) ) H(key) = key - 2004131000062004131006鄧煦男信息工程學(xué)院112004131011張國明男信息工程學(xué)院172004131017劉金棠男信息工程學(xué)院2220041

28、31022陳俊東男信息工程學(xué)院252004131025邱益林男信息工程學(xué)院312004131031陳明亮男信息工程學(xué)院322004131032郭寧男信息工程學(xué)院哈希函數(shù)哈希函數(shù)( (直接定址法特性直接定址法特性) ) 直接定址法僅適合于地址集合的大小與關(guān)鍵字集合的大小相等的情況 當a=1時，H(key)=key，即用關(guān)鍵字作地址 在實際應(yīng)用中能使用這種哈希函數(shù)的情況很少哈希函數(shù)哈希函數(shù)( (數(shù)字分析法數(shù)字分析法) ) 假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, , us) 分析關(guān)鍵字集中的全體 從中提取分布均勻的若干位或它們的組合作為地址。哈希函數(shù)哈希函數(shù)( (數(shù)字分

29、析法舉例數(shù)字分析法舉例) ) 有80個記錄，關(guān)鍵字為8位十進制數(shù)，哈希地址為2位十進制數(shù)8 1 3 4 6 5 3 28 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 3 6 8 5 3 78 1 4 1 9 3 5 58 1 4 1 9 3 5 5.分析：分析： 只取只取8

30、只取只取1 只取只取3、4 只取只取2、7、5 數(shù)字分布近乎隨機數(shù)字分布近乎隨機所以：取所以：取任意兩位或兩位任意兩位或兩位 與另兩位的疊加作哈希地址與另兩位的疊加作哈希地址哈希函數(shù)哈希函數(shù)( (數(shù)字分析法特性數(shù)字分析法特性) ) 數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵碼每一位數(shù)值的分布情況 數(shù)字分析法完全依賴于關(guān)鍵碼集合。 如果換一個關(guān)鍵碼集合，選擇哪幾位要重新決定。哈希函數(shù)哈希函數(shù)( (平方取中法平方取中法) ) 以關(guān)鍵字的平方值的中間幾位作為存儲地址。 求“關(guān)鍵字的平方值” 的目的是“擴大差別” 同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響。此方法在詞典處理中使用十分廣泛。它先

31、計算構(gòu)成關(guān)鍵碼的標識符的內(nèi)碼的平方, 然后按照散列表的大小取中間的若干位作為散列地址。哈希函數(shù)哈希函數(shù)( (平方取中法舉例平方取中法舉例) )標識符的八進制內(nèi)碼表示及其平方值哈希函數(shù)哈希函數(shù)( (平方取中法特性平方取中法特性) ) 平方取中法是較常用的構(gòu)造哈希函數(shù)的方法 適合于關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)且頻度很高的情況 中間所取的位數(shù)，由哈希表長決定哈希函數(shù)哈希函數(shù)( (折疊法折疊法) ) 將關(guān)鍵字分割成位數(shù)相同的若干部分(最后部分的倍數(shù)可以不同)，然后取它們的疊加和(舍去進位)為哈希地址。 移位疊加: :將分割后的幾部分低位對齊相加將分割后的幾部分低位對齊相加 間界疊加: :從一端

32、沿分割界來回折送，然后對齊相加從一端沿分割界來回折送，然后對齊相加哈希函數(shù)哈希函數(shù)( (折疊法舉例折疊法舉例) ) 關(guān)鍵字為：0442205864，哈希地址位數(shù)為45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位疊加移位疊加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092間界疊加間界疊加 折疊法適合于關(guān)鍵字的數(shù)字位數(shù)特別多，而且每一位上數(shù)字分布大致均勻的情況哈希函數(shù)哈希函數(shù)( (除留余數(shù)法除留余數(shù)法) ) 取關(guān)鍵字被某個不大于哈希表長m的數(shù)p除后所得余數(shù)為哈希地址H(key) = key MOD p ( pm ) m為表長 p為不大于m的素

33、數(shù)或是不含20以下的質(zhì)因子9.3.3 處理沖突的方法處理沖突的方法 “處理沖突” 的實際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。 處理沖突的方法主要有三種：1.開放定址法2.再哈希法3.鏈地址法處理沖突的方法處理沖突的方法( (開放定址法開放定址法) )Hi = H(key)+di MOD m i=1,2,s為產(chǎn)生沖突的地址 H(key) 求得一個地址序列： H0, H1, H2, , Hs，1sm-1 m為哈希表長 當di取1,2,3,m-1時，稱這種開放定址法為線性探測再散列 當di取= 12,22,32,時，稱這種開放定址法為二次探測再散列處理沖突的方法處理沖突的方法( (開放定址法

34、線性探測開放定址法線性探測) ) 舉例：給定關(guān)鍵字集合19,01,23,14,55,68, 11,82,36，設(shè)定哈希函數(shù)H(key)=key MOD 11 (表長=11)1901231455681182361 1 2 1 3 6 2 5 10 1 2 3 4 5 6 7 8 9 1 0 處理沖突的方法處理沖突的方法( (開放定址法二次探測開放定址法二次探測) ) 舉例：給定關(guān)鍵字集合19,01,23,14,55,68, 11,82,36，設(shè)定哈希函數(shù)H(key)=key MOD 11 (表長=11)1 1 2 1 2 1 3 1 30 1 2 3 4 5 6 7 8 9 1 0 190123146855118236處理沖突的方法處理沖突的方法( (開放定址法特性開放定址法特性) ) 優(yōu)點：只要哈希表中有空位置，總能找到一個不發(fā)生沖突的