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