JDK1.8源碼閱讀記錄
JAVA.Util包
HashMap類
1.概述
本篇文章我們來聊聊大家日常開發中常用的一個集合類 - HashMap。HashMap 最早出現在 JDK 1.2中，底層基于雜湊演算法實作。HashMap 允許 null 鍵和 null 值，在計算哈鍵的哈希值時，null 鍵哈希值為 0。HashMap 并不保證鍵值對的順序，這意味着在進行某些操作後，鍵值對的順序可能會發生變化。另外，需要注意的是，HashMap 是非線程安全類，在多線程環境下可能會存在問題。
在本篇文章中，我将會對 HashMap 中常用方法、重要屬性及相關方法進行分析。需要說明的是，HashMap 源碼中可分析的點很多，本文很難一一覆寫，請見諒。
2.原理
HashMap 底層是基于雜湊演算法實作，雜湊演算法分為散列再探測和拉鍊式。HashMap 則使用了拉鍊式的雜湊演算法，并在 JDK 1.8 中引入了紅黑樹優化過長的連結清單。資料結構示意圖如下：
對于拉鍊式的雜湊演算法，其資料結構是由數組和連結清單（或樹形結構）組成。在進行增删查等操作時，首先要定位到元素的所在桶的位置，之後再從連結清單中定位該元素。比如我們要查詢上圖結構中是否包含元素35，步驟如下：
- 定位元素35所處桶的位置，index = 35 % 16 = 3
- 在3号桶所指向的連結清單中繼續查找，發現35在連結清單中。
上面就是 HashMap 底層資料結構的原理，HashMap 基本操作就是對拉鍊式雜湊演算法基本操作的一層包裝。不同的地方在于 JDK 1.8 中引入了紅黑樹，底層資料結構由數組+連結清單變為了數組+連結清單+紅黑樹，不過本質并未變。好了，原理部分先講到這，接下來說說源碼實作。
3.源碼分析
本篇文章所分析的源碼版本為 JDK 1.8。與 JDK 1.7 相比，JDK 1.8 對 HashMap 進行了一些優化。比如引入紅黑樹解決過長連結清單效率低的問題。重寫 resize 方法，移除了 alternative hashing 相關方法，避免重新計算鍵的 hash 等。不過本篇文章并不打算對這些優化進行分析，本文僅會分析 HashMap 常用的方法及一些重要屬性和相關方法。
3.1 構造方法
3.1.1 構造方法分析
HashMap 的構造方法不多，隻有四個。HashMap 構造方法做的事情比較簡單，一般都是初始化一些重要變量，比如 loadFactor 和 threshold。而底層的資料結構則是延遲到插入鍵值對時再進行初始化。HashMap 相關構造方法如下：
/** 構造方法 1 */
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/** 構造方法 2 */
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/** 構造方法 3 */
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);
}
/** 構造方法 4 */
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
上面4個構造方法中，大家平時用的最多的應該是第一個了。第一個構造方法很簡單，僅将 loadFactor 變量設為預設值。構造方法2調用了構造方法3，而構造方法3仍然隻是設定了一些變量。構造方法4則是将另一個 Map 中的映射拷貝一份到自己的存儲結構中來，這個方法不是很常用。
上面就是對構造方法簡單的介紹，構造方法本身并沒什麼太多東西，是以就不說了。接下來說說構造方法所初始化的幾個的變量。
3.1.1 初始容量、負載因子、門檻值
我們在一般情況下，都會使用無參構造方法建立 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;
/** The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final float loadFactor;
/** The next size value at which to resize (capacity * load factor). */
int threshold;
如果大家去看源碼，會發現 HashMap 中沒有定義 initialCapacity 這個變量。這個也并不難了解，從參數名上可看出，這個變量表示一個初始容量，隻是構造方法中用一次，沒必要定義一個變量儲存。但如果大家仔細看上面 HashMap 的構造方法，會發現存儲鍵值對的資料結構并不是在構造方法裡初始化的。這就有個疑問了，既然叫初始容量，但最終并沒有用與初始化資料結構，那傳這個參數還有什麼用呢？這個問題我先不解釋，給大家留個懸念，後面會說明。
預設情況下，HashMap 初始容量是16，負載因子為 0.75。這裡并沒有預設門檻值，原因是門檻值可由容量乘上負載因子計算而來（注釋中有說明），即threshold = capacity * loadFactor。但當你仔細看構造方法3時，會發現門檻值并不是由上面公式計算而來，而是通過一個方法算出來的。這是不是可以說明 threshold 變量的注釋有誤呢？還是僅這裡進行了特殊處理，其他地方遵循計算公式呢？關于這個疑問，這裡也先不說明，後面在分析擴容方法時，再來解釋這個問題。接下來，我們來看看初始化 threshold 的方法長什麼樣的的，源碼如下：
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
上面的代碼長的有點不太好看，反正我第一次看的時候不明白它想幹啥。不過後來在紙上畫畫，知道了它的用途。總結起來就一句話：找到大于或等于 cap 的最小2的幂。至于為啥要這樣，後面再解釋。我們先來看看 tableSizeFor 方法的圖解：
上面是 tableSizeFor 方法的計算過程圖，這裡cap = 536,870,913 = 229 + 1，多次計算後，算出n + 1 = 1,073,741,824 = 230。通過圖解應該可以比較容易了解這個方法的用途，這裡就不多說了。
說完了初始門檻值的計算過程，再來說說負載因子（loadFactor）。對于 HashMap 來說，負載因子是一個很重要的參數，該參數反應了 HashMap 桶數組的使用情況（假設鍵值對節點均勻分布在桶數組中）。通過調節負載因子，可使 HashMap 時間和空間複雜度上有不同的表現。當我們調低負載因子時，HashMap 所能容納的鍵值對數量變少。擴容時，重新将鍵值對存儲新的桶數組裡，鍵的鍵之間産生的碰撞會下降，連結清單長度變短。此時，HashMap 的增删改查等操作的效率将會變高，這裡是典型的拿空間換時間。相反，如果增加負載因子（負載因子可以大于1），HashMap 所能容納的鍵值對數量變多，空間使用率高，但碰撞率也高。這意味着連結清單長度變長，效率也随之降低，這種情況是拿時間換空間。至于負載因子怎麼調節，這個看使用場景了。一般情況下，我們用預設值就可以了。
3.2 查找
HashMap 的查找操作比較簡單，查找步驟與原理篇介紹一緻，即先定位鍵值對所在的桶的位置，然後再對連結清單或紅黑樹進行查找。通過這兩步即可完成查找，該操作相關代碼如下：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> 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<K,V>)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 方法中的，getNode 方法源碼我已經寫了一些注釋，應該不難看懂。我們先來看看查找過程的第一步 - 确定桶位置，其實作代碼如下：
// index = (n - 1) & hash
first = tab[(n - 1) & hash]
這裡通過**(n - 1)& hash即可算出桶的在桶數組中的位置，可能有的朋友不太明白這裡為什麼這麼做，這裡簡單解釋一下。HashMap 中桶數組的大小 length 總是2的幂，此時，(n - 1) & hash** 等價于對 length 取餘。但取餘的計算效率沒有位運算高，是以**(n - 1) & hash**也是一個小的優化。舉個例子說明一下吧，假設 hash = 185，n = 16。計算過程示意圖如下：
上面的計算并不複雜，這裡就不多說了。
在上面源碼中，除了查找相關邏輯，還有一個計算 hash 的方法。這個方法源碼如下：
/**
* 計算鍵的 hash 值
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看這個方法的邏輯好像是通過位運算重新計算 hash，那麼這裡為什麼要這樣做呢？為什麼不直接用鍵的 hashCode 方法産生的 hash 呢？大家先可以思考一下，我把答案寫在下面。
這樣做有兩個好處，我來簡單解釋一下。我們再看一下上面求餘的計算圖，圖中的 hash 是由鍵的 hashCode 産生。計算餘數時，由于 n 比較小，hash 隻有低4位參與了計算，高位的計算可以認為是無效的。這樣導緻了計算結果隻與低位資訊有關，高位資料沒發揮作用。為了處理這個缺陷，我們可以上圖中的 hash 高4位資料與低4位資料進行異或運算，即 hash ^ (hash >>> 4)。通過這種方式，讓高位資料與低位資料進行異或，以此加大低位資訊的随機性，變相的讓高位資料參與到計算中。此時的計算過程如下：
在 Java 中，hashCode 方法産生的 hash 是 int 類型，32 位寬。前16位為高位，後16位為低位，是以要右移16位。
上面所說的是重新計算 hash 的一個好處，除此之外，重新計算 hash 的另一個好處是可以增加 hash 的複雜度。當我們覆寫 hashCode 方法時，可能會寫出分布性不佳的 hashCode 方法，進而導緻 hash 的沖突率比較高。通過移位和異或運算，可以讓 hash 變得更複雜，進而影響 hash 的分布性。這也就是為什麼 HashMap 不直接使用鍵對象原始 hash 的原因了。
3.3 周遊
和查找查找一樣，周遊操作也是大家使用頻率比較高的一個操作。對于 周遊 HashMap，我們一般都會用下面的方式：
for(Object key : map.keySet()) {
// do something
}
或
for(HashMap.Entry entry : map.entrySet()) {
// do something
}
從上面代碼片段中可以看出，大家一般都是對 HashMap 的 key 集合或 Entry 集合進行周遊。上面代碼片段中用 foreach 周遊 keySet 方法産生的集合，在編譯時會轉換成用疊代器周遊，等價于：
Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
Object key = ite.next();
// do something
}
大家在周遊 HashMap 的過程中會發現，多次對 HashMap 進行周遊時，周遊結果順序都是一緻的。但這個順序和插入的順序一般都是不一緻的。産生上述行為的原因是怎樣的呢？大家想一下原因。我先把周遊相關的代碼貼出來，如下：
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
/**
* 鍵集合
*/
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
// 省略部分代碼
}
/**
* 鍵疊代器
*/
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
// 尋找第一個包含連結清單節點引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
// 尋找下一個包含連結清單節點引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
//省略部分代碼
}
如上面的源碼，周遊所有的鍵時，首先要擷取鍵集合KeySet對象，然後再通過 KeySet 的疊代器KeyIterator進行周遊。KeyIterator 類繼承自HashIterator類，核心邏輯也封裝在 HashIterator 類中。HashIterator 的邏輯并不複雜，在初始化時，HashIterator 先從桶數組中找到包含連結清單節點引用的桶。然後對這個桶指向的連結清單進行周遊。周遊完成後，再繼續尋找下一個包含連結清單節點引用的桶，找到繼續周遊。找不到，則結束周遊。舉個例子，假設我們周遊下圖的結構：
HashIterator 在初始化時，會先周遊桶數組，找到包含連結清單節點引用的桶，對應圖中就是3号桶。随後由 nextNode 方法周遊該桶所指向的連結清單。周遊完3号桶後，nextNode 方法繼續尋找下一個不為空的桶，對應圖中的7号桶。之後流程和上面類似，直至周遊完最後一個桶。以上就是 HashIterator 的核心邏輯的流程，對應下圖：
周遊上圖的最終結果是 19 -> 3 -> 35 -> 7 -> 11 -> 43 -> 59，為了驗證正确性，簡單寫點測試代碼跑一下看看。測試代碼如下：
/**
* 應在 JDK 1.8 下測試，其他環境下不保證結果和上面一緻
*/
public class HashMapTest {
@Test
public void testTraversal() {
HashMap<Integer, String> map = new HashMap(16);
map.put(7, "");
map.put(11, "");
map.put(43, "");
map.put(59, "");
map.put(19, "");
map.put(3, "");
map.put(35, "");
System.out.println("周遊結果：");
for (Integer key : map.keySet()) {
System.out.print(key + " -> ");
}
}
}
周遊結果如下：
在本小節的最後，抛兩個問題給大家。在 JDK 1.8 版本中，為了避免過長的連結清單對 HashMap 性能的影響，特地引入了紅黑樹優化性能。但在上面的源碼中并沒有發現紅黑樹周遊的相關邏輯，這是為什麼呢？對于被轉換成紅黑樹的連結清單該如何周遊呢？大家可以先想想，然後可以去源碼或本文後續章節中找答案。
3.4 插入
3.4.1 插入邏輯分析
通過前兩節的分析，大家對 HashMap 低層的資料結構應該了然于心了。即使我不說，大家也應該能知道 HashMap 的插入流程是什麼樣的了。首先肯定是先定位要插入的鍵值對屬于哪個桶，定位到桶後，再判斷桶是否為空。如果為空，則将鍵值對存入即可。如果不為空，則需将鍵值對接在連結清單最後一個位置，或者更新鍵值對。這就是 HashMap 的插入流程，是不是覺得很簡單。當然，大家先别高興。這隻是一個簡化版的插入流程，真正的插入流程要複雜不少。首先 HashMap 是變長集合，是以需要考慮擴容的問題。其次，在 JDK 1.8 中，HashMap 引入了紅黑樹優化過長連結清單，這裡還要考慮多長的連結清單需要進行優化，優化過程又是怎樣的問題。引入這裡兩個問題後，大家會發現原本簡單的操作，現在略顯複雜了。在本節中，我将先分析插入操作的源碼，擴容、樹化（連結清單轉為紅黑樹，下同）以及其他和樹結構相關的操作，随後将在獨立的兩小結中進行分析。接下來，先來看一下插入操作的源碼：
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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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;
}
插入操作的入口方法是 put(K,V)，但核心邏輯在V putVal(int, K, V, boolean, boolean) 方法中。putVal 方法主要做了這麼幾件事情：
- 當桶數組 table 為空時，通過擴容的方式初始化 table
- 查找要插入的鍵值對是否已經存在，存在的話根據條件判斷是否用新值替換舊值
- 如果不存在，則将鍵值對鍊傳入連結表中，并根據連結清單長度決定是否将連結清單轉為紅黑樹
- 判斷鍵值對數量是否大于門檻值，大于的話則進行擴容操作
以上就是 HashMap 插入的邏輯，并不是很複雜，這裡就不多說了。接下來來分析一下擴容機制。
3.5 擴容機制
在 Java 中，數組的長度是固定的，這意味着數組隻能存儲固定量的資料。但在開發的過程中，很多時候我們無法知道該建多大的數組合适。建小了不夠用，建大了用不完，造成浪費。如果我們能實作一種變長的數組，并按需配置設定空間就好了。好在，我們不用自己實作變長數組，Java 集合架構已經實作了變長的資料結構。比如 ArrayList 和 HashMap。對于這類基于數組的變長資料結構，擴容是一個非常重要的操作。下面就來聊聊 HashMap 的擴容機制。
在詳細分析之前，先來說一下擴容相關的背景知識：
在 HashMap 中，桶數組的長度均是2的幂，門檻值大小為桶數組長度與負載因子的乘積。當 HashMap 中的鍵值對數量超過門檻值時，進行擴容。
HashMap 的擴容機制與其他變長集合的套路不太一樣，HashMap 按目前桶數組長度的2倍進行擴容，門檻值也變為原來的2倍（如果計算過程中，門檻值溢出歸零，則按門檻值公式重新計算）。擴容之後，要重新計算鍵值對的位置，并把它們移動到合适的位置上去。以上就是 HashMap 的擴容大緻過程，接下來我們來看看具體的實作：
final Node<K,V>[] resize() {
Node<K,V>[] 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 如果舊的桶數組不為空，則周遊桶數組，并将鍵值對映射到新的桶數組中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> 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;
}
上面的源碼有點長，希望大家耐心看懂它的邏輯。上面的源碼總共做了3件事，分别是：
- 計算新桶數組的容量 newCap 和新門檻值 newThr
- 根據計算出的 newCap 建立新的桶數組，桶數組 table 也是在這裡進行初始化的
- 将鍵值對節點重新映射到新的桶數組裡。如果節點是 TreeNode 類型，則需要拆分紅黑樹。如果是普通節點，則節點按原順序進行分組。
上面列的三點中，建立新的桶數組就一行代碼，不用說了。接下來，來說說第一點和第三點，先說說 newCap 和 newThr 計算過程。該計算過程對應 resize 源碼的第一和第二個條件分支，如下：
// 第一個條件分支
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 > 0 | threshold > 0，且桶數組未被初始化 | 調用 HashMap(int) 和 HashMap(int, float) 構造方法時會産生這種情況，此種情況下 newCap = oldThr，newThr 在第二個條件分支中算出 |
| oldCap == 0 && oldThr == 0 | 桶數組未被初始化，且 threshold 為 0 | 調用 HashMap() 構造方法會産生這種情況。 |
這裡把oldThr > 0情況單獨拿出來說一下。在這種情況下，會将 oldThr 指派給 newCap，等價于newCap = threshold = tableSizeFor(initialCapacity)。我們在初始化時傳入的 initialCapacity 參數經過 threshold 中轉最終指派給了 newCap。這也就解答了前面提的一個疑問：initialCapacity 參數沒有被儲存下來，那麼它怎麼參與桶數組的初始化過程的呢？
嵌套分支：
| 條件 | 覆寫情況 | 備注 |
|---|---|---|
| oldCap >= 230 | 桶數組容量大于或等于最大桶容量 230 | 這種情況下不再擴容 |
| newCap < 230 && oldCap > 16 | 新桶數組容量小于最大值，且舊桶數組容量大于 16 | 該種情況下新門檻值 newThr = oldThr << 1，移位可能會導緻溢出 |
這裡簡單說明一下移位導緻的溢出情況，當 loadFactor小數位為 0，整數位可被2整除且大于等于8時，在某次計算中就可能會導緻 newThr 溢出歸零。見下圖：
分支二：
| 條件 | 覆寫情況 | 備注 |
|---|---|---|
| newThr == 0 | 第一個條件分支未計算 newThr 或嵌套分支在計算過程中導緻 newThr 溢出歸零 |
說完 newCap 和 newThr 的計算過程，接下來再來分析一下鍵值對節點重新映射的過程。
在 JDK 1.8 中，重新映射節點需要考慮節點類型。對于樹形節點，需先拆分紅黑樹再映射。對于連結清單類型節點，則需先對連結清單進行分組，然後再映射。需要的注意的是，分組後，組内節點相對位置保持不變。關于紅黑樹拆分的邏輯将會放在下一小節說明，先來看看連結清單是怎樣進行分組映射的。
我們都知道往底層資料結構中插入節點時，一般都是先通過模運算計算桶位置，接着把節點放入桶中即可。事實上，我們可以把重新映射看做插入操作。在 JDK 1.7 中，也确實是這樣做的。但在 JDK 1.8 中，則對這個過程進行了一定的優化，邏輯上要稍微複雜一些。在詳細分析前，我們先來回顧一下 hash 求餘的過程：
上圖中，桶數組大小 n = 16，hash1 與 hash2 不相等。但因為隻有後4位參與求餘，是以結果相等。當桶數組擴容後，n 由16變成了32，對上面的 hash 值重新進行映射：
擴容後，參與模運算的位數由4位變為了5位。由于兩個 hash 第5位的值是不一樣，是以兩個 hash 算出的結果也不一樣。上面的計算過程并不難了解，繼續往下分析。
假設我們上圖的桶數組進行擴容，擴容後容量 n = 16，重新映射過程如下:
依次周遊連結清單，并計算節點 hash & oldCap 的值。如下圖所示
如果值為0，将 loHead 和 loTail 指向這個節點。如果後面還有節點 hash & oldCap 為0的話，則将節點鍊入 loHead 指向的連結清單中，并将 loTail 指向該節點。如果值為非0的話，則讓 hiHead 和 hiTail 指向該節點。完成周遊後，可能會得到兩條連結清單，此時就完成了連結清單分組：
最後再将這兩條連結存放到相應的桶中，完成擴容。如下圖：
從上圖可以發現，重新映射後，兩條連結清單中的節點順序并未發生變化，還是保持了擴容前的順序。以上就是 JDK 1.8 中 HashMap 擴容的代碼講解。另外再補充一下，JDK 1.8 版本下 HashMap 擴容效率要高于之前版本。如果大家看過 JDK 1.7 的源碼會發現，JDK 1.7 為了防止因 hash 碰撞引發的拒絕服務攻擊，在計算 hash 過程中引入随機種子。以增強 hash 的随機性，使得鍵值對均勻分布在桶數組中。在擴容過程中，相關方法會根據容量判斷是否需要生成新的随機種子，并重新計算所有節點的 hash。而在 JDK 1.8 中，則通過引入紅黑樹替代了該種方式。進而避免了多次計算 hash 的操作，提高了擴容效率。
本小節的内容講就先講到這，接下來，來講講連結清單與紅黑樹互相轉換的過程。
3.5.1 連結清單樹化、紅黑樹鍊化與拆分
JDK 1.8 對 HashMap 實作進行了改進。最大的改進莫過于在引入了紅黑樹處理頻繁的碰撞，代碼複雜度也随之上升。比如，以前隻需實作一套針對連結清單操作的方法即可。而引入紅黑樹後，需要另外實作紅黑樹相關的操作。紅黑樹是一種自平衡的二叉查找樹，本身就比較複雜。本篇文章中并不打算對紅黑樹展開介紹，本文僅會介紹連結清單樹化需要注意的地方。
在展開說明之前，先把樹化的相關代碼貼出來，如下：
static final int TREEIFY_THRESHOLD = 8;
/**
* 當桶數組容量小于該值時，優先進行擴容，而不是樹化
*/
static final int MIN_TREEIFY_CAPACITY = 64;
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
/**
* 将普通節點連結清單轉換成樹形節點連結清單
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> 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<K,V> hd = null, tl = null;
do {
// 将普通節點替換成樹形節點
TreeNode<K,V> 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<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
在擴容過程中，樹化要滿足兩個條件：
- 連結清單長度大于等于 TREEIFY_THRESHOLD
- 桶數組容量大于等于 MIN_TREEIFY_CAPACITY
第一個條件比較好了解，這裡就不說了。這裡來說說加入第二個條件的原因，個人覺得原因如下：
當桶數組容量比較小時，鍵值對節點 hash 的碰撞率可能會比較高，進而導緻連結清單長度較長。這個時候應該優先擴容，而不是立馬樹化。畢竟高碰撞率是因為桶數組容量較小引起的，這個是主因。容量小時，優先擴容可以避免一些列的不必要的樹化過程。同時，桶容量較小時，擴容會比較頻繁，擴容時需要拆分紅黑樹并重新映射。是以在桶容量比較小的情況下，将長連結清單轉成紅黑樹是一件吃力不讨好的事。
回到上面的源碼中，我們繼續看一下 treeifyBin 方法。該方法主要的作用是将普通連結清單轉成為由 TreeNode 型節點組成的連結清單，并在最後調用 treeify 是将該連結清單轉為紅黑樹。TreeNode 繼承自 Node 類，是以 TreeNode 仍然包含 next 引用，原連結清單的節點順序最終通過 next 引用被儲存下來。我們假設樹化前，連結清單結構如下：
HashMap 在設計之初，并沒有考慮到以後會引入紅黑樹進行優化。是以并沒有像 TreeMap 那樣，要求鍵類實作 comparable 接口或提供相應的比較器。但由于樹化過程需要比較兩個鍵對象的大小，在鍵類沒有實作 comparable 接口的情況下，怎麼比較鍵與鍵之間的大小了就成了一個棘手的問題。為了解決這個問題，HashMap 是做了三步處理，確定可以比較出兩個鍵的大小，如下：
- 比較鍵與鍵之間 hash 的大小，如果 hash 相同，繼續往下比較
- 檢測鍵類是否實作了 Comparable 接口，如果實作調用 compareTo 方法進行比較
- 如果仍未比較出大小，就需要進行仲裁了，仲裁方法為 tieBreakOrder（大家自己看源碼吧）
tie break 是網球術語，可以了解為加時賽的意思，起這個名字還是挺有意思的。
通過上面三次比較，最終就可以比較出孰大孰小。比較出大小後就可以構造紅黑樹了，最終構造出的紅黑樹如下：
橙色的箭頭表示 TreeNode 的 next 引用。由于空間有限，prev 引用未畫出。可以看出，連結清單轉成紅黑樹後，原連結清單的順序仍然會被引用仍被保留了（紅黑樹的根節點會被移動到連結清單的第一位），我們仍然可以按周遊連結清單的方式去周遊上面的紅黑樹。這樣的結構為後面紅黑樹的切分以及紅黑樹轉成連結清單做好了鋪墊，我們繼續往下分析。
3.5.2 紅黑樹拆分
擴容後，普通節點需要重新映射，紅黑樹節點也不例外。按照一般的思路，我們可以先把紅黑樹轉成連結清單，之後再重新映射連結清單即可。這種處理方式是大家比較容易想到的，但這樣做會損失一定的效率。不同于上面的處理方式，HashMap 實作的思路則是上好佳（上好佳請把廣告費打給我）。如上節所說，在将普通連結清單轉成紅黑樹時，HashMap 通過兩個額外的引用 next 和 prev 保留了原連結清單的節點順序。這樣再對紅黑樹進行重新映射時，完全可以按照映射連結清單的方式進行。這樣就避免了将紅黑樹轉成連結清單後再進行映射，無形中提高了效率。
以上就是紅黑樹拆分的邏輯，下面看一下具體實作吧：
// 紅黑樹轉連結清單門檻值
static final int UNTREEIFY_THRESHOLD = 6;
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
/*
* 紅黑樹節點仍然保留了 next 引用，故仍可以按連結清單方式周遊紅黑樹。
* 下面的循環是對紅黑樹節點進行分組，與上面類似
*/
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)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 連結清單樹化。舉個例子說明一下，假設擴容後，重新映射上圖的紅黑樹，映射結果如下：
3.5.3 紅黑樹鍊化
前面說過，紅黑樹中仍然保留了原連結清單節點順序。有了這個前提，再将紅黑樹轉成連結清單就簡單多了，僅需将 TreeNode 連結清單轉成 Node 類型的連結清單即可。相關代碼如下：
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
// 周遊 TreeNode 連結清單，并用 Node 替換
for (Node<K,V> q = this; q != null; q = q.next) {
// 替換節點類型
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
上面的代碼并不複雜，不難了解，這裡就不多說了。到此擴容相關内容就說完了，不知道大家了解沒。
3.6 删除
如果大家堅持看完了前面的内容，到本節就可以輕松一下。當然，前提是不去看紅黑樹的删除操作。不過紅黑樹并非本文講解重點，本節中也不會介紹紅黑樹相關内容，是以大家不用擔心。
HashMap 的删除操作并不複雜，僅需三個步驟即可完成。第一步是定位桶位置，第二步周遊連結清單并找到鍵值相等的節點，第三步删除節點。相關源碼如下：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
// 1. 定位桶位置
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> 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<K,V>)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<K,V>)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;
}
删除操作本身并不複雜，有了前面的基礎，了解起來也就不難了，這裡就不多說了。
3.7 其他細節
前面的内容分析了 HashMap 的常用操作及相關的源碼，本節内容再補充一點其他方面的東西。
3.7.1 被 transient 所修飾 table 變量
如果大家細心閱讀 HashMap 的源碼，會發現桶數組 table 被申明為 transient。transient 表示易變的意思，在 Java 中，被該關鍵字修飾的變量不會被預設的序列化機制序列化。我們再回到源碼中，考慮一個問題：桶數組 table 是 HashMap 底層重要的資料結構，不序列化的話，别人還怎麼還原呢？
這裡簡單說明一下吧，HashMap 并沒有使用預設的序列化機制，而是通過實作readObject/writeObject兩個方法自定義了序列化的内容。這樣做是有原因的，試問一句，HashMap 中存儲的内容是什麼？不用說，大家也知道是鍵值對。是以隻要我們把鍵值對序列化了，我們就可以根據鍵值對資料重建 HashMap。有的朋友可能會想，序列化 table 不是可以一步到位，後面直接還原不就行了嗎？這樣一想，倒也是合理。但序列化 talbe 存在着兩個問題：
- table 多數情況下是無法被存滿的，序列化未使用的部分，浪費空間
- 同一個鍵值對在不同 JVM 下，所處的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能會發生錯誤。
以上兩個問題中，第一個問題比較好了解，第二個問題解釋一下。HashMap 的get/put/remove等方法第一步就是根據 hash 找到鍵所在的桶位置，但如果鍵沒有覆寫 hashCode 方法，計算 hash 時最終調用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不同的 JVM 下，可能會有不同的實作，産生的 hash 可能也是不一樣的。也就是說同一個鍵在不同平台下可能會産生不同的 hash，此時再對在同一個 table 繼續操作，就會出現問題。
綜上所述，大家應該能明白 HashMap 不序列化 table 的原因了。
4.總結
本章對 HashMap 常見操作相關代碼進行了詳細分析，并在最後補充了一些其他細節。在本章中，插入操作一節的内容說的最多，主要是因為插入操作涉及的點特别多，一環扣一環。包含但不限于“table 初始化、擴容、樹化”等，總體來說，插入操作分析起來難度還是很大的。好在，最後分析完了。
本章篇幅雖比較大，但仍未把 HashMap 所有的點都分析到。比如，紅黑樹的增删查等操作。當然，我個人看來，以上的分析已經夠了。畢竟大家是類庫的使用者而不是設計者，沒必要去弄懂每個細節。是以如果某些細節實在看不懂的話就跳過吧，對我們開發來說，知道 HashMap 大緻原理即可。
好了，本章到此結束。
寫在最後
寫到這裡終于可以松一口氣了，這篇文章前前後後花了我一周多的時間。在我寫這篇文章之前，對 HashMap 認識僅限于原理層面，并未深入了解。一開始，我覺得關于 HashMap 沒什麼好寫的，畢竟大家對 HashMap 多少都有一定的了解。但等我深入閱讀 HashMap 源碼後，發現之前的認知是錯的。不是沒什麼可寫的，而是可寫的點太多了，不知道怎麼寫了。JDK 1.8 版本的 HashMap 實作上比之前版本要複雜的多，想弄懂衆多的細節難度還是不小的。僅自己弄懂還不夠，還要寫出來，難度就更大了，本篇文章基本上是在邊讀源碼邊寫的狀态下完成的。由于時間和能力有限，加之文章篇幅比較大，很難保證不出錯分析過程及配圖不出錯。如果有錯誤，希望大家指出來，我會及時修改，這裡先謝謝大家。
好了，本文就到這裡了，謝謝大家的閱讀！
源自
https://segmentfault.com/a/1190000012926722#comment-area