數(shù)據(jù)結(jié)構(gòu)于算法分析 Hash法

數(shù)據(jù)結(jié)構(gòu)于算法分析Hash法第1頁(yè)/共89頁(yè)第八章查找查找的基本概念基于線性表的查找法基于樹(shù)的查找法計(jì)算式查找法——哈希法要點(diǎn)小結(jié)第2頁(yè)/共89頁(yè)第八章查找查找的基本概念基于線性表的查找法基于樹(shù)的查找法計(jì)算式查找法——哈希法要點(diǎn)小結(jié)第3頁(yè)/共89頁(yè)SearchProblem&SearchEngine第4頁(yè)/共89頁(yè)GoogleMythLarryPage&SergeyBrin(GoogleCo-Founder)OriginatorofBackRub?AmitSinghal(Ph.D,India)(GoogleFellow)OriginatorofPageRank?第5頁(yè)/共89頁(yè)Google查詢的全過(guò)程第6頁(yè)/共89頁(yè)SearchEngine'Revolutionary'OriAllon(GoogleMember)OriginatorofOrion?第7頁(yè)/共89頁(yè)查找的基本概念列表：由同一類型的數(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è)數(shù)據(jù)元素，則稱其為主關(guān)鍵字，否則為次關(guān)鍵字。當(dāng)數(shù)據(jù)元素僅有一個(gè)數(shù)據(jù)項(xiàng)時(shí)，數(shù)據(jù)元素的值就是關(guān)鍵字。第8頁(yè)/共89頁(yè)查找的基本概念查找：根據(jù)給定的關(guān)鍵字值，在特定的列表中確定一個(gè)其關(guān)鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。若找到相應(yīng)的數(shù)據(jù)元素，則稱查找是成功的，否則稱查找是失敗的，此時(shí)應(yīng)返回空地址及失敗信息，并可根據(jù)要求插入這個(gè)不存在的數(shù)據(jù)元素。對(duì)于表的查找，一般有兩種情況：靜態(tài)查找：指在查找過(guò)程中只是對(duì)數(shù)據(jù)元素進(jìn)行查找動(dòng)態(tài)查找：指在實(shí)施查找的同時(shí)，插入找不到的元素，或從查找表中刪除查到的某個(gè)元素，即允許元素變化。第9頁(yè)/共89頁(yè)查找的基本概念顯然，查找算法中涉及到三類參量：①查找對(duì)象K（找什么）；②查找范圍L（在哪找）；③K在L中的位置（查找的結(jié)果）。其中①、②為輸入?yún)⒘?，③為輸出參量，在函?shù)中，輸入?yún)⒘勘夭豢缮伲敵鰠⒘恳部捎煤瘮?shù)返回值表示。平均查找長(zhǎng)度：為確定數(shù)據(jù)元素在列表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度。第10頁(yè)/共89頁(yè)查找的基本概念對(duì)于長(zhǎng)度為n的列表，查找成功時(shí)的平均查找長(zhǎng)度為：其中Pi為查找列表中第i個(gè)數(shù)據(jù)元素的概率，Ci為找到列表中第i個(gè)數(shù)據(jù)元素時(shí)，已經(jīng)進(jìn)行過(guò)的關(guān)鍵字比較次數(shù)。由于查找算法的基本運(yùn)算是關(guān)鍵字之間的比較操作，所以可用平均查找長(zhǎng)度來(lái)衡量查找算法的性能。

第11頁(yè)/共89頁(yè)查找的基本概念查找的基本方法可以分為兩大類：比較式查找法基于線性表的查找法基于樹(shù)的查找法計(jì)算式查找法也稱為HASH（哈希）查找法第12頁(yè)/共89頁(yè)第八章查找查找的基本概念基于線性表的查找法順序查找法折半查找法分塊查找法基于樹(shù)的查找法計(jì)算式查找法——哈希法要點(diǎn)小結(jié)第13頁(yè)/共89頁(yè)順序查找(SequentialSearch)順序查找法的特點(diǎn)是，用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個(gè)比較，直到成功或失敗。存儲(chǔ)結(jié)構(gòu)通常為順序結(jié)構(gòu)，也可為鏈?zhǔn)浇Y(jié)構(gòu)。第14頁(yè)/共89頁(yè)順序查找(SequentialSearch)第15頁(yè)/共89頁(yè)順序查找(SequentialSearch)第16頁(yè)/共89頁(yè)第八章查找查找的基本概念基于線性表的查找法順序查找法折半查找法分塊查找法基于樹(shù)的查找法計(jì)算式查找法——哈希法要點(diǎn)小結(jié)第17頁(yè)/共89頁(yè)折半查找(BinarySearch)折半查找法又稱為二分法查找法，這種方法要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。其基本過(guò)程是：將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過(guò)程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。第18頁(yè)/共89頁(yè)折半查找(BinarySearch)第19頁(yè)/共89頁(yè)折半查找(BinarySearch)【算法分析】用平均查找長(zhǎng)度(ASL)分析折半查找算法的性能。折半查找過(guò)程可用一個(gè)稱為判定樹(shù)的二叉樹(shù)描述，判定樹(shù)中每一結(jié)點(diǎn)對(duì)應(yīng)表中一個(gè)記錄，但結(jié)點(diǎn)值不是記錄的關(guān)鍵字，而是記錄在表中的位置序號(hào)。根結(jié)點(diǎn)對(duì)應(yīng)當(dāng)前區(qū)間的中間記錄，左子樹(shù)對(duì)應(yīng)前一子表，右子樹(shù)對(duì)應(yīng)后一子表。顯然，找到有序表中任一記錄的過(guò)程，對(duì)應(yīng)判定樹(shù)中從根結(jié)點(diǎn)到與該記錄相應(yīng)結(jié)點(diǎn)的路徑，而所做比較的次數(shù)恰為該結(jié)點(diǎn)在判定樹(shù)上的層次數(shù)。因此，折半查找成功時(shí)，關(guān)鍵字比較次數(shù)最多不超過(guò)判定樹(shù)的深度。第20頁(yè)/共89頁(yè)折半查找(BinarySearch)由于判定樹(shù)的葉子結(jié)點(diǎn)所在層次之差最多為1，故n個(gè)結(jié)點(diǎn)的判定樹(shù)的深度與n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度相等，均為+1。這樣，折半查找成功時(shí)，關(guān)鍵字比較次數(shù)最多不超過(guò)+1。相應(yīng)地，折半查找失敗時(shí)的過(guò)程對(duì)應(yīng)判定樹(shù)中從根結(jié)點(diǎn)到某個(gè)含空指針的結(jié)點(diǎn)的路徑，因此，折半查找成功時(shí)，關(guān)鍵字比較次數(shù)最多也不超過(guò)判定樹(shù)的深度+1。為便于討論，假定表的長(zhǎng)度n=2h-1，則相應(yīng)判定樹(shù)必為深度是h的滿二叉樹(shù)，h=log2(n+1)。又假設(shè)每個(gè)記錄的查找概率相等，則折半查找成功時(shí)的平均查找長(zhǎng)度為：第21頁(yè)/共89頁(yè)折半查找(BinarySearch)含11個(gè)記錄的有序表，其折半查找過(guò)程可用二叉判定樹(shù)表示：12345678910116121518222528354658606710412395811比較1次比較2次比較3次比較4次ASL=(1+2+2+3+3+3+3+4+4+4+4)/11=33/11=3第22頁(yè)/共89頁(yè)折半查找(BinarySearch)演示第23頁(yè)/共89頁(yè)折半查找(BinarySearch)折半查找方法的優(yōu)點(diǎn)：查找速度快平均性能好折半查找方法的缺點(diǎn)：要求待查表為有序表插入刪除困難因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。第24頁(yè)/共89頁(yè)第八章查找查找的基本概念基于線性表的查找法順序查找法折半查找法分塊查找法基于樹(shù)的查找法計(jì)算式查找法——哈希法要點(diǎn)小結(jié)第25頁(yè)/共89頁(yè)分塊查找法分塊查找法要求將列表組織成以下索引順序結(jié)構(gòu)：首先將列表分成若干個(gè)塊（子表）。一般情況下，塊的長(zhǎng)度均勻，最后一塊可以不滿。每塊中元素任意排列，即塊內(nèi)無(wú)序，但塊與塊之間有序。構(gòu)造一個(gè)索引表。其中每個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)塊并記錄每塊的起始位置，以及每塊中的最大關(guān)鍵字（或最小關(guān)鍵字）。索引表按關(guān)鍵字有序排列。第26頁(yè)/共89頁(yè)分塊查找法下圖為一個(gè)索引順序表。其中包括三個(gè)塊，第一個(gè)塊的起始地址為0，塊內(nèi)最大關(guān)鍵字為25；第二個(gè)塊的起始地址為5，塊內(nèi)最大關(guān)鍵字為58；第三個(gè)塊的起始地址為10，塊內(nèi)最大關(guān)鍵字為88。第27頁(yè)/共89頁(yè)分塊查找法分塊查找的基本過(guò)程如下：首先，將待查關(guān)鍵字K與索引表中的關(guān)鍵字進(jìn)行比較，以確定待查記錄所在的塊。具體的可用順序查找法或折半查找法進(jìn)行。進(jìn)一步用順序查找法，在相應(yīng)塊內(nèi)查找關(guān)鍵字為K的元素。例如，在上述索引順序表中查找36。首先，將36與索引表中的關(guān)鍵字進(jìn)行比較，因?yàn)?5＜36≤58，所以36在第二個(gè)塊中，進(jìn)一步在第二個(gè)塊中順序查找，最后在8號(hào)單元中找到36。第28頁(yè)/共89頁(yè)分塊查找法分塊查找的平均查找長(zhǎng)度由兩部分構(gòu)成，即查找索引表時(shí)的平均查找長(zhǎng)度為L(zhǎng)B，以及在相應(yīng)塊內(nèi)進(jìn)行順序查找的平均查找長(zhǎng)度為L(zhǎng)W：ASLbs=LB+LW假定將長(zhǎng)度為n的表分成b塊，且每塊含s個(gè)元素，則b=n/s。又假定表中每個(gè)元素的查找概率相等，則每個(gè)索引項(xiàng)的查找概率為1/b，塊中每個(gè)元素的查找概率為1/s。若用順序查找法確定待查元素所在的塊，則有第29頁(yè)/共89頁(yè)分塊查找法演示第30頁(yè)/共89頁(yè)第八章查找查找的基本概念基于線性表的查找法基于樹(shù)的查找法二叉排序樹(shù)平衡二叉排序樹(shù)B_樹(shù)計(jì)算式查找法——哈希法要點(diǎn)小結(jié)第31頁(yè)/共89頁(yè)二叉排序樹(shù)二叉樹(shù)排序又稱二叉查找樹(shù)，它是一種特殊的樹(shù)。其定義為：二叉樹(shù)排序樹(shù)或者是一棵空樹(shù)，或者是具有如下性質(zhì)的二叉樹(shù)：若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；它的左右子樹(shù)也分別為二叉排序樹(shù)。這是一個(gè)遞歸的定義。注意：只要結(jié)點(diǎn)之間具有可比性即可。第32頁(yè)/共89頁(yè)二叉排序樹(shù)下圖，(a)所示為數(shù)字值間的比較，(b)所示為單詞字符的ASCII碼間的比較。第33頁(yè)/共89頁(yè)二叉排序樹(shù)的查找二叉排序樹(shù)的特性：根據(jù)二叉排序樹(shù)的定義（左子樹(shù)小于根結(jié)點(diǎn)，右子樹(shù)大于根結(jié)點(diǎn)），根據(jù)二叉樹(shù)的中序遍歷的定義（先中序遍歷左子樹(shù)，訪問(wèn)根結(jié)點(diǎn)，再中序遍歷右子樹(shù)），因此，中序遍歷一個(gè)二叉排序樹(shù)，可以得到一個(gè)遞增有序序列。中序遍歷下面的二叉排序樹(shù)，則可得到一個(gè)遞增有序序列為：1,2,3,4,5,6,7,8,9。第34頁(yè)/共89頁(yè)二叉排序樹(shù)的查找因?yàn)槎媾判驑?shù)可看作是一個(gè)有序表，所以在二叉排序樹(shù)上進(jìn)行查找與折半查找類似，也是一個(gè)逐步縮小查找范圍的過(guò)程。根據(jù)二叉排序樹(shù)的特點(diǎn)，首先將待查關(guān)鍵字k與根結(jié)點(diǎn)關(guān)鍵字t進(jìn)行比較，如果：(1)

k=t，則返回根結(jié)點(diǎn)地址；(2)

k<t，則進(jìn)一步查左子樹(shù)；(3)

k>t，則進(jìn)一步查右子樹(shù)。顯然，這是一個(gè)遞歸過(guò)程。但可以用遞歸與非遞歸兩種算法實(shí)現(xiàn)。第35頁(yè)/共89頁(yè)二叉排序樹(shù)查找顯然，在二叉排序樹(shù)上進(jìn)行查找，若查找成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根到待查結(jié)點(diǎn)的路徑。若不成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根到某個(gè)葉子結(jié)點(diǎn)的路徑。因此，二叉排序樹(shù)的查找與折半查找過(guò)程類似，在二叉排序樹(shù)中查找一個(gè)記錄時(shí)，其比較次數(shù)不超過(guò)樹(shù)的深度。對(duì)長(zhǎng)度為n的有序表而言，折半查找對(duì)應(yīng)的判定樹(shù)是唯一的，而含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)卻是不唯一的。因?yàn)閷?duì)于同一個(gè)關(guān)鍵字集合，關(guān)鍵字插入的先后次序不同，所構(gòu)成的二叉排序樹(shù)的形態(tài)和深度也可能不同。第36頁(yè)/共89頁(yè)二叉排序樹(shù)查找二叉排序樹(shù)的平均查找長(zhǎng)度ASL與二叉排序樹(shù)的形態(tài)有關(guān)，二叉排序樹(shù)的各分支越均衡，樹(shù)的深度淺，其平均查找長(zhǎng)度ASL就越小。假設(shè)每個(gè)元素的查找概率相等，則它們的平均查找長(zhǎng)度分別是：(a)ASL=1/6(1+2+2+3+3+3)=14/6(b)ASL=1/6(1+2+3+4+5+6)=21/6第37頁(yè)/共89頁(yè)二叉排序樹(shù)查找由此可見(jiàn)，二叉排序樹(shù)的平均查找長(zhǎng)度ASL與二叉排序樹(shù)的形態(tài)有關(guān)。在最壞的情況下，二叉排序樹(shù)是通過(guò)把一個(gè)有序表的n個(gè)結(jié)點(diǎn)一次插入生成的，由此得到的二叉排序樹(shù)脫化為一棵深度為n的單支樹(shù)，它的平均查找長(zhǎng)度和單鏈表上的順序查找相同，也是(n+1)/2。在最好的情況下，二叉排序樹(shù)在生成過(guò)程中，樹(shù)的形態(tài)比較均勻，最終得到的是一棵形態(tài)與折半查找的判定樹(shù)相似的二叉排序樹(shù)，其平均查找長(zhǎng)度大約是log2n。若考慮把n個(gè)結(jié)點(diǎn)按各種可能的次序插入到二叉排序樹(shù)中，則有n!棵二叉排序樹(shù)（其中有的形態(tài)相同），可以證明，對(duì)這些二叉排序樹(shù)的查找長(zhǎng)度求平均，其平均查找長(zhǎng)度仍然是O(log2n)。第38頁(yè)/共89頁(yè)二叉排序樹(shù)查找就平均性能而言，二叉排序樹(shù)上的查找和折半查找相差不大，并且二叉排序樹(shù)上插入和刪除結(jié)點(diǎn)十分方便，無(wú)需移動(dòng)大量結(jié)點(diǎn)。因此，對(duì)于需要經(jīng)常做插入、刪除、查找運(yùn)算的表，宜采用二叉排序樹(shù)結(jié)構(gòu)。這也就是人們常常將二叉排序樹(shù)稱為二叉查找樹(shù)的原因。第39頁(yè)/共89頁(yè)第八章查找查找的基本概念基于線性表的查找法基于樹(shù)的查找法計(jì)算式查找法——哈希法哈希函數(shù)的構(gòu)造方法處理沖突的方法哈希表的查找過(guò)程哈希法性能分析要點(diǎn)小結(jié)第40頁(yè)/共89頁(yè)哈希(Hash)法哈希法又稱散列法、雜湊法以及關(guān)鍵字地址計(jì)算法等，相應(yīng)的表稱為哈希表(HashTables)?；舅枷胧牵菏紫仍谠氐年P(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)鍵字直接存取元素的目的。第41頁(yè)/共89頁(yè)HashHansPeterLuhn(1896.7.1~1964.8.19)GermanyBusinessIntelligence,KWICmethodofindexing,Hashfunction(1953)HansPeterLuhnappearstohavebeenthefirsttousetheconcept,andthatRobertMorrisusedtheterminasurveypaperinCACMwhichelevatedthetermfromtechnicaljargontoformalterminology.RobertMorris,Sr.UNIX,FormerNSAChiefScientist(hissonRobertTappanMorris,1988MorrisWorm)第42頁(yè)/共89頁(yè)HashFunctionAtypicalhashfunctionatwork.Notethatthehashsumsarealwaysthesamesize,nomatterhowshortorlongtheinputis.Alsonotethatthehashsumslookverydifferentevenwhenthereareonlyslightdifferencesintheinput.第43頁(yè)/共89頁(yè)哈希法當(dāng)關(guān)鍵字集合很大時(shí)，關(guān)鍵字值不同的元素可能會(huì)映象到哈希表的同一地址上，即

k1≠k2

，但

H(k1)=H(k2)，這種現(xiàn)象稱為沖突，此時(shí)稱k1和k2

為同義詞。實(shí)際中，沖突是不可避免的，只能通過(guò)改進(jìn)哈希函數(shù)的性能來(lái)減少?zèng)_突。綜上所述，哈希法主要包括以下兩方面的內(nèi)容：如何構(gòu)造哈希函數(shù)如何處理沖突第44頁(yè)/共89頁(yè)哈希函數(shù)的構(gòu)造方法構(gòu)造哈希函數(shù)的原則是：函數(shù)本身便于計(jì)算；計(jì)算出來(lái)的地址分布均勻，即對(duì)任一關(guān)鍵字key，H(key)對(duì)應(yīng)不同地址的概率相等，目的是盡可能減少?zèng)_突。下面介紹構(gòu)造哈希函數(shù)常用的五種方法：數(shù)字分析法平方取中法分段疊加法除留余數(shù)法偽隨機(jī)數(shù)法第45頁(yè)/共89頁(yè)數(shù)字分析法如果事先知道關(guān)鍵字集合，并且每個(gè)關(guān)鍵字的位數(shù)比哈希表的地址碼位數(shù)多時(shí)，可以從關(guān)鍵字中選出分布較均勻的若干位，構(gòu)成哈希地址。例如，有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制整數(shù)d1d2d3…d7d8，如哈希表長(zhǎng)取100，則哈希表的地址空間為：00~99。假設(shè)經(jīng)過(guò)分析，各關(guān)鍵字中d4和d7的取值分布較均勻，則哈希函數(shù)為：H(key)=H(d1d2d3…d7d8)=d4d7。例如，H(81346532)=43，H(81301367)=06。相反，假設(shè)經(jīng)過(guò)分析，各關(guān)鍵字中d1和d8的取值分布極不均勻，d1

都等于5，d8

都等于2，此時(shí)，如果哈希函數(shù)為：H(key)=H(d1d2d3…d7d8)=d1d8，則所有關(guān)鍵字的地址碼都是52，顯然不可取。第46頁(yè)/共89頁(yè)平方取中法當(dāng)無(wú)法確定關(guān)鍵字中哪幾位分布較均勻時(shí)，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因?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)鍵字哈希地址，如下表所示。第47頁(yè)/共89頁(yè)平方取中法平方取中法求得的哈希地址關(guān)鍵字內(nèi)部編碼內(nèi)部編碼的平方值H(key)關(guān)鍵字的哈希地址KEYA11052501122157778355001778KYAB11250102126564795010404795AKEY01110525001233265775625265BKEY02110525004454315775625315第48頁(yè)/共89頁(yè)分段疊加法按哈希表地址位數(shù)將關(guān)鍵字分成位數(shù)相等的幾部分（最后一部分可以較短），然后將這幾部分相加，舍棄最高進(jìn)位后的結(jié)果就是該關(guān)鍵字的哈希地址。移位法是將分割后的每部分低位對(duì)齊相加折疊法是從一端向另一端沿分割界來(lái)回折疊（奇數(shù)段為正序，偶數(shù)段為倒序），然后將各段相加。例如：key=12360324711202065，哈希表長(zhǎng)度為1000，則應(yīng)把關(guān)鍵字分成3位一段，在此舍去最低的兩位65，分別進(jìn)行移位疊加和折疊疊加，求得哈希地址為105和907，如下圖所示。第49頁(yè)/共89頁(yè)分段疊加法由疊加法求哈希地址23034712020+)11052330647211020+)907(a)移位疊加(b)折疊疊加

第50頁(yè)/共89頁(yè)除留余數(shù)法假設(shè)哈希表長(zhǎng)為m，p為小于等于m的最大素?cái)?shù)，則哈希函數(shù)為：h(key)=key%p，其中%為模p取余運(yùn)算。例如，已知待散列元素為(18，75，60，43，54，90，46)，表長(zhǎng)m=10，p=7，則有h(18)=18%7=4h(75)=75%7=5h(60)=60%7=4h(43)=43%7=1h(54)=54%7=5h(90)=90%7=6h(46)=46%7=4此時(shí)沖突較多。第51頁(yè)/共89頁(yè)除留余數(shù)法為減少?zèng)_突，可取較大的m值和p值，如m=p=13，結(jié)果如下：h(18)=18%13=5h(75)=75%13=10h(60)=60%13=8h(43)=43%13=4h(54)=54%13=2h(90)=90%13=12h(46)=46%13=7除留余數(shù)法求哈希地址544318466075900123456789101112第52頁(yè)/共89頁(yè)偽隨機(jī)數(shù)法采用一個(gè)偽隨機(jī)函數(shù)作哈希函數(shù)，即H(key)=random(key)。在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體情況，靈活采用不同的方法，并用實(shí)際數(shù)據(jù)測(cè)試它的性能，以便做出正確判定。通常應(yīng)考慮以下五個(gè)因素：計(jì)算哈希函數(shù)所需的時(shí)間（簡(jiǎn)單）。關(guān)鍵字的長(zhǎng)度。哈希表的大小。關(guān)鍵字的分布情況。記錄查找的頻率。第53頁(yè)/共89頁(yè)第八章查找查找的基本概念基于線性表的查找法基于樹(shù)的查找法計(jì)算式查找法——哈希法哈希函數(shù)的構(gòu)造方法處理沖突的方法哈希表的查找過(guò)程哈希法性能分析要點(diǎn)小結(jié)第54頁(yè)/共89頁(yè)處理沖突的方法通過(guò)構(gòu)造性能良好的哈希函數(shù)，可以減少?zèng)_突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個(gè)關(guān)鍵問(wèn)題。創(chuàng)建哈希表和查找哈希表都會(huì)遇到?jīng)_突，兩種情況下解決沖突的方法應(yīng)該一致。下面以創(chuàng)建哈希表為例，說(shuō)明解決沖突的方法。常用的解決沖突方法有以下四種：開(kāi)放定址法再哈希法鏈地址法建立公共溢出區(qū)第55頁(yè)/共89頁(yè)開(kāi)放定址法也稱再散列法，其基本思想是：當(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為表長(zhǎng)，di稱為增量序列。i=1，2，…，ni=1，2，…，n第56頁(yè)/共89頁(yè)開(kāi)放定址法增量序列的取值方式不同，相應(yīng)的再散列方式也不同。主要有以下三種：線性探測(cè)再散列di=1，2，3，…，m-1特點(diǎn)：沖突發(fā)生時(shí)，順序查看表中下一單元，直到找出一個(gè)空單元或查遍全表。二次探測(cè)再散列

di=12，-12，22，-22，…，k2，-k2(k≤m/2)特點(diǎn)：沖突發(fā)生時(shí)，在表的左右進(jìn)行跳躍式探測(cè)，比較靈活。第57頁(yè)/共89頁(yè)開(kāi)放定址法偽隨機(jī)探測(cè)再散列

di=偽隨機(jī)數(shù)序列。具體實(shí)現(xiàn)時(shí)，應(yīng)建立一個(gè)偽隨機(jī)數(shù)發(fā)生器，（如i=(i+p)%m），并給定一個(gè)隨機(jī)數(shù)做起點(diǎn)。第58頁(yè)/共89頁(yè)開(kāi)放定址法例如，已知哈希表長(zhǎng)度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沖突。如果用線性探測(cè)再散列處理沖突，下一個(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)單元，參見(jiàn)下圖(a)。0123456789101147266069(a)用線性探測(cè)再散列處理沖突第59頁(yè)/共89頁(yè)開(kāi)放定址法已知哈希表長(zhǎng)度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沖突。如果用二次探測(cè)再散列處理沖突，下一個(gè)哈希地址為h1=(3+12)%11=4，仍然沖突，再找下一個(gè)哈希地址為h2=(3-12)%11=2，此時(shí)不再?zèng)_突，將69填入2號(hào)單元，參見(jiàn)下圖(b)。0123456789101169472660(b)用二次探測(cè)再散列處理沖突第60頁(yè)/共89頁(yè)開(kāi)放定址法例如，已知哈希表長(zhǎng)度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ī)探測(cè)再散列處理沖突，且偽隨機(jī)數(shù)序列為：2，5，9……則下一個(gè)哈希地址為h1=(3+2)%11=5，仍然沖突，再找下一個(gè)哈希地址為h2=(3+5)%11=8，此時(shí)不再?zèng)_突，將69填入8號(hào)單元，參見(jiàn)下圖(c)。

0123456789101147266069(c)用偽隨機(jī)探測(cè)再散列處理沖突第61頁(yè)/共89頁(yè)開(kāi)放定址法從上述例子可以看出，線性探測(cè)再散列容易產(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è)元素并非同義詞。線性探測(cè)再散列的優(yōu)點(diǎn)是：只要哈希表不滿，就一定能找到一個(gè)不沖突的哈希地址，而二次探測(cè)再散列和偽隨機(jī)探測(cè)再散列則不一定。第62頁(yè)/共89頁(yè)開(kāi)放定址法建立散列表演示第63頁(yè)/共89頁(yè)再哈希法同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù)：Hi=Rhi(key)，i=1，2，…，n當(dāng)哈希地址Hi=Rh1(key)發(fā)生沖突時(shí)，再計(jì)算Hi=Rh2(key)……直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計(jì)算時(shí)間。第64頁(yè)/共89頁(yè)鏈地址法基本思想是將所有哈希地址為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），哈希表長(zhǎng)度為13，哈希函數(shù)為：H(key)=key%13，則用鏈地址法處理沖突的結(jié)果如下圖所示。本例的平均查找長(zhǎng)度：ASL=(1×7+2×4+3×1)=1.5第65頁(yè)/共89頁(yè)鏈地址法處理沖突時(shí)的哈希表第66頁(yè)/共89頁(yè)鏈地址法處理沖突時(shí)的哈希表第67頁(yè)/共89頁(yè)建立公共溢出區(qū)基本思想是將哈希表分為基本表和溢出表兩部分，凡是與基本表發(fā)生沖突的元素一律填入溢出表。第68頁(yè)/共89頁(yè)第七章查找查找的基本概念基于線性表的查找法基于樹(shù)的查找法計(jì)算式查找法——哈希法哈希函數(shù)的構(gòu)造方法處理沖突的方法哈希表的查找過(guò)程哈希法性能分析要點(diǎn)小結(jié)第69頁(yè)/共89頁(yè)哈希表的查找過(guò)程哈希表的查找過(guò)程與哈希表的創(chuàng)建過(guò)程是一致的。所設(shè)要查找關(guān)鍵字為為key的元素，查找過(guò)程如下：首先計(jì)算h0=hash(key)。如果單元h0為空，則所查元素不存在；如果單元h0中元素的關(guān)鍵字為key，則找到所查元素；否則重復(fù)下述解決沖突的過(guò)程：按解決沖突的方法，找出下一個(gè)哈希地址hi;如果單元hi為空，則所查元素不存在;如果單元hi中元素的關(guān)鍵字為key，則找到所查元素。第70頁(yè)/共89頁(yè)哈希表的查找算法#definem<哈希表長(zhǎng)度>#defineNULLKEY<代表空記錄的關(guān)鍵字值>typedefintKeyType;/*假設(shè)關(guān)鍵字為整型*/typedefstruct{KeyTypekey;……/*記錄中其它分量按需求確定*/……}RecordType;typedefRecordTypeHashTable[m];

intHashSearch(HashTableht,KeyTypeK){h0=hash(K);第71頁(yè)/共89頁(yè)哈希表的查找算法if(ht[h0].key==NULLKEY)return(-1);elseif(ht[h0].key==K)return(h0);else/*用線性探測(cè)再散列解決沖突*/{for(i=1;i<=m-1;i++){hi=(h0+i)%m;if(ht[hi].key==NULLKEY)return(-1);elseif(ht[hi].key==K)return(hi);}return(-1);}}第72頁(yè)/共89頁(yè)第八章查找查找的基本概念基于線性表的查找法基于樹(shù)的查找法計(jì)算式查找法——哈希法哈希函數(shù)的構(gòu)造方法處理沖突的方法哈希表的查找過(guò)程哈希法性能分析要點(diǎn)小結(jié)第73頁(yè)/共89頁(yè)哈希法性能分析由于沖突的存在，哈希法仍需進(jìn)行關(guān)鍵字比較，因此，仍需用平均查找長(zhǎng)度來(lái)評(píng)價(jià)哈希法的查找性能。哈希法中影響關(guān)鍵字比較次數(shù)的因素有三個(gè)：哈希函數(shù)處理沖突的方法哈希表的裝填因子α哈希表的裝填因子α的定義如下：

α=哈希表中元素個(gè)數(shù)/哈希表的長(zhǎng)度α可描述哈希表的裝滿程度。顯然，α越小，發(fā)生沖突的可能性越小，而α越大，發(fā)生沖突的可能性也越大。第74頁(yè)/共89頁(yè)哈希法性能分析假定哈希函數(shù)是均勻的，則影響平均查找長(zhǎng)度的因素只剩下兩個(gè)：處理沖突的方法哈希表的裝填因子α以下按處理沖突的不同方法分別列出相應(yīng)的平均查找長(zhǎng)度:線性探測(cè)再散列偽隨機(jī)探測(cè)再散列、二次探測(cè)再散列以及再哈希法鏈址法第75頁(yè)/共89頁(yè)哈希法性能分析線性探測(cè)再散列查找成功時(shí)查找失敗時(shí)偽隨機(jī)探測(cè)再散列、二次探測(cè)再散列以及再哈希法查找成功時(shí)第76頁(yè)/共89頁(yè)哈希法性能分析查找失敗時(shí)鏈址法查找成功時(shí)查找失敗時(shí)第77頁(yè)/共89頁(yè)哈希法性能分析從以上討論可知：哈希表的平均查找長(zhǎng)度是裝填因子α的函數(shù)，而與待散列元素?cái)?shù)目n無(wú)關(guān)。因此，無(wú)論元素?cái)?shù)目n有多大，都能通過(guò)調(diào)整α，使哈希表的平均查找長(zhǎng)度較小。已知一組關(guān)鍵字序列（19，14，23，01，68，20，84，27，55，11，10，79）按哈希函數(shù)H(key)=key%13和線性探測(cè)處理沖突構(gòu)造所得哈希表ht[0..15],如下圖所示。0123456789101112131415140168275519208479231110①②①④③①①③⑨①①③第78頁(yè)/共89頁(yè)哈希法性能分析手工計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度公式其中Ci為查找第i個(gè)元素時(shí)所需的比較次數(shù)。采用線性探測(cè)再散列法處理沖突，計(jì)算出在等概率查找的情況下其查找成功的平均查找長(zhǎng)度為：0123456789101112131415140168275519208479231110①②①④③①①③⑨①①③第79頁(yè)/共89頁(yè)哈希法性能分析手工計(jì)算等概率情況下查找不成功的平均查找長(zhǎng)度公式Ci為哈希函數(shù)取值為i時(shí)查找不成功的比較次數(shù)。查找不成功的情況：遇到空單元按解決沖突的方法完全探測(cè)一遍后仍未找到。0到r-1