數(shù)據(jù)結構第9章

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

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

3、素之間人為地附加某種確定的關系，換句話說，用另之間人為地附加某種確定的關系，換句話說，用另外一種結構來表示查找表。外一種結構來表示查找表。如何進行查找？如何進行查找？查找的方法取決于查找表的結構。查找的方法取決于查找表的結構。9.1 靜態(tài)查找表靜態(tài)查找表typedef struct ElemType *elem; int length; / 表的長度 SSTable;假設靜態(tài)查找表靜態(tài)查找表的順序存儲結構順序存儲結構為n 順序查找順序查找( (算法算法) )9.1.1 順序查找表順序查找表1.從表中最后一個記錄開始 2.逐個進行記錄的關鍵字和給定值的比較 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設置設置“哨兵哨兵”的目的是省略對下標越界的檢查，提高算法執(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、表中的位置所進行的和關鍵字比較的次數(shù)的平均值 n ASL = PiCi i=1n為查找表的長度，即表中所含元素的個數(shù)Pi為查找第i個元素的概率(Pi=1)Ci是查找第i個元素時同給定值K比較的次數(shù)n 衡量查找算法的標準衡量查找算法的標準: : 時間復雜度、空間復雜度 平均查找長度ASLn順序查找順序查找( (算法性能分析算法性能分析) ) 對順序表而言，Ci=n-i+1 在等概率查找的情況下，Pi=1/n ASL=n*P1 +(n-1)P2 + 2Pn-1+ Pn = (n+1)/2n 順序查找順序查找( (特點特點) ) 優(yōu)點：1.簡單2.適應面廣(對表的結構無任何要求) 缺點：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時，說明有序表中沒有關鍵字等于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、近似結果時，可得近似結果1) 1(log2nASLbs折半查找折半查找( (特點特點) )折半查找的效率比順序查找高(特別是在靜態(tài)查找表的長度很長時)折半查找只能適用于有序表，并且以順序存儲結構存儲9.1.4 分塊查找分塊查找 分塊查找是一種索引順序表(分塊有序表)查找方法，是折半查找和順序查找的簡單結合 索引順序表(分塊有序表)將整個表分成幾塊，塊內無序，塊間有序 所謂塊間有序是指后一塊表中所有記錄的關鍵字均大于前一塊表中的最大關鍵字分塊查找分塊查找( (分塊有序表分塊有序表) ) 主表：用數(shù)組存放待查記錄,每個數(shù)據(jù)元素至少含有關鍵字域 索引表：每個結點含有最大關鍵字域和指向本塊第一個結點的

10、指針1 2 3 4 5 6 7 8 9 10 11519132175566437888092主表主表211755929索引表索引表找找64分塊查找分塊查找( (性能分析性能分析) ) 若將長度為n的表分成b塊，每塊含s個記錄，并設表中每個記錄查找概率相等 用折半查找方法在索引表中查找索引塊，ASL塊間log2(n/s+1) 用順序查找方法在主表對應塊中查找記錄，ASL塊內=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、如下特性的二叉樹：.若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；.若它的右子樹不空，則右子樹上所有結點的值均大于根結點的值；.它的左、右子樹也都分別是二叉排序樹。566459237881980211375二叉排序樹二叉排序樹( (查找查找) ) 二叉排序樹又稱二叉查找樹 查找算法： 給定值與根結點比較：1.若相等，查找成功2.若小于，查找左子樹3.若大于，查找右子樹在二叉排序樹中查找關在二叉排序樹中查找關鍵字值等于鍵字值等于3737, ,8888, ,949456645923788198021137594二叉排序樹二叉排序樹( (插入插入) )二叉排序樹是一種動態(tài)樹表當樹中不存在

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

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

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

15、pe e ) /當二叉查找樹T中不存在關鍵字等于 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 為新的根結點為新的根結點else if ( e.key data.key ) p-lchild = s;/ 插入插入 *s 為為 *p 的左孩子的

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

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

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

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

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

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

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

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

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

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

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

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

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

29、函數(shù)( (數(shù)字分析法舉例數(shù)字分析法舉例) ) 有80個記錄，關鍵字為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.分析：分析

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

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

32、疊加: :從一端沿分割界來回折送，然后對齊相加從一端沿分割界來回折送，然后對齊相加哈希函數(shù)哈希函數(shù)( (折疊法舉例折疊法舉例) ) 關鍵字為：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間界疊加間界疊加 折疊法適合于關鍵字的數(shù)字位數(shù)特別多，而且每一位上數(shù)字分布大致均勻的情況哈希函數(shù)哈希函數(shù)( (除留余數(shù)法除留余數(shù)法) ) 取關鍵字被某個不大于哈希表長m的數(shù)p除后所得余數(shù)為哈希地址H(key) = key MOD p ( pm ) m為表長

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

34、( (開放定址法線性探測開放定址法線性探測) ) 舉例：給定關鍵字集合19,01,23,14,55,68, 11,82,36，設定哈希函數(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 處理沖突的方法處理沖突的方法( (開放定址法二次探測開放定址法二次探測) ) 舉例：給定關鍵字集合19,01,23,14,55,68, 11,82,36，設定哈希函數(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ā)生沖突