數據結構中的 Hash 表

什麼是散列表

是根據鍵 (Key) 而直接訪問在內存存儲位置的數據結構。也就是說，它通過計算一個關於鍵值的函數，將所需查詢的數據映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數稱做散列函數，存放記錄的數組稱做散列表。

通俗的解釋

一個通俗的例子是，為了查找電話簿中某人的號碼，可以創建一個按照人名首字母順序排列的表（即建立人名x 到首字母 F(x) 的一個函數關係），在首字母為W的表中查找 王 姓的電話號碼，顯然比直接查找就要快得多。這裡使用人名作為關鍵字，取首字母 是這個例子中散列函數的函數法則 F(x) ，存放首字母的表對應散列表。關鍵字和函數法則理論上可以任意確定。

基本思想

若關鍵字為 k，則其值存放在 f(k) 的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關係 f 為散列函數

散列表幾個重要概念 ：

散列函數、裝載因子、散列衝突

裝載因子：

α = 填入表中的元素個數 / 散列表的長度

α 是散列表裝滿程度的標誌因子。由於表長是定值，α 與“填入表中的元素個數”成正比，所以，α 越大，表明填入表中的元素越多，產生衝突的可能性就越大；反之，α 越小，標明填入表中的元素越少，產生衝突的可能性就越小。實際上，散列表的平均查找長度是載荷因子 α 的函數，只是不同處理衝突的方法有不同的函數。

對於開放定址法，荷載因子是特別重要因素，應嚴格限制在 0.7-0.8 以下。超過 0.8 ，查表時的CPU緩存不命中（cache missing）按照指數曲線上升。因此，一些採用開放定址法的 hash 庫，如 Java 的系統庫限制了荷載因子為 0.75，超過此值將 resize 散列表。

散列衝突：

就是指多個元素通過散列函數計算得到的散列地址是相同的。

散列函數：

散列函數選取原則：

好的散列函數 = 計算簡單 + 分佈均勻

數據結構中的散列函數：

1，直接定址法 ： 取關鍵字或關鍵字的某個線性函數值為散列地址。即hash(k)=k或hash(k)=a⋅k+b，其中 ab 為常數。

2，數字分析法 ： 數字分析法通常適合處理散列表中可能出現的關鍵字都是事先知道的，例如我們現在要存儲某家公司員工登記表，如果用手機號作為關鍵字，那麼我們發現抽取後面的四位數字作為散列地址是不錯的選擇，同理存儲身份證號碼時，也可以採用這樣的邏輯。

3，平方去中法 ： 平方取中法是將關鍵字平方之後取中間若干位數字作為散列地址。這種方法適用於不知道關鍵字的分佈，且數值的位數又不是很大的情況。

3，隨機數法 ： 選擇一個隨機數，取關鍵字的隨機函數值為它的散列地址，f(key)=random(key)

4，除留取餘法： 取關鍵字被某個不大於散列表表長 m 的數 p 除後所得的餘數為散列地址。即 hash(k)=kmodp,p≤m p為小於m的最大質數，所謂素數就是指只能被 1 與它本身整除的數。

主要的散列衝突的解決辦法

開放尋址法：

所謂的開放定址法就是一旦發生了衝突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，並將記錄存入。

主要是有線性探查 fi(key)=(f(key)+di)MODm(di=1,2,…,m−1)
平方探查 fi(key)=(f(key)+di)MODm(di=1²,−1²,2²,−2²…,q²,−q²,q<=m/1)

拉鍊法（鏈地址法）
將散列到同一個存儲位置的所有元素保存在一個鏈表中。

再散列法：

即在上次散列計算發生衝突時，利用該次衝突的散列函數地址產生新的散列函數地址，直到衝突不再發生。

Example

開放定址法

散列表查找的偽代碼

Java 中的散列

Java 中的散列衝突解決方法就是上文中提到的開放定址法。散列函數如下。

散列查找方法

散列表的插入

小結

最近在學習數據結構的時候，複習了一下散列表的基本概念，因為散列表在我們敲代碼的時候用的比較多，所以打好基礎還是有必要的。

參考鏈接

• 維基百科