數(shù)據(jù)結(jié)構(gòu) 9查找C

1、哈希表：哈希表：即散列存儲結(jié)構(gòu)。即散列存儲結(jié)構(gòu)。 散列法存儲的基本思想：散列法存儲的基本思想：建立關(guān)鍵碼字與其存儲位置的建立關(guān)鍵碼字與其存儲位置的對應(yīng)對應(yīng)關(guān)系，關(guān)系，或者說，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地址?；蛘哒f，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地址。 優(yōu)點：優(yōu)點：查找速度極快（查找速度極快（O(1)O(1)）, ,查找效率與元素個數(shù)查找效率與元素個數(shù)n n無關(guān)！無關(guān)！例例1 1：若將學生信息按如下方式存入計算機，如：若將學生信息按如下方式存入計算機，如：將將20010118102200101181020101的所有信息存入的所有信息存入VV0101 單元；單元；將將2001011810220010

2、1181020202的所有信息存入的所有信息存入VV0202 單元；單元；將將20010118102200101181023131的所有信息存入的所有信息存入V31V31單元。單元。欲查找學號為欲查找學號為20010118102200101181021616的信息，便可直接訪問的信息，便可直接訪問V16V16！例例2 ： 有數(shù)據(jù)元素序列有數(shù)據(jù)元素序列(14(14，2323，3939，9 9，2525，11)11)，若規(guī)定，若規(guī)定每個元素每個元素k k的存儲地址的存儲地址H H（k k）k k，請畫出存儲結(jié)構(gòu)圖。，請畫出存儲結(jié)構(gòu)圖。（注：（注：H H（k k）k k稱為散列函數(shù)）稱為散列函數(shù)）解

3、：解：根據(jù)散列函數(shù)根據(jù)散列函數(shù)H H（k k）k k ，可知元素，可知元素1414應(yīng)當存入地址為應(yīng)當存入地址為1414的單元，元素的單元，元素2323應(yīng)當存入地址為應(yīng)當存入地址為2323的單元，的單元，對應(yīng)散列存儲表（哈希表）如下：對應(yīng)散列存儲表（哈希表）如下：討論：如何進行散列查找？討論：如何進行散列查找？根據(jù)存儲時用到的散列函數(shù)根據(jù)存儲時用到的散列函數(shù)H(k)H(k)表達式表達式，迅即可查到結(jié)果！，迅即可查到結(jié)果！例如，查找例如，查找key=9,key=9,則訪問則訪問H(9)=9H(9)=9號地址，若內(nèi)容為號地址，若內(nèi)容為9 9則成功；則成功；若查不到，應(yīng)當設(shè)法返回一個特殊值，例如空指針

4、或空記錄。若查不到，應(yīng)當設(shè)法返回一個特殊值，例如空指針或空記錄。 地址地址 9 11 14 23 24 25 39 內(nèi)容內(nèi)取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，選取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，并按此存放；并按此存放；查找時，由同一個函數(shù)查找時，由同一個函數(shù)對給定值對給定值k k計算地址，計算地址，將將k k與地址單元中元素關(guān)鍵碼進行比，確定查找是否成功。與地址單元中元素關(guān)鍵碼進行比，確定查找是否成功。通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，過哈希函數(shù)變換后，可能將不同的關(guān)鍵碼

5、映射到同可能將不同的關(guān)鍵碼映射到同一個哈希地址上一個哈希地址上，這種現(xiàn)象稱為，這種現(xiàn)象稱為沖突沖突。若干術(shù)語若干術(shù)語哈希方法哈希方法( (雜湊法雜湊法) )哈希函數(shù)哈希函數(shù)( (雜湊函數(shù)雜湊函數(shù)) )哈希表哈希表( (雜湊表雜湊表) ) 沖沖 突突哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)哈希函數(shù)( (雜雜湊函數(shù)湊函數(shù)) )按上述思想構(gòu)造的表稱為按上述思想構(gòu)造的表稱為哈希表哈希表( (雜湊表雜湊表) ) 有有6個元素的關(guān)鍵碼分別為：（個元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。）。選取關(guān)鍵碼與元素位置間的函數(shù)為選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=k m

6、od 7通過哈希函數(shù)對通過哈希函數(shù)對6 6個元素建立哈希表：個元素建立哈希表：2539239146個元素用個元素用7個個地址應(yīng)該足夠地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4 0 1 2 3 4 5 6（a a）所選函數(shù)盡可能）所選函數(shù)盡可能簡單簡單，以便提高轉(zhuǎn)換速度；，以便提高轉(zhuǎn)換速度；（b b）所選函數(shù)對關(guān)鍵碼計算出的地址，應(yīng)在哈希地址集中）所選函數(shù)對關(guān)鍵碼計算出的地址，應(yīng)在哈希地址集中大致大致均勻均勻分布，以減少空間浪費。分布，以減少空間浪費。查找時，如果從哈希函數(shù)計算出的地址中查不到關(guān)鍵碼，則查找時，如果從哈希函數(shù)計算出的地址中查不到關(guān)鍵

7、碼，則應(yīng)當依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。應(yīng)當依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。二、要求一：要求一：n n個數(shù)據(jù)原僅占用個數(shù)據(jù)原僅占用n n個地址，個地址，雖然散列查找是以空間換時間，但仍雖然散列查找是以空間換時間，但仍希望散列的地址空間盡量小。希望散列的地址空間盡量小。要求二：要求二：無論用什么方法存儲，目無論用什么方法存儲，目的都是盡量均勻地存放元素，以避免的都是盡量均勻地存放元素，以避免沖突。沖突。Hash(key) = akey + b ( (a、b為常數(shù)為常數(shù)) )優(yōu)點：優(yōu)點：以關(guān)鍵碼以關(guān)鍵碼keykey的某個線性函數(shù)值為哈希地址，的某個線性函數(shù)值為哈希地址

8、，不會產(chǎn)生沖突不會產(chǎn)生沖突. .缺點：缺點：要占用連續(xù)地址空間，空間效率低。要占用連續(xù)地址空間，空間效率低。 例：例：關(guān)鍵碼集合為關(guān)鍵碼集合為100，300，500，700，800，900， 選取哈希函數(shù)為選取哈希函數(shù)為Hash(key)=key/100， 則存儲結(jié)構(gòu)（哈希表）如下：則存儲結(jié)構(gòu)（哈希表）如下：0 1 2 3 4 5 6 7 8 9900800700500300100Hash(key)= B*( A*key mod 1 ) ( (A、B均為常數(shù)，且均為常數(shù)，且0A 724+518+69 = 724+518+69 =13111311Hash(key) = random ( key

9、) (random (random為偽隨機函數(shù)為偽隨機函數(shù)) )適用于：適用于：關(guān)鍵字長度不等的情況。造表和查找都很方便。關(guān)鍵字長度不等的情況。造表和查找都很方便。 執(zhí)行速度（即計算哈希函數(shù)所需時間）；執(zhí)行速度（即計算哈希函數(shù)所需時間）； 關(guān)鍵字的長度；關(guān)鍵字的長度； 哈希表的大小；哈希表的大??； 關(guān)鍵字的分布情況；關(guān)鍵字的分布情況； 查找頻率。查找頻率。三、常見的沖突處理方法有：常見的沖突處理方法有：設(shè)計思路：設(shè)計思路：有沖突時就去尋找下一個空的哈希地址，有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。到，并將

10、數(shù)據(jù)元素存入。 具體實現(xiàn)：具體實現(xiàn)：Hi=(Hash(key)+di) mod m ( 1i m ) 其中：其中： Hash(key)為哈希函數(shù)為哈希函數(shù) m為哈希表長度為哈希表長度 di 為增量序列為增量序列 1，2，m-1，且，且di=i關(guān)鍵碼集為關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，設(shè)：設(shè)：哈希表表長為哈希表表長為m=m=11； 哈希函數(shù)為哈希函數(shù)為Hash(key)=key mod 11； 擬用擬用處理沖突。建哈希表如下：處理沖突。建哈希表如下：解釋：解釋： 47、7（以及（以及11、16、92）均是由哈希函數(shù)得到的沒有沖突均是由哈希函數(shù)得到的沒有沖突的哈希地址；

11、的哈希地址；0 1 2 3 4 5 6 7 8 9 10477 例：例：291116922283 Hash(29)=7，哈希地址有沖突，需尋找下一個空的哈希地址：，哈希地址有沖突，需尋找下一個空的哈希地址：由由H1=(Hash(29)+1) mod 11=8，哈希地址哈希地址8為空，因此將為空，因此將29存入。存入。 另外，另外，22、8、3同樣在哈希地址上有沖突，也是由同樣在哈希地址上有沖突，也是由H1找到空找到空的哈希地址的。的哈希地址的。線性探測法的優(yōu)點：線性探測法的優(yōu)點：只要哈希表未被填滿，保證能只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素；找到一個空地址單元存放有沖突

12、的元素；線性探測法的缺點：線性探測法的缺點：可能使第可能使第i個哈希地址的同義詞個哈希地址的同義詞存入第存入第i+1個哈希地址，這樣本應(yīng)存入第個哈希地址，這樣本應(yīng)存入第i+1個個哈希地址的元素變成了第哈希地址的元素變成了第i+2個哈希地址的同個哈希地址的同義詞，義詞， 因此，可能出現(xiàn)很多元素在相鄰的哈希地址因此，可能出現(xiàn)很多元素在相鄰的哈希地址上上“堆積堆積”起來，大大降低了查找效率。起來，大大降低了查找效率。解決方案：解決方案：可采用可采用，以，以改善改善“堆積堆積”問題。問題。 討論：討論：仍舉上例，改用二次探測法處理沖突，建表如下：仍舉上例，改用二次探測法處理沖突，建表如下： 0 1 2

13、 3 4 5 6 7 8 9 10112234792167298 注：注：只有只有3 3這個關(guān)鍵碼的沖突處理與上例不同，這個關(guān)鍵碼的沖突處理與上例不同，Hash(3)=3，哈希地址上沖突，由，哈希地址上沖突，由H1=(Hash(3)+12) mod 11=4，仍然沖突；，仍然沖突；H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。找到空的哈希地址，存入。 Hi=(Hash(key)di) mod m其中：其中：Hash(key)Hash(key)為哈希函數(shù)為哈希函數(shù) m為哈希表長度，為哈希表長度，m要求是某個要求是某個4k+3的質(zhì)數(shù)的質(zhì)數(shù)； di為增量序列為增量序列 1

14、2，-12，22，-22，q2 基本思想：基本思想：將具有相同哈希地址的記錄鏈成一個單鏈表，將具有相同哈希地址的記錄鏈成一個單鏈表，m個個哈希地址就設(shè)哈希地址就設(shè)m個單鏈表個單鏈表，然后用一個數(shù)組將，然后用一個數(shù)組將m個單個單鏈表的表頭指針存儲起來，形成一個動態(tài)的結(jié)構(gòu)。鏈表的表頭指針存儲起來，形成一個動態(tài)的結(jié)構(gòu)。 設(shè)設(shè) 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 的哈希函數(shù)為：的哈希函數(shù)為：Hash(key)=key mod 11，用用處理沖突，則建表處理沖突，則建表如右圖所示。如右圖所示。 例：例：0 1 2 3 4 5 6 7 8 9102211

15、8934737922971650810注：注：有沖突的元素可以插有沖突的元素可以插在表尾在表尾, ,也可以插在表頭也可以插在表頭Hi=RHi(key) i=1, 2, ，kRHi均是不同的哈希函數(shù)，當產(chǎn)生沖突時就計算另一個均是不同的哈希函數(shù)，當產(chǎn)生沖突時就計算另一個哈希函數(shù)，直到?jīng)_突不再發(fā)生。哈希函數(shù)，直到?jīng)_突不再發(fā)生。優(yōu)點：優(yōu)點：不易產(chǎn)生聚集；不易產(chǎn)生聚集；缺點：缺點：增加了計算時間。增加了計算時間。思路：思路：除設(shè)立哈?；颈硗猓O(shè)立哈希基本表外，另設(shè)立一個溢出向量表另設(shè)立一個溢出向量表。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希

16、函數(shù)得到的地址是什么，一旦發(fā)生沖突，都管它們由哈希函數(shù)得到的地址是什么，一旦發(fā)生沖突，都填入溢出表。填入溢出表。明確：明確：散列函數(shù)沒有散列函數(shù)沒有“萬能萬能”通式，要根據(jù)元素集合的特通式，要根據(jù)元素集合的特性而分別構(gòu)造。性而分別構(gòu)造。 算法：算法：見教材見教材P259P259討論：討論：哈希查找的速度是否為真正的哈希查找的速度是否為真正的O O（1 1）？）？不是。不是。由于沖突的產(chǎn)生，使得哈希表的查找過程仍然要進由于沖突的產(chǎn)生，使得哈希表的查找過程仍然要進行比較，仍然要以平均查找長度行比較，仍然要以平均查找長度ASLASL來衡量。來衡量。一般地，一般地，ASLASL依賴于哈希表的裝填因子依

17、賴于哈希表的裝填因子 , ,它標志著哈希表的它標志著哈希表的裝滿程度。裝滿程度。哈希表的長度哈希表的長度表中填入的記錄數(shù)表中填入的記錄數(shù) 越大，表中記錄數(shù)越多，說明表裝得越滿，發(fā)生沖突越大，表中記錄數(shù)越多，說明表裝得越滿，發(fā)生沖突的可能性就越大，查找時比較次數(shù)就越多。的可能性就越大，查找時比較次數(shù)就越多。00 11討論：討論：2 2）“沖突沖突”是不是特別討厭？是不是特別討厭？答：答：不一定！正因為有沖突，使得文件加密后無法破譯不一定！正因為有沖突，使得文件加密后無法破譯（不可逆，是單向散列函數(shù)，可用于數(shù)字簽名）。（不可逆，是單向散列函數(shù)，可用于數(shù)字簽名）。利用了哈希表性質(zhì)：利用了哈希表性質(zhì)：源文件稍稍改動，會導致哈希表變源文件稍稍改動，會導致哈希表變動很大。動很大。隨隨機機探探測測法法）線線性性探探測測