哈希表的概念

哈希表(hash)，又稱散列表，根據(jù)給定的關(guān)鍵字來計算關(guān)鍵字在表中的地址。

常用hash函數(shù)的構(gòu)造方法

1. 直接定址法:
取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)為hash地址，即H(key) = key 或者 H(key) = a*key + b，其中a和b為常數(shù)。

2. 數(shù)字分析法：
假設(shè)關(guān)鍵字是r進制數(shù)（如十進制數(shù)），并且hash表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可選取關(guān)鍵字的若干數(shù)位組成hash地址。選擇的原則是使得到的hash地址盡量減少沖突，即所選數(shù)位上的數(shù)字盡可能是隨機的。

3. 平方取中法：
取關(guān)鍵字平方后的中間幾位作為hash地址，取的位數(shù)由表長決定。

4. 除留余數(shù)法：（使用最多）
取關(guān)鍵字被某個不大于hash表表長的數(shù)p除后所得的余數(shù)為hash地址，即：

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

p的選取很重要，一般選小于或等于表長的最大素數(shù)，這樣可以減少沖突。

常見的哈希沖突解決方法

1. 開放定址法：
主要有兩種： 1）線性探查法；2）平方探查法
1）線性探查法：
線性探查法是從發(fā)生沖突的地址（設(shè)為d）開始，依次探查d的下一個地址（當?shù)竭_表尾時，從表首地址又開始探查）。其遞推公式為：

Hi(k) = (H(k) + i) Mod m (1 <= i <= m-1)

可能產(chǎn)生堆積問題。

2) 平方探查法：
平方探查法所得到的新的地址序列為d+1^2, d-1^2, d+2^2, d-2^2...
平方探查法是一種較好的處理沖突的方法，可以減少出現(xiàn)堆積問題。它的缺點是不能探查到hash表上所有單元，但至少能探查到一半的單元。

此外，開放定址法的探查方法還有偽隨機序列法以及雙hash函數(shù)法（雙hash 法即hash地址為H(H(k))）。

2. 鏈地址法：
鏈地址法是把所有相同的同義詞用單鏈表連接起來的方法。在這種方法中，hash表每個單元中存放的不再是記錄本身，而是相應(yīng)同義詞單鏈表的表頭指針。

散列表的性能分析：

查找成功時的平均查找長度是指找到表中已有表項的平均比較次數(shù)，它是找到表中各個已有表項的平均比較次數(shù)。
而查找不成功時的平均查找長度是指在表中找不到待查的表項，但找到插入位置的平均比較次數(shù)。
hash表的平均查找長度與關(guān)鍵字個數(shù)n無關(guān)，而與裝填因子a有關(guān)。a = n/m，n為關(guān)鍵字個數(shù)，m為表長。