面試阿里，HashMap 這一篇就夠了
微信搜尋【程式設計師囧輝】，關注這個堅持分享技術乾貨的程式設計師。
前言
某日，囧輝和同事二狗決定就誰是“&#￥*大廈11樓11室（只有囧輝和二狗兩人）HashMap 最強者”展開一番較量。畫面過於血腥，
成年人
請在未成年人陪同下觀看。
正文
二狗：天天聽你憨逼吹牛，是時候讓你知道什麼叫殘忍了。
囧輝：二狗子，這屎可以亂吃，這話不能亂說哦。
二狗：先來點簡單的，介紹下 HashMap 的底層資料結構吧。
囧輝：我們現在用的都是 JDK 1。8，底層是由“陣列+連結串列+紅黑樹”組成，如下圖，而在 JDK 1。8 之前是由“陣列+連結串列”組成。
二狗：為什麼要改成“陣列+連結串列+紅黑樹”？
囧輝：主要是為了提升在 hash 衝突嚴重時（連結串列過長）的查詢效能，使用連結串列的查詢效能是 O（n），而使用紅黑樹是 O（logn）。
二狗：那在什麼時候用連結串列？什麼時候用紅黑樹？
囧輝：對於插入，預設情況下是使用連結串列節點。當同一個索引位置的節點在新增後達到9個（閾值8）：如果此時陣列長度大於等於 64，則會觸發連結串列節點轉紅黑樹節點（treeifyBin）；而如果陣列長度小於64，則不會觸發連結串列轉紅黑樹，而是會進行擴容，因為此時的資料量還比較小。
對於移除，當同一個索引位置的節點在移除後達到 6 個，並且該索引位置的節點為紅黑樹節點，會觸發紅黑樹節點轉連結串列節點（untreeify）。
二狗：為什麼連結串列轉紅黑樹的閾值是8？
囧輝：我們平時在進行方案設計時，必須考慮的兩個很重要的因素是：時間和空間。對於 HashMap 也是同樣的道理，簡單來說，閾值為8是在時間和空間上權衡的結果（這 B 我裝定了）。
紅黑樹節點大小約為連結串列節點的2倍，在節點太少時，紅黑樹的查詢效能優勢並不明顯，付出2倍空間的代價作者覺得不值得。
理想情況下，使用隨機的雜湊碼，節點分佈在 hash 桶中的頻率遵循泊松分佈，按照泊松分佈的公式計算，連結串列中節點個數為8時的機率為 0。00000006（跟大樂透一等獎差不多，中大樂透？不存在的），這個機率足夠低了，並且到8個節點時，紅黑樹的效能優勢也會開始展現出來，因此8是一個較合理的數字。
二狗：（呦呦呦，時間和空間上權衡的結果，還裝起B來了）那為什麼轉回連結串列節點是用的6而不是複用8？
囧輝：如果我們設定節點多於8個轉紅黑樹，少於8個就馬上轉連結串列，當節點個數在8徘徊時，就會頻繁進行紅黑樹和連結串列的轉換，造成效能的損耗。
二狗：（小菜雞，懂得還不少）那 HashMap 有哪些重要屬性？分別用於做什麼的？
囧輝：除了用來儲存我們的節點 table 陣列外，HashMap 還有以下幾個重要屬性：1）size：HashMap 已經儲存的節點個數；2）threshold：擴容閾值，當 HashMap 的個數達到該值，觸發擴容。3）loadFactor：負載因子，擴容閾值 = 容量 * 負載因子。
二狗：threshold 除了用於存放擴容閾值還有其他作用嗎？
囧輝：在我們新建 HashMap 物件時， threshold 還會被用來存初始化時的容量。HashMap 直到我們第一次插入節點時，才會對 table 進行初始化，避免不必要的空間浪費。
二狗：HashMap 的預設初始容量是多少？HashMap 的容量有什麼限制嗎？
囧輝：預設初始容量是16。HashMap 的容量必須是2的N次方，HashMap 會根據我們傳入的容量計算一個大於等於該容量的最小的2的N次方，例如傳 9，容量為16。
二狗：（你他孃的是在繞口令吧）你這個*@%￥#&的N次方是怎麼算的？
囧輝：Talk is cheap。 Show you the code。
static
final
int
tableSizeFor
（
int
cap
）
{
int
n
=
cap
-
1
；
n
|=
n
>>>
1
；
n
|=
n
>>>
2
；
n
|=
n
>>>
4
；
n
|=
n
>>>
8
；
n
|=
n
>>>
16
；
return
（
n
<
0
）
？
1
：
（
n
>=
MAXIMUM_CAPACITY
）
？
MAXIMUM_CAPACITY
：
n
+
1
；
}
二狗：臥槽，還彪英文，來來來，這程式碼你給我解釋下。
囧輝：我們先不看第一行“int n = cap - 1”，先看下面的5行計算。
|=（或等於）：這個符號比較少見，但是“+=”應該都見過，看到這你應該明白了。例如：a |= b ，可以轉成：a = a | b。
>>>（無符號右移）：例如 a >>> b 指的是將 a 向右移動 b 指定的位數，右移後左邊空出的位用零來填充，移出右邊的位被丟棄。
假設 n 的值為 0010 0001，則該計算如下圖：
相信你應該看出來，這5個公式會透過最高位的1，拿到2個1、4個1、8個1、16個1、32個1。當然，有多少個1，取決於我們的入參有多大，但我們肯定的是經過這5個計算，得到的值是一個低位全是1的值，最後返回的時候 +1，則會得到1個比n 大的 2 的N次方。
這時再看開頭的 cap - 1 就很簡單了，這是為了處理 cap 本身就是 2 的N次方的情況。
計算機底層是二進位制的，移位和或運算是非常快的，所以這個方法的效率很高。
PS：這是 HashMap 中我個人最喜歡的設計，非常巧妙，真想給作者一個麼麼噠（不小心暴露了）。
二狗：（這叼毛講的還湊合啊，連我都聽懂了）你說 HashMap 的容量必須是 2 的 N 次方，這是為什麼？
囧輝：計算索引位置的公式為：（n - 1） & hash，當 n 為 2 的 N 次方時，n - 1 為低位全是 1 的值，此時任何值跟 n - 1 進行 & 運算會等於其本身，達到了和取模同樣的效果，實現了均勻分佈。實際上，這個設計就是基於公式：x mod 2^n = x & （2^n - 1），因為 & 運算比 mod 具有更高的效率。
如下圖，當 n 不為 2 的 N 次方時，hash 衝突的機率明顯增大。
二狗：你說 HashMap 的預設初始容量是 16，為什麼是16而不是其他的？
囧輝：（這是什麼煞筆問題）我認為是16的原因主要是：16是2的N次方，並且是一個較合理的大小。如果用8或32，我覺得也是OK的。實際上，我們在新建 HashMap 時，最好是根據自己使用情況設定初始容量，這才是最合理的方案。
二狗：剛才說的負載因子預設初始值又是多少？
囧輝：負載因子預設值是0。75。
二狗：為什麼是0。75而不是其他的？
囧輝：（又問這種憨逼問題）這個也是在時間和空間上權衡的結果。如果值較高，例如1，此時會減少空間開銷，但是 hash 衝突的機率會增大，增加查詢成本；而如果值較低，例如 0。5 ，此時 hash 衝突會降低，但是有一半的空間會被浪費，所以折衷考慮 0。75 似乎是一個合理的值。
二狗：為什麼不是 0。74 或 0。76？
囧輝：
二狗：那我們換個問題問吧，HashMap 的插入流程是怎麼樣的？
囧輝：Talk is cheap。 Show you the picture。
二狗：圖裡剛開始有個計算 key 的 hash 值，是怎麼設計的？
囧輝：拿到 key 的 hashCode，並將 hashCode 的高16位和 hashCode 進行異或（XOR）運算，得到最終的 hash 值。
static
final
int
hash
（
Object
key
）
{
int
h
；
return
（
key
==
null
）
？
0
：
（
h
=
key
。
hashCode
（））
^
（
h
>>>
16
）；
}
二狗：為什麼要將 hashCode 的高16位參與運算？
囧輝：主要是為了在 table 的長度較小的時候，讓高位也參與運算，並且不會有太大的開銷。
例如下圖，如果不加入高位運算，由於 n - 1 是 0000 0111，所以結果只取決於 hash 值的低3位，無論高位怎麼變化，結果都是一樣的。
如果我們將高位參與運算，則索引計算結果就不會僅取決於低位。
二狗：擴容（resize）流程介紹下？
囧輝：
二狗：紅黑樹和連結串列都是透過 e。hash & oldCap == 0 來定位在新表的索引位置，這是為什麼？
囧輝：請看對下面的例子。
擴容前 table 的容量為16，a 節點和 b 節點在擴容前處於同一索引位置。
擴容後，table 長度為32，新表的 n - 1 只比老表的 n - 1 在高位多了一個1（圖中標紅）。
因為 2 個節點在老表是同一個索引位置，因此計算新表的索引位置時，只取決於新表在高位多出來的這一位（圖中標紅），而這一位的值剛好等於 oldCap。
因為只取決於這一位，所以只會存在兩種情況：1） （e。hash & oldCap） == 0 ，則新表索引位置為“原索引位置” ；2）（e。hash & oldCap） == 1，則新表索引位置為“原索引 + oldCap 位置”。
二狗：HashMap 是執行緒安全的嗎？
囧輝：不是。HashMap 在併發下存在資料覆蓋、遍歷的同時進行修改會丟擲 ConcurrentModificationException 異常等問題，JDK 1。8 之前還存在死迴圈問題。
二狗：介紹一下死迴圈問題？
囧輝：導致死迴圈的根本原因是 JDK 1。7 擴容採用的是“頭插法”，會導致同一索引位置的節點在擴容後順序反掉。而 JDK 1。8 之後採用的是“尾插法”，擴容後節點順序不會反掉，不存在死迴圈問題。
JDK 1。7。0 的擴容程式碼如下，用例子來看會好理解點。
void
transfer
（
Entry
［］
newTable
）
{
Entry
［］
src
=
table
；
int
newCapacity
=
newTable
。
length
；
for
（
int
j
=
0
；
j
<
src
。
length
；
j
++）
{
Entry
<
K
，
V
>
e
=
src
［
j
］；
if
（
e
！=
null
）
{
src
［
j
］
=
null
；
do
{
Entry
<
K
，
V
>
next
=
e
。
next
；
int
i
=
indexFor
（
e
。
hash
，
newCapacity
）；
e
。
next
=
newTable
［
i
］；
newTable
［
i
］
=
e
；
e
=
next
；
}
while
（
e
！=
null
）；
}
}
}
PS：這個流程較難理解，建議對著程式碼自己模擬走一遍。
例子：我們有1個容量為2的 HashMap，loadFactor=0。75，此時執行緒1和執行緒2 同時往該 HashMap 插入一個數據，都觸發了擴容流程，接著有以下流程。
1）在2個執行緒都插入節點，觸發擴容流程之前，此時的結構如下圖。
2）執行緒1進行擴容，執行到程式碼：Entry
3）執行緒1被掛起後，執行緒2進入擴容流程，並走完整個擴容流程，此時的結構如下圖。
由於兩個執行緒操作的是同一個 table，所以該圖又可以畫成如下圖。
4）執行緒1恢復後，繼續走完第一次的迴圈流程，此時的結構如下圖。
5）執行緒1繼續走完第二次迴圈，此時的結構如下圖。
6）執行緒1繼續執行第三次迴圈，執行到 e。next = newTable［i］ 時形成環，執行完第三次迴圈的結構如下圖。
如果此時執行緒1呼叫 map。get（11） ，悲劇就出現了——Infinite Loop。
二狗：（尼瑪，沒聽懂，尷尬了）那總結下 JDK 1。8 主要進行了哪些最佳化？
囧輝：JDK 1。8 的主要最佳化剛才我們都聊過了，主要有以下幾點：
1）底層資料結構從“陣列+連結串列”改成“陣列+連結串列+紅黑樹”，主要是優化了 hash 衝突較嚴重時，連結串列過長的查詢效能：O（n） -> O（logn）。
2）計算 table 初始容量的方式發生了改變，老的方式是從1開始不斷向左進行移位運算，直到找到大於等於入參容量的值；新的方式則是透過“5個移位+或等於運算”來計算。
// JDK 1。7。0
public
HashMap
（
int
initialCapacity
，
float
loadFactor
）
{
// 省略
// Find a power of 2 >= initialCapacity
int
capacity
=
1
；
while
（
capacity
<
initialCapacity
）
capacity
<<=
1
；
// 。。。 省略
}
// JDK 1。8。0_191
static
final
int
tableSizeFor
（
int
cap
）
{
int
n
=
cap
-
1
；
n
|=
n
>>>
1
；
n
|=
n
>>>
2
；
n
|=
n
>>>
4
；
n
|=
n
>>>
8
；
n
|=
n
>>>
16
；
return
（
n
<
0
）
？
1
：
（
n
>=
MAXIMUM_CAPACITY
）
？
MAXIMUM_CAPACITY
：
n
+
1
；
}
3）優化了 hash 值的計算方式，老的透過一頓瞎JB操作，新的只是簡單的讓高16位參與了運算。
// JDK 1。7。0
static
int
hash
（
int
h
）
{
h
^=
（
h
>>>
20
）
^
（
h
>>>
12
）；
return
h
^
（
h
>>>
7
）
^
（
h
>>>
4
）；
}
// JDK 1。8。0_191
static
final
int
hash
（
Object
key
）
{
int
h
；
return
（
key
==
null
）
？
0
：
（
h
=
key
。
hashCode
（））
^
（
h
>>>
16
）；
}
4）擴容時插入方式從“頭插法”改成“尾插法”，避免了併發下的死迴圈。
5）擴容時計算節點在新表的索引位置方式從“h & （length-1）”改成“hash & oldCap”，效能可能提升不大，但設計更巧妙、更優雅。
二狗：除了 HashMap，還用過哪些 Map，在使用時怎麼選擇？
囧輝：
二狗：（不妙，這個 B HashMap 懂得比我還多，得趕緊溜）到時間和女朋友吃飯了，我們之後再分勝負。
囧輝：
推薦閱讀
![[LeetCode 141] 環形連結串列](https://img.heatask.com/upload/thumbnail/znrURfeVI4QgTgJ6iwPZzhTOjf2njMIkaFRW_PCvuf6BSDHn4vbvPIrUvAvB24vLa17rfEUuvLfov6+KibPPyPYZu.jpeg)