哈希函數

哈希表中元素是由哈希函數確定的。將數據元素的關鍵字K作為自變數，通過一定的函數關係（稱為哈希函數），計算出的值，即為該元素的存儲地址。

表示為：Addr = H（key）

為此在建立一個哈希表之前需要解決兩個主要問題：

⑴構造一個合適的哈希函數

均勻性 H（key）的值均勻分佈在哈希表中；

簡單以提高地址計算的速度

⑵衝突的處理

衝突：在哈希表中，不同的關鍵字值對應到同一個存儲位置的現象。即關鍵字K1≠K2，但H（K1）= H（K2）。均勻的哈希函數可以減少衝突，但不能避免衝突。發生衝突后，必須解決；也即必須尋找下一個可用地址。

解決衝突的方法：

⑴鏈接法（拉鏈法）。將具有同一散列地址的記錄存儲在一條線性鏈表中。例，除留餘數法中，設關鍵字為（18,14,01,68,27,55,79），除數為13。散列地址為（5,1,1,3,1,3,1），哈希散列表如圖。

⑵開放定址法。如果h(k）已經被佔用，按如下序列探查：(h(k)+p⑴）%TSize,(h(k)+p⑵）%TSize，…，（h(k)+p(i))%TSize，…

其中，h(k)為哈希函數，TSize為哈希表長，p(i）為探查函數。在 h(k)+p(i-1)）%TSize的基礎上，若發現衝突，則使用增量 p(i) 進行新的探測，直至無衝突出現為止。其中，根據探查函數p(i）的不同，開放定址法又分為線性探查法（p(i) = i : 1,2,3，…），二次探查法（p(i)=(-1)^(i-1)*((i+1)/2)^2，探查序列依次為：1, -1,4, -4, 9 …），隨機探查法（p(i): 隨機數），雙散列函數法（雙散列函數h(key) ，hp (key）若h(key）出現衝突，則再使用hp (key）求取散列地址。探查序列為：h(k),h(k)+ hp(k），…，h(k)+ i*hp(k））。

⑶桶定址法。桶：一片足夠大的存儲空間。桶定址：為表中的每個地址關聯一個桶。如果桶已經滿了，可以使用開放定址法來處理。例如，插入A5,A2,A3,B5,A9,B2,B9,C2，採用線性探查法解決衝突。如圖。

例如：有一個從1到100歲的人口數字統計表，其中，年齡作為關鍵字，哈希函數取關鍵字自身。

有學生的生日數據如下：

年。月。日

75.10.03

75.11.23

76.03.02

76.07.12

75.04.21

76.02.15

...

經分析，第一位，第二位，第三位重複的可能性大，取這三位造成衝突的機會增加，所以盡量不取前三位，取后三位比較好。

取關鍵字平方后的中間幾位為哈希地址。

將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為哈希地址，這方法稱為摺疊法。

例如：每一種西文圖書都有一個國際標準圖書編號，它是一個10位的十進位數字，若要以它作關鍵字建立一個哈希表，當館藏書種類不到10,000時，可採用此法構造一個四位數的哈希函數。

取關鍵字被某個不大於哈希表表長m的數p除后所得餘數為哈希地址。

H(key)=key MOD p (p<=m)

選擇一個隨機函數，取關鍵字的隨機函數值為它的哈希地址，即

H(key)=random(key），其中random為隨機函數。通常用於關鍵字長度不等時採用此法。

若已知哈希函數及衝突處理方法，哈希表的建立步驟如下：

Step1.取出一個數據元素的關鍵字key，計算其在哈希表中的存儲地址D=H(key）。若存儲地址為D的存儲空間還沒有被佔用，則將該數據元素存入；否則發生衝突，執行Step2。

Step2.根據規定的衝突處理方法，計算關鍵字為key的數據元素之下一個存儲地址。若該存儲地址的存儲空間沒有被佔用，則存入；否則繼續執行Step2，直到找出一個存儲空間沒有被佔用的存儲地址為止。

無論哈希函數設計有多麼精細，都會產生衝突現象，也就是2個關鍵字處理函數的結果映射在了同一位置上，因此，有一些方法可以避免衝突。

拉出一個動態鏈表代替靜態順序存儲結構，可以避免哈希函數的衝突，不過缺點就是鏈表的設計過於麻煩，增加了編程複雜度。此法可以完全避免哈希函數的衝突。

設計二種甚至多種哈希函數，可以避免衝突，但是衝突幾率還是有的，函數設計的越好或越多都可以將幾率降到最低（除非人品太差，否則幾乎不可能衝突）。

開放地址法有一個公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1）

其中，m為哈希表的表長。di 是產生衝突的時候的增量序列。如果di值可能為1,2,3,...m-1，稱線性探測再散列。

如果di取1，則每次衝突之後，向後移動1個位置。如果di取值可能為1,-1,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2）

稱二次探測再散列。如果di取值可能為偽隨機數列。稱偽隨機探測再散列。

假設哈希函數的值域為[0,m-1]，則設向量HashTable[0..m-1]為基本表，另外設立存儲空間向量OverTable[0..v]用以存儲發生衝突的記錄。