哈希表，終于姗姗來遲了。
本文系統講解了哈希表資料結構的相關概念，并以HashMap為案例講解一下它與普通哈希表的不同點，最後也手寫一個簡易的哈希表。
是以通過本文，我希望讀者們能對哈希表有一個清楚的認識，尤其是在Java面試過程中，HashMap的相關面試題幾乎是逢面必問，如果你連哈希表結構都不清楚，那真的很難從根上了解HashMap。
除了面試，在你掌握了哈希表之後也可以根據應用場景的需要，對哈希函數進行重寫，以此來保證在你的應用場景下哈希分布的更加均勻。
本文概覽如下：
散清單（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行通路的資料結構。也就是說，它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散清單。
哈希作為一個非常常用的查找資料結構，它能夠在O(1) 的時間複雜度下進行資料查找。
比方說我有一個集合有如下資料，而我想要快速查找一個資料在不在這個集合中，我應該采取什麼辦法？
一般情況下可以使用周遊的方式，但是如果資料量太多，則每次周遊的代價将不可接受。
那麼，如果它們是有序的，則可以使用樹形資料結構進行二分查找，效率也是非常的高，但很不巧我們這些資料是無序的。
是以就有人想到一個很巧妙的辦法來尋找它，就是将要尋找的資料（下文稱為鍵）進行一次計算得到一個數組下标值，然後将這個值放到對應的數組裡。
以後我們每次尋找的時候都對鍵進行計算進而得到一個數組下标值，然後通過下标拿到數組對應的資料，就能知道它是否存在于這個數組中了。
這種資料查找的資料結構就叫做哈希表，對鍵的計算的方法叫做哈希函數。
在Java中，典型的Hash資料結構的類是HashMap。
我們回顧一下哈希表的執行步驟：
對鍵進行哈希函數計算，得到一個哈希值。
對哈希值進行計算得到一個數組下标。
通過數組下标得到數組中對應的數組。
由于哈希表的查找步驟與哈希函數都是恒定不變的，是以哈希表的時間複雜度為O(1)。
哈希函數是一種提取資料特征的算法，針對不通的資料形式有不同的雜湊演算法，是以哈希函數并不通用，針對不同場景有很多不同的雜湊演算法，比如我們常見的MD5就是一種擷取檔案資訊摘要的雜湊演算法。
再比如在Java中，對于常用的資料類型，JDK就實作了多種不同的hash函數。
Integer：
Integer的哈希函數就是直接拿到它的值。
String：
對于字元串類型則是使用了一個這樣一種算法：<code>s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]</code>。
Double：
浮點類型則是使用位運算的方式進行哈希計算。
讀者們可能會有疑惑，為什麼要對這麼多資料結構實作不同的哈希計算方法，這主要還是為了哈希值的均勻。
哈希值越均勻，就說明哈希函數設計的越好，也預示的哈希沖突的減少，關于哈希沖突，将在下節講到。
在第一節的時候我說過，除了計算哈希值，我們還需要計算數組的位置。
計算數組位置有很多方法可用，這裡我就介紹比較簡單的除留餘數法：
假設我對<code>中國人</code>這個key進行計算，得到了一個哈希值：19942986，那麼我将用這個數字對數組的大小進行取餘，這裡我假設自己的數組大小是11，就得到這樣的計算公式：
<code>19942986 % 11 = 8</code>
那麼，我們就得出了本次哈希函數的結果為數組下标8，我們就可以将<code>中國人</code>這個字元串放到了數組下标8的位置上。
既然哈希值計算希望越均勻越好，那麼數組下标是否也有類似的需求呢？
還真有，比如我們上面的除留餘數法，在除留餘數法中，數組大小的選擇将深刻影響着取餘結果是否均勻，是以在除留餘數法中，我們一般使用質數，這也是為什麼HashTable的初始化大小為11，因為11是一個質數。
經過前文的學習後，相信大家對哈希表的相關概念都已經清楚了，那麼本節就來學習哈希表的一大重點：哈希沖突。
哈希沖突是指多個不同的鍵散列到了同一個數組下标位置上，案例如下：
在上圖中，<code>耳、朵、不</code>這三個字經過散列之後的數組下标都是0，而且因為是三個不同的值，是以也不能直接在數組上覆寫，那麼我們就需要有一個辦法把這三個值存起來。
這裡将介紹兩種常用的方法：<code>開放位址法</code>和<code>鍊位址法</code>。
開放位址法是一種比較簡單的解決沖突的方法，它的原理非常簡單：
就是在第一個<code>耳</code>字已經占用了下标0之後，第二個<code>朵</code>字則向後進行尋找空餘的下标，找到之後将自己設定進去，是以<code>朵</code>字在下标1處，而<code>不</code>字在下标2處。
根據尋找下标的方式不同，開放位址法可以分為以下幾種：
線性探測法：下标被占用之後，以步長為1依次向後尋找，上圖例中我使用的就是這種方法。
二次探測法：下标被占用之後，步長為2的倍數，依次向後尋找。
僞随機探測法：下标被占用後，随機出一個數字，然後使用這個數字作為下标進行尋找，這種方法全靠天意了。
其實原理都差不多，都是在目前下标的基礎上向後尋找空餘的下标，不過步長不一樣罷了。
鍊位址法俗稱拉鍊法，就是在沖突的下标元素處維護一個連結清單，所有沖突的元素都依次放到這個連結清單上去：
在上圖中，我将沖突的兩個鍵就按照順序放在了連結清單中，下次尋找時隻需要檢視該數組元素以及周遊這個連結清單即可，在Java中的HashMap中就是用了這種方法進行解決哈希沖突。
以上兩種方法都有可能随着沖突的增多，導緻查找效率變低，是以沒有一個完美的方案可以解決哈希沖突的問題，我一般推薦使用拉鍊法，因為它比較簡單易了解。
前文中大量提到了HashMap，這一節就将對HashMap中的一些和上文講述不一樣的關鍵點進行梳理。
首先是HashMap的表容量，表容量就是這個哈希表中可以裝下多少個元素。
前文我已經說過，在哈希表中最好使用質數作為表的容量，并且還拿了HashTable作為舉例。
而在HashMap中，它的初始容量是16，這不光是一個偶數還是2的倍數。
HashMap之是以沒有使用質數而是使用2的倍數作為它的容量，是因為它在計算數組下标時沒有使用除留餘數法，而是使用了位運算進行計算數組下标。
計算完哈希值之後，則是使用哈希值和數組長度進行位運算：<code>(tab.length - 1) & hash</code>。
了解了上面的哈希知識之後，就可以自己寫一個類似hashMap的資料結構了。
首先呢，我們先來想一下做一個哈希表的必要條件：
哈希函數
哈希沖突方法
隻要牢記這兩點，寫出符合要求的資料結構即可：
在我的示例中，使用了字元串作為哈希表的鍵，而hash函數則是簡單的依次乘以31相加得出，這裡的傳回值是一個int類型，是以哈希值最大是32位。
在哈希映射的步驟上，我使用了上文講過的除留餘數法，同時表的大小設定為了一個質數：11。
除了這些之外，還有兩點可以加以擴充：
表可以進行擴容，擴容大小可以為原來的兩倍并+1，盡可能使其是質數。
使用拉鍊法解決沖突，我目前的做法是直接覆寫，使用拉鍊法可以将表的Object數組換成别的抽象資料類型數組，并多加一個雙向連結清單引用即可。
好了，以上就是哈希表的全部内容了，當然了，哈希也是有缺點的：
哈希沖突太多會導緻部分查找線性。
不能進行範圍查找。
對于第一個缺點，一般正常使用是不會出現太多沖突，而且在Java中，沖突太多則會自動轉換為紅黑樹資料結構。
對于第二個缺點，這是哈希表一個無法回避的硬傷，在需要範圍的查找的需求下，還是樹類資料結構更能兼顧範圍查找與指數級速度。
當然哈希表的速度足以掩蓋很多缺點，它在很多應用中都有使用，比如redis本身就是一個大大的哈希表，資料庫中的索引也往往有着哈希索引的選項，還有作業系統的系統資料庫之類的快速查找都會使用哈希表資料結構，就像一白遮百醜一樣，哈希，隻要快就夠了。
最後如果你覺得此文對你有一丁點幫助，點個贊。或者可以加入我的開發交流群：1025263163互相學習，我們會有專業的技術答疑解惑
也可以給我們的開源項目點點star: http://github.crmeb.net/u/defu 不勝感激 ！