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

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

1 概述

散列表又稱為哈希表，是線性表中一種重要的存儲(chǔ)方式和檢索方法。在散列表中，可以對(duì)節(jié)點(diǎn)進(jìn)行快速檢索。散列表算法的基本思想是：由結(jié)點(diǎn)的關(guān)鍵碼值決定結(jié)點(diǎn)的存儲(chǔ)地址，即以關(guān)鍵碼值k為自變量，通過一定的函數(shù)關(guān)系h（稱為散列函數(shù)），計(jì)算出對(duì)應(yīng)的函數(shù)值h（k）來，將這個(gè)值解釋為結(jié)點(diǎn)的存儲(chǔ)地址，將結(jié)點(diǎn)存入該地址中，檢索時(shí)，根據(jù)要檢索的關(guān)鍵碼值，用同樣的散列函數(shù)計(jì)算出地址，然后，到相應(yīng)的地址中去獲取所要的結(jié)點(diǎn)數(shù)據(jù)。因此，散列表有一個(gè)重要特征：平均檢索的長(zhǎng)度不直接依賴于表中元素的個(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è)連表中。若選擇的鏈表長(zhǎng)度為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ù)，用線性探測(cè)法解決沖突構(gòu)造這組關(guān)鍵字的散列表

為了減少?zèng)_突通常令裝載因子小于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占用。故用拉鏈法存儲(chǔ)15，即重新申請(qǐng)一個(gè)空間將15放入空間中，對(duì)12和51處理方法是一樣的。

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

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

無限網(wǎng)狀結(jié)構(gòu)解決地址沖突問題的基本思想：將關(guān)鍵字放在帶頭指針的數(shù)組，數(shù)組數(shù)目可以視數(shù)據(jù)量自行申請(qǐng)空間設(shè)置，但是所有數(shù)組結(jié)構(gòu)都是一樣的。若選擇的數(shù)組的長(zhǎng)度為m，則可將數(shù)組定義為一由m個(gè)頭指針組成的指針數(shù)組T[0...m-1]，然后各各數(shù)組之間的相互連接方式，根據(jù)實(shí)際情況自行進(jìn)行，所有數(shù)組中關(guān)鍵字的存儲(chǔ)都按照相應(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)來存儲(chǔ)，將關(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)行處理，對(duì)home開創(chuàng)一個(gè)數(shù)組將其按照第二個(gè)字母確定其地址，對(duì)于 fabt fbet必須創(chuàng)建一個(gè)數(shù)組進(jìn)行儲(chǔ)存，又因?yàn)閒aat和fabt關(guān)鍵字的發(fā)生了沖突，故應(yīng)該在此運(yùn)用拉鏈法來解決，即在申請(qǐng)一個(gè)數(shù)組空間來存儲(chǔ)該關(guān)鍵字，這些關(guān)鍵字的存儲(chǔ)結(jié)果結(jié)構(gòu)圖如下圖：

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

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

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

4 結(jié)論

在這里提出的無限網(wǎng)狀結(jié)構(gòu)，可以對(duì)拉鏈法解決地址沖圖問題進(jìn)行完善優(yōu)化，對(duì)于拉鏈法中，無法很好的處理發(fā)生沖突的關(guān)鍵字即同義詞的存儲(chǔ)問題有了很好的解決，然而其在解決問題的同時(shí)也帶來了新的問題，即存儲(chǔ)空間的浪費(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版.北京：國(guó)防工業(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.