我們?cè)谶@篇文章將要學(xué)習(xí)最有用的數(shù)據(jù)結(jié)構(gòu)之一—哈希表，哈希表的英文叫 Hash Table，也可以稱(chēng)為散列表或者Hash 表。

哈希表用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問(wèn)數(shù)據(jù)的特性，所以哈希表其實(shí)就是數(shù)組的一種擴(kuò)展，由數(shù)組演化而來(lái)。可以說(shuō)，如果沒(méi)有數(shù)組，就沒(méi)有散列表。

哈希表存儲(chǔ)的是由鍵（key）和值（value）組成的數(shù)據(jù)。例如，我們將每個(gè)人的性別作為數(shù)據(jù)進(jìn)行存儲(chǔ)，鍵為人名，值為對(duì)應(yīng)的性別，其中 M 表示性別為男，F(xiàn) 表示性別為女。

為什么需要哈希表？

為了和哈希表進(jìn)行對(duì)比，我們先將這些數(shù)據(jù)存儲(chǔ)在數(shù)組中。

此處準(zhǔn)備了6個(gè)箱子（即長(zhǎng)度為6的數(shù)組）來(lái)存儲(chǔ)數(shù)據(jù)，假設(shè)我們需要查詢(xún) Ally 的性別，由于不知道 Ally 的數(shù)據(jù)存儲(chǔ)在哪個(gè)箱子里，所以只能從頭開(kāi)始查詢(xún)，這個(gè)操作便叫作線性查找。一般來(lái)說(shuō)，我們可以把鍵當(dāng)成數(shù)據(jù)的標(biāo)識(shí)符，把值當(dāng)成數(shù)據(jù)的內(nèi)容。

從 0 號(hào)箱子開(kāi)始查找，發(fā)現(xiàn) 0 號(hào)箱子中存儲(chǔ)的鍵是 Joe 而不是 Ally，因此接著查找 1 號(hào)箱子。

哦豁，1 號(hào)箱子中的也不是 Ally，沒(méi)辦法，只能接著往下找。

有點(diǎn)小糟糕，2 號(hào)、3 號(hào)箱子中的也都不是 Ally。

功夫不負(fù)有心人，當(dāng)我們查找到 4 號(hào)箱子的時(shí)候，發(fā)現(xiàn)其中數(shù)據(jù)的鍵為 Ally，把鍵對(duì)應(yīng)的值取出，我們就知道 Ally 的性別為女（F）。

通過(guò)上面的查找過(guò)程，我們發(fā)現(xiàn)數(shù)據(jù)量越多，線性查找耗費(fèi)的時(shí)間就越長(zhǎng)。由此可知：由于數(shù)據(jù)的查詢(xún)較為耗時(shí)，所以此處并不適合使用數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)。

但使用哈希表便可以解決這個(gè)問(wèn)題，首先準(zhǔn)備好數(shù)組，這次我們用 5 個(gè)箱子的數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)。

嘗試把 Joe 存進(jìn)去，使用哈希函數(shù)（Hash）計(jì)算 Joe 的鍵，也就是字符串 Joe 的哈希值，比如得到的結(jié)果為4928。

將得到的哈希值除以數(shù)組的長(zhǎng)度 5，求得其余數(shù)，這樣的求余運(yùn)算叫作mod運(yùn)算，此處mod運(yùn)算的結(jié)果為3。

因此，我們將 Joe 的數(shù)據(jù)存進(jìn)數(shù)組的 3 號(hào)箱子中，重復(fù)前面的操作，將其他數(shù)據(jù)也存進(jìn)數(shù)組中。

Sue 鍵的哈希值為 7291, mod 5 的結(jié)果為 1，將 Sue 的數(shù)據(jù)存進(jìn) 1 號(hào)箱中。

Dan 鍵的哈希值為 1539, mod 5 的結(jié)果為 4，將 Dan 的數(shù)據(jù)存進(jìn) 4 號(hào)箱中。

Nell 鍵的哈希值為 6276, mod 5 的結(jié)果為 1，本應(yīng)將其存進(jìn)數(shù)組的 1 號(hào)箱中，但此時(shí) 1 號(hào)箱中已經(jīng)存儲(chǔ)了 Sue 的數(shù)據(jù)，這種存儲(chǔ)位置重復(fù)了的情況便叫作沖突。

遇到這種情況，可使用鏈表在已有數(shù)據(jù)的后面繼續(xù)存儲(chǔ)新的數(shù)據(jù)（鏈表法）。

Ally 鍵的哈希值為 9143, mod 5 的結(jié)果為 3，本應(yīng)將其存儲(chǔ)在數(shù)組的 3 號(hào)箱中，但 3 號(hào)箱中已經(jīng)有了 Joe 的數(shù)據(jù)，所以使用鏈表，在其后面存儲(chǔ) Ally 的數(shù)據(jù)。

Bob 鍵的哈希值為 5278, mod 5 的結(jié)果為 3，本應(yīng)將其存儲(chǔ)在數(shù)組的 3 號(hào)箱中，但 3 號(hào)箱中已經(jīng)有了 Joe 和 Ally 的數(shù)據(jù)，所以使用鏈表，在 Ally 的后面繼續(xù)存儲(chǔ) Bob 的數(shù)據(jù)。

像這樣存儲(chǔ)完所有數(shù)據(jù)，哈希表也就制作完成了。

接下來(lái)講解數(shù)據(jù)的查詢(xún)方法，假設(shè)我們要查詢(xún) Dan 的性別。

為了知道 Dan 存儲(chǔ)在哪個(gè)箱子里，首先需要算出 Dan 鍵的哈希值，然后對(duì)其進(jìn)行 mod 運(yùn)算，最后得到的結(jié)果為 4，于是我們知道了它存儲(chǔ)在 4 號(hào)箱中。

查看 4 號(hào)箱可知，其中的數(shù)據(jù)的鍵與 Dan 一致，于是取出對(duì)應(yīng)的值，由此我們便知道了 Dan 的性別為男（M）。

那么，想要查詢(xún) Ally 的性別時(shí)該怎么做呢？為了找到它的存儲(chǔ)位置，先要算出 Ally 鍵的哈希值，再對(duì)其進(jìn)行 mod 運(yùn)算，最終得到的結(jié)果為 3。

然而 3 號(hào)箱中數(shù)據(jù)的鍵是 Joe 而不是 Ally，此時(shí)便需要對(duì) Joe 所在的鏈表進(jìn)行線性查找。

于是我們找到了鍵為 Ally 的數(shù)據(jù)，取出其對(duì)應(yīng)的值，便知道了 Ally 的性別為女（F）。

哈希沖突

在哈希表中，我們可以利用哈希函數(shù)快速訪問(wèn)到數(shù)組中的目標(biāo)數(shù)據(jù)。如果發(fā)生哈希沖突，就使用鏈表進(jìn)行存儲(chǔ)，這樣一來(lái)，不管數(shù)據(jù)量為多少，我們都能夠靈活應(yīng)對(duì)。

如果數(shù)組的空間太小，使用哈希表的時(shí)候就容易發(fā)生沖突，線性查找的使用頻率也會(huì)更高；反過(guò)來(lái)，如果數(shù)組的空間太大，就會(huì)出現(xiàn)很多空箱子，造成內(nèi)存的浪費(fèi)。因此，給數(shù)組設(shè)定合適的空間非常重要。

在存儲(chǔ)數(shù)據(jù)的過(guò)程中，如果發(fā)生沖突，可以利用鏈表在已有數(shù)據(jù)的后面插入新數(shù)據(jù)來(lái)解決沖突，這種方法被稱(chēng)為鏈表法，也被稱(chēng)為鏈地址法。

其中在 Java 集合類(lèi)的 HashMap 中解決沖突的方法就是采用的鏈表法，建議閱讀 HashMap 源碼。

除了鏈地址法以外，還有幾種解決沖突的方法。其中，應(yīng)用較為廣泛的是開(kāi)放地址法，或稱(chēng)為開(kāi)放尋址法。這種方法是指當(dāng)沖突發(fā)生時(shí)，立刻計(jì)算出一個(gè)候補(bǔ)地址（數(shù)組上的位置）并將數(shù)據(jù)存進(jìn)去。如果仍然有沖突，便繼續(xù)計(jì)算下一個(gè)候補(bǔ)地址，直到有空地址為止，可以通過(guò)多次使用哈希函數(shù)或線性探測(cè)法等方法計(jì)算候補(bǔ)地址。

在 Java 中，ThreadLocal所使用的就是開(kāi)放地址法。

哈希函數(shù)設(shè)計(jì)的好壞決定了哈希沖突的概率，也就決定哈希表的性能。

總結(jié)

這篇文章主要講了一些比較基礎(chǔ)的哈希表知識(shí)，包括哈希表的由來(lái)、哈希沖突的解決方法。

哈希表也叫散列表，來(lái)源于數(shù)組，它借助哈希函數(shù)對(duì)數(shù)組這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行擴(kuò)展，利用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問(wèn)元素的特性，是存儲(chǔ) Key-Value 映射的集合。

哈希表兩個(gè)核心問(wèn)題是哈希函數(shù)設(shè)計(jì)和哈希沖突解決。對(duì)于某一個(gè) Key，哈希表可以在接近 O(1) 的時(shí)間內(nèi)進(jìn)行讀寫(xiě)操作。哈希表通過(guò)哈希函數(shù)實(shí)現(xiàn) Key 和數(shù)組下標(biāo)的轉(zhuǎn)換，通過(guò)開(kāi)放尋址法和鏈表法來(lái)解決哈希沖突。哈希函數(shù)設(shè)計(jì)的好壞決定了哈希沖突的概率，也就決定哈希表的性能。

有興趣的可以在 JDK 中閱讀 HashMap 的源碼，在 JDK 8 和之前的版本的實(shí)現(xiàn)還有許多不多，比如在 JDK 8 中，引入紅黑樹(shù)，當(dāng)鏈表長(zhǎng)度太長(zhǎng)（默認(rèn)超過(guò) 8）時(shí)，鏈表就轉(zhuǎn)換為紅黑樹(shù)，就可以利用紅黑樹(shù)快速增刪改查的特點(diǎn)，提高 HashMap 的性能。