散列的基本思想就是映射，通過哈希函數將關鍵字信息映射到另外一個值，這個值保存了關鍵字信息的存儲地址，查找的時候可以直接通過關鍵字獲取查找的信息，而不需要進行復雜的搜索運算，查找的期望時間為O(1)，保存了關鍵字信息的數據結構叫做散列表。例如數12，23，34，46，59，散列函數為數值的十位數字，則這5個值可以分別映射到1，2，3，4，5保存在散列表中，在查找數據時根據其映射值在表中可以直接得到消息。 　　兩個不同的關鍵字，由于散列函數值相同，因而被映射到同一表位置上。該現(xiàn)象稱為沖突。因為在散列表中一般映射值是作為表的下標來確定數據保存位置的，因此需要考慮映射值的范圍。 　　 　　散列中需要考慮的兩個問題： 　　１、如何構造使結點“分布均勻”的散列函數？ 　　２、一旦發(fā)生沖突，用什么方法來解決？

　　通常有兩類方法處理沖突：開放定址(Open Addressing)法和拉鏈(Chaining)法。前者是將所有結點均存放在散列表T[0..m-1]中；后者通常是將互為同義詞的結點鏈成一個單鏈表，而將此鏈表的頭指針放在散列表T[0..m-1]中。 　　 　　開放地址法 　　用開放定址法解決沖突的做法是：當沖突發(fā)生時，使用某種探查(亦稱探測)技術在散列表中形成一個探查(測)序列。沿此序列逐個單元地查找，直到找到給定的關鍵字，或者碰到一個開放的地址(即該地址單元為空)為止（若要插入，在探查到開放的地址，則可將待插入的新結點存人該地址單元）。查找時探查到開放的地址則表明表中無待查的關鍵字，即查找失敗。 　常用的探查技術有：線性探查法，二次探查法，雙重散列法等。 　 　　拉鏈法 　　拉鏈法解決沖突的做法是：將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。 　 　 參考：散列 　　　http://student.zjzk.cn/course_ware/data_structure/web/main.htm