我們在這篇文章將要學習最有用的資料結構之一—哈希表，哈希表的英文叫 Hash Table，也可以稱為散串列或者 Hash 表，
哈希表用的是陣列支持按照下標隨機訪問資料的特性，所以哈希表其實就是陣列的一種擴展，由陣列演化而來，可以說，如果沒有陣列，就沒有散串列，
哈希表存盤的是由鍵（key）和值（value）組成的資料， 例如，我們將每個人的性別作為資料進行存盤，鍵為人名，值為對應的性別，其中 M 表示性別為男，F 表示性別為女，
為什么需要哈希表？
為了和哈希表進行對比，我們先將這些資料存盤在陣列中，
此處準備了6個箱子（即長度為6的陣列）來存盤資料，假設我們需要查詢 Ally 的性別，由于不知道 Ally 的資料存盤在哪個箱子里，所以只能從頭開始查詢，這個操作便叫作線性查找，一般來說，我們可以把鍵當成資料的識別符號，把值當成資料的內容，
從 0 號箱子開始查找，發現 0 號箱子中存盤的鍵是 Joe 而不是 Ally，因此接著查找 1 號箱子，
哦豁，1 號箱子中的也不是 Ally，沒辦法，只能接著往下找，
有點小糟糕，2 號、3 號箱子中的也都不是 Ally，
功夫不負有心人，當我們查找到 4 號箱子的時候，發現其中資料的鍵為 Ally，把鍵對應的值取出，我們就知道 Ally 的性別為女（F），
通過上面的查找程序，我們發現資料量越多，線性查找耗費的時間就越長，由此可知：由于資料的查詢較為耗時，所以此處并不適合使用陣列來存盤資料，
但使用哈希表便可以解決這個問題，首先準備好陣列，這次我們用 5 個箱子的陣列來存盤資料，
嘗試把 Joe 存進去，使用哈希函式（Hash）計算 Joe 的鍵，也就是字串 Joe 的哈希值，比如得到的結果為4928，
將得到的哈希值除以陣列的長度 5，求得其余數，這樣的求余運算叫作mod運算，此處mod運算的結果為3，
因此，我們將 Joe 的資料存進陣列的 3 號箱子中，重復前面的操作，將其他資料也存進陣列中，
Sue 鍵的哈希值為 7291, mod 5 的結果為 1，將 Sue 的資料存進 1 號箱中，
Dan 鍵的哈希值為 1539, mod 5 的結果為 4，將 Dan 的資料存進 4 號箱中，
Nell 鍵的哈希值為 6276, mod 5 的結果為 1，本應將其存進陣列的 1 號箱中，但此時 1 號箱中已經存盤了 Sue 的資料，這種存盤位置重復了的情況便叫作沖突，
遇到這種情況，可使用鏈表在已有資料的后面繼續存盤新的資料（鏈表法），
Ally 鍵的哈希值為 9143, mod 5 的結果為 3，本應將其存盤在陣列的 3 號箱中，但 3 號箱中已經有了 Joe 的資料，所以使用鏈表，在其后面存盤 Ally 的資料，
Bob 鍵的哈希值為 5278, mod 5 的結果為 3，本應將其存盤在陣列的 3 號箱中，但 3 號箱中已經有了 Joe 和 Ally 的資料，所以使用鏈表，在 Ally 的后面繼續存盤 Bob 的資料，
像這樣存盤完所有資料，哈希表也就制作完成了，
接下來講解資料的查詢方法，假設我們要查詢 Dan 的性別，
為了知道 Dan 存盤在哪個箱子里，首先需要算出 Dan 鍵的哈希值，然后對其進行 mod 運算，最后得到的結果為 4，于是我們知道了它存盤在 4 號箱中，
查看 4 號箱可知，其中的資料的鍵與 Dan 一致，于是取出對應的值，由此我們便知道了 Dan 的性別為男（M），
那么，想要查詢 Ally 的性別時該怎么做呢？為了找到它的存盤位置，先要算出 Ally 鍵的哈希值，再對其進行 mod 運算，最終得到的結果為 3，
然而 3 號箱中資料的鍵是 Joe 而不是 Ally，此時便需要對 Joe 所在的鏈表進行線性查找，
于是我們找到了鍵為 Ally 的資料，取出其對應的值，便知道了 Ally 的性別為女（F），
哈希沖突
在哈希表中，我們可以利用哈希函式快速訪問到陣列中的目標資料，如果發生哈希沖突，就使用鏈表進行存盤，這樣一來，不管資料量為多少，我們都能夠靈活應對，
如果陣列的空間太小，使用哈希表的時候就容易發生沖突，線性查找的使用頻率也會更高；反過來，如果陣列的空間太大，就會出現很多空箱子，造成記憶體的浪費，因此，給陣列設定合適的空間非常重要，
在存盤資料的程序中，如果發生沖突，可以利用鏈表在已有資料的后面插入新資料來解決沖突，這種方法被稱為鏈表法，也被稱為鏈地址法，
其中在 Java 集合類的 HashMap 中解決沖突的方法就是采用的鏈表法，建議閱讀 HashMap 原始碼，
除了鏈地址法以外，還有幾種解決沖突的方法，其中，應用較為廣泛的是開放地址法，或稱為開放尋址法，這種方法是指當沖突發生時，立刻計算出一個候補地址（陣列上的位置）并將資料存進去，如果仍然有沖突，便繼續計算下一個候補地址，直到有空地址為止，可以通過多次使用哈希函式或線性探測法等方法計算候補地址，
在 Java 中，ThreadLocal 所使用的就是開放地址法，
哈希函式設計的好壞決定了哈希沖突的概率，也就決定哈希表的性能，
總結
這篇文章主要講了一些比較基礎的哈希表知識，包括哈希表的由來、哈希沖突的解決方法，
哈希表也叫散串列，來源于陣列，它借助哈希函式對陣列這種資料結構進行擴展，利用的是陣列支持按照下標隨機訪問元素的特性，是存盤 Key-Value 映射的集合，
哈希表兩個核心問題是哈希函式設計和哈希沖突解決，對于某一個 Key，哈希表可以在接近 O(1) 的時間內進行讀寫操作，哈希表通過哈希函式實作 Key 和陣列下標的轉換，通過開放尋址法和鏈表法來解決哈希沖突，哈希函式設計的好壞決定了哈希沖突的概率，也就決定哈希表的性能，
有興趣的可以在 JDK 中閱讀 HashMap 的原始碼，在 JDK 8 和之前的版本的實作還有許多不多，比如在 JDK 8 中，引入紅黑樹，當鏈表長度太長（默認超過 8）時，鏈表就轉換為紅黑樹，就可以利用紅黑樹快速增刪改查的特點，提高 HashMap 的性能，
參考
《我的第一本演算法書》
https://github.com/wupeixuan/JDKSourceCode1.8
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/86921.html
標籤：其他
上一篇：鏈表
下一篇：二進制中1的個數