無限網狀結構對拉鏈法解決地址沖突問題的優化

摘 要：本文提出利用無限網狀結構對拉鏈法解決地址沖突問題進行優化，通過實例證明，此法提高了拉鏈法解決散列表中存在的地址沖突問題的工作效率。

關鍵詞：散列表；沖突；拉鏈法；無線網狀結構

1 概述

散列表又稱為哈希表，是線性表中一種重要的存儲方式和檢索方法。在散列表中，可以對節點進行快速檢索。散列表算法的基本思想是：由結點的關鍵碼值決定結點的存儲地址，即以關鍵碼值k為自變量，通過一定的函數關系h（稱為散列函數），計算出對應的函數值h（k）來，將這個值解釋為結點的存儲地址，將結點存入該地址中，檢索時，根據要檢索的關鍵碼值，用同樣的散列函數計算出地址，然后，到相應的地址中去獲取所要的結點數據。因此，散列表有一個重要特征：平均檢索的長度不直接依賴于表中元素的個數。兩個不同的關鍵字，由于散列函數值相同，因而被映射到同一表位置上。該現象稱為沖突（Collision）或碰撞。發生沖突的兩個關鍵字稱為該散列函數的同義詞（Synonym）。拉鏈法是解決沖突問題的傳統方法，可拉鏈法存在一些缺點，用無限網狀結構可以解決部分問題。

2 拉鏈法解決地址沖突問題

拉鏈法解決地址沖突問題的基本思想：將所有關鍵字為同義詞的結點放在同一個連表中。若選擇的鏈表長度為m，則可將散列表定義為一由m個頭指針組成的指針數組T[0...m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中個分量的初值均為空指針。

例1：已知一組數據為（26，36，41，38，44，15，68，12，06，51，06，51，），用除余法構造散列函數，用線性探測法解決沖突構造這組關鍵字的散列表

為了減少沖突通常令裝載因子小于1，這里關鍵字個數n=10，不妨設計m=13，此時裝載因子為0.77，散列表為T[0.....12]，散列函數為：h（key）=key%13。由除余法的散列函數計算出的上述關鍵字的地址為（0，10，2，12，5，2，3，12，6，12），前五個關鍵字插入時，其相應的地址均為開放地址，故將它們直接插入T[0]，T[10]，T[2]，T[12]和T[5]中，當插入第六個關鍵字15時，其散列地址為2已被關鍵字41占用。故用拉鏈法存儲15，即重新申請一個空間將15放入空間中，對12和51處理方法是一樣的。

拉鏈法的缺點：單鏈表對于同義詞的存儲沒有采用合適的算法解決，即使在單鏈表中采用了很好的算法解決存儲問題，但是若是在單鏈表中又出現沖突時問題無法解決。

3 無限網狀結構解決地址沖突問題

無限網狀結構解決地址沖突問題的基本思想：將關鍵字放在帶頭指針的數組，數組數目可以視數據量自行申請空間設置，但是所有數組結構都是一樣的。若選擇的數組的長度為m，則可將數組定義為一由m個頭指針組成的指針數組T[0...m-1]，然后各各數組之間的相互連接方式，根據實際情況自行進行，所有數組中關鍵字的存儲都按照相應的散列函數來確定其在相應數組中的位置。

例2：已知一組英文單詞：zero about out great hight konw home void play int floay fabt faat fbet將這些關鍵字存入散列表中。

本例中我們用無限網狀結構來存儲，將關鍵字的值減去a的值作為其地址，不同數組散列函數不同，并且每一個備份空間，一次用其下一個字符來確定其地址，由題可知about floay great hight int know out play void zero的地址分別是0 5 6 7 8 10 14 15 21和25，但是home faat fabt fbet他們出現了地址沖突，必須進行處理，對home開創一個數組將其按照第二個字母確定其地址，對于 fabt fbet必須創建一個數組進行儲存，又因為faat和fabt關鍵字的發生了沖突，故應該在此運用拉鏈法來解決，即在申請一個數組空間來存儲該關鍵字，這些關鍵字的存儲結果結構圖如下圖：

拉鏈法和無限網狀結構的聯系：無限網狀結構是對拉鏈法的優化，它是將用拉鏈法解決沖突的散列表退化成一個數組，即無限網狀結構的一個元素，然后根據實際情況自行連接各各元素，即拉鏈法的反復應用。無限網狀結構就是將拉鏈法反復的應用在一個散列表中，很好的解決散列表中的地址沖突問題，既能夠很好的解決對于同義詞在備份空間的存儲方法問題，又能很好的解決在同義詞中又出現地址沖突問題，彌補了拉鏈法既解決不了同義詞的存儲方法問題又解決不了同義詞中出現地址沖突問題，完善了拉鏈法，是對拉鏈法的充分應用。

無限網狀結構的優點：無限網狀結構既能夠很好的解決對于同義詞在備份空間的存儲方法問題，又能很好的解決在同義詞中又出現地址沖突問題，是對拉鏈法，能夠很好的解決拉鏈法所不能解決的問題，如在例2中，在解決關鍵字沖突時，一方面在存儲關鍵字時，對同義詞關鍵字也采取了散列表存儲，提高了其查找速率，另一方面，在存儲faat時，由于其和fabt又發生了關鍵字沖突，在無限網狀結構中，采取了再次運用拉鏈法來解決同義詞沖突問題，但是若是采取拉鏈法來存儲，其則會采取如例1的方法來解決。

無限網狀結構的缺點：由于無限網狀結構沒有對關鍵字的存儲經行很好的控制，使得在無限網狀結構存儲數據時有可能造成存儲空間的浪費，在存儲空間有限或是對存儲空間要求過高時候該結構的弊端尤為突出。例如在例2 中，由于在存儲fa-at時，由于其和baft發生了同義詞沖突，如果用拉鏈法來存儲，則可以比無限網狀結構節省了單獨存儲關鍵字faat的存儲數組。

4 結論

在這里提出的無限網狀結構，可以對拉鏈法解決地址沖圖問題進行完善優化，對于拉鏈法中，無法很好的處理發生沖突的關鍵字即同義詞的存儲問題有了很好的解決，然而其在解決問題的同時也帶來了新的問題，即存儲空間的浪費，正是由于無限網狀結構的這個缺點導致其現在還無法應用，需要進行進一步研究和優化。

[參考文獻]

[1]殷人昆.教據結構（用面向對象方法與C++語言描述）[M].2版.北京：清華大學出版社，2007.

[2]克努特.蘇運霖，譯.計算機程序設計藝術（第3卷排序與查找）[M].2版.北京：國防工業出版社，2002：478.

[3]許卓群，楊冬青，唐世渭，等.數據結構與算法[M].北京：高等教育出版社，2004：306—309.

[4]徐孝凱.教據結構[M].北京：電子工業出版社，2004：271.

[5]維斯.馮舜璽，譯.數據結構與算法分析：C語言描述[M].2版.北京：機械工業出版社，2004：126.