[[358225]]

本文轉(zhuǎn)載自微信公眾號(hào)「石杉的架構(gòu)筆記」，作者雨后晴天 。轉(zhuǎn)載本文請(qǐng)聯(lián)系石杉的架構(gòu)筆記公眾號(hào)。  

1、前言

HashMap 是 java工程師最常用的數(shù)據(jù)結(jié)構(gòu)之一，但是能對(duì)其原理掌握的比較深的同學(xué)很少。尤其是本文的主題，據(jù)一些常年負(fù)責(zé)招 聘的朋友介紹。

HashMap 的死循環(huán)是面試中的常見問題，但是能講清楚的面試者很少，即使這些應(yīng)聘者工作時(shí)間都比較長(zhǎng)。

原因是，目前講解這個(gè)問題的文章雖多，但好文章卻不多。

也有些文章講解的很完善，但內(nèi)容太過燒腦，所以看下來基本上都云里霧 里。鑒于目前的情況，本文基于我個(gè)人對(duì)源碼熟練掌握的基礎(chǔ)上，跳出源碼，因?yàn)槟翘珶X，提煉出核心環(huán)節(jié)。盡量一步一圖，以大白話 形式將底層原理呈現(xiàn)出來。本文的理論基礎(chǔ)是基于 jdk1.8 以下版本。死循環(huán)問題也主要存在 于 jdk1.8 以下的版本中。

2、HashMap 的數(shù)據(jù)結(jié)構(gòu)

jdk1.7 版本的HashMap，底層結(jié)構(gòu)是一個(gè)數(shù)組，數(shù)組中的每項(xiàng)都可以是個(gè)鏈表，開始時(shí)我們用數(shù)組保存元素，當(dāng)添加元素遇到?jīng)_突，即相同位置處有多個(gè)元素時(shí)，就將這些元素添加到對(duì)應(yīng)的鏈表 中，所以 HashMap 的底層結(jié)構(gòu)可以認(rèn)為是由數(shù)組和鏈表構(gòu)成。

如果，你在構(gòu)建一個(gè) HashMap 時(shí)不指定數(shù)組大小，那么默認(rèn)情況下，數(shù)組大小為 16，但限于篇幅。

下面我們只畫了一個(gè)大小為 8 的 數(shù)組數(shù)組，在索引為 2 處有個(gè)鏈表，存放著 3 個(gè)元素，分別為 Entry1、Entry2、Entry3。這三個(gè)元素的 hash 運(yùn)算結(jié)果是一樣的而 且都為 2，所以在數(shù)組的 index=2 構(gòu)成了一條鏈表。

3、插入數(shù)據(jù)

在往 HashMap 中添加元素時(shí)，比如需要在上面的HashMap 中 添加一個(gè)節(jié)點(diǎn) Entry4(k4,v4)。

首先會(huì)根據(jù)它的 key 值 k4 計(jì)算 hashcode 值，然后再對(duì)這個(gè) hashcode 值做些復(fù)雜運(yùn)算，得到在數(shù)組中的目標(biāo) index，比如為 4， 這時(shí)因?yàn)閿?shù)組索引為 4 的位置為空，可直接將該元素插入到其底層數(shù) 組中。

因?yàn)椴煌?key 完全可能有相同的 hashcode 值，當(dāng)然也完全可能在數(shù)組中有相同的目標(biāo) index。比如，要新添加一個(gè)元素 Entry5(k5,v5)，對(duì) k5 進(jìn)行運(yùn)算得到的目標(biāo) index 為4。

但是因?yàn)閿?shù)組中對(duì)應(yīng)位置已有一個(gè)元素 Entry4， 我們清楚一個(gè)數(shù)組的同一個(gè)索引處不可能連續(xù)存儲(chǔ)兩個(gè)元素而不被覆 蓋，所以這時(shí)會(huì)怎么處理呢?

這時(shí)鏈表就派上用場(chǎng)了，將這兩個(gè)元素在 index 為 4 處構(gòu)成一個(gè) 鏈表即可以完美的解決沖突問題。

但是要注意，jdk1.7 采用的是頭插 法。就是將新節(jié)點(diǎn) Entry5 放在數(shù)組中作為鏈表的頭節(jié)點(diǎn)，將原來的 Entry4 移出作為其 next 節(jié)點(diǎn)。如下圖所示：

為何要一直強(qiáng)調(diào)是 jdk1.7 版本，因?yàn)樵?jdk1.8 的時(shí)候 HashMap 結(jié)構(gòu)發(fā)生了較大的變化，1.8 版本的 HashMap 采用的是尾插法而且底 層結(jié)構(gòu)也發(fā)生了變化。

4、擴(kuò)容

java 工程師都清楚 jdk1.7 版本的 HashMap初始默認(rèn)長(zhǎng)度為 16，你也可以自己定義，但不管你是自定義還是選擇默認(rèn)長(zhǎng)度，

隨著 元素的增加并達(dá)到了一定的閾值，總是要擴(kuò)容的。擴(kuò)容時(shí)是按 2 倍來進(jìn)行的，就是創(chuàng)建一個(gè) 2 倍大小的數(shù)組，將原 來的元素重新 Hash，計(jì)算新的 index 放入到新的數(shù)組+鏈表結(jié)構(gòu)中。

5、高并發(fā)下的擴(kuò)容問題

HashMap 的這一結(jié)構(gòu)和擴(kuò)容機(jī)制可以保證，在大數(shù)據(jù)量情況 下，讀寫性能依然能保持優(yōu)良。

插入時(shí)采用頭插法會(huì)非常快速，讀取 時(shí)，也不會(huì)因?yàn)殒湵磉^長(zhǎng)而影響讀取性能?？吹竭@，會(huì)不會(huì)覺得 Hash 是個(gè)完美的設(shè)計(jì)，其實(shí)不是，因?yàn)?HashMap 并不是線程安全的數(shù)據(jù)結(jié)構(gòu)。

尤其是在擴(kuò)容時(shí)，如果并發(fā)量不大通常不會(huì)有什么問題，但在高 并發(fā)情況下，擴(kuò)容可能導(dǎo)致很嚴(yán)重的問題。我們下面來模擬一個(gè)高并發(fā)情況下擴(kuò)容的例子。

1)假設(shè)有一個(gè) HashMap，它的負(fù)載因子為 1，有兩個(gè)元素(7，x)和 (11，y)，它們 hash 運(yùn)算的結(jié)果都為 1，所以都在 1 號(hào)鏈表(即 index 為 1 所指向的鏈表中，為便于描述，下面都簡(jiǎn)稱)中，如下所 示。

2)這時(shí)你需要往里面添加一個(gè)節(jié)點(diǎn)(15，z)，這時(shí)有 3 個(gè)節(jié)點(diǎn)，因?yàn)?已達(dá)到擴(kuò)容閾值，需要擴(kuò)容。

3)首先是線程 2 過來，按照擴(kuò)容的底層源碼，需要將 e 指針指向鏈表 的頭節(jié)點(diǎn)(7，x)，next 指針指向下一個(gè)節(jié)點(diǎn)(11，y)，如下圖所 示：

其中 e 表示當(dāng)前線程正要遷移的節(jié)點(diǎn)，next 表示下一個(gè)需要遷移 的節(jié)點(diǎn)。如果 e 指向的節(jié)點(diǎn)遷移完成，則進(jìn)入下一次循環(huán)，e 指針重新指 向節(jié)點(diǎn)(11，y)，next 指針重新指向節(jié)點(diǎn)(15，z)。

4)但是當(dāng)線程 2 剛開始標(biāo)記好 e 和 next 兩個(gè)指針，正準(zhǔn)備遷移第一 個(gè)節(jié)點(diǎn)時(shí)。線程 1 過來了，并完成了遷移。

5)前面我們說過，HashMap 進(jìn)入鏈表是采用頭插法，所以對(duì)三個(gè)元 素 rehash 遷移后的鏈表順序?yàn)?15，z) —> (11，y) —> (7，x) 圖中的 e 和 next 指針屬于線程

2，它們還停留在原來的節(jié)點(diǎn)上， 這一階段的結(jié)構(gòu)如下圖所示：

這時(shí)線程 2 中的 table 有(7，x)這個(gè)節(jié)點(diǎn)。

6)然后將 next 指向的節(jié)點(diǎn)(11, y)添加到線程 2 表示的 HashMap 中，因?yàn)椴捎妙^插法，所以(11, y)成了鏈表的頭節(jié)點(diǎn)，原來的(7， x)則成了它的下一個(gè)節(jié)點(diǎn)

這時(shí)線程 2 中的 table 有(11，y)---->(7，x)這些節(jié)點(diǎn)，鏈 表的頭節(jié)點(diǎn)為(11，y)。

7)繼續(xù)循環(huán)遷移元素，將 e 指向(7，x)，則 next 為 null。然后將 線程 2 的數(shù)組下標(biāo)索引 3 指向 e 指向的節(jié)點(diǎn)，即將(7，x)又添加到 頭節(jié)點(diǎn)(頭插法)，這時(shí)線程 2 中的 table 有(7，x)—>(11，y) ---->(7，x)，構(gòu)成了環(huán)，如圖所示：

6、問題很嚴(yán)重

如果上述的遷移過程最后以線程 2 的 table 作為新的 hashmap， 則最后的遷移結(jié)果如下圖所示：

7、環(huán)形鏈表會(huì)帶來什么后果呢?

假設(shè)我現(xiàn)在要查詢上述 HashMap 是否包含節(jié)點(diǎn)(7，x)，首先根 據(jù) hash 運(yùn)算得到目標(biāo) index 為 3，所以查找目標(biāo)轉(zhuǎn)到了 3 號(hào)鏈表，

然后根據(jù) key 值為 11 判斷與鏈表的頭節(jié)點(diǎn)(7，x)的 key 恰好相等，再 判斷它們的 value 也相等。說明該 HashMap 中包含了我們所要查詢 的幾點(diǎn)，返回 true。

假設(shè)我現(xiàn)在要查詢節(jié)點(diǎn)(11，y),經(jīng)過 hash 運(yùn)算也將查找目標(biāo)轉(zhuǎn) 到了 3 號(hào)鏈表，然后根據(jù) key 值為 11 判斷與頭節(jié)點(diǎn)(7，x)的 key 不 相等，則轉(zhuǎn)向下一個(gè)節(jié)點(diǎn)。

通過對(duì)比，發(fā)現(xiàn)與下一個(gè)節(jié)點(diǎn)的 key 和 value 都相等，則直接返回 true。

這樣看來似乎沒什么問題，然后我們?cè)俨橐粋€(gè)節(jié)點(diǎn)(15，m)，經(jīng) 過 hash 運(yùn)算也將查找目標(biāo)轉(zhuǎn)到了 3 號(hào)鏈表，首先與頭節(jié)點(diǎn)(7，x)判斷 不相等，然后與下一個(gè)節(jié)點(diǎn)(11，y)對(duì)比也不相等。再與下一個(gè)節(jié)點(diǎn) 判斷，這時(shí)鏈表中節(jié)點(diǎn)為(7，x)其實(shí)就是重新回到了頭節(jié)點(diǎn)，

它的下一 個(gè)節(jié)點(diǎn)又是(11，y)，這種搜索會(huì)一直無限循環(huán)下去，CPU 很快飆 升到 100%，后果很嚴(yán)重。其實(shí)不管你搜索什么節(jié)點(diǎn)，只要路由到 3 號(hào)鏈表，并且待搜索的 key 不是 7 或 11，都將發(fā)生死循環(huán)。