簡單介紹

什麼是 HashMap？

HashMap 是Java日常開發常用的一個集合類。Map集合即Key-Value的集合，前面加個Hash，即雜湊，無序的。所以

HashMap是一個用於儲存Key-Value鍵值對的無序集合

，每一個鍵值對也叫做Entry。

HashMap 的特性

這裡我們先做回答，解決幾個面試常問的HashMap問題，藉此方式來初步瞭解HashMap的特性。

HashMap的底層是怎麼實現的？&& HashMap的擴容機制？

在JDK1。8之前，HashMap採用陣列+連結串列實現，即使用拉鍊法解決hash衝突。但是當位於一個桶中的元素較多，即hash值相等的元素較多時，透過key值查詢要遍歷連結串列，時間複雜度為O（N），效率較低。因此JDK1。8中，HashMap採用陣列+連結串列+紅黑樹實現，當連結串列長度超過閾值（8）時，將連結串列轉換為紅黑樹（將連結串列轉換成紅黑樹前會判斷，如果當前陣列的長度小於 64，那麼會選擇先進行陣列擴容，而不是轉換為紅黑樹），搜尋的時間複雜度為O（logN），這樣大大減少了查詢時間。

為什麼說HashMap是執行緒不安全的？

HashMap在put的時候，插入的元素超過了容量（由負載因子決定）的範圍就會觸發擴容操作，就是rehash，這個會重新將原陣列的內容重新hash到新的擴容陣列中，在多執行緒的環境下，存在同時其他的元素也在進行put操作，如果hash值相同，可能出現同時在同一陣列下用連結串列表示，造成閉環，導致在get時會出現死迴圈，所以HashMap是執行緒不安全的。

HashMap的長度為什麼是2的冪次方？

為了能讓 HashMap 存取高效，儘量較少碰撞，也就是要儘量把資料分配均勻。Hash 值的範圍值-2147483648 到 2147483647，前後加起來大概 40 億的對映空間，只要雜湊函式對映得比較均勻鬆散，一般應用是很難出現碰撞的。但問題是一個 40 億長度的陣列，記憶體是放不下的。所以這個雜湊值是不能直接拿來用的。用之前還要先做對陣列的長度取模運算，得到的餘數才能用來要存放的位置也就是對應的陣列下標。這個陣列下標的計算方法是“ （n - 1） & hash”。（n 代表陣列長度）。這也就解釋了 HashMap 的長度為什麼是 2 的冪次方。

其他的特性？

HashMap 允許 null 鍵和 null 值

HashMap 預設的初始化大小為 16。之後每次擴充，容量變為原來的 2 倍。

HashMap 原始碼分析

這裡我們主要的閱讀材料是JDK1。8的HashMap原始碼

底層資料結構

在網上找到一張很好的圖

可以說HashMap就是一個桶陣列，當桶內資料超過八個之後，桶記憶體儲結構會由連結串列變成紅黑樹。

大體結構我們瞭解了，接下來是具體編碼了

類的屬性：

public class HashMap extends AbstractMap implements Map， Cloneable， Serializable { // 序列號 private static final long serialVersionUID = 362498820763181265L； // 預設的初始容量是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4； // 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30； // 預設的填充因子 static final float DEFAULT_LOAD_FACTOR = 0。75f； // 當桶（bucket）上的結點數大於這個值時會轉成紅黑樹 static final int TREEIFY_THRESHOLD = 8； // 當桶（bucket）上的結點數小於這個值時樹轉連結串列 static final int UNTREEIFY_THRESHOLD = 6； // 桶中結構轉化為紅黑樹對應的table的最小容量 static final int MIN_TREEIFY_CAPACITY = 64； // 儲存元素的陣列，總是2的冪次倍 transient Node［］ table； // 存放具體元素的集 transient Set> entrySet； // 存放元素的個數，注意這個不等於陣列的長度。 transient int size； // 每次擴容和更改map結構的計數器 transient int modCount； // 臨界值（容量*填充因子） 當實際大小超過臨界值時，會進行擴容 int threshold； // 載入因子 final float loadFactor； }複製程式碼

HashMap內部連結串列節點類的實現：

static class Node implements Map。Entry { final int hash； final K key； V value； Node next； Node（int hash， K key， V value， Node next） { this。hash = hash； this。key = key； this。value = value； this。next = next； } ​ public final K getKey（） { return key； } public final V getValue（） { return value； } public final String toString（） { return key + “=” + value； } ​ public final int hashCode（） { return Objects。hashCode（key） ^ Objects。hashCode（value）； } ​ public final V setValue（V newValue） { V oldValue = value； value = newValue； return oldValue； } ​ public final boolean equals（Object o） { if （o == this） return true； if （o instanceof Map。Entry） { Map。Entry<？，？> e = （Map。Entry<？，？>）o； if （Objects。equals（key， e。getKey（）） && Objects。equals（value， e。getValue（））） return true； } return false； } }複製程式碼

HashMap內部紅黑樹節點型別的實現

static final class TreeNode extends LinkedHashMap。Entry { TreeNode parent； // red-black tree links TreeNode left； TreeNode right； TreeNode prev； // needed to unlink next upon deletion boolean red； TreeNode（int hash， K key， V val， Node next） { super（hash， key， val， next）； } ​ /** * Returns root of tree containing this node。 */ final TreeNode root（） { for （TreeNode r = this， p；；） { if （（p = r。parent） == null） return r； r = p； } } ​ /** * Ensures that the given root is the first node of its bin。 */ static void moveRootToFront（Node［］ tab， TreeNode root） { } ​ /** * Finds the node starting at root p with the given hash and key。 * The kc argument caches comparableClassFor（key） upon first use * comparing keys。 */ final TreeNode find（int h， Object k， Class<？> kc） { } ​ /** * Calls find for root node。 */ final TreeNode getTreeNode（int h， Object k） { } ​ /** * Tie-breaking utility for ordering insertions when equal * hashCodes and non-comparable。 We don‘t require a total * order， just a consistent insertion rule to maintain * equivalence across rebalancings。 Tie-breaking further than * necessary simplifies testing a bit。 */ static int tieBreakOrder（Object a， Object b） { } ​ /** * Forms tree of the nodes linked from this node。 */ final void treeify（Node［］ tab） { } ​ /** * Returns a list of non-TreeNodes replacing those linked from * this node。 */ final Node untreeify（HashMap map） { } ​ /** * Tree version of putVal。 */ final TreeNode putTreeVal（HashMap map， Node［］ tab， int h， K k， V v） { } ​ /** * Removes the given node， that must be present before this call。 * This is messier than typical red-black deletion code because we * cannot swap the contents of an interior node with a leaf * successor that is pinned by “next” pointers that are accessible * independently during traversal。 So instead we swap the tree * linkages。 If the current tree appears to have too few nodes， * the bin is converted back to a plain bin。 （The test triggers * somewhere between 2 and 6 nodes， depending on tree structure）。 */ final void removeTreeNode（HashMap map， Node［］ tab， boolean movable） { } ​ /** * Splits nodes in a tree bin into lower and upper tree bins， * or untreeifies if now too small。 Called only from resize； * see above discussion about split bits and indices。 * * @param map the map * @param tab the table for recording bin heads * @param index the index of the table being split * @param bit the bit of hash to split on */ final void split（HashMap map， Node［］ tab， int index， int bit） { } ​ /* —————————————————————————————— */ // Red-black tree methods， all adapted from CLR ​ static TreeNode rotateLeft（TreeNode root， TreeNode p） { } ​ static TreeNode rotateRight（TreeNode root， TreeNode p） { } ​ static TreeNode balanceInsertion（TreeNode root， TreeNode x） { } ​ static TreeNode balanceDeletion（TreeNode root， TreeNode x） { } ​ /** * Recursive invariant check */ static boolean checkInvariants（TreeNode t） { } }複製程式碼

初始容量、負載因子、閾值

一般情況下我們都會使用無參構造 HashMap。但當我們對時間和空間複雜讀有要求的時候，我們需要手動調參，以讓 HashMap 滿足我們的要求。可供我們調整的引數有兩個，一個是初始容量 initialCapacity，另一個負載因子 loadFactor。設定這兩個引數會影響到閾值的大小。初始閾值 threshold 由 initialCapacity 經過移位操作計算得出。他們的作用分別如下：

名稱

用途

initialCapacity

HashMap 初始容量

loadFactor

負載因子

threshold

閾值（當前 HashMap 所能容納鍵值對數量的最大值，超過這個值，則需擴容）

相關程式碼如下：

/** * The default initial capacity - MUST be a power of two。 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4； // aka 16 ​ /** * The load factor used when none specified in constructor。 */ static final float DEFAULT_LOAD_FACTOR = 0。75f； ​ ​ /** * The next size value at which to resize （capacity * load factor）。 * * @serial */ int threshold； ​ /** * The load factor for the hash table。 * * @serial */ final float loadFactor；複製程式碼

我們首先從閾值（threshold）開始分析

透過看程式碼我們知道了HashMap初始容量是16，負載因子是0。75，而閾值我們從註釋中知道是由容量乘以負載因子計算得來的。

本著求實的態度，我們檢視下HashMap的建構函式：

public HashMap（int initialCapacity， float loadFactor） { if （initialCapacity < 0） throw new IllegalArgumentException（“Illegal initial capacity： ” + initialCapacity）； if （initialCapacity > MAXIMUM_CAPACITY） initialCapacity = MAXIMUM_CAPACITY； if （loadFactor <= 0 || Float。isNaN（loadFactor）） throw new IllegalArgumentException（“Illegal load factor： ” + loadFactor）； this。loadFactor = loadFactor； this。threshold = tableSizeFor（initialCapacity）； }複製程式碼

tableSizeFor方法：

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方法，似乎與上面說的 threshold=capacity * load factor 有出入。

這個演算法的作用就是

找到大於或等於 cap 的最小2的冪

。過程就是將二進位制數從左往右數的第一個1開始右邊全部變成1，最後再加上1，就是結果了。

比如我們傳入的cap為31，觀察n的變化過程：

1 1110（30） -> 1 1111 -> 10 0000（31 + 1） -> 32

事實也是如此：

以上就是初始閾值（threshold）的計算過程了。接著我們看看負載因子（loadFactor）。

先問幾個問題：

什麼是負載因子？

根據上面的學習我們知道

閾值（threshold） = 負載因子（loadFactor） * 容量（capacity）

loadFactor 是負載因子，

表示 HashMap 滿的程度

，預設值為 0。75f，也就是說預設情況下，當 HashMap 中元素個數達到了容量的 3/4 的時候就會進行自動擴容。

為什麼要擴容？

HashMap 在擴容到過程中不僅要對其容量進行擴充，還需要進行 rehash！所以，這個過程其實是很耗時的，並且 Map 中元素越多越耗時。

rehash 的過程相當於對其中所有的元素重新做一遍 hash，重新計算要分配到那個桶中。

那麼為什麼要擴容？HashMap 不是一個數組連結串列嗎？不擴容的話，也是可以無限儲存的呀。為啥要擴容？

原因就在於

雜湊碰撞

！

雜湊碰撞

：兩個不同的輸入值，根據同一雜湊函式計算出的雜湊值相同的現象叫做碰撞。

為了解決雜湊衝突，HashMap使用了鏈地址法。

HashMap是基於連結串列的陣列的資料結構實現的。

我們知道衝突以後拉鍊法會向對應連結串列後面新增元素，一旦衝突多了陣列的連結串列就會退化成連結串列，

查詢效率大大降低

。

所以為了保證HashMap的查詢效率，我們需要擴容，來保證HashMap的衝突不要太高。

所以負載因子實際是反應了 HashMap 桶陣列的使用情況：

調低負載因子

，HashMap 所能容納的鍵值對數量變少。擴容時，重新將鍵值對儲存進新的桶數組裡，鍵與鍵之間產生的碰撞會下降，連結串列長度變短。此時，HashMap 的CRUD操作效率會變高，這就是典型的

拿空間換時間

。

增加負載因子

（負載因子可以大於1），HashMap所能容納的鍵值對數量變多，空間利用率高，但碰撞率也高。這意味著連結串列長度變長，效率也隨之降低，這種情況是

拿時間換空間

。

正常來說預設的0。75就已經是很合理的解了，如果有特殊需求，可以按照上面講的進行調整。

hash方法（擾動函式）

HashMap 透過 key 的 hashCode 經過擾動函式處理過後得到 hash 值，然後透過（n - 1） & hash判斷當前元素存放的位置（這裡的n指的是陣列的長度），如果當前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆蓋，不相同就透過拉鍊法解決衝突。

jdk1。8 的 hash 方法

static final int hash（Object key） { int h； // key。hashCode（）：返回雜湊值也就是hashcode // ^ ：按位異或 // >>>：無符號右移，忽略符號位，空位都以0補齊 return （key == null） ？ 0 ： （h = key。hashCode（）） ^ （h >>> 16）； }複製程式碼

解釋

key。hashCode（）是Keyt自帶的hashCode（）方法，返回一個int的雜湊值，範圍從-2147483648到2147483648。但是這樣的雜湊值是不能直接拿來用的，用之前需要對陣列的長度做取模運算。得到的餘數才是索引值。

int index = hash & （arrays。length-1）； 複製程式碼

那麼這也就明白了為什麼HashMap的陣列長度是2的整數冪。

比如以初始長度為16為例，16-1 = 15，15的二進位制數位00000000 00000000 00001111。可以看出一個奇數二進位制最後一位必然位1，當與一個hash值進行與運算時，

最後一位可能是0也可能是1。但偶數與一個hash值進行與運算最後一位必然為0，造成有些位置永遠對映不上值

。（想盡辦法的擾動）

但是，即使雜湊函式很鬆散，但是最後結果我們只取後面幾位，碰撞依舊是很嚴重的。這個時候我們的hash函式的價值體現出來了。

我們將hashCode與自己右移16位的結果（剛好32bit的一半）進行異或操作。就是為了混合雜湊值的高位和低位，增加低位的隨機性，並且混合後的值也變相保持了高位的特徵。

對比 jdk1。7 的hash方法

static int hash（int h） { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions （approximately 8 at default load factor）。 ​ h ^= （h >>> 20） ^ （h >>> 12）； return h ^ （h >>> 7） ^ （h >>> 4）； }複製程式碼

1。7的hash演算法擾動了4次，所以相比於1。8的演算法是比較慢的。

get方法 （查詢）

查詢的入口方法在get， 主要邏輯在getNode方法

查詢操作，先定位鍵值對所在的桶位置，然後再對連結串列或者紅黑樹進行查詢。

public V get（Object key） { Node e； return （e = getNode（hash（key）， key）） == null ？ null ： e。value； } ​ ​ final Node getNode（int hash， Object key） { Node［］ tab； Node first， e； int n； K k； // 1。 定位鍵值對所在桶的位置 if （（tab = table） ！= null && （n = tab。length） > 0 && （first = tab［（n - 1） & hash］） ！= null） { if （first。hash == hash && // always check first node （（k = first。key） == key || （key ！= null && key。equals（k）））） return first； if （（e = first。next） ！= null） { // 2。 如果first是TreeNode型別，則使用紅黑樹查詢方法 if （first instanceof TreeNode） return （（TreeNode）first）。getTreeNode（hash， key）； // 2。 否則對連結串列進行查詢 do { if （e。hash == hash && （（k = e。key） == key || （key ！= null && key。equals（k）））） return e； } while （（e = e。next） ！= null）； } } return null； }複製程式碼

查詢核心在於getNode（）方法。裡面已經做了註釋。

我們先看到第一步“定位鍵值對所在桶的位置”，實現程式碼如下：

first = tab［（n - 1） & hash複製程式碼

這裡透過（n-1）&hash可以算出桶在桶陣列中的位置。解釋一下，HashMap中桶陣列的大小 length 總是 2 的冪。此時，（n-1）&hash等價於對length取餘。但取餘效率沒有位運算高，所以（n-1）&hash也是一個小的最佳化。

假設 hash=143，n=16。計算過程如下：

最終結果為15，剛好就是143%16的結果。

put方法 （插入）

對於插入操作我們先分析大體流程：

首先肯定是先定位要插入的鍵值對屬於哪個桶，定位到桶後，再判斷桶是否為空。如果為空，則將鍵值對存入即可。如果不為空，則需將鍵值對接在連結串列最後一個位置，或者更新鍵值對。

當然插入過程還有很多細節。首先HashMap是變長集合，需要考慮擴容問題。其次，在JDK1。8中，HashMap引入了紅黑樹最佳化過長連結串列，所以這裡要考慮最佳化過程。

插入操作的入口在put（K，V），核心在V putVal（int， K， V， boolean， boolean）方法中。

首先我們看下插入操作的原始碼：

public V put（K key， V value） { return putVal（hash（key）， key， value， false， true）； } ​ final V putVal（int hash， K key， V value， boolean onlyIfAbsent， boolean evict） { Node［］ tab； Node p； int n， i； // 初始化桶陣列 table，table 被延遲到插入新資料時再進行初始化 if （（tab = table） == null || （n = tab。length） == 0） n = （tab = resize（））。length； // 如果桶中不包含鍵值對節點引用，則將新鍵值對節點的引用存入桶中即可 if （（p = tab［i = （n - 1） & hash］） == null） tab［i］ = newNode（hash， key， value， null）； else { Node e； K k； // 如果鍵的值以及節點 hash 等於連結串列中的第一個鍵值對節點時，則將 e 指向該鍵值對 if （p。hash == hash && （（k = p。key） == key || （key ！= null && key。equals（k）））） e = p； // 如果桶中的引用型別為 TreeNode，則呼叫紅黑樹的插入方法 else if （p instanceof TreeNode） e = （（TreeNode）p）。putTreeVal（this， tab， hash， key， value）； else { // 對連結串列進行遍歷，並統計連結串列長度 for （int binCount = 0； ； ++binCount） { // 連結串列中不包含要插入的鍵值對節點時，則將該節點接在連結串列的最後 if （（e = p。next） == null） { p。next = newNode（hash， key， value， null）； // 如果連結串列長度大於或等於樹化閾值，則進行樹化操作 if （binCount >= TREEIFY_THRESHOLD - 1） // -1 for 1st treeifyBin（tab， hash）； break； } // 條件為 true，表示當前連結串列包含要插入的鍵值對，終止遍歷 if （e。hash == hash && （（k = e。key） == key || （key ！= null && key。equals（k）））） break； p = e； } } // 判斷要插入的鍵值對是否存在 HashMap 中 if （e ！= null） { // existing mapping for key V oldValue = e。value； // onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對的值 if （！onlyIfAbsent || oldValue == null） e。value = value； afterNodeAccess（e）； return oldValue； } } ++modCount； // 鍵值對數量超過閾值時，則進行擴容 if （++size > threshold） resize（）； afterNodeInsertion（evict）； return null； }複製程式碼

putVal的主要邏輯：

當桶陣列 table 為空時，透過resize（

擴容

）的方式初始化 table

如果定位到的陣列位置有元素，存在的話如果 key 相同就直接覆蓋，如果 key 不相同，就判斷 p 是否是一個樹節點，如果是就呼叫putTreeVal將元素新增進入。如果不是就遍歷連結串列插入（插入的是連結串列尾部）。

如果定位到的陣列位置沒有元素，則將鍵值對鏈入連結串列中，並根據連結串列長度決定是否將連結串列轉為紅黑樹（treeifyBin

樹化操作

）

判斷鍵值對數量是否大於閾值，大於的話則進行

擴容操作

resize

可以看出來resize（擴容）在插入操作的邏輯中非常重要，接下來我們就講HashMap的

擴容機制

。

擴容機制

resize方法 （擴容主要邏輯）

背景知識：在 HashMap 中，桶陣列的長度均是2的冪，閾值大小為桶陣列長度與負載因子的乘積。當 HashMap 中的鍵值對數量超過閾值時，進行擴容。

需要注意：進行擴容，會伴隨著一次重新 hash 分配，並且會遍歷 hash 表中所有的元素，是非常耗時的。在編寫程式中，要儘量避免 resize。

HashMap按照當前桶陣列長度的2倍進行擴容，擴容之後，要重新計算鍵值對的位置，並把它們移動到合適的位置上去。

具體實現：

final Node［］ resize（） { Node［］ oldTab = table； int oldCap = （oldTab == null） ？ 0 ： oldTab。length； int oldThr = threshold； int newCap， newThr = 0； // 如果 table 不為空，表明已經初始化過了 if （oldCap > 0） { // 當 table 容量超過容量最大值，則不再擴容 if （oldCap >= MAXIMUM_CAPACITY） { threshold = Integer。MAX_VALUE； return oldTab； } // 按舊容量和閾值的2倍計算新容量和閾值的大小 else if （（newCap = oldCap << 1） < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY） newThr = oldThr << 1； // double threshold } else if （oldThr > 0） // initial capacity was placed in threshold /* * 初始化時，將 threshold 的值賦值給 newCap， * HashMap 使用 threshold 變數暫時儲存 initialCapacity 引數的值 */ newCap = oldThr； else { // zero initial threshold signifies using defaults /* * 呼叫無參構造方法時，桶陣列容量為預設容量， * 閾值為預設容量與預設負載因子乘積 */ newCap = DEFAULT_INITIAL_CAPACITY； newThr = （int）（DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY）； } // newThr 為 0 時，按閾值計算公式進行計算 if （newThr == 0） { float ft = （float）newCap * loadFactor； newThr = （newCap < MAXIMUM_CAPACITY && ft < （float）MAXIMUM_CAPACITY ？ （int）ft ： Integer。MAX_VALUE）； } threshold = newThr； // 建立新的桶陣列，桶陣列的初始化也是在這裡完成的 Node［］ newTab = （Node［］）new Node［newCap］； table = newTab； if （oldTab ！= null） { // 如果舊的桶陣列不為空，則遍歷桶陣列，並將鍵值對對映到新的桶陣列中 for （int j = 0； j < oldCap； ++j） { Node e； if （（e = oldTab［j］） ！= null） { oldTab［j］ = null； if （e。next == null） newTab［e。hash & （newCap - 1）］ = e； else if （e instanceof TreeNode） // 重新對映時，需要對紅黑樹進行拆分 （（TreeNode）e）。split（this， newTab， j， oldCap）； else { // preserve order Node loHead = null， loTail = null； Node hiHead = null， hiTail = null； Node next； // 遍歷連結串列，並將連結串列節點按原順序進行分組 do { next = e。next； if （（e。hash & oldCap） == 0） { if （loTail == null） loHead = e； else loTail。next = e； loTail = e； } else { if （hiTail == null） hiHead = e； else hiTail。next = e； hiTail = e； } } while （（e = next） ！= null）； // 將分組後的連結串列對映到新桶中 if （loTail ！= null） { loTail。next = null； newTab［j］ = loHead； } if （hiTail ！= null） { hiTail。next = null； newTab［j + oldCap］ = hiHead； } } } } } return newTab； }複製程式碼

resize方法的主要邏輯：

計算新桶陣列的容量 newCap 和新閾值 newThr

// 第一個條件分支 if （ oldCap > 0） { // 巢狀條件分支 if （oldCap >= MAXIMUM_CAPACITY） {。。。} else if （（newCap = oldCap << 1） < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY） {。。。} } else if （oldThr > 0） {。。。} else {。。。} ​ // 第二個條件分支 if （newThr == 0） {。。。} 複製程式碼

分支一：

oldCap>0：桶陣列table已經被初始化，這種情況下，會將 oldThr 賦值給 newCap，等價於newCap = threshold = tableSizeFor（initialCapacity）。我們在初始化時傳入的 initialCapacity 引數經過 threshold 中轉最終賦值給了 newCap。

oldThr>0：threshold>0， 且桶陣列未被初始化，呼叫 HashMap（int） 和 HashMap（int， float） 構造方法時會產生這種情況，此種情況下 newCap = oldThr，newThr 在第二個條件分支中算出

oldCap == 0 && oldThr == 0：桶陣列未被初始化，且 threshold 為 0，呼叫 HashMap（） 構造方法會產生這種情況。

巢狀分支：

oldCap >= MAXIMUM_CAPACITY：桶陣列容量大於或等於最大桶容量 2^30，這個時候不再擴容

newCap < MAXIMUM_CAPACITY && oldCap > DEFAULT_INITIAL_CAPACITY：新桶陣列容量小於最大值，且舊桶陣列容量大於 16

分支二：

newThr == 0：第一個條件分支未計算 newThr 或巢狀分支在計算過程中導致 newThr 溢位歸零

根據計算出的 newCap 建立新的桶陣列，桶陣列 table 也是在這裡進行初始化的

將鍵值對節點重新對映到新的桶數組裡。如果節點是 TreeNode 型別，則需要拆分紅黑樹。如果是普通節點，則節點按原順序進行分組。該種情況下新閾值 newThr = oldThr << 1，移位可能會導致溢位。

那麼如何連結串列是重新對映呢？

往底層資料結構中插入節點時，先透過模運算計算桶位置，接著把節點放入桶中即可。我們可以將重新對映看作是插入操作，JDK1。7確實就是這樣做的。

但在JDK1。8中對過程進行了一定最佳化，重新對映節點需要考慮節點型別。對於樹形節點，需先拆分紅黑樹再對映。對於連結串列型別節點，則需先對連結串列進行分組，然後再對映。需要的注意的是，分組後，組內節點相對位置保持不變。

看個例子：

如果我們對上圖桶陣列進行擴容，擴容後容量 n =16，重新對映過程如下：

依次遍歷連結串列，並計算節點 hash & oldCap 的值。

35&8=0； 27&8！=0； 19&8=0； 43&8！=0；

如果值為0，將 loHead 和 loTail 指向這個節點。如果後面還有節點 hash & oldCap 為0的話，則將節點鏈入 loHead 指向的連結串列中，並將 loTail 指向該節點。如果值為非0的話，則讓 hiHead 和 hiTail 指向該節點。完成遍歷後，可能會得到兩條連結串列，此時就完成了連結串列分組：

最後將這兩條連直接存放到對應的桶中，完成擴容。

JDK1。8的HashMap擴容效率是要高於之前版本的。JDK1。7為了防止因hash碰撞引發的拒絕服務攻擊，在計算hash過程中引入隨機種子，為了增強hash的隨機性，使得鍵值對均勻分佈在桶陣列中。在擴容過程中，相關方法會根據容量判斷是否需要生成新的隨機種子，並重新計算所有節點的hash。而在JDK1。8中則透過引入紅黑樹替代了該方式。從而避免了多次計算hash的操作，提高了擴容效率。

以上我們就講完了擴容的主體邏輯。擴容後，紅黑樹節點和普通節點一樣是需要重新對映的。於是我們接著就說紅黑樹的分組和重新對映。（split方法的呼叫可以在resize方法體中找到。）

split方法 （紅黑樹拆分）

// 紅黑樹轉連結串列閾值 static final int UNTREEIFY_THRESHOLD = 6； ​ final void split（HashMap map， Node［］ tab， int index， int bit） { TreeNode b = this； // Relink into lo and hi lists， preserving order TreeNode loHead = null， loTail = null； TreeNode hiHead = null， hiTail = null； int lc = 0， hc = 0； /* * 紅黑樹節點仍然保留了 next 引用，故仍可以按連結串列方式遍歷紅黑樹。 * 下面的迴圈是對紅黑樹節點進行分組，與上面類似 */ for （TreeNode e = b， next； e ！= null； e = next） { next = （TreeNode）e。next； e。next = null； if （（e。hash & bit） == 0） { if （（e。prev = loTail） == null） loHead = e； else loTail。next = e； loTail = e； ++lc； } else { if （（e。prev = hiTail） == null） hiHead = e； else hiTail。next = e； hiTail = e； ++hc； } } ​ if （loHead ！= null） { // 如果 loHead 不為空，且連結串列長度小於等於 6，則將紅黑樹轉成連結串列 if （lc <= UNTREEIFY_THRESHOLD） tab［index］ = loHead。untreeify（map）； else { tab［index］ = loHead； /* * hiHead == null 時，表明擴容後， * 所有節點仍在原位置，樹結構不變，無需重新樹化 */ if （hiHead ！= null） loHead。treeify（tab）； } } // 與上面類似 if （hiHead ！= null） { if （hc <= UNTREEIFY_THRESHOLD） tab［index + bit］ = hiHead。untreeify（map）； else { tab［index + bit］ = hiHead； if （loHead ！= null） hiHead。treeify（tab）； } } }複製程式碼

重新對映紅黑樹的邏輯和重新對映連結串列的邏輯基本一致。不同的地方在於，重新對映後，會將紅黑樹拆分成兩條由 TreeNode 組成的連結串列。如果連結串列長度小於 UNTREEIFY_THRESHOLD，則將連結串列轉換成普通連結串列。否則根據條件重新將 TreeNode 連結串列樹化。

舉個例子：

我們對該桶陣列進行擴容，擴容後需要重新對映上面的紅黑樹，對映結果如下：

treeifyBin方法 （連結串列樹化）

JDK1。8對HashMap實現進行了改進。最大的改進就是引入了紅黑樹。

關於紅黑樹可以參考我的另一篇部落格：juejin。cn/post/713683…

樹化相關的程式碼：

static final int TREEIFY_THRESHOLD = 8； ​ /** * 當桶陣列容量小於該值時，優先進行擴容，而不是樹化 */ static final int MIN_TREEIFY_CAPACITY = 64； ​ static final class TreeNode extends LinkedHashMap。Entry { TreeNode parent； // red-black tree links TreeNode left； TreeNode right； TreeNode prev； // needed to unlink next upon deletion boolean red； TreeNode（int hash， K key， V val， Node next） { super（hash， key， val， next）； } } ​ /** * 將普通節點連結串列轉換成樹形節點連結串列 */ final void treeifyBin（Node［］ tab， int hash） { int n， index； Node e； // 桶陣列容量小於 MIN_TREEIFY_CAPACITY，優先進行擴容而不是樹化 if （tab == null || （n = tab。length） < MIN_TREEIFY_CAPACITY） resize（）； else if （（e = tab［index = （n - 1） & hash］） ！= null） { // hd 為頭節點（head），tl 為尾節點（tail） TreeNode hd = null， tl = null； do { // 將普通節點替換成樹形節點 TreeNode p = replacementTreeNode（e， null）； if （tl == null） hd = p； else { p。prev = tl； tl。next = p； } tl = p； } while （（e = e。next） ！= null）； // 將普通連結串列轉成由樹形節點連結串列 if （（tab［index］ = hd） ！= null） // 將樹形連結串列轉換成紅黑樹 hd。treeify（tab）； } } ​ TreeNode replacementTreeNode（Node p， Node next） { return new TreeNode<>（p。hash， p。key， p。value， next）； }複製程式碼

擴容的過程中，樹化需要滿足兩個條件：

連結串列長度大於等於 TREEIFY_THRESHOLD

連結串列長度大於等於了樹化閾值，也就是我們面試常考的8，才進行樹化。

桶陣列容量大於等於 MIN_TREEIFY_CAPACITY

桶陣列容量比較小的時候，應當優先擴容，減少hash碰撞的機率。

HashMap在設計之初，沒有考慮到以後會引入紅黑樹進行最佳化。所以並沒有像TreeMap一樣，要求鍵類實現Comparable介面，或提供對應的比較器。但由於樹化的過程需要比較兩個鍵物件的大小，在鍵類沒有實現Comparable介面的情況下，這成了一個問題。HashMap做了三步操作。透過下面三步操作就能知道誰大誰小，最終構造出紅黑樹了。

比較鍵與鍵之間hash的大小，如果hash相同，繼續往下比較。

檢測鍵類是否實現了Comparable介面，如果實現呼叫compareTo方法進行比較

如果仍未比較出大小，據需要進行仲裁了，仲裁方法為tieBreadOrder

untreeify方法 （紅黑樹鏈化）

紅黑樹中仍然保留了原連結串列節點的順序。有了這個前提，將紅黑樹轉化成連結串列，僅需將 TreeNode 連結串列轉換成 Node 型別的連結串列即可。

final Node untreeify（HashMap map） { Node hd = null， tl = null； // 遍歷 TreeNode 連結串列，並用 Node 替換 for （Node q = this； q ！= null； q = q。next） { // 替換節點型別 Node p = map。replacementNode（q， null）； if （tl == null） hd = p； else tl。next = p； tl = p； } return hd； } ​ Node replacementNode（Node p， Node next） { return new Node<>（p。hash， p。key， p。value， next）； }複製程式碼

remove方法 （刪除）

HashMap 的刪除操作並不複雜，入口方法為remove，主要邏輯在removeNode方法。

刪除僅需三個步驟即可完成。第一步是定位桶位置，第二步遍歷連結串列並找到鍵值相等的節點，第三步刪除節點。相關原始碼如下：

public V remove（Object key） { Node e； return （e = removeNode（hash（key）， key， null， false， true）） == null ？ null ： e。value； } ​ final Node removeNode（int hash， Object key， Object value， boolean matchValue， boolean movable） { Node［］ tab； Node p； int n， index； if （（tab = table） ！= null && （n = tab。length） > 0 && // 1。 定位桶位置 （p = tab［index = （n - 1） & hash］） ！= null） { Node node = null， e； K k； V v； // 如果鍵的值與連結串列第一個節點相等，則將 node 指向該節點 if （p。hash == hash && （（k = p。key） == key || （key ！= null && key。equals（k）））） node = p； else if （（e = p。next） ！= null） { // 如果是 TreeNode 型別，呼叫紅黑樹的查詢邏輯定位待刪除節點 if （p instanceof TreeNode） node = （（TreeNode）p）。getTreeNode（hash， key）； else { // 2。 遍歷連結串列，找到待刪除節點 do { if （e。hash == hash && （（k = e。key） == key || （key ！= null && key。equals（k）））） { node = e； break； } p = e； } while （（e = e。next） ！= null）； } } // 3。 刪除節點，並修復連結串列或紅黑樹 if （node ！= null && （！matchValue || （v = node。value） == value || （value ！= null && value。equals（v）））） { if （node instanceof TreeNode） （（TreeNode）node）。removeTreeNode（this， tab， movable）； else if （node == p） tab［index］ = node。next； else p。next = node。next； ++modCount； ——size； afterNodeRemoval（node）； return node； } } return null； }複製程式碼

HashMap 的使用

HashMap 的幾種遍歷方式

總共的遍歷方式在查閱後發現有7種。

遍歷方式主要分成下面的四個方向：

迭代器（Iterator）方式遍歷。

// 遍歷 EntrySet Iterator> iterator = map。entrySet（）。iterator（）； while （iterator。hasNext（）） { Map。Entry entry = iterator。next（）； System。out。println（entry。getKey（））； System。out。println（entry。getValue（））； } ​ ​ // 遍歷 KeySet Iterator iterator = map。keySet（）。iterator（）； while （iterator。hasNext（）） { Integer key = iterator。next（）； System。out。println（key）； System。out。println（map。get（key））； } 複製程式碼

For Each 方式遍歷。

// 遍歷 EntrySet for （Map。Entry entry ： map。entrySet（）） { System。out。println（entry。getKey（））； System。out。println（entry。getValue（））； } ​ ​ // 遍歷 KeySet for （Integer key ： map。keySet（）） { System。out。println（key）； System。out。println（map。get（key））； } 複製程式碼

Lambda 表示式遍歷（JDK 1。8+）。

// 遍歷 map。forEach（（key， value） -> { System。out。println（key）； System。out。println（value）； }）； 複製程式碼

Streams API 遍歷（JDK 1。8+）。

// 遍歷 單執行緒 map。entrySet（）。stream（）。forEach（（entry） -> { System。out。println（entry。getKey（））； System。out。println（entry。getValue（））； }）； ​ // 遍歷 多執行緒 map。entrySet（）。parallelStream（）。forEach（（entry） -> { System。out。println（entry。getKey（））； System。out。println（entry。getValue（））； }）； 複製程式碼

entrySet的效能比keySet的效能高，所以我們還是儘量使用entrySet來遍歷HashMap。

小結

HashMap是Java學習者繞不過去的一道坎，無論是應付面試或者是實際的應用都要經常和這個資料結構打交道。本文參考了很多前人的分析並由自己消化，最終呈現出來。不得不說對原始碼的深入理解需要大量的功夫，需要融匯諸多思考。所以在我有新的思考之後可能會對文章再做更新，希望能為這思考再加上一層。

作者：pixel_revolve

連結：https：//juejin。cn/post/7142388342103998494

著作權歸作者所有。商業轉載請聯絡作者獲得授權，非商業轉載請註明出處。