哈希表的原理
哈希表的原理
簡介
哈希表是一種根據關鍵字key來訪問值value的一種數據結構。
哈希表的基本原理
哈希表的本質是數組加哈希函數。數組不難理解，那什麼是哈希函數？
在哈希表中，它的作用就是將哈希表的某個key作為輸入，然後經過一系列的運算後，得到數組的某
個索引。一種很樸素的思路是，先用key計算出一個很大的數，然後對數組長度取模，從而得到索引，這只是眾多方法中的一種，其他的比如：直接尋址法，平方取中法等。
得到索引後就可以通過索引對數組執行插入或查找的操作，因為本質上是通過索引來訪問數組，所以哈希表的插入和查找的效率非常高，時間複雜度都是O(1)。
哈希衝突
我們不難發現哈希函數是整個哈希表的關鍵。所以為了更好的性能，我們希望在儘可能短的時間內，相同的key經過哈希函數的計算，可以得到相同的索引，不同的key經過哈希函數的計算，可以得到不同的索引，但在實際中往往事與願違，不同的key小概率會計算出相同的索引，這就是哈希衝突（collision），幾乎所有的哈希函數都存在這個問題。
這裡介紹幾個常見的解決哈希衝突的方法：
開放尋址法
開放尋址是一種思想，如果通過哈希函數計算出的索引所對應的空間已經被佔用了，就再找一個還沒被佔用的空間將數據存進去。
常見的體現開放尋址思想的方法：
- 線性探測法：簡單來說就是從當前被佔用的空間的索引開始，向下遍歷整個數組，直到找到空閑空間為止。如下圖所示：
- 雙重哈希法：使用多個哈希函數來計算索引，如果第一個哈希函數計算得到的索引所對應的空間已被佔用，就用第二個，第二個被佔用就用第三個，以此類推，直到計數出沒被佔用的空間對應的索引。
鏈表法
鏈表法是一種更加常見的解決哈希衝突的方法，Java中的HashMap就是採用這種方法。在這種方法中，數組索引對應的空間並不直接存儲數據，而是存儲一個鏈表的地址，而數據存在鏈表中。如下圖所示：
這樣發生衝突時，就可將衝突的key對應的數據存在同一個鏈表上，當需要取數據時，就先找到key對應的鏈表，然後遍歷鏈表。
數組擴容
上面說的方法只能在一定程度上解決哈希衝突，因為畢竟數組的容量有限，當頻繁插入數據時，因為數組的容量有限，所以就會使哈希衝突加劇，進而使鏈表的長度增加，鏈表的長度增加，就會使得查找的性能降低，這不是我們想看到的結果，所以要對數組擴容。
那什麼時候給數組擴容呢？裝載因子（已插入元素的數量除以數組容量）超過某一閾值時就進行擴容，Java中HashMap的裝載因子是0.75，當然，也可以是別的值。因為之前插入的元素都是按照原數組的長度來計算索引的，所以一旦數組擴容後，長度改變，就要重新進行計算，然後將已插入的元素移動到新的位置上，所以數組擴容不僅僅只是將容量增大而已。
