摘 要：在利用計算機對大量散列信息進行處理時，人們發(fā)現(xiàn)通過構造哈希函數(shù)對信息進行存儲和查詢是一種行之有效的方法。但是，人們在處理這類問題的過程中發(fā)現(xiàn)該函數(shù)還存在著一個主要的問題，就是在由關鍵字到地址的映射時發(fā)生了“沖突”，即出現(xiàn)了多個關鍵字對應一個地址，與我們想要得到的一個關鍵字只對應一個地址的設想出現(xiàn)了偏差。盡管在這方面有許多專家學者從事過研究，但依然未能很好的解決這種“沖突”。因此，為了更好地解決該問題，應盡量選擇一種更合理的構造哈希函數(shù)的方法來解決這種“沖突”，達到評價哈希函數(shù)所要滿足的好壞標準“使函數(shù)值盡可能均勻的分布到散列地址空間中，減少沖突發(fā)生的次數(shù)”的要求，實現(xiàn)對信息的高效存儲或查找。本文正是基于這一目的，對前人的算法進行分析比較、給出實例驗證。在前人算法的基礎上做了一些改進，減少了沖突發(fā)生的次數(shù)。

關鍵詞：散列；哈希函數(shù)；沖突

則此時散列函數(shù)呈波動的狀態(tài)，存儲的關鍵字地址也就相應地呈現(xiàn)波動的狀態(tài)；如果增量di 取偽隨機數(shù)序列，則此時的關鍵字的存儲位置隨該增量的隨機變化而變化。找到相應的關鍵字后，就可以發(fā)現(xiàn)所需要的信息了。若查找完畢沒有發(fā)現(xiàn)所要查找的關鍵字，則說明所要查找的信息根本就不存在。

再哈希法算法思想：先考察哈希函數(shù)的構造方法，針對不同的方法，然后在查找的過程中采用與之相類似的不同再哈希函數(shù)一直哈希到不再產(chǎn)生沖突時為止，這樣便完成了一次查找。依此類推，直到查找出所有需要的關鍵字，找出對應的信息，查找成功；或是查找完畢，找不到所需要的信息，查找失敗。

鏈地址法算法思想：先構造一定長的靜態(tài)地址表（可以為數(shù)組），然后結合所選用的哈希函數(shù)找出關鍵字對應的地址。如發(fā)現(xiàn)在關鍵字到地址的映射過程中出現(xiàn)了同義詞沖突，則按照關鍵字遞增順序將其構成一單鏈表，鏈接到發(fā)生沖突時的那個地址上即可。接下來就可以順著鏈表往下查找，直到找出我們所需要的信息，查找成功；或是查找完畢，找不到所需要的信息，查找失敗。

當然哈希函數(shù)的查找算法遠不只以上幾種，但這幾種是比較常見的，下面將結合一個實際的例子來比較說明哈希函數(shù)的這幾種構造方法的查找效率。

2 實例分析

從對查找的結果分析中可得出哈希函數(shù)構造方法的查找效率，如表1所示。

表1 哈希函數(shù)構造方法查找效率比較

從以上三個關鍵字查找的運行結果圖及表1可以看出：直接定址法效率最高，平方取中法效率相對較高，其它四種方法：數(shù)字分析法、折疊法、除留余數(shù)法和隨機數(shù)法的效率較低，其中除留余數(shù)法又是這四個中相對較高的。由此可以證明對比分析總結的正確性了。

4 結束語

本文描述了構造哈希函數(shù)常用六種基本方法的算法思想，同時也選擇性地描述了三個相關處理沖突的沖突函數(shù)的算法思想，通過對算法的一些改進用一個簡單的實例來比較分析了各構造函數(shù)的查找效率。得出的結論是直接定址法查找效率最高，平方取中法相對較高，其它四種方法：數(shù)字分析法、折疊法、除留余數(shù)法和隨機數(shù)法的效率較低，其中除留余數(shù)法又是這四法中相對較高的，并且改進后的算法進一步提高了查找效率，減少了沖突的次數(shù)。

參考文獻：

[1]薛超英.數(shù)據(jù)結構[M].武漢：華中科技大學出版社，2002.

[2]許卓群.數(shù)據(jù)結構[M].北京：高等教育出版社，1987.

[3]朱戰(zhàn)立.數(shù)據(jù)結構[M].西安：西安交通大學出版社，2004.

[4]霍義興.實用數(shù)據(jù)結構[M].上海：上海科學技術出版社，1987.

[5][美]Clifford A. Shaffer著.數(shù)據(jù)結構與算法分析（Java版）[M].北京：電子工業(yè)出版社，2001.

[6]嚴蔚敏.數(shù)據(jù)結構[M].北京：清華大學出版社，1997.

[7]劉良觀，黃水松.數(shù)據(jù)結構[M].武漢：武漢大學出版社，2000.

[8]嚴蔚敏，吳偉民.數(shù)據(jù)結構（C語言版）[M].北京：清華大學出版社，2004.

作者簡介：杜志林（1983-），男，理學學士，助理工程師，主要研究方向：計算機科學與技術、計算機應用和多媒體技術。

作者單位：北京師范大學珠海分校教務處，廣州珠海 519085