1、第八章查找（Hash法） 本章要求 熟練掌握順序表和有序表的查找方法及其平均查找長度的計(jì)算方法； 復(fù)習(xí)二叉排序樹的構(gòu)造和查找方法； 熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別； 掌握按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長度。 本章難點(diǎn) 掌握哈希表的構(gòu)造方法第八章查找查找的基本概念基于線性表的查找法 基于樹的查找法 計(jì)算式查找法哈希法 要點(diǎn)小結(jié)第八章查找查找的基本概念基于線性表的查找法 基于樹的查找法 計(jì)算式查找法哈希法 要點(diǎn)小結(jié)Search Problem & Search EngineGoogle MythLarry Page &

2、 Sergey Brin(Google Co-Founder)Originator of BackRubAmit Singhal(Ph.D, India)(Google Fellow)Originator of PageRankGoogle 查詢的全過程Search Engine RevolutionaryOri Allon (Google Member)Originator of Orion查找的基本概念 列表：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合， 可利用任意數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。 關(guān)鍵字：數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)列表中的一個(gè)或一組數(shù)據(jù)元素。如果一個(gè)關(guān)鍵字可以唯一標(biāo)識(shí)列表中的一個(gè)

3、數(shù)據(jù)元素， 則稱其為主關(guān)鍵字，否則為次關(guān)鍵字。當(dāng)數(shù)據(jù)元素僅有一個(gè)數(shù)據(jù)項(xiàng)時(shí)， 數(shù)據(jù)元素的值就是關(guān)鍵字。 查找的基本概念 查找： 根據(jù)給定的關(guān)鍵字值，在特定的列表中確定一個(gè)其關(guān)鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。 若找到相應(yīng)的數(shù)據(jù)元素， 則稱查找是成功的，否則稱查找是失敗的，此時(shí)應(yīng)返回空地址及失敗信息，并可根據(jù)要求插入這個(gè)不存在的數(shù)據(jù)元素。 對(duì)于表的查找，一般有兩種情況： 靜態(tài)查找：指在查找過程中只是對(duì)數(shù)據(jù)元素進(jìn)行查找 動(dòng)態(tài)查找：指在實(shí)施查找的同時(shí)，插入找不到的元素，或從查找表中刪除查到的某個(gè)元素，即允許元素變化。查找的基本概念 顯然，查找算法中涉及到三類參量： 查找對(duì)象K

4、（找什么）； 查找范圍L（在哪找）； K在L中的位置（查找的結(jié)果）。 其中、為輸入?yún)⒘浚?為輸出參量，在函數(shù)中，輸入?yún)⒘勘夭豢缮?，輸出參量也可用函?shù)返回值表示。 平均查找長度：為確定數(shù)據(jù)元素在列表中的位置， 需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長度。 查找的基本概念 對(duì)于長度為n的列表， 查找成功時(shí)的平均查找長度為： 其中Pi為查找列表中第i個(gè)數(shù)據(jù)元素的概率，Ci為找到列表中第i個(gè)數(shù)據(jù)元素時(shí)，已經(jīng)進(jìn)行過的關(guān)鍵字比較次數(shù)。由于查找算法的基本運(yùn)算是關(guān)鍵字之間的比較操作，所以可用平均查找長度來衡量查找算法的性能。 niiinnCPCPCPCPASL12211查找

5、的基本概念查找的基本方法可以分為兩大類： 比較式查找法 基于線性表的查找法 基于樹的查找法 計(jì)算式查找法 也稱為HASH（哈希）查找法第八章查找 查找的基本概念 基于線性表的查找法 順序查找法 折半查找法 分塊查找法 基于樹的查找法 計(jì)算式查找法哈希法 要點(diǎn)小結(jié)順序查找(Sequential Search) 順序查找法的特點(diǎn)是，用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個(gè)比較，直到成功或失敗。存儲(chǔ)結(jié)構(gòu)通常為順序結(jié)構(gòu)，也可為鏈?zhǔn)浇Y(jié)構(gòu)。順序查找(Sequential Search)順序查找(Sequential Search)第八章查找 查找的基本概念 基于線性表的查找法 順序查找法 折半查找法 分塊

6、查找法 基于樹的查找法 計(jì)算式查找法哈希法 要點(diǎn)小結(jié)折半查找(Binary Search) 折半查找法又稱為二分法查找法，這種方法要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。其基本過程是： 將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功； 否則利用中間位置記錄將表分成前、后兩個(gè)子表， 如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。 重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。折半查找(Binary Search)折半查找(Binary Search) 【算法分析】用平均查找長度(AS

7、L)分析折半查找算法的性能。折半查找過程可用一個(gè)稱為判定樹的二叉樹描述，判定樹中每一結(jié)點(diǎn)對(duì)應(yīng)表中一個(gè)記錄，但結(jié)點(diǎn)值不是記錄的關(guān)鍵字，而是記錄在表中的位置序號(hào)。根結(jié)點(diǎn)對(duì)應(yīng)當(dāng)前區(qū)間的中間記錄， 左子樹對(duì)應(yīng)前一子表，右子樹對(duì)應(yīng)后一子表。 顯然，找到有序表中任一記錄的過程，對(duì)應(yīng)判定樹中從根結(jié)點(diǎn)到與該記錄相應(yīng)結(jié)點(diǎn)的路徑，而所做比較的次數(shù)恰為該結(jié)點(diǎn)在判定樹上的層次數(shù)。因此，折半查找成功時(shí)，關(guān)鍵字比較次數(shù)最多不超過判定樹的深度。 折半查找(Binary Search) 由于判定樹的葉子結(jié)點(diǎn)所在層次之差最多為1，故n個(gè)結(jié)點(diǎn)的判定樹的深度與n個(gè)結(jié)點(diǎn)的完全二叉樹的深度相等，均為 +1。這樣，折半查找成功時(shí)，關(guān)鍵字

8、比較次數(shù)最多不超過 +1。相應(yīng)地，折半查找失敗時(shí)的過程對(duì)應(yīng)判定樹中從根結(jié)點(diǎn)到某個(gè)含空指針的結(jié)點(diǎn)的路徑，因此，折半查找成功時(shí)，關(guān)鍵字比較次數(shù)最多也不超過判定樹的深度 +1。為便于討論，假定表的長度n=2h-1，則相應(yīng)判定樹必為深度是h的滿二叉樹，h=log2(n+1)。又假設(shè)每個(gè)記錄的查找概率相等， 則折半查找成功時(shí)的平均查找長度為：njjniiibsnnnjnCPASL12111)1(log121折半查找(Binary Search) 含11個(gè)記錄的有序表，其折半查找過程可用二叉判定樹表示：12345678910116121518222528354658606710412395811比較1次比

9、較2次比較3次比較4次ASL=(1+2+2+3+3+3+3+4+4+4+4)/11=33/11=3折半查找(Binary Search)演示折半查找(Binary Search) 折半查找方法的優(yōu)點(diǎn)： 查找速度快 平均性能好 折半查找方法的缺點(diǎn)： 要求待查表為有序表 插入刪除困難 因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。第八章查找 查找的基本概念 基于線性表的查找法 順序查找法 折半查找法 分塊查找法 基于樹的查找法 計(jì)算式查找法哈希法 要點(diǎn)小結(jié)分塊查找法 分塊查找法要求將列表組織成以下索引順序結(jié)構(gòu)： 首先將列表分成若干個(gè)塊（子表）。一般情況下，塊的長度均勻， 最后一塊可以不滿

10、。每塊中元素任意排列，即塊內(nèi)無序，但塊與塊之間有序。 構(gòu)造一個(gè)索引表。其中每個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)塊并記錄每塊的起始位置，以及每塊中的最大關(guān)鍵字（或最小關(guān)鍵字）。索引表按關(guān)鍵字有序排列。分塊查找法 下圖為一個(gè)索引順序表。其中包括三個(gè)塊，第一個(gè)塊的起始地址為0，塊內(nèi)最大關(guān)鍵字為25；第二個(gè)塊的起始地址為5， 塊內(nèi)最大關(guān)鍵字為58；第三個(gè)塊的起始地址為10，塊內(nèi)最大關(guān)鍵字為88。分塊查找法分塊查找的基本過程如下： 首先，將待查關(guān)鍵字K與索引表中的關(guān)鍵字進(jìn)行比較， 以確定待查記錄所在的塊。具體的可用順序查找法或折半查找法進(jìn)行。 進(jìn)一步用順序查找法，在相應(yīng)塊內(nèi)查找關(guān)鍵字為K的元素。 例如，在上述索引順序表中

11、查找36。首先，將36與索引表中的關(guān)鍵字進(jìn)行比較，因?yàn)?53658，所以36在第二個(gè)塊中， 進(jìn)一步在第二個(gè)塊中順序查找， 最后在8號(hào)單元中找到36。分塊查找法分塊查找的平均查找長度由兩部分構(gòu)成， 即查找索引表時(shí)的平均查找長度為LB，以及在相應(yīng)塊內(nèi)進(jìn)行順序查找的平均查找長度為LW：ASLbs=LB+LW假定將長度為n的表分成b塊，且每塊含s個(gè)元素，則b=n/s。又假定表中每個(gè)元素的查找概率相等，則每個(gè)索引項(xiàng)的查找概率為1/b，塊中每個(gè)元素的查找概率為1/s。若用順序查找法確定待查元素所在的塊，則有 21,21111siLbjbLsibjWB分塊查找法演示第八章查找 查找的基本概念 基于線性表的查

12、找法 基于樹的查找法 二叉排序樹 平衡二叉排序樹 B_樹 計(jì)算式查找法哈希法 要點(diǎn)小結(jié)二叉排序樹 二叉樹排序又稱二叉查找樹，它是一種特殊的樹。其定義為：二叉樹排序樹或者是一棵空樹， 或者是具有如下性質(zhì)的二叉樹： 若它的左子樹非空， 則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 若它的右子樹非空， 則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； 它的左右子樹也分別為二叉排序樹。 這是一個(gè)遞歸的定義。 注意：只要結(jié)點(diǎn)之間具有可比性即可。二叉排序樹 下圖，(a)所示為數(shù)字值間的比較，(b)所示為單詞字符的ASCII碼間的比較。二叉排序樹的查找 二叉排序樹的特性：根據(jù)二叉排序樹的定義（左子樹小于根結(jié)點(diǎn)，右子樹大

13、于根結(jié)點(diǎn)），根據(jù)二叉樹的中序遍歷的定義（先中序遍歷左子樹，訪問根結(jié)點(diǎn)，再中序遍歷右子樹），因此，中序遍歷一個(gè)二叉排序樹，可以得到一個(gè)遞增有序序列。 中序遍歷下面的二叉排序樹，則可得到一個(gè)遞增有序序列為：1,2,3,4,5,6,7,8,9。二叉排序樹的查找 因?yàn)槎媾判驑淇煽醋魇且粋€(gè)有序表，所以在二叉排序樹上進(jìn)行查找與折半查找類似，也是一個(gè)逐步縮小查找范圍的過程。 根據(jù)二叉排序樹的特點(diǎn)，首先將待查關(guān)鍵字k與根結(jié)點(diǎn)關(guān)鍵字t進(jìn)行比較，如果： (1) k=t， 則返回根結(jié)點(diǎn)地址； (2) kt， 則進(jìn)一步查右子樹。 顯然， 這是一個(gè)遞歸過程。但可以用遞歸與非遞歸兩種算法實(shí)現(xiàn)。 二叉排序樹查找 顯然，在

14、二叉排序樹上進(jìn)行查找，若查找成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根到待查結(jié)點(diǎn)的路徑。若不成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根到某個(gè)葉子結(jié)點(diǎn)的路徑。因此，二叉排序樹的查找與折半查找過程類似，在二叉排序樹中查找一個(gè)記錄時(shí)，其比較次數(shù)不超過樹的深度。 對(duì)長度為n的有序表而言，折半查找對(duì)應(yīng)的判定樹是唯一的，而含有n個(gè)結(jié)點(diǎn)的二叉排序樹卻是不唯一的。因?yàn)閷?duì)于同一個(gè)關(guān)鍵字集合，關(guān)鍵字插入的先后次序不同，所構(gòu)成的二叉排序樹的形態(tài)和深度也可能不同。二叉排序樹查找 二叉排序樹的平均查找長度ASL與二叉排序樹的形態(tài)有關(guān)，二叉排序樹的各分支越均衡，樹的深度淺，其平均查找長度ASL就越小。假設(shè)每個(gè)元素的查找概率相等，則它們的

15、平均查找長度分別是： (a)ASL=1/6(1+2+2+3+3+3)=14/6 (b) ASL=1/6(1+2+3+4+5+6)=21/6二叉排序樹查找 由此可見，二叉排序樹的平均查找長度ASL與二叉排序樹的形態(tài)有關(guān)。在最壞的情況下，二叉排序樹是通過把一個(gè)有序表的n個(gè)結(jié)點(diǎn)一次插入生成的，由此得到的二叉排序樹脫化為一棵深度為n的單支樹，它的平均查找長度和單鏈表上的順序查找相同，也是(n+1)/2。 在最好的情況下，二叉排序樹在生成過程中，樹的形態(tài)比較均勻，最終得到的是一棵形態(tài)與折半查找的判定樹相似的二叉排序樹，其平均查找長度大約是log2n。 若考慮把n個(gè)結(jié)點(diǎn)按各種可能的次序插入到二叉排序樹中，

16、則有n!棵二叉排序樹（其中有的形態(tài)相同），可以證明，對(duì)這些二叉排序樹的查找長度求平均，其平均查找長度仍然是O(log2n)。二叉排序樹查找 就平均性能而言，二叉排序樹上的查找和折半查找相差不大，并且二叉排序樹上插入和刪除結(jié)點(diǎn)十分方便，無需移動(dòng)大量結(jié)點(diǎn)。因此，對(duì)于需要經(jīng)常做插入、刪除、查找運(yùn)算的表，宜采用二叉排序樹結(jié)構(gòu)。這也就是人們常常將二叉排序樹稱為二叉查找樹的原因。第八章查找 查找的基本概念 基于線性表的查找法 基于樹的查找法 計(jì)算式查找法哈希法 哈希函數(shù)的構(gòu)造方法 處理沖突的方法 哈希表的查找過程 哈希法性能分析 要點(diǎn)小結(jié)哈希(Hash)法 哈希法又稱散列法、雜湊法以及關(guān)鍵字地址計(jì)算法等，

17、相應(yīng)的表稱為哈希表(Hash Tables)。 基本思想是： 首先在元素的關(guān)鍵字k和元素的存儲(chǔ)位置p之間建立一個(gè)對(duì)應(yīng)關(guān)系H，使得p=H(k)，H稱為哈希函數(shù)。 創(chuàng)建哈希表時(shí)，把關(guān)鍵字為k的元素直接存入地址為H(k)的單元；以后當(dāng)查找關(guān)鍵字為k的元素時(shí)，再利用哈希函數(shù)計(jì)算出該元素的存儲(chǔ)位置p=H(k)，從而達(dá)到按關(guān)鍵字直接存取元素的目的。HashHans Peter Luhn(1896.7.11964.8.19) GermanyBusiness Intelligence, KWIC method of indexing, Hash function(1953)Hans Peter Luhn ap

18、pears to have been the first to use the concept, and that Robert Morris used the term in a survey paper in CACM which elevated the term from technical jargon to formal terminology.Robert Morris, Sr.UNIX, Former NSA Chief Scientist(his son Robert Tappan Morris, 1988 Morris Worm)Hash Function A typica

19、l hash function at work. Note that the hash sums are always the same size, no matter how short or long the input is. Also note that the hash sums look very different even when there are only slight differences in the input.哈希法 當(dāng)關(guān)鍵字集合很大時(shí)，關(guān)鍵字值不同的元素可能會(huì)映象到哈希表的同一地址上，即 k1k2 ，但 H(k1)=H(k2)，這種現(xiàn)象稱為沖突，此時(shí)稱k1和k

20、2 為同義詞。 實(shí)際中，沖突是不可避免的，只能通過改進(jìn)哈希函數(shù)的性能來減少?zèng)_突。 綜上所述，哈希法主要包括以下兩方面的內(nèi)容： 如何構(gòu)造哈希函數(shù) 如何處理沖突哈希函數(shù)的構(gòu)造方法 構(gòu)造哈希函數(shù)的原則是： 函數(shù)本身便于計(jì)算； 計(jì)算出來的地址分布均勻，即對(duì)任一關(guān)鍵字key，H(key) 對(duì)應(yīng)不同地址的概率相等，目的是盡可能減少?zèng)_突。 下面介紹構(gòu)造哈希函數(shù)常用的五種方法： 數(shù)字分析法 平方取中法 分段疊加法 除留余數(shù)法 偽隨機(jī)數(shù)法數(shù)字分析法如果事先知道關(guān)鍵字集合，并且每個(gè)關(guān)鍵字的位數(shù)比哈希表的地址碼位數(shù)多時(shí)，可以從關(guān)鍵字中選出分布較均勻的若干位， 構(gòu)成哈希地址。例如，有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制整數(shù)

21、d1d2d3d7d8，如哈希表長取100，則哈希表的地址空間為： 0099。假設(shè)經(jīng)過分析，各關(guān)鍵字中d4和d7的取值分布較均勻， 則哈希函數(shù)為：H(key)=H(d1d2d3d7d8)=d4d7。例如， H(81346532)=43，H(81301367)=06。 相反， 假設(shè)經(jīng)過分析， 各關(guān)鍵字中 d1和d8的取值分布極不均勻，d1 都等于5，d8 都等于2，此時(shí)，如果哈希函數(shù)為：H(key)=H(d1d2d3d7d8)=d1d8， 則所有關(guān)鍵字的地址碼都是52，顯然不可取。 平方取中法當(dāng)無法確定關(guān)鍵字中哪幾位分布較均勻時(shí)，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。

22、這是因?yàn)椋浩椒胶笾虚g幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵字會(huì)以較高的概率產(chǎn)生不同的哈希地址。 例：我們把英文字母在字母表中的位置序號(hào)作為該英文字母的內(nèi)部編碼。例如K的內(nèi)部編碼為11，E的內(nèi)部編碼為05，Y的內(nèi)部編碼為25，A的內(nèi)部編碼為01, B的內(nèi)部編碼為02。由此組成關(guān)鍵字“KEYA”的內(nèi)部代碼為11052501，同理我們可以得到關(guān)鍵字“KYAB”、“AKEY”、 “BKEY”的內(nèi)部編碼。之后對(duì)關(guān)鍵字進(jìn)行平方運(yùn)算后，取出第7到第9位作為該關(guān)鍵字哈希地址， 如下表所示。 平方取中法 平方取中法求得的哈希地址關(guān)鍵字 內(nèi)部編碼 內(nèi)部編碼的平方值 H(key)關(guān)鍵字的哈希地址 KEYA 1105

23、2501 122157778355001 778 KYAB 11250102 126564795010404 795AKEY 01110525 001233265775625 265BKEY 02110525 004454315775625 315分段疊加法按哈希表地址位數(shù)將關(guān)鍵字分成位數(shù)相等的幾部分（最后一部分可以較短），然后將這幾部分相加，舍棄最高進(jìn)位后的結(jié)果就是該關(guān)鍵字的哈希地址。移位法是將分割后的每部分低位對(duì)齊相加折疊法是從一端向另一端沿分割界來回折疊（奇數(shù)段為正序，偶數(shù)段為倒序），然后將各段相加。例如：key=12360324711202065，哈希表長度為1000，則應(yīng)把關(guān)鍵字分成

24、3位一段，在此舍去最低的兩位65，分別進(jìn)行移位疊加和折疊疊加，求得哈希地址為105和907，如下圖所示。分段疊加法 由疊加法求哈希地址12 360 324 721 20 2 0+)1 1 0 512 33 0 624 72 1 10 2 0+) 9 0 7(a) 移位疊加 (b) 折疊疊加 除留余數(shù)法假設(shè)哈希表長為m， p為小于等于m的最大素?cái)?shù)， 則哈希函數(shù)為：h(key)=key%p， 其中%為模p取余運(yùn)算。例如，已知待散列元素為(18，75，60，43，54，90，46)，表長m=10， p=7， 則有h(18)=18 % 7=4 h(75)=75 % 7=5 h(60)=60 % 7=4

25、 h(43)=43 % 7=1 h (54)=54 % 7=5 h(90)=90 % 7=6 h(46)=46 % 7=4 此時(shí)沖突較多。除留余數(shù)法 為減少?zèng)_突， 可取較大的m值和p值， 如m=p=13， 結(jié)果如下：h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8 h(43)=43 % 13=4 h(54)=54 % 13=2 h(90)=90 % 13=12 h(46)=46 % 13=7 除留余數(shù)法求哈希地址54431846607590 0 1 2 3 4 5 6 7 8 9 10 11 12 偽隨機(jī)數(shù)法 采用一個(gè)偽隨機(jī)函數(shù)作哈希函數(shù)，即H(

26、key)=random(key)。 在實(shí)際應(yīng)用中， 應(yīng)根據(jù)具體情況， 靈活采用不同的方法， 并用實(shí)際數(shù)據(jù)測試它的性能，以便做出正確判定。 通常應(yīng)考慮以下五個(gè)因素： 計(jì)算哈希函數(shù)所需的時(shí)間（簡單）。 關(guān)鍵字的長度。 哈希表的大小。 關(guān)鍵字的分布情況。 記錄查找的頻率。 第八章查找 查找的基本概念 基于線性表的查找法 基于樹的查找法 計(jì)算式查找法哈希法 哈希函數(shù)的構(gòu)造方法 處理沖突的方法 哈希表的查找過程 哈希法性能分析 要點(diǎn)小結(jié)處理沖突的方法通過構(gòu)造性能良好的哈希函數(shù)，可以減少?zèng)_突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個(gè)關(guān)鍵問題。創(chuàng)建哈希表和查找哈希表都會(huì)遇到?jīng)_突，兩種情況下解決

27、沖突的方法應(yīng)該一致。下面以創(chuàng)建哈希表為例，說明解決沖突的方法。常用的解決沖突方法有以下四種：開放定址法再哈希法鏈地址法建立公共溢出區(qū)開放定址法 也稱再散列法，其基本思想是：當(dāng)關(guān)鍵字key的哈希地址h0= H(key)出現(xiàn)沖突時(shí)，以h0為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址h1，如果h1仍然沖突，再以h0為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址h2，直到找出一個(gè)不沖突的哈希地址hi，將相應(yīng)元素存入其中。這種方法有一個(gè)通用的再散列函數(shù)形式： 或其中，H(key)為哈希函數(shù)，h0=H(key)，m為表長， di稱為增量序列。 mdkeyHhii)%)(i=1， 2， ， n mdhhii)%(0i=1， 2， ， n 開放定

28、址法 增量序列的取值方式不同，相應(yīng)的再散列方式也不同。主要有以下三種： 線性探測再散列di=1，2，3， m-1 特點(diǎn)：沖突發(fā)生時(shí)，順序查看表中下一單元， 直到找出一個(gè)空單元或查遍全表。 二次探測再散列 di=12，-12， 22，-22，k2，-k2 (km/2) 特點(diǎn)：沖突發(fā)生時(shí)，在表的左右進(jìn)行跳躍式探測， 比較靈活。 開放定址法 偽隨機(jī)探測再散列 di=偽隨機(jī)數(shù)序列。 具體實(shí)現(xiàn)時(shí)，應(yīng)建立一個(gè)偽隨機(jī)數(shù)發(fā)生器，（如i=(i+p) %m）， 并給定一個(gè)隨機(jī)數(shù)做起點(diǎn)。開放定址法 例如，已知哈希表長度m=11，哈希函數(shù)為：H(key)= key%11， 則H(47)=3，H(26)=4，H(60)

29、=5，假設(shè)下一個(gè)關(guān)鍵字為69，則H(69)=3，與47沖突。如果用線性探測再散列處理沖突，下一個(gè)哈希地址為h1=(3+1)%11=4， 仍然沖突，再找下一個(gè)哈希地址為h2=(3+2)%11=5，還是沖突，繼續(xù)找下一個(gè)哈希地址為h3=(3+3)%11=6，此時(shí)不再?zèng)_突，將69填入6號(hào)單元，參見下圖(a)。 0123456789101147266069(a) 用線性探測再散列處理沖突開放定址法 已知哈希表長度m=11，哈希函數(shù)為：H(key)= key%11， 則H(47)=3，H(26)=4，H(60)=5，假設(shè)下一個(gè)關(guān)鍵字為69，則H(69)=3，與47沖突。如果用二次探測再散列處理沖突，下一

30、個(gè)哈希地址為h1=(3+12)%11=4， 仍然沖突，再找下一個(gè)哈希地址為h2=(3-12)%11=2，此時(shí)不再?zèng)_突，將69填入2號(hào)單元，參見下圖(b)。0123456789101169472660(b)用二次探測再散列處理沖突開放定址法 例如，已知哈希表長度m=11，哈希函數(shù)為：H(key)= key%11， 則H(47)=3，H(26)=4，H(60)=5，假設(shè)下一個(gè)關(guān)鍵字為69，則H(69)=3，與47沖突。如果用偽隨機(jī)探測再散列處理沖突，且偽隨機(jī)數(shù)序列為：2，5，9則下一個(gè)哈希地址為h1=(3+2)%11=5，仍然沖突，再找下一個(gè)哈希地址為h2=(3+5)%11=8，此時(shí)不再?zèng)_突，將6

31、9填入8號(hào)單元，參見下圖(c)。 0123456789101147266069(c)用偽隨機(jī)探測再散列處理沖突開放定址法 從上述例子可以看出，線性探測再散列容易產(chǎn)生“二次聚集”，即在處理同義詞的沖突時(shí)又導(dǎo)致非同義詞的沖突。 例如，當(dāng)表中i, i+1 ,i+2三個(gè)單元已滿時(shí)，下一個(gè)哈希地址為i, 或i+1 ,或i+2，或i+3的元素，都將填入i+3這同一個(gè)單元，而這四個(gè)元素并非同義詞。 線性探測再散列的優(yōu)點(diǎn)是：只要哈希表不滿，就一定能找到一個(gè)不沖突的哈希地址，而二次探測再散列和偽隨機(jī)探測再散列則不一定。開放定址法建立散列表演示再哈希法 同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù)：Hi=Rhi(key)， i=1

32、，2， ， n 當(dāng)哈希地址Hi=Rh1(key) 發(fā)生沖突時(shí)，再計(jì)算Hi=Rh2(key) 直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計(jì)算時(shí)間。 鏈地址法 基本思想是將所有哈希地址為i的元素構(gòu)成一個(gè)稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個(gè)單元中， 因而查找、插入和刪除主要在同義詞鏈中進(jìn)行。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況。 例如，已知一組關(guān)鍵字（32，40， 36， 53， 16， 46， 71， 27， 42， 24， 49， 64）， 哈希表長度為13，哈希函數(shù)為：H(key)=key%13，則用鏈地址法處理沖突的結(jié)果如下圖所示。 本例的平均查找長度：ASL=

33、(17+24+31)=1.5 鏈地址法處理沖突時(shí)的哈希表 鏈地址法處理沖突時(shí)的哈希表 建立公共溢出區(qū) 基本思想是將哈希表分為基本表和溢出表兩部分，凡是與基本表發(fā)生沖突的元素一律填入溢出表。第七章查找 查找的基本概念 基于線性表的查找法 基于樹的查找法 計(jì)算式查找法哈希法 哈希函數(shù)的構(gòu)造方法 處理沖突的方法 哈希表的查找過程 哈希法性能分析 要點(diǎn)小結(jié)哈希表的查找過程 哈希表的查找過程與哈希表的創(chuàng)建過程是一致的。 所設(shè)要查找關(guān)鍵字為為key的元素，查找過程如下： 首先計(jì)算h0=hash(key)。 如果單元h0為空， 則所查元素不存在； 如果單元h0中元素的關(guān)鍵字為key，則找到所查元素； 否則重

34、復(fù)下述解決沖突的過程： 按解決沖突的方法，找出下一個(gè)哈希地址hi; 如果單元hi為空，則所查元素不存在; 如果單元hi中元素的關(guān)鍵字為key，則找到所查元素。哈希表的查找算法#define m #define NULLKEY typedef int KeyType; /*假設(shè)關(guān)鍵字為整型*/typedef struct KeyType key; /*記錄中其它分量按需求確定*/ RecordType ;typedef RecordType HashTablem;int HashSearch( HashTable ht, KeyType K)h0=hash(K);哈希表的查找算法if (hth0

35、.key=NULLKEY) return(-1);else if (hth0.key=K) return (h0); else /* 用線性探測再散列解決沖突 */ for (i=1; i=m-1; i+) hi=(h0+i) % m; if (hthi .key=NULLKEY) return (-1); else if (hthi.key=K) return (hi); return (-1); 第八章查找 查找的基本概念 基于線性表的查找法 基于樹的查找法 計(jì)算式查找法哈希法 哈希函數(shù)的構(gòu)造方法 處理沖突的方法 哈希表的查找過程 哈希法性能分析 要點(diǎn)小結(jié)哈希法性能分析由于沖突的存在，哈希

36、法仍需進(jìn)行關(guān)鍵字比較，因此，仍需用平均查找長度來評(píng)價(jià)哈希法的查找性能。哈希法中影響關(guān)鍵字比較次數(shù)的因素有三個(gè)：哈希函數(shù)處理沖突的方法哈希表的裝填因子哈希表的裝填因子的定義如下： =哈希表中元素個(gè)數(shù) / 哈希表的長度可描述哈希表的裝滿程度。顯然，越小，發(fā)生沖突的可能性越小，而越大，發(fā)生沖突的可能性也越大。哈希法性能分析 假定哈希函數(shù)是均勻的，則影響平均查找長度的因素只剩下兩個(gè)： 處理沖突的方法 哈希表的裝填因子 以下按處理沖突的不同方法分別列出相應(yīng)的平均查找長度: 線性探測再散列 偽隨機(jī)探測再散列、二次探測再散列以及再哈希法 鏈址法哈希法性能分析 線性探測再散列 查找成功時(shí) 查找失敗時(shí) 偽隨機(jī)探

37、測再散列、二次探測再散列以及再哈希法 查找成功時(shí)11121succASL211121unsuccASL1ln1succASL哈希法性能分析 查找失敗時(shí) 鏈址法 查找成功時(shí) 查找失敗時(shí) 11unsuccASL21succASLeASLunsucc哈希法性能分析 從以上討論可知：哈希表的平均查找長度是裝填因子的函數(shù)，而與待散列元素?cái)?shù)目n無關(guān)。因此，無論元素?cái)?shù)目n有多大，都能通過調(diào)整，使哈希表的平均查找長度較小。 已知一組關(guān)鍵字序列（19，14，23，01，68，20，84，27，55，11，10，79）按哈希函數(shù)H(key)=key%13 和線性探測處理沖突構(gòu)造所得哈希表ht0.15,如下圖所示。

38、0123456789101112131415140168275519208479231110哈希法性能分析 手工計(jì)算等概率情況下查找成功的平均查找長度公式 其中Ci為查找第i個(gè)元素時(shí)所需的比較次數(shù)。 采用線性探測再散列法處理沖突，計(jì)算出在等概率查找的情況下其查找成功的平均查找長度為：niisuccCnASL11表中置入元素個(gè)數(shù)5.2)9433261(121succASL0123456789101112131415140168275519208479231110哈希法性能分析 手工計(jì)算等概率情況下查找不成功的平均查找長度公式 Ci為哈希函數(shù)取值為i時(shí)查找不成功的比較次數(shù)。 查找不成功的情況： 遇

39、到空單元 按解決沖突的方法完全探測一遍后仍未找到。0到r-1相當(dāng)于r個(gè)不成功的查找的入口，從每個(gè)入口進(jìn)入后，直到確定查找不成功為止，其關(guān)鍵字的比較次數(shù)就是與入口對(duì)應(yīng)的不成功查找長度。riiunsuccCrASL11哈希函數(shù)取值個(gè)數(shù)哈希法性能分析 采用線性探測再散列法處理沖突，計(jì)算出在等概率查找的情況下其查找不成功的平均查找長度為：0123456789101112131415140168275519208479231110623456789101112131131）（unsuccASL第八章查找查找的基本概念基于線性表的查找法 基于樹的查找法 計(jì)算式查找法哈希法要點(diǎn)小結(jié)要點(diǎn)小結(jié) 查找表的檢索機(jī)制

40、 線性索引：記錄關(guān)鍵字一般按序排列，以提高檢索速度，對(duì)應(yīng)檢索采用基于比較的檢索方法。 樹型索引：樹型的典型結(jié)構(gòu)是二叉排序樹，其檢索時(shí)間復(fù)雜度與樹的深度數(shù)量級(jí)，為對(duì)數(shù)函數(shù)，其對(duì)應(yīng)的檢索方法是基于樹表的檢索，即將待查找的表組織成樹、在樹型結(jié)構(gòu)上實(shí)現(xiàn)查找。 散列（哈希）結(jié)構(gòu)：根據(jù)數(shù)據(jù)的關(guān)鍵字“計(jì)算”數(shù)據(jù)的存儲(chǔ)地址。散列（哈希）表既是建立表的方法，也是查找表的方法，其對(duì)應(yīng)的檢索方法是“計(jì)算式”的檢索。要點(diǎn)小結(jié)平均查找長度為確定數(shù)據(jù)元素在列表中的位置，需和給定關(guān)鍵字進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長度。由于查找算法的基本運(yùn)算是關(guān)鍵字之間的比較操作，所以平均查找長度是衡量查

41、找算法性能的重要指標(biāo)。計(jì)算平均查找長度的基本公式對(duì)于長度為n的列表，查找成功時(shí)的平均查找長度為：Pi為查找列表中第i個(gè)元素的概率，Ci為找到列表中第i個(gè)元素時(shí)，已經(jīng)進(jìn)行過的關(guān)鍵字比較次數(shù)。niiinnCPCPCPCPASL12211要點(diǎn)小結(jié)計(jì)算方法采用公式法計(jì)算（通用），也可采用手工計(jì)算公式（具體），針對(duì)實(shí)際的具體問題，計(jì)算相應(yīng)的查找成功時(shí)的平均查找長度。雖然兩種方式在計(jì)算相同問題時(shí)得到的具體結(jié)果不一定相同，但基于的原理原則相同。故應(yīng)當(dāng)掌握這些方法原則并能應(yīng)用。折半查找折半查找要求待查找表應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)且按關(guān)鍵字有序排列。折半查找過程借助于折半判定樹加以描述。判定樹中每一結(jié)點(diǎn)對(duì)應(yīng)表中一個(gè)記錄在表中的位置序號(hào)。要點(diǎn)小結(jié) 折半查找算法的性能：在等概率時(shí)查找成功的平均查找長度與折半判定樹的深度相關(guān)： 折半查找算法速度快，平均性能好，但插入刪除困難。 二叉排序樹 性質(zhì)：中序遍歷一個(gè)二叉排序樹可以得到一個(gè)遞增有序序列。 含有n個(gè)結(jié)點(diǎn)的二叉排序樹型態(tài)不唯一，其構(gòu)造與數(shù)列的輸入順序有關(guān)。njjniiibsnnnjnCPASL12111)1(