哈希表的概念

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

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

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

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

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

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

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

p的選取很重要，一般選小于或等于表長(zhǎng)的最大素?cái)?shù)，這樣可以減少?zèng)_突。

常見(jiàn)的哈希沖突解決方法

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

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

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

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

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

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

散列表的性能分析：

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