Categories
程式開發

Java源碼系列4——HashMap擴容時究竟對鍊錶和紅黑樹做了什麼?


我們知道HashMap 的底層是由數組,鍊錶,紅黑樹組成的,在HashMap 做擴容操作時,除了把數組容量擴大為原來的兩倍外,還會對所有元素重新計算hash 值,因為長度擴大以後,hash值也隨之改變。

如果是簡單的Node 對象,只需要重新計算下標放進去就可以了,如果是鍊錶和紅黑樹,那麼操作就會比較複雜,下面我們就來看下,JDK1.8 下的HashMap 在擴容時對鍊錶和紅黑樹做了哪些優化?

rehash 時,鍊錶怎麼處理?

假設一個HashMap 原本bucket 大小為16。下標3 這個位置上的19, 3, 35 由於索引衝突組成鍊錶。

Java源碼系列4——HashMap擴容時究竟對鍊錶和紅黑樹做了什麼? 1

當HashMap 由16 擴容到32 時,19, 3, 35 重新hash 之後拆成兩條鍊錶。

Java源碼系列4——HashMap擴容時究竟對鍊錶和紅黑樹做了什麼? 2

查看JDK1.8 HashMap 的源碼,我們可以看到關於鍊錶的優化操作如下:

// 把原有链表拆成两个链表
// 链表1存放在低位(原索引位置)
Node loHead = null, loTail = null;
// 链表2存放在高位(原索引 + 旧数组长度)
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
// 链表1
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 链表2
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 链表1存放于原索引位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 链表2存放原索引加上旧数组长度的偏移量
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}

正常我們是把所有元素都重新計算一下下標值,再決定放入哪個桶,JDK1.8 優化成直接把鍊錶拆成高位和低位兩條,通過位運算來決定放在原索引處或者原索引加原數組長度的偏移量處。我們通過位運算來分析下。

先回顧一下原hash 的求餘過程:

Java源碼系列4——HashMap擴容時究竟對鍊錶和紅黑樹做了什麼? 3

再看一下rehash 時,判斷時做的位操作,也就是這句e.hash & oldCap:

Java源碼系列4——HashMap擴容時究竟對鍊錶和紅黑樹做了什麼? 4

再看下擴容後的實際求餘過程:

Java源碼系列4——HashMap擴容時究竟對鍊錶和紅黑樹做了什麼? 5

這波操作是不是很666,為什麼2 的整數冪- 1可以作& 操作可以代替求餘計算,因為2 的整數冪- 1 的二進制比較特殊,就是一串11111,與這串數字1 作& 操作,結果就是保留下原數字的低位,去掉原數字的高位,達到求餘的效果。 2 的整數冪的二進制也比較特殊,就是一個1 後面跟上一串0。

HashMap 的擴容都是擴大為原來大小的兩倍,從二進制上看就是給這串數字加個0,比如16 -> 32 = 10000 -> 100000,那麼他的n – 1 就是15 -> 32 = 1111 -> 11111。也就是多了一位,所以擴容後的下標可以從原有的下標推算出來。差異就在於上圖我標紅的地方,如果標紅處是0,那麼擴容後再求餘結果不變,如果標紅處是1,那麼擴容後再求餘就為原索引+ 原偏移量。如何判斷標紅處是0 還是1,就是把e.hash & oldCap。

rehash 時,紅黑樹怎麼處理?

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;

// 扩容操作
final Node[] resize() {
// ....
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
// ...
}

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;
/**
* TreeNode 是间接继承于 Node,保留了 next,可以像链表一样遍历
* 这里的操作和链表的一毛一样
*/
for (TreeNode e = b, next; e != null; e = next) {
next = (TreeNode)e.next;
e.next = null;
// bit 就是 oldCap
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 { /** * hiHead == null 时,表明扩容后, * 所有节点仍在原位置,树结构不变,无需重新树化 */ 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); } } }

從源碼可以看出,紅黑樹的拆分和鍊錶的邏輯基本一致,不同的地方在於,重新映射後,會將紅黑樹拆分成兩條鍊錶,根據鍊錶的長度,判斷需不需要把鍊錶重新進行樹化。

源碼系列文章

Java源碼系列1——ArrayList

Java源碼系列2——HashMap

Java源碼系列3——LinkedHashMap

Java源碼系列4——HashMap擴容時究竟對鍊錶和紅黑樹做了什麼?

參考

HashMap 源碼詳細分析(JDK1.8)

本文首發於我的個人博客https://chaohang.top作者張小超"轉載請註明出處

歡迎關注我的微信公眾號【超超不會飛】,獲取第一時間的更新。

Java源碼系列4——HashMap擴容時究竟對鍊錶和紅黑樹做了什麼? 6