在 Java8 中，HashMap 由數組+連結清單+紅黑樹組成的。

擴容時，數組容量翻倍，數組中每一個桶中的多個節點（鍊結構或樹結構）都需要 rehash 遷移到新的數組中去。

本文通過閱讀 JDK8 中 HashMap 的 resize 方法了解其擴容原理，對桶節點的遷移算法進行單元測試，畫圖以友善了解。

本文基于 jdk1.8.0_91

文章目錄

1. 擴容的時機
2. 擴容的源碼
- 如果是鍊結構
- 如果是樹結構
3. 連結清單遷移算法
- 執行結果
- 執行過程圖示

1. 擴容的時機

HashMap 中 put 入第一個元素，初始化數組 table。
HashMap 中的元素數量大于門檻值 threshold。

threshold = capacity * load factor。

當 size > threshold 時，觸發 rehash。

2. 擴容的源碼

HashMap 中的 resize 方法主要包含兩部分邏輯：

初始化數組 table，并設定門檻值。
數組容量翻倍，将元素遷移到新數組。

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {
	Node<K,V>[] oldTab = table;
	int oldCap = (oldTab == null) ? 0 : oldTab.length;
	int oldThr = threshold;
	int newCap, newThr = 0;
	if (oldCap > 0) { // 第一次進來，table為null，oldCap為0，不會進入這裡
		if (oldCap >= MAXIMUM_CAPACITY) { // 擴容前的數組大小如果已經達到最大(2^30)了
			threshold = Integer.MAX_VALUE; // 取整型最大值(2^31-1)，這樣以後就不會擴容了
			return oldTab;
		}
		else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // oldCap翻倍得到newCap
				 oldCap >= DEFAULT_INITIAL_CAPACITY)
			newThr = oldThr << 1; // double threshold
	}
	else if (oldThr > 0) // initial capacity was placed in threshold // 第一次進來，如果手動設定了初始容量initialCapacity，這裡為true，則将threshold作為初始容量
		newCap = oldThr;
	else {               // zero initial threshold signifies using defaults // 如果沒有手動設定initialCapacity，則設為預設值16
		newCap = DEFAULT_INITIAL_CAPACITY;
		newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}
	if (newThr == 0) { // 第一次進來，這裡必為true，重新計算 threshold = capacity * Load factor
		float ft = (float)newCap * loadFactor;
		newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
				  (int)ft : Integer.MAX_VALUE);
	}
	threshold = newThr;
	@SuppressWarnings({"rawtypes","unchecked"})
		Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
	table = newTab;
	if (oldTab != null) { // 對oldTab中所有元素進行rehash。由于每次擴容是2次幂的擴充(指數組長度/桶數量擴為原來2倍)，是以，元素的位置要麼是在原位置，要麼是在原位置再移動2次幂的位置
		for (int j = 0; j < oldCap; ++j) {
			Node<K,V> e;
			if ((e = oldTab[j]) != null) { // 數組j位置的元素不為空，需要該位置上的所有元素進行rehash
				oldTab[j] = null;
				if (e.next == null) // 桶中隻有一個元素，則直接rehash
					newTab[e.hash & (newCap - 1)] = e;
				else if (e instanceof TreeNode) // 桶中是樹結構
					((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
				else { // preserve order // 桶中是連結清單結構（JDK1.7中舊連結清單遷移新連結清單的時候，用的是頭插法，如果在新表的數組索引位置相同，則連結清單元素會倒置；但是JDK1.8不會倒置，用的是雙指針）
					Node<K,V> loHead = null, loTail = null; // low位連結清單，其桶位置不變，head和tail分别代表首尾指針
					Node<K,V> hiHead = null, hiTail = null; // high位連結清單，其桶位于追加後的新數組中
					Node<K,V> next;
					do {
						next = e.next;
						if ((e.hash & oldCap) == 0) { // 是0的話索引沒變，是1的話索引變成“原索引+oldCap”
							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; // 原索引+oldCap
					}
				}
			}
		}
	}
	return newTab;
}

在 Java8 中，HashMap 中的桶可能是連結清單結構，也可能是樹結構。

從網上找來一張圖，直覺展示 HashMap 結構：

閱讀 JDK 源碼：HashMap 擴容總結及圖解1. 擴容的時機2. 擴容的源碼3. 連結清單遷移算法

如果是鍊結構

将舊連結清單拆分成兩條新的連結清單，通過

e.hash & oldCap

來計算新連結清單在擴容後的數組中的新下标。

當 e.hash & oldCap = 0，則節點在新數組中的索引值與舊索引值相同。

當 e.hash & oldCap = 1，則節點在新數組中的索引值為舊索引值+舊數組容量。

對

e.hash & oldCap

公式的推導見上一篇文章《HashMap中的取模和擴容公式推導》

如果是樹結構

HashMap 對樹結構的定義如下：

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);
	}
}

需要明确的是：TreeNode 既是一個紅黑樹結構，也是一個雙連結清單結構。

判斷節點

e instanceof TreeNode

為 true，則調用 HashMap.TreeNode#split 方法對樹進行拆分，而拆分主要用的是 TreeNode 的連結清單屬性。

拆分代碼如下：

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; // 用于決定紅黑樹是否要轉回連結清單
	for (TreeNode<K,V> e = b, next; e != null; e = next) { // 對節點e進行周遊（首先明确：TreeNode既是一個紅黑樹結構，也是一個雙連結清單結構）
		next = (TreeNode<K,V>)e.next;
		e.next = null; // 把e的下一個節點指派給next後，斷開e與e.next節點
		if ((e.hash & bit) == 0) { // 原索引
			if ((e.prev = loTail) == null)
				loHead = e;
			else
				loTail.next = e;
			loTail = e;
			++lc;
		}
		else { // 原索引 + oldCap
			if ((e.prev = hiTail) == null)
				hiHead = e;
			else
				hiTail.next = e;
			hiTail = e;
			++hc;
		}
	}

	if (loHead != null) {
		if (lc <= UNTREEIFY_THRESHOLD)
			tab[index] = loHead.untreeify(map); // 轉為鍊結構
		else {
			tab[index] = loHead;
			if (hiHead != null) // (else is already treeified)
				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);
		}
	}
}

3. 連結清單遷移算法

Java8 中如何遷移桶中的連結清單呢？

這裡建構一個連結清單

A->B->C

來進行調試，應用 HashMap 中的擴容算法，擴容的時候，會将該連結清單拆分成兩個新的連結清單。

單元測試代碼如下：

/**
 * 舊連結清單資料遷移至新連結清單
 * 本例中，桶的數量由1擴容為2.
 * 
 * @author Sumkor https://segmentfault.com/blog/sumkor
 * @since 2021/2/28
 */
@Test
public void resizeLink() {
	int oldCap = 1;
	int newCap = 2;
	Node[] oldTable = new Node[oldCap];
	Node[] newTable = new Node[newCap];

	// A -> B -> C
	Node firstLinkNode03 = new Node(new Integer(3).hashCode(), 3, "C", null);
	Node firstLinkNode02 = new Node(new Integer(2).hashCode(), 2, "B", firstLinkNode03);
	Node firstLinkNode01 = new Node(new Integer(1).hashCode(), 1, "A", firstLinkNode02);
	oldTable[0] = firstLinkNode01;
	// print
	System.out.println("--------------------------");
	System.out.println("原連結清單：");
	printTable(oldTable);
	System.out.println("--------------------------");

	/**
	 * HashMap中resize遷移算法
	 * @see HashMap#resize()
	 */
	for (int j = 0; j < oldCap; ++j) {
		Node loHead = null, loTail = null; // low位連結清單，其桶位置不變，head和tail分别代表首尾指針
		Node hiHead = null, hiTail = null; // high位連結清單，其桶位于追加後的新數組中
		Node e = oldTable[j];// 将要處理的元素
		Node next;
		do {
			next = e.next;
			if ((e.hash & oldCap) == 0) { // 是0的話索引沒變，是1的話索引變成“原索引+oldCap”
				if (loTail == null)
					loHead = e; // 總是指向頭結點
				else
					loTail.next = e; // 把loTail.next指向e。
				loTail = e;
			} else {
				if (hiTail == null)
					hiHead = e;
				else
					hiTail.next = e; // 把hiTail.next指向e。若hiTail.next原先并不指向e，該操作會改變oldTable[j]上的舊連結清單結構
				hiTail = e; // 把hiTail指向e所指向的節點
			}
		} while ((e = next) != null);
		if (loTail != null) {
			loTail.next = null; // 這一步是必須的，loTail.next有可能還其他節點，需要設為null
			newTable[j] = loHead; // 原索引
		}
		if (hiTail != null) {
			hiTail.next = null;
			newTable[j + oldCap] = hiHead; // 原索引+oldCap
		}
	}
	System.out.println("新連結清單：");
	printTable(newTable);
	System.out.println("--------------------------");
}

其中，采用 HashMap 中的 Node 結構作為連結清單節點：

/**
 * HashMap 中的 Node 結構
 */
static class Node<K, V> implements Map.Entry<K, V> {
	final int hash;
	final K key;
	V value;
	Node<K, V> next;

	Node(int hash, K key, V value, Node<K, V> 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;
	}
}

對數組 table 上的連結清單結構進行列印：

/**
 * HashMap 中的 Node 結構，列印
 */
private void printTable(Node[] table) {
	for (int i = 0; i < table.length; i++) {
		Node tmpNode = table[i];// 用于列印，不改變table的結構
		while (tmpNode != null) {
			System.out.print(tmpNode + " -> ");
			tmpNode = tmpNode.next;
		}
		System.out.println();
	}
}

執行結果

--------------------------
原連結清單：
1=A -> 2=B -> 3=C -> 
--------------------------
新連結清單：
2=B -> 
1=A -> 3=C -> 
--------------------------

注意到，遷移之後，節點 C 依舊排在節點 A 之後，而不是反過來。

在 Java8 中，HashMap 插入元素使用尾插法，擴容時使用了首尾指針保證了連結清單元素順序不會倒置，進而解決了 Java7 擴容時産生的環問題。

執行過程圖示

第一、二次循環之後，高低位連結清單指針如下：

閱讀 JDK 源碼：HashMap 擴容總結及圖解1. 擴容的時機2. 擴容的源碼3. 連結清單遷移算法

第三次循環，由于

hiTail != null

，是以執行

hiTail.next = e

，注意此時 B 依舊指向 C。

閱讀 JDK 源碼：HashMap 擴容總結及圖解1. 擴容的時機2. 擴容的源碼3. 連結清單遷移算法

接着執行

hiTail = e

，把 hiTail 指向 e 所在節點。

最後執行

loTail.next = null

和

hiTail.next = null

，把尾指針都指向 null。

閱讀 JDK 源碼：HashMap 擴容總結及圖解1. 擴容的時機2. 擴容的源碼3. 連結清單遷移算法

閱讀 JDK 源碼：HashMap 擴容總結及圖解1. 擴容的時機2. 擴容的源碼3. 連結清單遷移算法

文章目錄

1. 擴容的時機

2. 擴容的源碼

如果是鍊結構

如果是樹結構

3. 連結清單遷移算法

執行結果

執行過程圖示

繼續閱讀

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

JBoss,Geronimo和Glassfish初窺

scala (3) Function 和 Method