散列表及其沖突處理方法的性能分析

賈永勝

（石家莊職業(yè)技術(shù)學(xué)院 信息工程系，河北 石家莊 050081）

散列表也稱作哈希表，是根據(jù)記錄的關(guān)鍵字（key）進(jìn)行直地址運(yùn)算，進(jìn)而進(jìn)行數(shù)據(jù)訪問的一種數(shù)據(jù)結(jié)構(gòu).散列表地址轉(zhuǎn)換的基本思路為：定義一個記錄的關(guān)鍵字與地址之間的一種映射關(guān)系，通過這個映射關(guān)系，根據(jù)關(guān)鍵字直接計算出記錄的地址.通常，記錄關(guān)鍵字用key表示，用h表示關(guān)鍵字和記錄地址間的函數(shù)關(guān)系，即為散列函數(shù)，記錄的地址用h（key）表示［1］.本文主要介紹散列函數(shù)的構(gòu)造方法、沖突處理方法及查找性能.

1 散列函數(shù)的構(gòu)造方法

散列函數(shù)多種多樣，應(yīng)力爭尋找一個這樣的散列函數(shù)：該函數(shù)能使關(guān)鍵字在整個地址范圍內(nèi)分布比較均勻.常用的散列函數(shù)構(gòu)造方法有：

（1）直接法

對關(guān)鍵字進(jìn)行簡單線性運(yùn)算，將結(jié)果作為記錄的地址.例如h（key）＝a＊key＋b，其中a，b是常數(shù).這種方法獲得的地址序列不發(fā)生地址沖突，計算簡單，但得到的地址序列很分散，地址范圍較廣.

（2）折疊法

如果記錄的關(guān)鍵字的位數(shù)較多，可將關(guān)鍵字劃分成等位數(shù)的多段（最后一段除外），再將這多段進(jìn)行簡單的四則運(yùn)算.例如｛12345678｝，可進(jìn)行如下計算：

由此，可算出該關(guān)鍵字的散列地址為657.

（3）平方取中法

對關(guān)鍵字求平方，在所得結(jié)果中連續(xù)取若干位，位數(shù)由散列表的長度決定.例如key＝1234，key2＝1522756，取中間的三位227作為地址碼.

（4）求余法

將關(guān)鍵字除以某個常數(shù)得到其余數(shù)，把該余數(shù)作為記錄的地址h（key）＝key%c，常數(shù)c一般小于散列表的總長度.

2 沖突的處理方法

如果有兩個或多個關(guān)鍵字使用同一個散列函數(shù)計算得到的地址為一個，即key1≠key2，但h（key1）＝h（key2），即為發(fā)生沖突.發(fā)生沖突的幾個關(guān)鍵字通常稱為同義詞.在進(jìn)行散列函數(shù)構(gòu)造時，應(yīng)盡量避免產(chǎn)生沖突，但實際上不發(fā)生沖突很難.本文給出兩種沖突處理的常用方法，即拉鏈法和開放定址法［2］.

（1）拉鏈法

拉鏈法的基本思路是：將同義詞存儲在一個公共的線性鏈表中，把這個鏈表稱為同義詞鏈表；另外定義一個順序表，里面記錄各同義詞在鏈表里的頭指針.例如，關(guān)鍵字｛1，2，3，4，5，6，7，8｝，函數(shù)為h（key）＝key%4，用拉鏈法處理沖突時的散列表如圖1所示.

圖1 拉鏈法處理沖突散列表

（2）開放定址法

①線性探測法

線性探測法的原理是：將散列表t［0..Max－1］看成一個循環(huán)向量，首先試探地址h（key）＝d是否可用.若不可用，則按下列地址探查：d＋1，d＋2，…，Max－1，0，1，…，d－1.即探查時從地址d開始，首先探查t［d］，然后依次探查t［d＋1］，…，t［Max－1］，此后又循環(huán)到t［0］，t［1］，…，t［d－1］.按線性探測法進(jìn)行插入操作時，先看當(dāng)前被探查的單元是否為空.如果為空，就將關(guān)鍵字key寫入這個空單元；若不空，則按上述規(guī)則依次繼續(xù)向后探查，直到遇到空單元插入關(guān)鍵字為止，如果測試到t［d－1］時還沒有找到空單元，說明表已滿，插入失敗.進(jìn)行查找操作時，若當(dāng)前正在探查的單元內(nèi)的關(guān)鍵字為k，表示成功查找到記錄；若不等于k，則繼續(xù)按順序向后探查，直至發(fā)現(xiàn)關(guān)鍵字為k的記錄即為查找成功；若探查到t［d－1］時，還沒有等于k的關(guān)鍵字，則查找失敗.例如，序列｛91，123，149，183，230，6，20｝，表長為14，散列函數(shù)h（x）＝x%14，散列表如圖2所示.

圖2 線性探測法的散列表

②二次探測法

從線性探測法可知，可能第i個同義詞存入了第i＋1個同義詞對應(yīng)的散列地址中，本應(yīng)存入第i＋1個散列地址的元素只能存到第i＋2個記錄的地址中……因此，可能有很多元素在其相鄰的地址中存儲，這就必然使每一個關(guān)鍵字的沖突幾率增高，大大降低查找效率.為此，可采用二次探測法，以改善上述的“堆積”問題.

二次探測法的基本思想是：跳躍式生成探測地址序列，其計算公式為：di＝（h（key）＋i2）mod Max，0≤i≤Max－1，即探查的序列為：d＝h（key），d＋1，d＋4，d＋9….也就是說，探查從地址d開始，先探查t［d］，然后依次探查t［d＋1］，t［d＋4］，t［d＋9］….例如，序列｛91，123，149，183，230，6，20｝的表長為14.插入6時，有散列函數(shù)h（6）＝6%14＝6，地址6中已經(jīng)有關(guān)鍵字230，沖突；套用上式得h＝（6＋1）%14＝7，地址7中也存在關(guān)鍵字91，沖突；繼續(xù)套用h＝（6＋4）%14＝10，而地址10空閑，則將6插入到地址10中，其散列表如圖3所示.

圖3 二次探測法

3 散列表的查找及分析

散列表的查找過程和散列表的構(gòu)造過程相似，一部分記錄的地址可直接經(jīng)關(guān)鍵字運(yùn)算得到，另一部分關(guān)鍵字在地址運(yùn)算時會發(fā)生沖突，需要選擇一種沖突處理方法進(jìn)行地址查找.在沖突處理的方法中，查找的總體思路是用給定值與關(guān)鍵字進(jìn)行比較.所以，可用平均查找長度（ASL）來衡量散列表查找的效率［3］.關(guān)鍵字的比較次數(shù)與產(chǎn)生沖突的多少息息相關(guān)，產(chǎn)生的沖突和查找次數(shù)越少，效率越高；產(chǎn)生的沖突越多，查找效率就越低.因此，查找效率實際上是由產(chǎn)生沖突的影響因素決定的.通常，影響沖突產(chǎn)生次數(shù)的因素有三個：散列函數(shù)是否均勻、處理沖突方法的好壞和散列表的裝填因子α的情況.散列表的裝填因子定義為：

這三個因素中，盡管散列函數(shù)的“優(yōu)劣”會直接影響沖突產(chǎn)生的頻度，但在一般情況下，可認(rèn)為散列函數(shù)“均勻”分布，可以忽略散列函數(shù)對平均查找長度產(chǎn)生的影響.分別用線性探測法和二次探測法來進(jìn)行沖突處理發(fā)現(xiàn)，即使關(guān)鍵字集合和散列函數(shù)均相同，在查找概率相同的情況下，它們的平均查找長度仍有所不同.采用線性探測法的平均查找長度ASL＝（5×1＋3×1＋1×5）／7＝13／7，采用二次探測法的平均查找長度ASL＝（5×1＋3×1＋1×4）／7＝12／7.由于表長是定值，α與填入表中的元素個數(shù)成正比，所以，α越大，填入表中的元素越多，產(chǎn)生沖突的可能性就越大；α越小，填入表中的元素越少，產(chǎn)生沖突的可能性就越小.

事實上，散列表的ASL通常是裝填因子α的函數(shù).只是處理沖突的方法不同，函數(shù)也不同.不同處理沖突方法的平均查找長度見表1.

此方法的存取速度較快，空間復(fù)雜度也不高，但由于存取是隨機(jī)的，不便于順序查找.

表1 不同方法構(gòu)造散列表的平均查找長度

［1］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)：C語言版 ［M］.北京：清華大學(xué)出版社，1997：237.

［2］郭芳，曹桂琴.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)：第5版 ［M］.大連：大連理工大學(xué)出版社，2004：210.

［3］張世和.數(shù)據(jù)結(jié)構(gòu) ［M］.北京：清華大學(xué)出版社，2000：258.