厲害了！把 HashMap 剖析的只剩渣了！
HashMap 是一個非常重要的集合，日常使用也非常的頻繁，同時也是面試重點。本文並不打算講解基礎的使用 api，而是深入 HashMap 的底層，講解關於 HashMap 的重點知識。需要讀者對散列表和 HashMap 有一定的認識。
HashMap 本質上是一個散列表，那麼就離不開散列表的三大問題：散列函數、哈希衝突、擴容方案；同時作爲一個數據結構，必須考慮多線程併發訪問的問題，也就是線程安全。這四大重點則爲學習 HashMap 的重點，也是 HashMap 設計的重點。
HashMap 屬於 Map 集合體系的一部分，同時繼承了 Serializable 接口可以被序列化，繼承了 Cloneable 接口可以被複制。他的的繼承結構如下：
HashMap 並不是全能的，對於一些特殊的情景下的需求官方拓展了一些其他的類來滿足，如線程安全的 ConcurrentHashMap、記錄插入順序的 LinkHashMap、給 key 排序的 TreeMap 等。
文章內容主要講解四大重點：散列函數、哈希衝突、擴容方案、線程安全，再補充關鍵的源碼分析和相關的問題。
本文所有內容如若未特殊說明，均爲 JDK1.8 版本。
哈希函數
哈希函數的目標是計算 key 在數組中的下標。判斷一個哈希函數的標準是：散列是否均勻、計算是否簡單。
HashMap 哈希函數的步驟：
-
對 key 對象的 hashcode 進行擾動
-
通過取模求得數組下標
擾動是爲了讓 hashcode 的隨機性更高，第二步取模就不會讓所以的 key 都聚集在一起，提高散列均勻度。擾動可以看到 hash() 方法：
1static final int hash(Object key) {
2 int h;
3 // 獲取到key的hashcode，在高低位異或運算
4 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
5}
6
7
也就是低 16 位是和高 16 位進行異或，高 16 位保持不變。一般的數組長度都會比較短，取模運算中只有低位參與散列；高位與低位進行異或，讓高位也得以參與散列運算，使得散列更加均勻。具體運算如下圖（圖中爲了方便採用 8 位進行演示，32 位同理）：
對 hashcode 擾動之後需要對結果進行取模。HashMap 在 jdk1.8 並不是簡單使用 % 進行取模，而是採用了另外一種更加高性能的方法。HashMap 控制數組長度爲 2 的整數次冪，好處是對 hashcode 進行求餘運算和讓 hashcode 與數組長度 - 1 進行位與運算是相同的效果。如下圖：
img
但位與運算的效率卻比求餘高得多，從而提升了性能。在擴容運算中也利用到了此特性，後面會講。取模運算的源碼看到 putVal() 方法，該方法在 put() 方法中被調用：
1final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
2 boolean evict) {
3 ...
4 // 與數組長度-1進行位與運算，得到下標
5 if ((p = tab[i = (n - 1) & hash]) == null)
6 ...
7}
8
9
完整的 hash 計算過程可以參考下圖：
上面我們提到 HashMap 的數組長度爲 2 的整數次冪，那麼 HashMap 是如何控制數組的長度爲 2 的整數次冪的？修改數組長度有兩種情況：
-
初始化時指定的長度
-
擴容時的長度增量
先看第一種情況。默認情況下，如未在 HashMap 構造器中指定長度，則初始長度爲 16。16 是一個較爲合適的經驗值，他是 2 的整數次冪，同時太小會頻繁觸發擴容、太大會浪費空間。如果指定一個非 2 的整數次冪，會自動轉化成大於該指定數的最小 2 的整數次冪。如指定 6 則轉化爲 8，指定 11 則轉化爲 16。結合源碼來分析，當我們初始化指定一個非 2 的整數次冪長度時，HashMap 會調用 tableSizeFor() 方法：
1public HashMap(int initialCapacity, float loadFactor) {
2 ...
3 this.loadFactor = loadFactor;
4 // 這裏調用了tableSizeFor方法
5 this.threshold = tableSizeFor(initialCapacity);
6}
7
8static final int tableSizeFor(int cap) {
9 // 注意這裏必須減一
10 int n = cap - 1;
11 n |= n >>> 1;
12 n |= n >>> 2;
13 n |= n >>> 4;
14 n |= n >>> 8;
15 n |= n >>> 16;
16 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
17}
18
19
tableSizeFor() 方法的看起來很複雜，作用是使得最高位 1 後續的所有位都變爲 1，最後再 + 1 則得到剛好大於 initialCapacity 的最小 2 的整數次冪數。如下圖（這裏使用了 8 位進行模擬，32 位也是同理）：
那爲什麼必須要對 cap 進行 - 1 之後再進行運算呢？如果指定的數剛好是 2 的整數次冪，如果沒有 - 1 結果會變成比他大兩倍的數，如下：
100100 --高位1之後全變1--> 00111 --加1---> 01000
2
3
第二種改變數組長度的情況是擴容。HashMap 每次擴容的大小都是原來的兩倍，控制了數組大小一定是 2 的整數次冪，相關源碼如下：
1final Node[] resize() {
2 ...
3 if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
4 oldCap >= DEFAULT_INITIAL_CAPACITY)
5 // 設置爲原來的兩倍
6 newThr = oldThr << 1;
7 ...
8}
9
10
小結
-
HashMap 通過高 16 位與低 16 位進行異或運算來讓高位參與散列，提高散列效果；
-
HashMap 控制數組的長度爲 2 的整數次冪來簡化取模運算，提高性能；
-
HashMap 通過控制初始化的數組長度爲 2 的整數次冪、擴容爲原來的 2 倍來控制數組長度一定爲 2 的整數次冪。
哈希衝突解決方案
再優秀的 hash 算法永遠無法避免出現 hash 衝突。hash 衝突指的是兩個不同的 key 經過 hash 計算之後得到的數組下標是相同的。解決 hash 衝突的方式很多，如開放定址法、再哈希法、公共溢出表法、鏈地址法。HashMap 採用的是鏈地址法，jdk1.8 之後還增加了紅黑樹的優化，如下圖：
出現衝突後會在當前節點形成鏈表，而當鏈表過長之後，會自動轉化成紅黑樹提高查找效率。紅黑樹是一個查找效率很高的數據結構，時間複雜度爲 O(logN)，但紅黑樹只有在數據量較大時才能發揮它的優勢。關於紅黑樹的轉化，HashMap 做了以下限制。
-
當鏈表的長度 >=8 且數組長度 >=64 時，會把鏈表轉化成紅黑樹。
-
當鏈表長度 >=8，但數組長度 < 64 時，會優先進行擴容，而不是轉化成紅黑樹。
-
當紅黑樹節點數 <=6，自動轉化成鏈表。
那就有了以下問題：
爲什麼需要數組長度到 64 纔會轉化紅黑樹？
當數組長度較短時，如 16，鏈表長度達到 8 已經是佔用了最大限度的 50%，意味着負載已經快要達到上限，此時如果轉化成紅黑樹，之後的擴容又會再一次把紅黑樹拆分平均到新的數組中，這樣非但沒有帶來性能的好處，反而會降低性能。所以在數組長度低於 64 時，優先進行擴容。
爲什麼要大於等於 8 轉化爲紅黑樹，而不是 7 或 9？
樹節點的比普通節點更大，在鏈表較短時紅黑樹並未能明顯體現性能優勢，反而會浪費空間，在鏈表較短是採用鏈表而不是紅黑樹。
在理論數學計算中（裝載因子 = 0.75），鏈表的長度到達 8 的概率是百萬分之一；把 7 作爲分水嶺，大於 7 轉化爲紅黑樹，小於 7 轉化爲鏈表。
紅黑樹的出現是爲了在某些極端的情況下，抗住大量的 hash 衝突，正常情況下使用鏈表是更加合適的。
注意，紅黑樹在 jdk1.8 之後出現的，jdk1.7 採用的是數組 + 鏈表模式。
小結
-
HashMap 採用鏈地址法，當發生衝突時會轉化爲鏈表，當鏈表過長會轉化爲紅黑樹提高效率。
-
HashMap 對紅黑樹進行了限制，讓紅黑樹只有在極少數極端情況下進行抗壓。
擴容方案
當 HashMap 中的數據越來越多，那麼發生 hash 衝突的概率也就會越來越高，通過數組擴容可以利用空間換時間，保持查找效率在常數時間複雜度。那什麼時候進行擴容？由 HashMap 的一個關鍵參數控制：裝載因子。
裝載因子 = HashMap 中節點數 / 數組長度，他是一個比例值。當 HashMap 中節點數到達裝載因子這個比例時，就會觸發擴容；也就是說，裝載因子控制了當前數組能夠承載的節點數的閾值。如數組長度是 16，裝載因子是 0.75，那麼可容納的節點數是 16*0.75=12。
裝載因子的數值大小需要仔細權衡。裝載因子越大，數組利用率越高，同時發生哈希衝突的概率也就越高；裝載因子越小，數組利用率降低，但發生哈希衝突的概率也降低了。
所以裝載因子的大小需要權衡空間與時間之間的關係。在理論計算中，0.75 是一個比較合適的數值，大於 0.75 哈希衝突的概率呈指數級別上升，而小於 0.75 衝突減少並不明顯。
HashMap 中的裝載因子的默認大小是 0.75，沒有特殊要求的情況下，不建議修改他的值。
那麼在到達閾值之後，HashMap 是如何進行擴容的呢？HashMap 會把數組長度擴展爲原來的兩倍，再把舊數組的數據遷移到新的數組，而 HashMap 針對遷移做了優化：使用 HashMap 數組長度是 2 的整數次冪的特點，以一種更高效率的方式完成數據遷移。
JDK1.7 之前的數據遷移比較簡單，就是遍歷所有的節點，把所有的節點依次通過 hash 函數計算新的下標，再插入到新數組的鏈表中。
這樣會有兩個缺點：
1、每個節點都需要進行一次求餘計算；2、插入到新的數組時候採用的是頭插入法，在多線程環境下會形成鏈表環。
jdk1.8 之後進行了優化，原因在於他控制數組的長度始終是 2 的整數次冪，每次擴展數組都是原來的 2 倍，帶來的好處是 key 在新的數組的 hash 結果只有兩種：在原來的位置，或者在原來位置 + 原數組長度。
具體爲什麼我們可以看下圖：
從圖中我們可以看到，在新數組中的 hash 結果，僅僅取決於高一位的數值。如果高一位是 0，那麼計算結果就是在原位置，而如果是 1，則加上原數組的長度即可。這樣我們只需要判斷一個節點的高一位是 1 or 0 就可以得到他在新數組的位置，而不需要重複 hash 計算。
HashMap 把每個鏈表拆分成兩個鏈表，對應原位置或原位置 + 原數組長度，再分別插入到新的數組中，保留原來的節點順序，如下：
小結
-
裝載因子決定了 HashMap 擴容的閾值，需要權衡時間與空間，一般情況下保持 0.75 不作改動；
-
HashMap 擴容機制結合了數組長度爲 2 的整數次冪的特點，以一種更高的效率完成數據遷移，同時避免頭插法造成鏈表環。
線程安全
HashMap 作爲一個集合，主要功能則爲 CRUD，也就是增刪查改數據，那麼就肯定涉及到多線程併發訪問數據的情況。併發產生的問題，需要我們特別關注。
HashMap 並不是線程安全的，在多線程的情況下無法保證數據的一致性。舉個例子：HashMap 下標 2 的位置爲 null，線程 A 需要將節點 X 插入下標 2 的位置，在判斷是否爲 null 之後，線程被掛起；此時線程 B 把新的節點 Y 插入到下標 2 的位置；恢復線程 A，節點 X 會直接插入到下標 2，覆蓋節點 Y，導致數據丟失，如下圖：
jdk1.7 及以前擴容時採用的是頭插法，這種方式插入速度快，但在多線程環境下會造成鏈表環，而鏈表環會在下一次插入時找不到鏈表尾而發生死循環。
那如果結果數據一致性問題呢？解決這個問題有三個方案：
-
採用 Hashtable
-
調用 Collections.synchronizeMap() 方法來讓 HashMap 具有多線程能力
-
採用 ConcurrentHashMap
前兩個方案的思路是相似的，均是每個方法中，對整個對象進行上鎖。Hashtable 是老一代的集合框架，很多的設計均以及落後，他在每一個方法中均加上了 synchronize 關鍵字保證線程安全。
1// Hashtable
2public synchronized V get(Object key) {...}
3public synchronized V put(K key, V value) {...}
4public synchronized V remove(Object key) {...}
5public synchronized V replace(K key, V value) {...}
6...
7
8
第二種方法是返回一個 SynchronizedMap 對象，這個對象默認每個方法會鎖住整個對象。如下源碼：
這裏的 mutex 是什麼呢？直接看到構造器：
1final Object mutex; // Object on which to synchronize
2SynchronizedMap(Map m) {
3 this.m = Objects.requireNonNull(m);
4 // 默認爲本對象
5 mutex = this;
6}
7SynchronizedMap(Map m, Object mutex) {
8 this.m = m;
9 this.mutex = mutex;
10}
11
12
可以看到默認鎖的就是本身，效果和 Hashtable 其實是一樣的。這種簡單粗暴鎖整個對象的方式造成的後果是：
-
鎖是非常重量級的，會嚴重影響性能。
-
同一時間只能有一個線程進行讀寫，限制了併發效率。
ConcurrentHashMap 的設計就是爲了解決此問題。他通過降低鎖粒度 + CAS 的方式來提高效率。簡單來說，ConcurrentHashMap 鎖的並不是整個對象，而是一個數組的一個節點，那麼其他線程訪問數組其他節點是不會互相影響，極大提高了併發效率；同時
ConcurrentHashMap 讀操作並不需要獲取鎖，如下圖：
關於 ConcurrentHashMap 和 Hashtable 的更多內容，限於篇幅，我會在另一篇文章講解。
那麼，使用了上述的三種解決方案是不是絕對線程安全？先觀察下面的代碼：
1ConcurrentHashMap map = new ConcurrentHashMap<>();
2map.put("abc","123");
3
4Thread1:
5if (map.containsKey("abc")){
6 String s = map.get("abc");
7}
8
9Thread2:
10map.remove("abc");
11
12
當 Thread1 調用 containsKey 之後釋放鎖，Thread2 獲得鎖並把 “abc” 移除再釋放鎖，這個時候 Thread1 讀取到的 s 就是一個 null 了，也就出現了問題了。所以 ConcurrentHashMap 類或者 Collections.synchronizeMap()方法或者 Hashtable 都只能在一定的限度上保證線程安全，而無法保證絕對線程安全。
關於線程安全，還有一個 fast-fail 問題，即快速失敗。當使用 HashMap 的迭代器遍歷 HashMap 時，如果此時 HashMap 發生了結構性改變，如插入新數據、移除數據、擴容等，那麼 Iteractor 會拋出 fast-fail 異常，防止出現併發異常，在一定限度上保證了線程安全。
如下源碼：
1final Node nextNode() {
2 ...
3 if (modCount != expectedModCount)
4 throw new ConcurrentModificationException();
5 ...
6}
7
8
創建 Iteractor 對象時會記錄 HashMap 的 modCount 變量，每當 HashMap 發生結構性改變時，modCount 會加 1。在迭代時判斷 HashMap 的 modCount 和自己保存的 expectedModCount 是否一致即可判斷是否發生了結構性改變。
fast-fail 異常只能當做遍歷時的一種安全保證，而不能當做多線程併發訪問 HashMap 的手段。若有併發需求，還是需要使用上述的三種方法。
小結
-
HashMap 並不能保證線程安全，在多線程併發訪問下會出現意想不到的問題，如數據丟失等
-
HashMap1.8 採用尾插法進行擴容，防止出現鏈表環導致的死循環問題
-
解決併發問題的的方案有 Hashtable、Collections.synchronizeMap()、ConcurrentHashMap。其中最佳解決方案是 ConcurrentHashMap
-
上述解決方案並不能完全保證線程安全
-
快速失敗是 HashMap 迭代機制中的一種併發安全保證
源碼解析
關鍵變量的理解
HashMap 源碼中有很多的內部變量，這些變量會在下面源碼分析中經常出現，首先需要理解這些變量的意義。
1// 存放數據的數組
2transient Node[] table;
3// 存儲的鍵值對數目
4transient int size;
5// HashMap結構修改的次數，主要用於判斷fast-fail
6transient int modCount;
7// 最大限度存儲鍵值對的數目(threshodl=table.length*loadFactor)，也稱爲閾值
8int threshold;
9// 裝載因子，表示可最大容納數據數量的比例
10final float loadFactor;
11// 靜態內部類，HashMap存儲的節點類型；可存儲鍵值對，本身是個鏈表結構。
12static class Node implements Map.Entry {...}
13
14
擴容
HashMap 源碼中把初始化操作也放到了擴容方法中，因而擴容方法源碼主要分爲兩部分：確定新的數組大小、遷移數據。詳細的源碼分析如下，我打了非常詳細的註釋，可選擇查看。擴容的步驟在上述已經講過了，讀者可以自行結合源碼，分析 HashMap 是如何實現上述的設計。
1final Node[] resize() {
2 // 變量分別是原數組、原數組大小、原閾值；新數組大小、新閾值
3 Node[] oldTab = table;
4 int oldCap = (oldTab == null) ? 0 : oldTab.length;
5 int oldThr = threshold;
6 int newCap, newThr = 0;
7
8 // 如果原數組長度大於0
9 if (oldCap > 0) {
10 // 如果已經超過了設置的最大長度(1<<30,也就是最大整型正數)
11 if (oldCap >= MAXIMUM_CAPACITY) {
12 // 直接把閾值設置爲最大正數
13 threshold = Integer.MAX_VALUE;
14 return oldTab;
15 }
16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
17 oldCap >= DEFAULT_INITIAL_CAPACITY)
18 // 設置爲原來的兩倍
19 newThr = oldThr << 1;
20 }
21
22 // 原數組長度爲0，但最大限度不是0，把長度設置爲閾值
23 // 對應的情況就是新建HashMap的時候指定了數組長度
24 else if (oldThr > 0)
25 newCap = oldThr;
26 // 第一次初始化，默認16和0.75
27 // 對應使用默認構造器新建HashMap對象
28 else {
29 newCap = DEFAULT_INITIAL_CAPACITY;
30 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
31 }
32 // 如果原數組長度小於16或者翻倍之後超過了最大限制長度，則重新計算閾值
33 if (newThr == 0) {
34 float ft = (float)newCap * loadFactor;
35 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
36 (int)ft : Integer.MAX_VALUE);
37 }
38 threshold = newThr;
39
40 @SuppressWarnings({"rawtypes","unchecked"})
41 // 建立新的數組
42 Node[] newTab = (Node[])new Node[newCap];
43 table = newTab;
44 if (oldTab != null) {
45 // 循環遍歷原數組，並給每個節點計算新的位置
46 for (int j = 0; j < oldCap; ++j) {
47 Node e;
48 if ((e = oldTab[j]) != null) {
49 oldTab[j] = null;
50 // 如果他沒有後繼節點，那麼直接使用新的數組長度取模得到新下標
51 if (e.next == null)
52 newTab[e.hash & (newCap - 1)] = e;
53 // 如果是紅黑樹，調用紅黑樹的拆解方法
54 else if (e instanceof TreeNode)
55 ((TreeNode)e).split(this, newTab, j, oldCap);
56 // 新的位置只有兩種可能：原位置，原位置+老數組長度
57 // 把原鏈表拆成兩個鏈表，然後再分別插入到新數組的兩個位置上
58 // 不用多次調用put方法
59 else {
60 // 分別是原位置不變的鏈表和原位置+原數組長度位置的鏈表
61 Node loHead = null, loTail = null;
62 Node hiHead = null, hiTail = null;
63 Node next;
64 // 遍歷老鏈表，判斷新增判定位是1or0進行分類
65 do {
66 next = e.next;
67 if ((e.hash & oldCap) == 0) {
68 if (loTail == null)
69 loHead = e;
70 else
71 loTail.next = e;
72 loTail = e;
73 }
74 else {
75 if (hiTail == null)
76 hiHead = e;
77 else
78 hiTail.next = e;
79 hiTail = e;
80 }
81 } while ((e = next) != null);
82 // 最後賦值給新的數組
83 if (loTail != null) {
84 loTail.next = null;
85 newTab[j] = loHead;
86 }
87 if (hiTail != null) {
88 hiTail.next = null;
89 newTab[j + oldCap] = hiHead;
90 }
91 }
92 }
93 }
94 }
95 // 返回新數組
96 return newTab;
97}
98
99
添加數值
調用 put() 方法添加鍵值對，最終會調用 putVal() 來真正實現添加邏輯。代碼解析如下：
1public V put(K key, V value) {
2 // 獲取hash值，再調用putVal方法插入數據
3 return putVal(hash(key), key, value, false, true);
4}
5
6// onlyIfAbsent表示是否覆蓋舊值，true表示不覆蓋，false表示覆蓋，默認爲false
7// evict和LinkHashMap的回調方法有關，不在本文討論範圍
8final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
9 boolean evict) {
10
11 // tab是HashMap內部數組，n是數組的長度，i是要插入的下標，p是該下標對應的節點
12 Node[] tab; Node p; int n, i;
13
14 // 判斷數組是否是null或者是否是空，若是，則調用resize()方法進行擴容
15 if ((tab = table) == null || (n = tab.length) == 0)
16 n = (tab = resize()).length;
17
18 // 使用位與運算代替取模得到下標
19 // 判斷當前下標是否是null，若是則創建節點直接插入，若不是，進入下面else邏輯
20 if ((p = tab[i = (n - 1) & hash]) == null)
21 tab[i] = newNode(hash, key, value, null);
22 else {
23
24 // e表示和當前key相同的節點，若不存在該節點則爲null
25 // k是當前數組下標節點的key
26 Node e; K k;
27
28 // 判斷當前節點與要插入的key是否相同，是則表示找到了已經存在的key
29 if (p.hash == hash &&
30 ((k = p.key) == key || (key != null && key.equals(k))))
31 e = p;
32 // 判斷該節點是否是樹節點，如果是調用紅黑樹的方法進行插入
33 else if (p instanceof TreeNode)
34 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
35 // 最後一種情況是直接鏈表插入
36 else {
37 for (int binCount = 0; ; ++binCount) {
38 if ((e = p.next) == null) {
39 p.next = newNode(hash, key, value, null);
40 // 長度大於等於8時轉化爲紅黑樹
41 // 注意，treeifyBin方法中會進行數組長度判斷，
42 // 若小於64，則優先進行數組擴容而不是轉化爲樹
43 if (binCount >= TREEIFY_THRESHOLD - 1)
44 treeifyBin(tab, hash);
45 break;
46 }
47 // 找到相同的直接跳出循環
48 if (e.hash == hash &&
49 ((k = e.key) == key || (key != null && key.equals(k))))
50 break;
51 p = e;
52 }
53 }
54
55 // 如果找到相同的key節點，則判斷onlyIfAbsent和舊值是否爲null
56 // 執行更新或者不操作，最後返回舊值
57 if (e != null) {
58 V oldValue = e.value;
59 if (!onlyIfAbsent || oldValue == null)
60 e.value = value;
61 afterNodeAccess(e);
62 return oldValue;
63 }
64 }
65
66 // 如果不是更新舊值，說明HashMap中鍵值對數量發生變化
67 // modCount數值+1表示結構改變
68 ++modCount;
69 // 判斷長度是否達到最大限度，如果是則進行擴容
70 if (++size > threshold)
71 resize();
72 // 最後返回null（afterNodeInsertion是LinkHashMap的回調）
73 afterNodeInsertion(evict);
74 return null;
75}
76
77
代碼中關於每個步驟有了詳細的解釋，這裏來總結一下：
-
總體上分爲兩種情況：找到相同的 key 和找不到相同的 key。找了需要判斷是否更新並返回舊 value，沒找到需要插入新的 Node、更新節點數並判斷是否需要擴容。
-
查找分爲三種情況：數組、鏈表、紅黑樹。數組下標 i 位置不爲空且不等於 key，那麼就需要判斷是否樹節點還是鏈表節點並進行查找。
-
鏈表到達一定長度後需要擴展爲紅黑樹，當且僅當鏈表長度 >=8 且數組長度 >=64。
最後畫一張圖總體再加深一下整個流程的印象：
其他問題
爲什麼 jdk1.7 以前控制數組的長度爲素數，而 jdk1.8 之後卻採用的是 2 的整數次冪？
答：素數長度可以有效減少哈希衝突；JDK1.8 之後採用 2 的整數次冪是爲了提高求餘和擴容的效率，同時結合高低位異或的方法使得哈希散列更加均勻。
爲何素數可以減少哈希衝突？若能保證 key 的 hashcode 在每個數字之間都是均勻分佈，那麼無論是素數還是合數都是相同的效果。
例如 hashcode 在 1~20 均勻分佈，那麼無論長度是合數 4，還是素數 5，分佈都是均勻的。而如果 hashcode 之間的間隔都是 2，如 1,3,5..., 那麼長度爲 4 的數組，位置 2 和位置 4 兩個下標無法放入數據，而長度爲 5 的數組則沒有這個問題。
長度爲合數的數組會使間隔爲其因子的 hashcode 聚集出現，從而使得散列效果降低。
爲什麼插入 HashMap 的數據需要實現 hashcode 和 equals 方法？對這兩個方法有什麼要求？
答：通過 hashcode 來確定插入下標，通過 equals 比較來尋找數據；兩個相等的 key 的 hashcode 必須相等，但擁有相同的 hashcode 的對象不一定相等。
這裏需要區分好他們之間的區別：hashcode 就像一個人的名，相同的人名字肯定相等，但是相同的名字不一定是同個人；equals 比較內容是否相同，一般由對象覆蓋重寫，默認情況下比較的是引用地址；“==” 引用隊形比較的是引用地址是否相同，值對象比較的是值是否相同。
HashMap 中需要使用 hashcode 來獲取 key 的下標，如果兩個相同的對象的 hashcode 不同，那麼會造成 HashMap 中存在相同的 key；所以 equals 返回相同的 key 他們的 hashcode 一定要相同。HashMap 比較兩個元素是否相同採用了三種比較方法結合：p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))) 。
最後
關於 HashMap 的內容很難在一篇文章講完，他的設計到的內容非常多，如線程安全的設計可以延伸到 ConcurrentHashMap 與 Hashtable，這兩個類與 HashMap 的區別以及內部設計均非常重要，這些內容我將在另外的文章做補充。
最後，希望文章對你有幫助。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/lAkRYxnHm0ruXwH8xJnaOg