數(shù)據(jù)結(jié)構(gòu)第九章查找.ppt

數(shù)據(jù)結(jié)構(gòu) 第九章 查找,本章內(nèi)容 9.1 查找的基本概念 9.2 靜態(tài)查找表 9.3 動(dòng)態(tài)查找表 9.4 哈希表,9-3,9.1 查找的基本概念,查找表(Search Table) 查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。對(duì)查找表的操作主要有： 查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中； 檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性； 在查找表中插入一個(gè)數(shù)據(jù)元素； 從查找表中刪去某個(gè)數(shù)據(jù)元素。 查找表分類 靜態(tài)查找表 僅作查詢和檢索操作的查找表。 動(dòng)態(tài)查找表 在查找過(guò)程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素,9-4,9.1 查找的基本概念,關(guān)鍵字(Key) 關(guān)鍵字是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。 主關(guān)鍵字：可以識(shí)別唯一的一個(gè)記錄的關(guān)鍵字 次關(guān)鍵字：能識(shí)別若干記錄的關(guān)鍵字 查找(Searching) 是根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）。,9-5,9.1 查找的基本概念,衡量查找算法的標(biāo)準(zhǔn) 時(shí)間復(fù)雜度； 空間復(fù)雜度； 平均查找長(zhǎng)度ASL：定義為確定記錄在表中的位置所進(jìn)行的和關(guān)鍵字比較的次數(shù)的平均值 n ASL = PiCi i=1 n為查找表的長(zhǎng)度，即表中所含元素的個(gè)數(shù) Pi為查找第i個(gè)元素的概率(Pi=1) Ci是查找第i個(gè)元素時(shí)同給定值K比較的次數(shù),9-6,9.2 靜態(tài)查找表,9.2.1 順序表的查找 順序查找算法是順序表（既無(wú)序表）的查找方法。在順序查找算法中，以順序表或線性鏈表表示靜態(tài)查找表。 面臨的問(wèn)題 下標(biāo)越界的檢查，需要相當(dāng)?shù)臅r(shí)間和空間代價(jià)。解決的辦法是，將ST.elem0.key 置為key,所有元素檢查完還沒(méi)有找到時(shí)，在ST.elem0處一定找到。從而免去了檢查下標(biāo)越界的時(shí)間。 順序查找算法 從表中最后一個(gè)記錄開(kāi)始 逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較 若某個(gè)記錄比較相等，則查找成功 若直到第1個(gè)記錄都比較不等，則查找不成功,9-7,9.2 靜態(tài)查找表,順序查找算法描述 設(shè)置“哨兵”的目的是省略對(duì)下標(biāo)越界的檢查，提高算法執(zhí)行速度。當(dāng)然，哨兵也可以設(shè)置在高下標(biāo)處。,int Search_Seq(SSTable ST, KeyType key) / 若查找成功，返回位置 ST.elem0.key = key; / “哨兵”， for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找 return i; / 找不到時(shí),i=0 ,9-8,9.2 靜態(tài)查找表,順序查找示舉例 在下列順序表中尋找62，如果找到，給出其所在位置的下標(biāo)。,監(jiān)視哨兵,比較次數(shù)=5,比較次數(shù)分析： 查找第n個(gè)元素： 1次 查找第n-1個(gè)元素： 2次 . 查找第1個(gè)元素： n次 查找第i個(gè)元素： n+1-i次 查找失?。?n+1次,0 1 2 3 4 5 6 7 8 9 10 11,9-9,9.2 靜態(tài)查找表,順序查找性能分析 對(duì)順序表而言，Ci=n-i+1 在等概率查找的情況下，Pi=1/n 平均查找長(zhǎng)度 ASLss=n*P1 +(n-1)P2 + 2Pn-1+ Pn = (n+1)/2 如果被查找的記錄概率不等時(shí)， ASLss在 PnPn-1 P2P1 時(shí)取極小值 若查找概率無(wú)法事先測(cè)定，則查找過(guò)程采取的改進(jìn)辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。 順序查找特點(diǎn) 優(yōu)點(diǎn)： 1.簡(jiǎn)單 2.適應(yīng)面廣(對(duì)表的結(jié)構(gòu)無(wú)任何要求) 缺點(diǎn)： 1.平均查找長(zhǎng)度較大 2.特別是當(dāng)n很大時(shí)，查找效率很低,9-10,9.2 靜態(tài)查找表,9.2.2 折半查找 折半查找算法是有序表的查找方法。在折半查找算法中，靜態(tài)查找表按關(guān)鍵字大小的次序，有序地存放在順序表中。 折半查找的原理 先確定待查記錄所在的范圍(前部分或后部分) 逐步縮小(一半)范圍直到找(不)到該記錄為止,9-11,9.2 靜態(tài)查找表,折半查找算法 n個(gè)對(duì)象從小到大存放在有序順序表ST中，k為給定值 設(shè)low、high指向待查元素所在區(qū)間的下界、上界，即low=1, high=n 設(shè)mid指向待查區(qū)間的中點(diǎn)，即 mid=(low+high)/2 讓k與mid指向的記錄比較 若 k=STmid.key，查找成功 若 kSTmid.key，則low=mid+1 下半?yún)^(qū)間 重復(fù)3,4操作，直至lowhigh時(shí)，查找失敗。,9-12,9.2 靜態(tài)查找表,折半成功查找舉例：在下列有序表中用折半查找法查找62所在位置。Key = 62,第一步：low=1, high=11, mid=6,STmid=ST6=5662, 則改變low；,第二步：low=mid+1=7, mid=9,STmid=ST9=8062, 則改變high；,第三步：high=mid-1=8, mid=7,STmid=ST7=62=62, 找到！,62,9-13,9.2 靜態(tài)查找表,折半查找失敗舉例：在上例有序表中找61。,high=6,low=7,找61,當(dāng)下界low大于上界high時(shí)，說(shuō)明有序 表中沒(méi)有關(guān)鍵字等于K的元素，查找失敗,9-14,9.2 靜態(tài)查找表,折半查找的性能分析 折半查找過(guò)程可以用二叉樹(shù)（也叫判定樹(shù)）來(lái)描述： 判定樹(shù)上每個(gè)結(jié)點(diǎn)需要的查找次數(shù)剛好為該結(jié)點(diǎn)所在的層數(shù)； 查找成功時(shí)查找次數(shù)不會(huì)超過(guò)判定樹(shù)的深度 n個(gè)結(jié)點(diǎn)的判定樹(shù)的深度為 log2n +1 比較次數(shù)最多不超過(guò) log2n +1 折半查找的算法復(fù)雜度為 log2n +1,9-15,9.2 靜態(tài)查找表,折半查找特點(diǎn) 折半查找的效率比順序查找高，特別是查找表的長(zhǎng)度很長(zhǎng)時(shí)； 折半查找只能適用于等概率有序表，并且以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。,9-16,9.2 靜態(tài)查找表,9.2.3 分塊查找 分塊查找是一種索引順序表(分塊有序表)查找方法，是折半查找和順序查找的簡(jiǎn)單結(jié)合； 索引順序表(分塊有序表)將整個(gè)表分成幾塊，塊內(nèi)無(wú)序，塊間有序 所謂塊間有序是指后一塊表中所有記錄的關(guān)鍵字均大于前一塊表中的最大關(guān)鍵字,9-17,9.2 靜態(tài)查找表,基本概念 主表：用數(shù)組存放待查記錄,每個(gè)數(shù)據(jù)元素至少含有關(guān)鍵字域 索引表：每個(gè)結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個(gè)結(jié)點(diǎn)的指針,9-18,9.2 靜態(tài)查找表,分塊查找舉例 采用折半查找方法在索引表中找到塊（第2塊） 用順序查找方法在主表對(duì)應(yīng)塊中找到記錄（第3個(gè)記錄）,找62,9-19,9.2 靜態(tài)查找表,分塊查找性能分析 若將長(zhǎng)度為n的表分成b塊，每塊含s個(gè)記錄，并設(shè)表中每個(gè)記錄查找概率相等 用折半查找方法在索引表中查找索引塊，ASL塊間log2(n/s+1) 用順序查找方法在主表對(duì)應(yīng)塊中查找記錄，ASL塊內(nèi)=s/2 ASLlog2(n/s+1) + s/2,9-20,9.3 動(dòng)態(tài)查找表,動(dòng)態(tài)查找表 如果應(yīng)用問(wèn)題涉及的數(shù)據(jù)量很大，而且數(shù)據(jù)經(jīng)常發(fā)生變化，如圖書(shū)館經(jīng)常購(gòu)進(jìn)圖書(shū)，每購(gòu)進(jìn)新書(shū)，需將新書(shū)記錄插入圖書(shū)表，對(duì)這類表除了提供前面的介紹的查找外，還要提供動(dòng)態(tài)查找功能： 查找某個(gè)“特定”元素是否在表中，若不在，將該元素插入； 查找某個(gè)“特定”元素是否在表中，若在，從表中刪除； 如何組織動(dòng)態(tài)查找表？ 用靜態(tài)查找方法不能滿足要求了。本節(jié)介紹幾種方法。,9-21,9.3 動(dòng)態(tài)查找表,9.3.1 二叉排序樹(shù) 二叉排序樹(shù)又稱二叉查找樹(shù) 空樹(shù)或者是具有如下特性的二叉樹(shù)： 若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； 左、右子樹(shù)也都分別是二叉排序樹(shù)。,21,二叉排序樹(shù),非二叉排序樹(shù),9-22,9.3 動(dòng)態(tài)查找表,二叉排序樹(shù)查找算法 給定值與根結(jié)點(diǎn)比較： 若相等，查找成功 若小于，查找左子樹(shù) 若大于，查找右子樹(shù),例1：在右圖二叉排序樹(shù)中查找關(guān)鍵字值等于37,37,找到,例2：在右圖二叉排序樹(shù)中查找關(guān)鍵字值等于88,找到,例3：在右圖二叉排序樹(shù)中查找關(guān)鍵字值等于94,無(wú)此數(shù),9-23,9.3 動(dòng)態(tài)查找表,二叉排序樹(shù)插入 二叉排序樹(shù)是一種動(dòng)態(tài)樹(shù)表。 當(dāng)樹(shù)中不存在查找的結(jié)點(diǎn)時(shí)，作插入操作 新插入的結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)（只需改動(dòng)一個(gè)結(jié)點(diǎn)的指針） 該葉子結(jié)點(diǎn)是查找不成功時(shí)路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)左孩子或右孩子(新結(jié)點(diǎn)值小于或大于該結(jié)點(diǎn)值),例：在右圖二叉樹(shù)中插入結(jié)點(diǎn)94。,9-24,9.3 動(dòng)態(tài)查找表,二叉排序樹(shù)生成 例：畫(huà)出在初始為空的二叉排序樹(shù)中依次插入56,64,92,80,88,75時(shí)該樹(shù)的生長(zhǎng)全過(guò)程,56,9-25,9.3 動(dòng)態(tài)查找表,二叉排序樹(shù)中序遍歷 中序遍歷二叉排序樹(shù)，可得到一個(gè)關(guān)鍵字的有序序列,如5,13,19,21,37,56,64,92,75,80,88,9-26,9.3 動(dòng)態(tài)查找表,二叉排序樹(shù)刪除 刪除二叉排序樹(shù)中的一個(gè)結(jié)點(diǎn)后，必須保持二叉排序樹(shù)的特性：左子樹(shù)的所有結(jié)點(diǎn)值小于根結(jié)點(diǎn)，右子樹(shù)的所有結(jié)點(diǎn)值大于根結(jié)點(diǎn)。也即保持中序遍歷后，輸出為有序序列 被刪除結(jié)點(diǎn)具有以下三種情況 是葉子結(jié)點(diǎn) 只有左子樹(shù)或右子樹(shù) 同時(shí)有左、右子樹(shù) 下面針對(duì)三種情況各舉一例。,9-27,9.3 動(dòng)態(tài)查找表,被刪除結(jié)點(diǎn)是葉子結(jié)點(diǎn)：直接刪除結(jié)點(diǎn)，并讓其父結(jié)點(diǎn)指向該結(jié)點(diǎn)的指針變?yōu)榭铡?例：刪除右二叉排序樹(shù)中的88節(jié)點(diǎn),56,64,5,92,37,88,19,80,21,13,75,9-28,9.3 動(dòng)態(tài)查找表,被刪除結(jié)點(diǎn)只有左子樹(shù)或右子樹(shù) 刪除結(jié)點(diǎn),讓其父結(jié)點(diǎn)指向該結(jié)點(diǎn)的指針指向其左子樹(shù)(或右子樹(shù)),即用孩子結(jié)點(diǎn)替代被刪除結(jié)點(diǎn)即可 例：對(duì)于右邊二叉排序樹(shù)中，先刪除節(jié)點(diǎn)37，再刪除節(jié)點(diǎn)64。,56,5,13,9-29,9.3 動(dòng)態(tài)查找表,被刪除結(jié)點(diǎn)p既有左子樹(shù)，又有右子樹(shù) 以中序遍歷時(shí)的直接前驅(qū)s替代被刪除結(jié)點(diǎn)p，然后再按照前面介紹的發(fā)刪除該直接前驅(qū)s（只可能有左孩子）,56,64,5,92,37,88,80,13,75,例：在右邊二叉排序樹(shù)中,節(jié)點(diǎn)56 的中序遍歷的直接前趨是節(jié)點(diǎn)37。,9-30,9.3 動(dòng)態(tài)查找表,二叉排序樹(shù)性能分析 在最好的情況下，二叉排序樹(shù)為一近似完全二叉樹(shù)時(shí)，其查找深度為log2n量級(jí)，即其時(shí)間復(fù)雜性為O(log2n) 在最壞的情況下，二叉排序樹(shù)為近似線性表時(shí)(如以升序或降序輸入結(jié)點(diǎn)時(shí)，見(jiàn)右圖)，其查找深度為n量級(jí)，即其時(shí)間復(fù)雜性為O(n),9-31,9.3 動(dòng)態(tài)查找表,二叉排序樹(shù)特性 一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列（通過(guò)中序遍歷） 插入新記錄時(shí)，只需改變一個(gè)結(jié)點(diǎn)的指針，相當(dāng)于在有序序列中插入一個(gè)記錄而不需要移動(dòng)其它記錄 二叉排序樹(shù)既擁有類似于折半查找的特性，又采用了鏈表作存儲(chǔ)結(jié)構(gòu) 但當(dāng)插入記錄的次序不當(dāng)時(shí)(如升序或降序)，則二叉排序樹(shù)深度很深（見(jiàn)右圖），增加了查找的時(shí)間,9-32,9.3 動(dòng)態(tài)查找表,平衡二叉樹(shù) 平衡二叉樹(shù)(Balanced Binary Tree, Height-Balanced Tree,又稱AVL樹(shù),Adelsen - Velskii and Landis，阿德?tīng)柹痪S爾斯和蘭迪斯)是二叉排序樹(shù)的另一種形式。其特點(diǎn)為：樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)深度之差的絕對(duì)值不大于1，即|hL-hR|1?？梢宰C明，它們的深度和logn是同數(shù)量級(jí)的（其中n為節(jié)點(diǎn)個(gè)數(shù)）。,AVL樹(shù),非AVL樹(shù),9-33,9.3 動(dòng)態(tài)查找表,平衡二叉樹(shù)平衡因子 每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字, 給出該結(jié)點(diǎn)左子樹(shù)的高度減去右子樹(shù)的高度所得的高度差,這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子(balance factor) AVL樹(shù)任一結(jié)點(diǎn)平衡因子只能取 -1, 0, 1 若某個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則這棵二叉搜索樹(shù)就失去了平衡，不再是AVL樹(shù)。,9-34,9.3 動(dòng)態(tài)查找表,非平衡二叉樹(shù)的平衡處理 若一棵二叉排序樹(shù)是平衡二叉樹(shù)，扦入某個(gè)結(jié)點(diǎn)后，可能會(huì)變成非平衡二叉樹(shù)，這時(shí)，就可以對(duì)該二叉樹(shù)進(jìn)行平衡處理，使其變成一棵平衡二叉樹(shù)。 處理的原則應(yīng)該是處理與插入點(diǎn)最近的、而平衡因子又比1大或比-1小的結(jié)點(diǎn)。下面將分四種情況討論平衡處理。,9-35,9.3 動(dòng)態(tài)查找表,LL型 的處理(左左型) 如下圖所示，若在C的左孩子B上扦入一個(gè)左孩子結(jié)點(diǎn)A，使C的平衡因子由1變成了2，成為不平衡的二叉樹(shù)序樹(shù)。 平衡處理：將C順時(shí)針旋轉(zhuǎn)，成為B的右子樹(shù)，而原來(lái)B的右子樹(shù)則變成C的左子樹(shù)，待扦入結(jié)點(diǎn)A作為B的左子樹(shù)。,結(jié)點(diǎn)旁邊的數(shù)字表示該 結(jié)點(diǎn)的平衡因子,9-36,9.3 動(dòng)態(tài)查找表,LR型的處理(左右型) 如下圖所示，在C的左孩子A上扦入一個(gè)右孩子B，使的C的平衡因子由1變成了2，成為不平衡的二叉排序樹(shù)。 平衡處理：將B變到A與C 之間，使之成為L(zhǎng)L型，然后按第1種情形LL型處理。,結(jié)點(diǎn)旁邊的數(shù)字表示該 結(jié)點(diǎn)的平衡因子,9-37,9.3 動(dòng)態(tài)查找表,RR型的處理(右右型) 如下圖所示，在A的右孩子B上扦入一個(gè)右孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹(shù)。 平衡處理：將A逆時(shí)針旋轉(zhuǎn)，成為B的左子樹(shù)，而原來(lái)B的左子樹(shù)則變成A的右子樹(shù)，待扦入結(jié)點(diǎn)C成為B的右子樹(shù)。,結(jié)點(diǎn)旁邊的數(shù)字表示該 結(jié)點(diǎn)的平衡因子,9-38,9.3 動(dòng)態(tài)查找表,RL型的處理(右左型) 如下圖所示，在A的右孩子C上扦入一個(gè)左孩子B，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹(shù)。 平衡處理：將B變到A與C之間，使之成為RR型，然后按第(3) 種情形RR型處理。,結(jié)點(diǎn)旁邊的數(shù)字表示該 結(jié)點(diǎn)的平衡因子,9-39,9.3 動(dòng)態(tài)查找表,例1：給定一個(gè)關(guān)鍵字序列4,5,7,2 ,1,3,6，試生成一棵平衡二叉樹(shù)。 分析：平衡二叉樹(shù)實(shí)際上也是一棵二叉排序樹(shù)，故可以按建立二叉排序樹(shù)的思想建立，在建立的過(guò)程中，若遇到不平衡，則進(jìn)行相應(yīng)平衡處理，最后就可以建成一棵平衡二叉樹(shù)。具體生成過(guò)程見(jiàn)下圖。,9-40,9.3 動(dòng)態(tài)查找表,9-41,9.3 動(dòng)態(tài)查找表,9-42,9.3 動(dòng)態(tài)查找表,平衡二叉樹(shù)的查找及性能分析 平衡二叉樹(shù)本身就是一棵二叉排序樹(shù)，故它的查找與二叉排序樹(shù)完全相同。但它的查找 性能優(yōu)于二叉排序樹(shù)，不像二叉排序樹(shù)一樣，會(huì)出現(xiàn)最壞的時(shí)間復(fù)雜度O(n)，它的時(shí)間復(fù)雜度與二叉排序樹(shù)的最好時(shí)間復(fù)雜相同，都為O(log2n)。,9-43,9.3 動(dòng)態(tài)查找表,例2，對(duì)例1給定的關(guān)鍵字序列4,5,7,2,1,3,6，試用二叉排序樹(shù)和平衡二叉樹(shù)兩種方法查找，給出查找6的次數(shù)及成功的平均查找長(zhǎng)度。 分析：由于關(guān)鍵字序列的順序己經(jīng)確定，故得到的二叉排序樹(shù)和平衡二叉樹(shù)都是唯一的。得到的平衡二叉樹(shù)見(jiàn)下座圖，得到的二叉排序樹(shù)見(jiàn)下右圖。,從右圖的二叉排序樹(shù)可知，查找6需4次，平均查找長(zhǎng)度 ASL=(1+2+2+3+3+3+4)/7=18/72.57 從左圖的平衡二叉樹(shù)可知，查找6需2次，平均查找長(zhǎng)度 ASL=(1+2+2+3+3+3+3)=17/72.43 從結(jié)果可知，平衡二叉樹(shù)的查找性能優(yōu)于二叉排序樹(shù)。,9-44,9.4 哈希表,9.4.1 哈希表 哈希(Hash)表又稱散列表,是一種直接計(jì)算記錄存放地址的方法，它在關(guān)鍵碼與存儲(chǔ)位置之間直接建立了映象。 哈希函數(shù) 哈希函數(shù)是從關(guān)鍵字空間到存儲(chǔ)地址空間的一種映象 哈希函數(shù)在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立起一種對(duì)應(yīng)關(guān)系?？蓪?xiě)成： addr(ai)= H(keyi) H( )為哈希函數(shù) keyi是表中元素ai關(guān)鍵字,addr(ai)是存儲(chǔ)地址,9-45,9.4 哈希表,哈希查找 哈希查找也叫散列查找，是利用哈希函數(shù)進(jìn)行查找的過(guò)程 首先利用哈希函數(shù)及記錄的關(guān)鍵字計(jì)算出記錄的存儲(chǔ)地址 然后直接到指定地址進(jìn)行查找 不需要經(jīng)過(guò)比較，一次存取就能得到所查元素 哈希沖突 不同的記錄，其關(guān)鍵字通過(guò)哈希函數(shù)的計(jì)算，可能得到相同的地址 把不同的記錄映射到同一個(gè)散列地址上，這種現(xiàn)象稱為沖突,9-46,9.4 哈希表,哈希表定義 根據(jù)設(shè)定的哈希函數(shù) H(key) 和所選中的處理沖突的方法 將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集上 以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲(chǔ)位置 如此構(gòu)造所得的查找表稱之為“哈希表”。 哈希函數(shù)均勻性 哈希函數(shù)實(shí)現(xiàn)的一般是從一個(gè)大的集合（部分元素，空間位置上一般不連續(xù)）到一個(gè)小的集合（空間連續(xù)）的映射 一個(gè)好的哈希函數(shù)，對(duì)于記錄中的任何關(guān)鍵字，將其映射到地址集合中任何一個(gè)地址的概率應(yīng)該是相等的 即關(guān)鍵字經(jīng)過(guò)哈希函數(shù)得到一個(gè)“隨機(jī)的地址”,9-47,9.4 哈希表,9.4.2 哈希函數(shù) 要求 哈希函數(shù)應(yīng)是簡(jiǎn)單的，能在較短的時(shí)間內(nèi)計(jì)算出結(jié)果 哈希函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵字，如果散列表允許有 m 個(gè)地址時(shí)，其值域必須在 0 到 m-1 之間 散列函數(shù)計(jì)算出來(lái)的地址應(yīng)能均勻分布在整個(gè)地址空間中,9-48,9.4 哈希表,哈希函數(shù)(直接定址法) 直接定址法中，哈希函數(shù)取關(guān)鍵字的線性函數(shù) H(key) = a key + b 其中a和b為常數(shù) 直接定址法舉例 H(key) = key - 2005131000,9-49,9.4 哈希表,直接定址法特性 直接定址法僅適合于地址集合的大小與關(guān)鍵字集合的大小相等的情況 當(dāng)a=1時(shí)，H(key)=key，即用關(guān)鍵字作地址 在實(shí)際應(yīng)用中能使用這種哈希函數(shù)的情況很少,9-50,9.4 哈希表,哈希函數(shù)(數(shù)字分析法) 假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, , us) 分析關(guān)鍵字集中的全體 從中提取分布均勻的若干位或它們的組合作為地址。,9-51,9.4 哈希表,數(shù)字分析法舉例 有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù),分析：只取8 只取1 只取3、4 只取2、7、5 數(shù)字分布近乎隨機(jī) 所以：取任意兩位或兩位與另兩位的疊加作哈希地址,9-52,9.4 哈希表,數(shù)字分析法特性 數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵碼每一位數(shù)值的分布情況 數(shù)字分析法完全依賴于關(guān)鍵碼集合。 如果換一個(gè)關(guān)鍵碼集合，選擇哪幾位要重新決定。,9-53,9.4 哈希表,哈希函數(shù)(平方取中法) 以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。 求“關(guān)鍵字的平方值” 的目的是“擴(kuò)大差別” 同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。,9-54,9.4 哈希表,平方取中法舉例 此方法在詞典處理中使用十分廣泛。它先計(jì)算構(gòu)成關(guān)鍵碼的標(biāo)識(shí)符的內(nèi)碼的平方, 然后按照散列表的大小取中間的若干位作為散列地址。 標(biāo)識(shí)符的八進(jìn)制內(nèi)碼表示及其平方值,標(biāo)識(shí)符 內(nèi)碼 內(nèi)碼的平方 散列地址 A 01 01 001 A1 0134 20420 042 B 02 4 004 DMAX 04150130 21526443617100 443 DMAX1 0415013034 5264473522151420 352 AMAX 01150130 135423617100 236 AMAX1 0115013034 3454246522151420 652,9-55,9.4 哈希表,平方取中法特性 平方取中法是較常用的構(gòu)造哈希函數(shù)的方法 適合于關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)且頻度很高的情況 中間所取的位數(shù)，由哈希表長(zhǎng)決定,9-56,9.4 哈希表,哈希函數(shù)(折疊法) 將關(guān)鍵字分割成位數(shù)相同的若干部分(最后部分的位數(shù)可以不同)，然后取它們的疊加和(舍去進(jìn)位)為哈希地址。 移位疊加:將分割后的幾部分低位對(duì)齊相加 間界疊加:從一端沿分割界來(lái)回折送，然后對(duì)齊相加,9-57,9.4 哈希表,折疊法舉例：關(guān)鍵字為：0442205864，哈希地址位數(shù)為4 折疊法特性 折疊法適合于關(guān)鍵字的數(shù)字位數(shù)特別多，而且每一位上數(shù)字分布大致均勻的情況,9-58,9.4 哈希表,哈希函數(shù)(除留余數(shù)法) 取關(guān)鍵字被某個(gè)不大于哈希表長(zhǎng)m的數(shù)p除后所得余數(shù)為哈希地址 H(key) = key MOD p ( pm ) m為表長(zhǎng) p為不大于m的素?cái)?shù)或是不含20以下的質(zhì)因子 哈希函數(shù)(除留余數(shù)法p值) 給定一組關(guān)鍵字為: 12,39,18,24,33,21，若取 p=9, 則他們對(duì)應(yīng)的哈希函數(shù)值將為: 3, 3, 0, 6, 6, 3 可見(jiàn)，若p中含質(zhì)因子3, 則所有含質(zhì)因子3的關(guān)鍵字均映射到“3 的倍數(shù)”的地址上，從而增加了“沖突”的可能 除留余數(shù)法特性 除留余數(shù)法是一種最簡(jiǎn)單、最常用的構(gòu)造哈希函數(shù)的方法 可以對(duì)關(guān)鍵字直接取模(MOD)，也可在折疊、平方取中等運(yùn)算之后取模。,9-59,9.4 哈希表,9.4.3 處理沖突法 “處理沖突” 的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。處理沖突的方法主要有三種： 開(kāi)放定址法 再哈希法 鏈地址法,9-60,9.4 哈希表,處理沖突的方法(開(kāi)放定址法) 為產(chǎn)生沖突的地址 H(key) 求得一個(gè)空的地址序列：H0, H1, H2, , Hs，1sm-1 Hi = H(key)+di MOD m ( i=1,2,s ) H(key)為哈希函數(shù) m為哈希表長(zhǎng) 當(dāng)di取1,2,3,m-1時(shí)，稱這種開(kāi)放定址法為線性探測(cè)再散列。,9-61,舉例：在長(zhǎng)度為11的哈希表中已填有關(guān)鍵字分別為17，60和29的記錄（哈希函數(shù)H(key) key MOD 11），現(xiàn)有第四個(gè)記錄，其關(guān)鍵字為38，由哈希函數(shù)得到的哈希地址為5，產(chǎn)生沖突。 線性探測(cè)再散列：得到下一個(gè)地址6，仍沖突；再求下一個(gè)地址7，仍沖突；直到哈希地址為8的位置（“空”）時(shí)止。 二次探測(cè)再散列：應(yīng)填入序號(hào)為4的位置。 偽隨機(jī)探測(cè)再散列：偽隨機(jī)數(shù)列9, 應(yīng)填入序號(hào)為2的位置。,9.4 哈希表,9-62,9.4 哈希表,用開(kāi)放定址處理沖突時(shí)，關(guān)鍵字為38的記錄插入前后的哈希表,9-63,9.4 哈希表,處理沖突的方法(再哈希法) Hi = RHi (key) ( i = 1, 2, , k ) 其中，R、Hi均是不同的哈希函數(shù)，即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。 再哈希法特點(diǎn)：不易產(chǎn)生聚集，但增加計(jì)算時(shí)間 處理沖突的方法(鏈地址法) 將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中。假設(shè)某哈希函數(shù)產(chǎn)生的哈希地址區(qū)間0, m1上，則設(shè)立一個(gè)指針型向量： Chain Chain Hashm; 其每個(gè)分裂的初始狀態(tài)都是空指針。凡哈希地址為i的記錄都插入到頭指針為Chain Hashm的鏈表中。在鏈表中的插入位置可以在表頭或表尾，也可以在中間，以保持同義詞在同一線性鏈表中按關(guān)鍵字有序。,9-64,9.4 哈希表,舉例：給定關(guān)鍵字集合19,01,23,14,55,68, 11,82,36，設(shè)定哈希函數(shù)H(key)=key MOD 11 (表長(zhǎng)=11)表后插入 查找不成功，再插入新結(jié)點(diǎn)時(shí)，用表后插入方法較好,9-65,9.4 哈希表,舉例：給定關(guān)鍵字集合19,01,23,14,55,68, 11,82,36，設(shè)定哈希函數(shù)H(key)=key MOD 11 (表長(zhǎng)=11)表頭插入 給定關(guān)鍵字集合，逐步生成哈希表時(shí)，用表頭插入方法較好,9-66,9.4 哈希表,9.4.4 哈希表的實(shí)現(xiàn) 假設(shè)哈希函數(shù)為關(guān)鍵字求模運(yùn)算，哈希表用拉鏈法解決沖突，其結(jié)構(gòu)可以定義如下：,#define LEN 31 / 表長(zhǎng)LEN最好為質(zhì)數(shù) type