哈希函式

一般的線性表，樹中，記錄在結構中的相對位置是隨機的，即和記錄的關鍵字之間不存在確定的關係，因此，在結構中查找記錄時需進行一系列和關鍵字的比較。這一類查找方法建立在“比較“的基礎上，查找的效率依賴於查找過程中所進行的比較次數。 理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關係f，使每個關鍵字和結構中一個唯一的存儲位置相對應。

基本介紹

• 中文名：哈希函式
• 外文名：Hash Function
• 其他名稱：散列函式
• 表達式：Addr = H（key）
• 作用1：加密
• 作用2：語音識別
• 作用3：散列表
• 領域：計算機算法

哈希表的概念及作用

哈希表中元素是由哈希函式確定的。將數據元素的關鍵字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]用以存儲發生衝突的記錄。