什么是散列表

散列表（hash table），我們平時叫它哈希表或者Hash 表，你肯定經(jīng)常聽到它。

散列表是根據(jù)關鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

由定義我們可以知道，散列表用的是數(shù)組支持下標訪問數(shù)據(jù)的特性，所以散列表是數(shù)組的一種擴展，有數(shù)組演化而來。

舉個例子

假如我們一共有 50 人參加學校的數(shù)學競賽，然后我們?yōu)槊總€學生分配一個編號，依次是 1 到 50.

如果我們想要快速知道編號對應學生的信息，我們就可以用一個數(shù)組來存放學生的信息，編號為 1 的放到數(shù)組下標為 1 的位置，編號為 2 的放到數(shù)組下標為 2 的位置，依次類推。

現(xiàn)在如果我們想知道編號為 20 的學生的信息，我們只需要把數(shù)組下標為 20 的元素取出來就可以了，時間復雜度為 O(1)，是不是效率非常高呢。

但是這些學生肯定來自不同的年級和班級，為了包含更詳細的信息，我們在原來編號前邊加上年級和班級的信息，比如 030211 ，03 表示年級，02 表示班級，11 原來的編號，這樣我們該怎么存儲學生的信息，才能夠像原來一樣使用下標快速查找學生的信息呢？

思路還是和原來一樣，我們通過編號作為下標來儲存，但是現(xiàn)在編號多出了年級和班級的信息怎么辦呢，我們只需要截取編號的后兩位作為數(shù)組下標來儲存就可以了。

這個過程就是典型的散列思想。其中，參賽學生的編號我們稱之為鍵（key)，我們用它來標識一個學生。然后我們通過一個方法（比如上邊的截取編號最后兩位數(shù)字）把編號轉變?yōu)閿?shù)組下標，這個方法叫做散列函數(shù)（哈希函數(shù)），通過散列函數(shù)得到的值叫做散列值（哈希值）。

散列函數(shù)

通過上邊的例子，我們知道了散列函數(shù)的用途，散列函數(shù)在整個過程中起著非常關鍵的作用。

它本質就是一個函數(shù)，我們把它定義為 hash(key)，key 就是元素的鍵值，通過 hash 函數(shù)得到的值就是散列值。

在上邊的例子中，散列函數(shù)就是截取編號后兩位作為數(shù)組的下標，我們通過代碼一塊來看一下：

public int hash(String key)
{
    String lastTowNum = key.substring(key.length()-2,key.length());
    int index = Integer.parseInt(lastTowNum);
    return index;
}

那我們自己在設計散列函數(shù)的函數(shù)時應該遵循什么規(guī)則呢？

1. 得到的散列值是一個非負整數(shù)
2. 兩個相同的鍵，通過散列函數(shù)計算出的散列值也相同
3. 兩個不同的鍵，計算出的散列值不同

雖然我們在設計的時候要求滿足以上三條要求，但是對于第三條來說，想要找到不同的 key 對應的散列值都不一樣的散列函數(shù)是不可能的。即使現(xiàn)在非常著名的 MD5、SHA、CRC 哈希算法，也沒辦法避免這用哈希沖突。而且因為數(shù)組的存儲空間有限，也會加大這種哈希沖突。

哈希沖突

既然我們無法避免哈希沖突，那我們應該怎么解決它呢？常用的方法有兩種，開放尋址法和鏈表法。

開放尋址法

開發(fā)尋址法就是但我們遇到了哈希沖突，我們就重新探索一個空閑位置，然后插入。

我們探索空閑位置有以下幾種方法。

• 線性探測

當我們往散列表中插入數(shù)據(jù)時，經(jīng)過散列函數(shù)發(fā)現(xiàn)位置已經(jīng)被占用了，我們就從當前位置開始，依次往后查找，直到找到空閑位置為止。

比如一個散列表的大小為 10，一個數(shù)據(jù)經(jīng)過散列函數(shù)之后，到了下標為 8 的位置，但是發(fā)現(xiàn)這個位置已經(jīng)有數(shù)據(jù)了，那么就依次往后遍歷，如果到了尾部，還是沒有找到空閑位置，那么就再從頭開始找，直到找到空閑位置。

查找元素和插入類似，通過散列函數(shù)計算出哈希值，然后找到對應位置數(shù)據(jù)，然后與查找的元素進行比較，如果相等，則它就是我們要找的數(shù)據(jù)，如果不相等，就依次往后遍歷，如果遍歷到空閑位置還沒找到，就說明元素不在散列表中。

但是刪除的時候稍微有點特別，我們不能直接刪除數(shù)據(jù)，因為我們在查找的時候，如果找到一個空閑位置，就說元素不在散列表中，如果我們直接刪除了之后可能會導致某些元素找不到。所以我們將要刪除的元素，標記為 deleted，當我們查找的時候，遇到標記為 deleted 的元素，繼續(xù)往下遍歷。

線性探測法存在很大的問題，當散列表中插入的元素越來越多時，發(fā)生散列沖突的概率就越來越大，空閑的位置就越來越少，先行探索的時間就會越來越長，甚至在極端情況下，我們需要遍歷整個散列表。

• 二次探索

二次探索，和線性探索原理一樣，先行探索每次的步長為 1 ，探索的下標依次為 hash(key)+0，hash(key)+1，hash(key)+2...，二次探索每次的步長變?yōu)樵瓉淼亩畏?，所以每次探索的下邊?hash(key)+0，hash(key)+1^{2，hash(key)+2}2。

• 雙重散列

原來我們使用一個散列函數(shù)，雙重散列，我們使用多個散列函數(shù)，我們先用第一個散列函數(shù)，如果計算得到的位置已經(jīng)被占用，就使用第二個散列函數(shù)，以此類推，直到找到空閑時的位置。

不管用哪個探索方法，當空閑位置變少的時候，散列沖突的概率會變得很高。為了盡可能保證散列表的操作效率，一般情況下，我們會盡可能保證散列表中有一定比例的空閑槽位。我們用裝載因子來表示空位的多少。
裝載因子 = 填入散列表的元素個數(shù) / 散列表的長度

鏈表法

鏈表法是一種更為常用的解決散列沖突的方法，比開放尋址法更加簡單。在散列表中每個下標位置對應一個鏈表，所有經(jīng)過散列函數(shù)得到的散列值相同的元素，我們都放到對應下標位置的鏈表中。

插入元素時，經(jīng)過散列函數(shù)得到散列值，然后插入到對應下標位置的鏈表中即可，時間復雜度為 O(1)。查找和刪除同樣的對對應位置的鏈表進行操作，對應的時間復雜度和鏈表的長度有關系，也就是 O(n)。

怎樣設計散列函數(shù)

通過上邊介紹，我們知道散列函數(shù)在散列表中占非常重要的作用，關系到散列沖突的概率的大小，從而影響散列表的性能。那么怎么來判斷一個散列函數(shù)的好壞呢？

首先散列函數(shù)不能太復雜，太復雜肯定會消耗更多的時間，從而影響散列表的性能。

散列函數(shù)得到的散列值盡可能隨機且均勻分布，這樣才能減少散列沖突，即使有沖突，每個位置對應的元素也會比較平均，不會有的特別多，而有的特別少的情況。

散列表動態(tài)擴容

前邊我們提到過，當散列表的裝載因子過大的時候，散列表的空閑位置變得很少，散列沖突的概率就變得很大，而且插入和查找數(shù)據(jù)的效率也會變得很低。
這個時候我們就需要對散列表動態(tài)擴容，重新申請一個更大的散列表，然后把原有的數(shù)據(jù)移到新的散列表中。

如果擴容的時候我們重新申請一個原來散列表兩倍大的新散列表，原來的轉載因子如果為 0.8，那么重新申請的散列表的裝載因子即為 0.4。前邊我們講過數(shù)組的動態(tài)擴容，數(shù)據(jù)的遷移比較簡單，而散列表數(shù)據(jù)的遷移就相對比較復雜了，因為散列表的大小變了，那么數(shù)據(jù)存儲的位置也就變了，我們需要通過散列函數(shù)重新計算數(shù)據(jù)的存儲的位置。

我們可以設定一個閾值，當裝載因子大于閾值的時候，就需要對散列表動態(tài)擴容。

如果我們內存空間比較緊張，也可以設定另外一個閾值，當散列表的裝載因子小于閾值的時候，對散列表進行動態(tài)縮容，但這樣做散列表的執(zhí)行效率就會降低。

所以裝載因子的閾值我們要選擇得當，根據(jù)實際情況來權衡時間、空間復雜度的平衡。如果更在意性能，可以適當?shù)臓奚恍﹥却婵臻g；如果內存空間緊張，可以犧牲一些性能來換取內存空間。

當我們插入數(shù)據(jù)的時候，如果裝載因子大于閾值，就需要先擴容，再執(zhí)行插入操作，如果散列表很大，我們擴容搬遷數(shù)據(jù)的就會非常慢，所以就導致插入數(shù)據(jù)變得非常慢。

為了解決一次性擴容的耗時問題，我們把數(shù)據(jù)的遷移分批完成，每次插入操作遷移一部分數(shù)據(jù)。當達到閾值的時候我們只申請新的散列表，然后把新數(shù)據(jù)放到新的散列表中，當再有新數(shù)據(jù)插入的時候，我們將新數(shù)據(jù)插入到新的散列表，并把一部分數(shù)據(jù)從老的散列表遷移到新的散列表中。然后重復這樣的操作，直到所有數(shù)據(jù)遷移完成。這樣就解決了一次性遷移耗時過長的情況。

數(shù)據(jù)遷移期間，如果有查詢操作，我們首先在新的散列表中進行查找，如果沒有，再去老的散列表中查找。