無限網(wǎng)狀結(jié)構(gòu)對拉鏈法解決地址沖突問題的優(yōu)化

摘 要：本文提出利用無限網(wǎng)狀結(jié)構(gòu)對拉鏈法解決地址沖突問題進(jìn)行優(yōu)化，通過實(shí)例證明，此法提高了拉鏈法解決散列表中存在的地址沖突問題的工作效率。

關(guān)鍵詞：散列表；沖突；拉鏈法；無線網(wǎng)狀結(jié)構(gòu)

1 概述

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

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

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

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

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

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

3 無限網(wǎng)狀結(jié)構(gòu)解決地址沖突問題

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

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

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

拉鏈法和無限網(wǎng)狀結(jié)構(gòu)的聯(lián)系：無限網(wǎng)狀結(jié)構(gòu)是對拉鏈法的優(yōu)化，它是將用拉鏈法解決沖突的散列表退化成一個(gè)數(shù)組，即無限網(wǎng)狀結(jié)構(gòu)的一個(gè)元素，然后根據(jù)實(shí)際情況自行連接各各元素，即拉鏈法的反復(fù)應(yīng)用。無限網(wǎng)狀結(jié)構(gòu)就是將拉鏈法反復(fù)的應(yīng)用在一個(gè)散列表中，很好的解決散列表中的地址沖突問題，既能夠很好的解決對于同義詞在備份空間的存儲方法問題，又能很好的解決在同義詞中又出現(xiàn)地址沖突問題，彌補(bǔ)了拉鏈法既解決不了同義詞的存儲方法問題又解決不了同義詞中出現(xiàn)地址沖突問題，完善了拉鏈法，是對拉鏈法的充分應(yīng)用。

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

無限網(wǎng)狀結(jié)構(gòu)的缺點(diǎn)：由于無限網(wǎng)狀結(jié)構(gòu)沒有對關(guān)鍵字的存儲經(jīng)行很好的控制，使得在無限網(wǎng)狀結(jié)構(gòu)存儲數(shù)據(jù)時(shí)有可能造成存儲空間的浪費(fèi)，在存儲空間有限或是對存儲空間要求過高時(shí)候該結(jié)構(gòu)的弊端尤為突出。例如在例2 中，由于在存儲fa-at時(shí)，由于其和baft發(fā)生了同義詞沖突，如果用拉鏈法來存儲，則可以比無限網(wǎng)狀結(jié)構(gòu)節(jié)省了單獨(dú)存儲關(guān)鍵字faat的存儲數(shù)組。

4 結(jié)論

在這里提出的無限網(wǎng)狀結(jié)構(gòu)，可以對拉鏈法解決地址沖圖問題進(jìn)行完善優(yōu)化，對于拉鏈法中，無法很好的處理發(fā)生沖突的關(guān)鍵字即同義詞的存儲問題有了很好的解決，然而其在解決問題的同時(shí)也帶來了新的問題，即存儲空間的浪費(fèi)，正是由于無限網(wǎng)狀結(jié)構(gòu)的這個(gè)缺點(diǎn)導(dǎo)致其現(xiàn)在還無法應(yīng)用，需要進(jìn)行進(jìn)一步研究和優(yōu)化。

[參考文獻(xiàn)]

[1]殷人昆.教據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語言描述）[M].2版.北京：清華大學(xué)出版社，2007.

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

[3]許卓群，楊冬青，唐世渭，等.數(shù)據(jù)結(jié)構(gòu)與算法[M].北京：高等教育出版社，2004：306—309.

[4]徐孝凱.教據(jù)結(jié)構(gòu)[M].北京：電子工業(yè)出版社，2004：271.

[5]維斯.馮舜璽，譯.數(shù)據(jù)結(jié)構(gòu)與算法分析：C語言描述[M].2版.北京：機(jī)械工業(yè)出版社，2004：126.