哈希表中元素是由哈希函數(shù)確定的。將數(shù)據(jù)元素的關(guān)鍵字K作為自變量，通過一定的函數(shù)關(guān)系（稱為哈希函數(shù)），計(jì)算出的值，即為該元素的存儲地址。表示為：

Addr = H（key）

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

⑴構(gòu)造一個(gè)合適的哈希函數(shù)

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

簡單　以提高地址計(jì)算的速度

⑵沖突的處理

沖突：在哈希表中，不同的關(guān)鍵字值對應(yīng)到同一個(gè)存儲位置的現(xiàn)象。即關(guān)鍵字K1≠K2，但H（K1）= H（K2）。均勻的哈希函數(shù)可以減少?zèng)_突，但不能避免沖突。發(fā)生沖突后，必須解決；也即必須尋找下一個(gè)可用地址。

解決沖突的方法： ^[1] 

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

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

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

⑶桶定址法。桶：一片足夠大的存儲空間。桶定址：為表中的每個(gè)地址關(guān)聯(lián)一個(gè)桶。如果桶已經(jīng)滿了，可以使用開放定址法來處理。例如，插入A5,A2,A3,B5,A9,B2,B9,C2，采用線性探查法解決沖突。如圖。

 

哈希函數(shù)哈希表的構(gòu)造方法

例如：有一個(gè)從1到100歲的人口數(shù)字統(tǒng)計(jì)表，其中，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身。

有學(xué)生的生日數(shù)據(jù)如下：

年.月.日

75.10.03

75.11.23

76.03.02

76.07.12

75.04.21

76.02.15

...

經(jīng)分析，第一位，第二位，第三位重復(fù)的可能性大，取這三位造成沖突的機(jī)會(huì)增加，所以盡量不取前三位，取后三位比較好。

取關(guān)鍵字平方后的中間幾位為哈希地址。

將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址，這方法稱為折疊法。

例如：每一種西文圖書都有一個(gè)國際標(biāo)準(zhǔn)圖書編號，它是一個(gè)10位的十進(jìn)制數(shù)字，若要以它作關(guān)鍵字建立一個(gè)哈希表，當(dāng)館藏書種類不到10,000時(shí)，可采用此法構(gòu)造一個(gè)四位數(shù)的哈希函數(shù)。

取關(guān)鍵字被某個(gè)不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址。

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

選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即

H(key)=random(key），其中random為隨機(jī)函數(shù)。通常用于關(guān)鍵字長度不等時(shí)采用此法。

若已知哈希函數(shù)及沖突處理方法，哈希表的建立步驟如下：

Step1.　取出一個(gè)數(shù)據(jù)元素的關(guān)鍵字key，計(jì)算其在哈希表中的存儲地址D=H(key）。若存儲地址為D的存儲空間還沒有被占用，則將該數(shù)據(jù)元素存入；否則發(fā)生沖突，執(zhí)行Step2。

Step2.　根據(jù)規(guī)定的沖突處理方法，計(jì)算關(guān)鍵字為key的數(shù)據(jù)元素之下一個(gè)存儲地址。若該存儲地址的存儲空間沒有被占用，則存入；否則繼續(xù)執(zhí)行Step2，直到找出一個(gè)存儲空間沒有被占用的存儲地址為止。

無論哈希函數(shù)設(shè)計(jì)有多么精細(xì)，都會(huì)產(chǎn)生沖突現(xiàn)象，也就是2個(gè)關(guān)鍵字處理函數(shù)的結(jié)果映射在了同一位置上，因此，有一些方法可以避免沖突。

拉出一個(gè)動(dòng)態(tài)鏈表代替靜態(tài)順序存儲結(jié)構(gòu)，可以避免哈希函數(shù)的沖突，不過缺點(diǎn)就是鏈表的設(shè)計(jì)過于麻煩，增加了編程復(fù)雜度。此法可以完全避免哈希函數(shù)的沖突。

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

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

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

如果di取1，則每次沖突之后，向后移動(dòng)1個(gè)位置.如果di取值可能為1,-1,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2）

稱二次探測再散列。如果di取值可能為偽隨機(jī)數(shù)列。稱偽隨機(jī)探測再散列。

假設(shè)哈希函數(shù)的值域?yàn)閇0,m-1]，則設(shè)向量HashTable[0..m-1]為基本表，另外設(shè)立存儲空間向量OverTable[0..v]用以存儲發(fā)生沖突的記錄。