HashMap終於被這篇文章講明白了！
2022-01-14由 紙鶴視界 發表于 漁業
什麼叫異或
HashMap
雜湊表
雜湊函式
衝突解決
位運算子
HashMap簡介
繼承關係
成員變數
DEFAULT_INITIAL_CAPACITY（預設集合初始容量）
DEFAULT_LOAD_FACTOR
TREEIFY_THRESHOLD
table
threshold
新增元素
流程
原始碼
treeifyBin方法
擴容機制
流程
原始碼
併發問題
預設JDK8，如果有錯誤，麻煩在評論區告訴我一下
雜湊表
雜湊表（Hash table，也叫散列表），能夠根據鍵（key）直接訪問相應的值（value）。查詢演算法分為兩步：
用雜湊函式將被查詢的key轉化為陣列的一個索引。理想情況下，不同的key都會轉化為不同的索引值，但現實情況也會存在不同的key有相同的索引值。這就叫
碰撞衝突
，可以透過拉鍊法或線性探測法解決衝突（後面會講）。
透過生成的索引值直接訪問資料。
雜湊表是演算法在
時間和空間上做出權衡
的經典案例。如果沒有記憶體限制，那麼我們可以直接將key作為陣列的索引，那麼所有的查詢操作只需要訪問記憶體一次；如果沒有時間限制，我們可以用無序陣列並進行順序查詢，這樣只需要很少的記憶體，但花費的時間太長了。而雜湊表則使用了適度的空間和時間並在這兩種極端中找到一個平衡。
雜湊函式
假設有一個能夠儲存M個鍵值對的陣列，那麼我們就需要一個能夠將任意key轉化為該陣列範圍內的索引（［0，M-1］範圍內的整數）的雜湊函式。這個雜湊函式最好還要滿足下面的要求：
容易計算並且速度快
。
計算出來的索引值
最好能夠均勻分佈所有的鍵
，避免產生太多的衝突。
由於key的型別可能是數字，字串，所以我們需要設計不同的雜湊函式來對應不同的鍵。Java中為許多常用的資料型別重寫了hashCode（）方法，在文章Object中的hashCode（）終於搞懂了！！！有詳細的介紹。
衝突解決
當出現兩個或多個key的雜湊值相同的情況，可以透過拉鍊法或線性探測法來解決，這篇文章著重講解一下拉鍊法，因為HashMap的底層實現就是基於拉鍊法。
大致思路如下：將大小為M的陣列中的每個元素指向一個連結串列，連結串列中的每個結點都儲存了雜湊值為該元素的索引的鍵值對。當要查詢某個元素時，首先根據雜湊值找到對應的連結串列，然後沿著連結串列順序查詢相應的key，並返回value。
位運算子
在介紹HashMap之前補充一些位運算子的知識
<<
：左移，空位補0，被移除的高位丟棄，空缺位補0。
>>
： 右移，被移位的二進位制最高位是0，右移後，空缺位補0；最高位是1，空缺位補1。
>>>
： 無符號右移，被移位二進位制最高位無論是0或者是1，空缺位都用0補。
&
： 與運算，二進位制位進行&運算，只有
1&1
時結果是1，否則是0；
|
：或運算，二進位制位進行 | 運算，只有
0 | 0
時結果是0，否則是1；
^
：異或運算，相同二進位制位進行 ^ 運算，結果是0；
1^1=0
，
0^0=0
；不相同二進位制位 ^ 運算結果是1。
1^0=1
，
0^1=1
~
：取反運算，正數取反，各二進位制碼按補碼各位取反負數取反，各二進位制碼按補碼各位取反
HashMap簡介
HashMap基於雜湊表的Map介面實現，是以key-value儲存形式存在，即主要用來存放鍵值對。HashMap 的實現不是同步的，這意味著它
不是執行緒安全的
。它的key、value都可以為null。此外，HashMap中的對映不是有序的。
JDK1。8 之前 HashMap 由 陣列+連結串列 組成的，陣列是 HashMap 的主體，連結串列則是主要為了解決雜湊衝突
(兩個物件呼叫的hashCode方法計算的雜湊碼值一致導致計算的陣列索引值相同)
而存在的（“拉鍊法”解決衝突）。
JDK1。8 以後在解決雜湊衝突時有了較大的變化，
當連結串列長度大於閾值（或者紅黑樹的邊界值，預設為 8）並且當前陣列的長度大於64時，此時此索引位置上的所有資料改為使用紅黑樹儲存。
補充：將連結串列轉換成紅黑樹前會判斷，即使閾值大於8，但是陣列長度小於64，此時並不會將連結串列變為紅黑樹。而是選擇進行陣列擴容。
這樣做的目的是因為陣列比較小，儘量避開紅黑樹結構，這種情況下變為紅黑樹結構，反而會降低效率，因為紅黑樹需要進行左旋，右旋，變色這些操作來保持平衡 。同時陣列長度小於64時，搜尋時間相對要快些。所以綜上所述為了提高效能和減少搜尋時間，底層在閾值大於8並且陣列長度大於64時，連結串列才轉換為紅黑樹。具體可以參考
treeifyBin
方法。
雖然增了紅黑樹作為底層資料結構，結構變得複雜了，但是閾值大於8並且陣列長度大於64時，連結串列轉換為紅黑樹時，效率也變的更高效。
繼承關係
HashMap類實現了一個Map介面，該介面定義了一組鍵值對對映通用的操作，同時還繼承了AbstractMap抽象類，該抽象類繼承Map介面。但是HashMap類透過繼承AbstractMap抽象類也實現了Map介面，是不是多此一舉呀？
據 Java集合框架的創始人Josh Bloch描述，這樣的寫法是一個失誤。在java集合框架中，類似這樣的寫法很多，最開始寫java集合框架的時候，他認為這樣寫，在某些地方可能是有價值的，直到他意識到錯了。顯然的，JDK的維護者，後來不認為這個小小的失誤值得去修改，所以就這樣存在下來了。 StackOverFlow問題連結
HashMap還實現了Cloneable介面和Serializable介面，分別用來進行物件克隆和物件序列化。
成員變數
下面介紹幾個重要的變數
DEFAULT_INITIAL_CAPACITY（預設集合初始容量）
//預設初始容量是16（必須是2的n次冪）
static
final
int
DEFAULT_INITIAL_CAPACITY
=
1
<<
4
；
// aka 16
可以發現初始容量必須是2的n次冪，具體原因下面分析一下：根據雜湊表的原理，我們可以知道當向HashMap中新增一個元素時，需要根據key的雜湊值去確定其在陣列中的具體位置。HashMap為了存取高效，要儘量減少衝突碰撞，也就是要儘量把資料分配均勻，每個連結串列長度大致相同。
key的雜湊值可能是一個很大的整數，超過散列表的範圍，因此需要把它縮小到適合索引的範圍。假設假設雜湊表的索引處於0到n-1之間，將一個整數縮小到0和n-1之間的最常用的做法是使用
hash%n
，其中n為大於2的素數。比如Hashtable初始化桶大小為11，就是桶大小設計為素數的應用（Hashtable擴容後不能保證還是素數）。理想情況下應該為n選擇一個素數，但是選擇一個大的素數將很耗時。而在HashMap中使用的方法很巧妙，它透過
hash&（length-1）
來計算，當length長度為2的n次冪時，
hash&（length-1）
的運算結果總是等價於
hash%length
，&的運算效率也比%更高。
在建立HashMap物件的時候，可以傳入
initialCapacity
，如果輸入的大小不是2的n次冪，那麼底層會透過位移運算和或運算得到一個離你傳入的數字最近的一個2的冪次數。
原始碼如下：
//建立HashMap集合的物件，指定陣列長度是10，不是2的冪
HashMap
hashMap
=
new
HashMap
（
10
）
；
——
——
——
——
——
——
——
——
——
——
——
——
——
——
——
——
——
——
——
——
——
——
——
-
/* 指定“容量大小”和“載入因子”的建構函式 initialCapacity： 指定的容量 loadFactor：指定的載入因子 */
public
HashMap
（
int
initialCapacity
，
float
loadFactor
）
{
//判斷初始化容量initialCapacity是否小於0
if
（
initialCapacity
<
0
）
//如果小於0，則丟擲非法的引數異常IllegalArgumentException
throw
new
IllegalArgumentException
（
“Illegal initial capacity： ”
+
initialCapacity
）
；
//判斷初始化容量initialCapacity是否大於集合的最大容量MAXIMUM_CAPACITY-》2的30次冪
if
（
initialCapacity
>
MAXIMUM_CAPACITY
）
//如果超過MAXIMUM_CAPACITY，會將MAXIMUM_CAPACITY賦值給initialCapacity
initialCapacity
=
MAXIMUM_CAPACITY
；
//判斷負載因子loadFactor是否小於等於0或者是否是一個非數值
if
（
loadFactor
<=
0
||
Float
。
isNaN
（
loadFactor
）
）
//如果滿足上述其中之一，則丟擲非法的引數異常IllegalArgumentException
throw
new
IllegalArgumentException
（
“Illegal load factor： ”
+
loadFactor
）
；
//將指定的載入因子賦值給HashMap成員變數的負載因子loadFactor
this
。
loadFactor
=
loadFactor
；
/** * tableSizeFor（initialCapacity） 判斷指定的初始化容量是否是2的n次冪，如果不是那麼會 * 變為比指定初始化容量大的最小的2的n次冪。但是注意，在tableSizeFor方法體內部將計算後的資料返回給呼叫這裡了， * 並且直接賦值給threshold邊界值了。有些人會覺得這裡是一個bug，應該這樣書寫： * this。threshold = tableSizeFor（initialCapacity） * this。loadFactor； * 這樣才符合threshold的意思（當HashMap的size到達threshold這個閾值時會擴容）。 * 但是，請注意，在jdk8以後的構造方法中，並沒有對table這個成員變數進行初始化， * table的初始化被推遲到了put方法中，在put方法中會對threshold重新計算，put方法的具體實現我們下面會進行講解 */
this
。
threshold
=
tableSizeFor
（
initialCapacity
）
；
}
最後呼叫了tableSizeFor，來看一下方法實現：
/** * Returns a power of two size for the given target capacity。 返回比指定初始化容量大的最小的2的n次冪 */
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
；
}
tableSizeFor（int cap） 是解決
initialCapacity
不是2的n次冪的核心方法。過程如下圖：
這裡說兩個問題：
首先，為什麼要對cap做減1操作，
int n = cap - 1
？這是為了防止，cap已經是2的冪。如果cap已經是2的冪， 又沒有執行這個減1操作，則執行完後面的幾條無符號右移操作之後，返回的capacity將是這個cap的2倍。比如傳入16，如果不減1，最後結果會是32，讀者可以進行測試。
容量最大也就是32bit的正數，因此最後
n |= n >>> 16
，最多也就32個1，但是這已經是負數了。在執行tableSizeFor之前，其實會對initialCapacity做了判斷，如果大於MAXIMUM_CAPACITY（2 ^ 30），則取MAXIMUM_CAPACITY。如果等於MAXIMUM_CAPACITY（2 ^ 30），會執行移位操作。所以這裡面的移位操作之後，最大30個1，不會大於等於MAXIMUM_CAPACITY。30個1，加1之後得2 ^ 30 。
DEFAULT_LOAD_FACTOR
static
final
float
DEFAULT_LOAD_FACTOR
=
0。75f
；
預設的裝載因子，用於衡量HashMap滿的程度，計算HashMap的實時裝載因子
loadFactor
的方法是size/capacity。size是當前HashMap中存放鍵值對的數量，capacity是桶的數量。預設值為0。75，
loadFactor太大導致查詢元素效率低，太小導致陣列的利用率低，存放的資料會很分散
。這是對空間和時間效率的一個平衡選擇，建議不要修改。
當HashMap裡面容納的元素已經達到HashMap陣列長度的75%時，表示HashMap太擠了，需要擴容，而擴容這個過程涉及到 rehash、複製資料等操作，非常消耗效能。，所以開發中儘量減少擴容的次數，可以透過建立HashMap集合物件時指定初始容量來儘量避免。
TREEIFY_THRESHOLD
//當桶（bucket）上的結點數大於這個值時會轉成紅黑樹
static
final
int
TREEIFY_THRESHOLD
=
8
；
TreeNodes佔用空間是普通Nodes的兩倍，所以只有當bin包含足夠多的節點時才會轉成TreeNodes，而是否足夠多就是由TREEIFY_THRESHOLD的值決定的。當bin中節點數變少時，又會轉成普通的bin。並且我們檢視原始碼的時候發現，陣列長度大於64且連結串列長度達到8就轉成紅黑樹，當長度降到6就轉成普通bin。
//當桶（bucket）上的結點數小於這個值時樹轉連結串列
static
final
int
UNTREEIFY_THRESHOLD
=
6
；
//當集合中的容量大於這個值時，表中的桶才會進行樹形化，否則桶內元素太多時會擴容。
static
final
int
MIN_TREEIFY_CAPACITY
=
64
；
這樣就解釋了為什麼不是一開始就將其轉換為TreeNodes，而是需要一定節點數才轉為TreeNodes，其實就是空間和時間的權衡。
這段內容還說到：當hashCode離散性很好的時候，樹型bin用到的機率非常小，因為資料均勻分佈在每個bin中，幾乎不會有bin中連結串列長度會達到閾值。但是
在隨機hashCode下，離散性可能會變差，然而JDK又不能阻止使用者實現這種不好的hash演算法，因此就可能導致不均勻的資料分佈。
不過理想情況下隨機hashCode演算法下所有bin中節點的分佈頻率會遵循泊松分佈，我們可以看到，一個bin中連結串列長度達到8個元素的機率為0。00000006，幾乎是不可能事件。所以，之所以選擇8，不是隨便決定的，而是根據
機率統計
決定的。由此可見，發展將近30年的Java每一項改動和最佳化都是非常嚴謹和科學的。
也就是說：選擇8因為符合泊松分佈，超過8的時候，機率已經非常小了，所以我們選擇8這個數字。
table
//儲存元素的陣列
transient
Node
<
K
，
V
>
［
］
table
；
在JDK8中我們瞭解到HashMap是由陣列加連結串列加紅黑樹來組成的結構，其中table就是HashMap中的陣列，JDK8之前陣列型別是Entry
threshold
// 臨界值 當實際大小（容量*負載因子）超過臨界值時，會進行擴容
int
threshold
；
計算公式：
capacity（陣列長度預設16） * loadFactor（負載因子預設0。75）
。這個值是當前已佔用陣列長度的最大值。
當size>=threshold
的時候，那麼就要考慮對陣列的resize（擴容），也就是說，這個的意思就是
衡量陣列是否需要擴增的一個標準
。 擴容後的 HashMap 容量是之前容量的兩倍。
新增元素
流程
put方法還是比較複雜的，步驟大致如下：
先透過hash值計算出key對映到哪個桶；
如果桶上沒有碰撞衝突，則直接插入；
如果出現碰撞衝突了，則需要處理衝突：
如果該桶使用紅黑樹處理衝突，則呼叫紅黑樹的方法插入資料；
否則採用傳統的鏈式方法插入。如果鏈的長度達到臨界值，則把鏈轉變為紅黑樹；
如果桶中存在重複的鍵，則為該鍵替換新值value；
如果size大於閾值threshold，則進行擴容；
原始碼
具體的方法如下：
public
V
put
（
K
key
，
V
value
）
{
return
putVal
（
hash
（
key
）
，
key
，
value
，
false
，
true
）
；
}
我們可以看到在putVal（）方法中key在這裡執行了一下hash（）方法。確定雜湊桶陣列索引位置需要下面三步：
取hashCode值，
key。hashCode（）
。
高位參與運算，h>>>16。
取模運算，（n-1）&hash。
來看一下Hash方法是如何實現的。
static
final
int
hash
（
Object
key
）
{
int
h
；
/* 1）如果key等於null： 可以看到當key等於null的時候也是有雜湊值的，返回的是0。 2）如果key不等於null： 首先計算出key的hashCode賦值給h，然後與h無符號右移16位後的二進位制進行按位異或得到最後的hash值 */
return
（
key
==
null
）
？
0
：
（
h
=
key
。
hashCode
（
）
）
^
（
h
>>>
16
）
；
}
hashCode（）得到的是一個32位int型別的值，透過hashCode（）的高16位異或低16位實現，如果當n即陣列長度很小，假設是16的話，那麼n-1即為
00000000 00000000 00000000 00001111
，這樣的值和hashCode（）直接做按位與操作，實際上只使用了雜湊值的後4位。
如果當雜湊值的高位變化很大，低位變化很小，這樣就很容易造成雜湊衝突了
，所以這裡把高低位都利用起來，從而解決了這個問題。例如下面這個例子，hashCode值的紅色部分再怎麼變化也沒用，如果hashCode值的紅色部分變了，黑色部分沒變，就會造成索引結果仍然是10，從而造成了雜湊衝突。
獲取桶陣列索引的步驟如下：
現在看putVal（）方法，看看它到底做了什麼。
主要引數：
hash： key的hash值
key： 原始Key
value： 要存放的值
onlyIfAbsent： 如果true代表不更改現有的值
evict ：如果為false表示table為建立狀態
final
V
putVal
（
int
hash
，
K
key
，
V
value
，
boolean
onlyIfAbsent
，
boolean
evict
）
{
Node
<
K
，
V
>
［
］
tab
；
Node
<
K
，
V
>
p
；
int
n
，
i
；
/* 1）transient Node
if
（
（
tab
=
table
）
==
null
||
（
n
=
tab
。
length
）
==
0
）
n
=
（
tab
=
resize
（
）
）
。
length
；
/* 1）i = （n - 1） & hash 表示計算陣列的索引賦值給i，即確定元素存放在哪個桶中 2）p = tab［i = （n - 1） & hash］表示獲取計算出的位置的資料賦值給節點p 3） （p = tab［i = （n - 1） & hash］） == null 判斷節點位置是否等於null， 如果為null，則執行程式碼：tab［i］ = newNode（hash， key， value， null）；根據鍵值對建立新的節點放入該位置的桶中 小結：如果當前桶沒有雜湊碰撞衝突，則直接把鍵值對插入空間位置 */
if
（
（
p
=
tab
［
i
=
（
n
-
1
）
&
hash
］
）
==
null
）
//建立一個新的節點存入到桶中
tab
［
i
］
=
newNode
（
hash
，
key
，
value
，
null
）
；
else
{
// 執行else說明tab［i］不等於null，表示這個位置已經有值了。
Node
<
K
，
V
>
e
；
K
k
；
/* 比較桶中第一個元素（陣列中的結點）的hash值和key是否相等 1）p。hash == hash ：p。hash表示原來存在資料的hash值 hash表示後新增資料的hash值 比較兩個hash值是否相等 說明：p表示tab［i］，即 newNode（hash， key， value， null）方法返回的Node物件。 Node
if
（
p
。
hash
==
hash
&&
（
（
k
=
p
。
key
）
==
key
||
（
key
！=
null
&&
key
。
equals
（
k
）
）
）
）
/* 說明：兩個元素雜湊值相等，並且key的值也相等 將舊的元素整體物件賦值給e，用e來記錄 */
e
=
p
；
// hash值不相等或者key不相等；判斷p是否為紅黑樹結點
else
if
（
p
instanceof
TreeNode
）
// 放入樹中
e
=
（
（
TreeNode
<
K
，
V
>
）
p
）
。
putTreeVal
（
this
，
tab
，
hash
，
key
，
value
）
；
// 說明是連結串列節點
else
{
/* 1）如果是連結串列的話需要遍歷到最後節點然後插入 2）採用迴圈遍歷的方式，判斷連結串列中是否有重複的key */
for
（
int
binCount
=
0
；
；
++
binCount
）
{
/* 1）e = p。next 獲取p的下一個元素賦值給e 2）（e = p。next） == null 判斷p。next是否等於null，等於null， 說明p沒有下一個元素，那麼此時到達了連結串列的尾部，還沒有找到重複的key，則說明HashMap沒有包含該鍵 將該鍵值對插入連結串列中 */
if
（
（
e
=
p
。
next
）
==
null
）
{
/* 1）建立一個新的節點插入到尾部 p。next = newNode（hash， key， value， null）； Node
p
。
next
=
newNode
（
hash
，
key
，
value
，
null
）
；
/* 1）節點新增完成之後判斷此時節點個數是否大於TREEIFY_THRESHOLD臨界值8，如果大於則將連結串列轉換為紅黑樹 2）int binCount = 0 ：表示for迴圈的初始化值。從0開始計數。記錄著遍歷節點的個數。 值是0表示第一個節點，1表示第二個節點。。。。7表示第八個節點，加上陣列中的的一個元素，元素個數是9 TREEIFY_THRESHOLD - 1 ——》8 - 1 ——-》7 如果binCount的值是7（加上陣列中的的一個元素，元素個數是9） TREEIFY_THRESHOLD - 1也是7，此時轉換紅黑樹 */
if
（
binCount
>=
TREEIFY_THRESHOLD
-
1
）
// -1 for 1st
//轉換為紅黑樹
treeifyBin
（
tab
，
hash
）
；
// 跳出迴圈
break
；
}
/* 執行到這裡說明e = p。next 不是null，不是最後一個元素。繼續判斷連結串列中結點的key值與插入的元素的key值是否相等 */
if
（
e
。
hash
==
hash
&&
（
（
k
=
e
。
key
）
==
key
||
（
key
！=
null
&&
key
。
equals
（
k
）
）
）
）
// 相等，跳出迴圈
/* 要新增的元素和連結串列中的存在的元素的key相等了，則跳出for迴圈。不用再繼續比較了 直接執行下面的if語句去替換去 if （e ！= null） */
break
；
/* 說明新新增的元素和當前節點不相等，繼續查詢下一個節點。 用於遍歷桶中的連結串列，與前面的e = p。next組合，可以遍歷連結串列 */
p
=
e
；
}
}
/* 表示在桶中找到key值、hash值與插入元素相等的結點 也就是說透過上面的操作找到了重複的鍵，所以這裡就是把該鍵的值變為新的值，並返回舊值 這裡完成了put方法的修改功能 */
if
（
e
！=
null
）
{
// 記錄e的value
V
oldValue
=
e
。
value
；
// onlyIfAbsent為false或者舊值為null
if
（
！
onlyIfAbsent
||
oldValue
==
null
）
//用新值替換舊值
//e。value 表示舊值 value表示新值
e
。
value
=
value
；
// 訪問後回撥
afterNodeAccess
（
e
）
；
// 返回舊值
return
oldValue
；
}
}
//修改記錄次數
++
modCount
；
// 判斷實際大小是否大於threshold閾值，如果超過則擴容
if
（
++
size
>
threshold
）
resize
（
）
；
// 插入後回撥
afterNodeInsertion
（
evict
）
；
return
null
；
}
treeifyBin方法
節點新增完成之後判斷此時節點個數是否大於
TREEIFY_THRESHOLD
臨界值8，如果大於則將連結串列轉換為紅黑樹（treeifyBin方法裡面還會判斷陣列長度是否大於64），轉換紅黑樹的方法 treeifyBin，整體程式碼如下：
if
（
binCount
>=
TREEIFY_THRESHOLD
-
1
）
// -1 for 1st
//轉換為紅黑樹 tab表示陣列名 hash表示雜湊值
treeifyBin
（
tab
，
hash
）
；
treeifyBin方法如下所示：
/** * Replaces all linked nodes in bin at index for given hash unless * table is too small， in which case resizes instead。 替換指定雜湊表的索引處桶中的所有連結節點，除非表太小，否則將修改大小。 Node
final
void
treeifyBin
（
Node
<
K
，
V
>
［
］
tab
，
int
hash
）
{
int
n
，
index
；
Node
<
K
，
V
>
e
；
/* 如果當前陣列為空或者陣列的長度小於進行樹形化的閾值（MIN_TREEIFY_CAPACITY = 64）， 就去擴容。而不是將節點變為紅黑樹。 目的：如果陣列很小，那麼轉換紅黑樹，然後遍歷效率要低一些。這時進行擴容，那麼重新計算雜湊值 ，連結串列長度有可能就變短了，資料會放到陣列中，這樣相對來說效率高一些。 */
if
（
tab
==
null
||
（
n
=
tab
。
length
）
<
MIN_TREEIFY_CAPACITY
）
//擴容方法
resize
（
）
；
else
if
（
（
e
=
tab
［
index
=
（
n
-
1
）
&
hash
］
）
！=
null
）
{
/* 1）執行到這裡說明雜湊表中的陣列長度大於閾值64，開始進行樹形化 2）e = tab［index = （n - 1） & hash］表示將陣列中的元素取出賦值給e，e是雜湊表中指定位置桶裡的連結串列節點，從第一個開始 */
//hd：紅黑樹的頭結點 tl ：紅黑樹的尾結點
TreeNode
<
K
，
V
>
hd
=
null
，
tl
=
null
；
do
{
//新建立一個樹的節點，內容和當前連結串列節點e一致
TreeNode
<
K
，
V
>
p
=
replacementTreeNode
（
e
，
null
）
；
if
（
tl
==
null
）
//將新創鍵的p節點賦值給紅黑樹的頭結點
hd
=
p
；
else
{
/* p。prev = tl：將上一個節點p賦值給現在的p的前一個節點 tl。next = p；將現在節點p作為樹的尾結點的下一個節點 */
p
。
prev
=
tl
；
tl
。
next
=
p
；
}
tl
=
p
；
/* e = e。next 將當前節點的下一個節點賦值給e，如果下一個節點不等於null 則回到上面繼續取出連結串列中節點轉換為紅黑樹 */
}
while
（
（
e
=
e
。
next
）
！=
null
）
；
/* 讓桶中的第一個元素即陣列中的元素指向新建的紅黑樹的節點，以後這個桶裡的元素就是紅黑樹 而不是連結串列資料結構了 */
if
（
（
tab
［
index
］
=
hd
）
！=
null
）
hd
。
treeify
（
tab
）
；
}
}
擴容機制
流程
當HashMap中的元素個數超過
capacity（陣列長度預設16） * loadFactor（負載因子預設0。75
時，就會進行陣列擴容，loadFactor的預設值（DEFAULT_LOAD_FACTOR）是0。75，這是一個折中的取值。也就是說，預設情況下，陣列大小為16，那麼當HashMap中的元素個數超過16×0。75=12（這個值就是閾值或者邊界值threshold值）的時候，就把陣列的大小擴充套件為2×16=32，即擴大一倍，然後重新計算每個元素在陣列中的位置，而這是一個非常耗效能的操作，所以如果我們已經預知HashMap中元素的個數，那麼預知元素的個數能夠有效的提高HashMap的效能。
HashMap在進行擴容時，使用的rehash方式非常巧妙，因為每次擴容都是翻倍，與原來計算的 （n-1）&hash的結果相比，只是多了一個bit位，所以節點要麼就在原來的位置，要麼就被分配到“
原位置+舊容量
”這個位置。例如我們從16擴充套件為32時，具體的變化如下所示：
容量變為原來的二倍後，
n-1
的二進位制數也由
1111
變為
11111
。當容量為16時，（n-1）&hash的結果都是0101，即十進位制的5；當容量變為32時，hash1的結果是0101，十進位制的5，hash2的結果是10101，十進位制的21（5+16）。擴容之後所以節點要麼就在原來的位置，要麼就被分配到“
原位置+舊容量
”這個位置。
因此，我們在擴充HashMap的時候，不需要重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就可以了，是0的話索引沒變，是1的話索引變成“原索引+oldCap（
原位置+舊容量
）”。在原始碼中透過
e。hash & oldCap
進行判斷。oldCap就是擴容之前的容量，在上面的例子中就是16，hash1結果為0，表示還在原位置，hash2結果不為1，表示結果為
原位置+舊容量
，即
5+16=21
。
可以看看下圖為16擴充為32的resize示意圖：
正是因為這樣巧妙的rehash方式，既省去了重新計算hash值的時間，而且同時，由於新增的1bit是0還是1可以認為是隨機的，在resize的過程中保證了rehash之後每個桶上的節點數一定小於等於原來桶上的節點數，保證了rehash之後不會出現更嚴重的hash衝突，均勻的把之前的衝突的節點分散到新的桶中了。
原始碼
final
Node
<
K
，
V
>
［
］
resize
（
）
{
//得到當前陣列
Node
<
K
，
V
>
［
］
oldTab
=
table
；
//如果當前陣列等於null長度返回0，否則返回當前陣列的長度
int
oldCap
=
（
oldTab
==
null
）
？
0
：
oldTab
。
length
；
//當前閾值點 預設是12（16*0。75）
int
oldThr
=
threshold
；
int
newCap
，
newThr
=
0
；
//如果老的陣列長度大於0
//開始計算擴容後的大小
if
（
oldCap
>
0
）
{
// 超過最大值就不再擴充了，就只好隨你碰撞去吧
if
（
oldCap
>=
MAXIMUM_CAPACITY
）
{
//修改閾值為int的最大值
threshold
=
Integer
。
MAX_VALUE
；
return
oldTab
；
}
/* 沒超過最大值，就擴充為原來的2倍 1）（newCap = oldCap << 1） < MAXIMUM_CAPACITY 擴大到2倍之後容量要小於最大容量 2）oldCap >= DEFAULT_INITIAL_CAPACITY 原陣列長度大於等於陣列初始化長度16 */
else
if
（
（
newCap
=
oldCap
<<
1
）
<
MAXIMUM_CAPACITY
&
&
oldCap
>
=
DEFAULT_INITIAL_CAPACITY
）
//閾值擴大一倍
newThr
=
oldThr
<<
1
；
// double threshold
}
//老閾值點大於0 直接賦值
else
if
（
oldThr
>
0
）
// 老閾值賦值給新的陣列長度
newCap
=
oldThr
；
else
{
// 直接使用預設值
newCap
=
DEFAULT_INITIAL_CAPACITY
；
//16
newThr
=
（
int
）
（
DEFAULT_LOAD_FACTOR
*
DEFAULT_INITIAL_CAPACITY
）
；
}
// 計算新的resize最大上限
if
（
newThr
==
0
）
{
float
ft
=
（
float
）
newCap
*
loadFactor
；
newThr
=
（
newCap
<
MAXIMUM_CAPACITY
&&
ft
<
（
float
）
MAXIMUM_CAPACITY
？
（
int
）
ft
：
Integer
。
MAX_VALUE
）
；
}
//新的閾值 預設原來是12 乘以2之後變為24
threshold
=
newThr
；
//建立新的雜湊表
@SuppressWarnings
（
{
“rawtypes”
，
“unchecked”
}
）
//newCap是新的陣列長度——》32
Node
<
K
，
V
>
［
］
newTab
=
（
Node
<
K
，
V
>
［
］
）
new
Node
［
newCap
］
；
table
=
newTab
；
//判斷舊陣列是否等於空
if
（
oldTab
！=
null
）
{
// 把每個bucket都移動到新的buckets中
//遍歷舊的雜湊表的每個桶，重新計算桶裡元素的新位置
for
（
int
j
=
0
；
j
<
oldCap
；
++
j
）
{
Node
<
K
，
V
>
e
；
if
（
（
e
=
oldTab
［
j
］
）
！=
null
）
{
//原來的資料賦值為null 便於GC回收
oldTab
［
j
］
=
null
；
//判斷陣列是否有下一個引用
if
（
e
。
next
==
null
）
//沒有下一個引用，說明不是連結串列，當前桶上只有一個鍵值對，直接插入
newTab
［
e
。
hash
&
（
newCap
-
1
）
］
=
e
；
//判斷是否是紅黑樹
else
if
（
e
instanceof
TreeNode
）
//說明是紅黑樹來處理衝突的，則呼叫相關方法把樹分開
（
（
TreeNode
<
K
，
V
>
）
e
）
。
split
（
this
，
newTab
，
j
，
oldCap
）
；
else
{
// 採用連結串列處理衝突
Node
<
K
，
V
>
loHead
=
null
，
loTail
=
null
；
Node
<
K
，
V
>
hiHead
=
null
，
hiTail
=
null
；
Node
<
K
，
V
>
next
；
//透過上述講解的原理來計算節點的新位置
do
{
// 原索引
next
=
e
。
next
；
//這裡來判斷如果等於true e這個節點在resize之後不需要移動位置
if
（
（
e
。
hash
&
oldCap
）
==
0
）
{
if
（
loTail
==
null
）
loHead
=
e
；
else
loTail
。
next
=
e
；
loTail
=
e
；
}
// 原索引+oldCap
else
{
if
（
hiTail
==
null
）
hiHead
=
e
；
else
hiTail
。
next
=
e
；
hiTail
=
e
；
}
}
while
（
（
e
=
next
）
！=
null
）
；
// 原索引放到bucket裡
if
（
loTail
！=
null
）
{
loTail
。
next
=
null
；
newTab
［
j
］
=
loHead
；
}
// 原索引+oldCap放到bucket裡
if
（
hiTail
！=
null
）
{
hiTail
。
next
=
null
；
newTab
［
j
+
oldCap
］
=
hiHead
；
}
}
}
}
}
return
newTab
；
}
好，原始碼就先分析到這裡，如果前面看懂了，後面的刪除查詢對你來說相信也不是問題。
併發問題
在多執行緒使用場景中，應該儘量避免使用執行緒不安全的
HashMap
，而使用執行緒安全的
ConcurrentHashMap
。在多執行緒環境下，JDK1。7 會產生死迴圈、資料丟失、資料覆蓋的問題，JDK1。8 中會有資料覆蓋和多執行緒同時擴容等問題。
，https：//blog。csdn。net/weixin_46215617/article/details/119576554