文章目錄
- 1. 前言
- 2.基本屬性
- 3. 定位哈希桶數組索引位置
- 4. get 方法
-
- 4.1 代碼塊1:getTreeNode
- 4.2 代碼塊2:find
- 4.2 代碼塊3:comparableClassFor
- 5. put 方法
-
- 5.1 代碼塊4:putTreeVal
-
- 5.1.1 代碼塊5:tieBreakOrder
- 5.2 代碼塊6:treeifyBin
-
- 5.2.1 代碼塊7:treeify
-
- 5.2.1.1 代碼塊8:moveRootToFront
-
- 5.2.1.1.1 代碼塊9:checkInvariants
- 6. resize 方法
-
- 6.1 代碼塊10:split
-
- 6.1.1 代碼塊11:untreeify
- 6.2 疑問1 擴容後,節點重 hash 為什麼隻可能分布在 “原索引位置” 與 “原索引 + oldCap 位置” ?
- 7. 總結
1. 前言
JDK 1.8 對 HashMap 進行了比較大的優化,底層實作由之前的 “
數組+連結清單
” 改為 “
數組+連結清單+紅黑樹
”,本文就 HashMap 的幾個常用的重要方法和 JDK 1.8 之前的死循環問題展開學習讨論。
JDK 1.8 的 HashMap 的資料結構如下圖所示,當連結清單節點較少時仍然是以連結清單存在,當連結清單節點較多時(大于8)會轉為紅黑樹。
幾個要點:
先了解以下幾個點,有利于更好的了解 HashMap 的源碼和閱讀本文。
1、本文中
頭節點
指的是 table 表上索引位置的節點,也就是連結清單的頭節點。
2、
根節點
(root 節點)指的是紅黑樹最上面的那個節點,也就是沒有父節點的節點。
3、紅黑樹的根節點
不一定
是索引位置的
頭節點
(也就是連結清單的頭節點),HashMap 通過 moveRootToFront 方法來維持紅黑樹的根結點就是索引位置的頭結點,但是在 removeTreeNode 方法中,當 movable 為 false 時,不會調用 moveRootToFront 方法,此時紅黑樹的根節點
不一定
是索引位置的頭節點,該場景發生在 HashIterator 的 remove 方法中。
4、
轉為紅黑樹節點後,連結清單的結構還存在
,通過 next 屬性維持,紅黑樹節點在進行操作時都會維護連結清單的結構,并不是轉為紅黑樹節點,連結清單結構就不存在了。
5、
在紅黑樹上,葉子節點也可能有 next 節點
,因為紅黑樹的結構跟連結清單的結構是互不影響的,不會因為是葉子節點就說該節點已經沒有 next 節點。
6、源碼中一些變量定義:如果定義了一個節點 p,則 pl(p left)為 p 的左節點,pr(p right)為 p 的右節點,pp(p parent)為 p 的父節點,ph(p hash)為 p 的 hash 值,pk(p key)為 p 的 key 值,kc(key class)為 key 的類等等。源碼中很喜歡在 if/for 等語句中進行指派并判斷,請注意。
7、連結清單中移除一個節點隻需如下圖操作,其他操作同理。
8、紅黑樹在維護連結清單結構時,移除一個節點隻需如下圖操作(紅黑樹中增加了一個 prev 屬性),其他操作同理。注:此處隻是紅黑樹維護連結清單結構的操作,紅黑樹還需要單獨進行紅黑樹的移除或者其他操作。
9、源碼中進行紅黑樹的查找時,會反複用到以下兩條規則:1)如果目标節點的 hash 值小于 p 節點的 hash 值,則向 p 節點的左邊周遊;否則向 p 節點的右邊周遊。2)如果目标節點的 key 值小于 p 節點的 key 值,則向 p 節點的左邊周遊;否則向 p 節點的右邊周遊。這兩條規則是利用了紅黑樹的特性(左節點 < 根節點 < 右節點)。
10、源碼中進行紅黑樹的查找時,會用 dir(direction)來表示向左還是向右查找,dir 存儲的值是目标節點的 hash/key 與 p 節點的 hash/key 的比較結果。
2.基本屬性
// 預設容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 預設負載因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 連結清單節點轉換紅黑樹節點的門檻值, 9個節點轉
static final int TREEIFY_THRESHOLD = 8;
// 紅黑樹節點轉換連結清單節點的門檻值, 6個節點轉
static final int UNTREEIFY_THRESHOLD = 6;
// 轉紅黑樹時, table的最小長度
static final int MIN_TREEIFY_CAPACITY = 64;
// 連結清單節點, 繼承自Entry
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// ... ...
}
// 紅黑樹節點
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;
// ...
}
需要注意的是
MIN_TREEIFY_CAPACITY=64
,當需要将解決 hash 沖突的連結清單轉變為紅黑樹時,需要判斷下此時數組容量,若是由于數組容量太小(小于 MIN_TREEIFY_CAPACITY )導緻的 hash 沖突太多,則不進行連結清單轉變為紅黑樹操作,轉為利用 resize() 函數優先對 hashMap 擴容
3. 定位哈希桶數組索引位置
不管增加、删除、查找鍵值對,定位到哈希桶數組的位置都是很關鍵的第一步。前面說過 HashMap 的資料結構是“數組+連結清單+紅黑樹”的結合,是以我們當然希望這個 HashMap 裡面的元素位置盡量分布均勻些,盡量使得每個位置上的元素數量隻有一個,那麼當我們用 hash 算法求得這個位置的時候,馬上就可以知道對應位置的元素就是我們要的,不用周遊連結清單/紅黑樹,大大優化了查詢的效率。HashMap 定位數組索引位置,直接決定了 hash 方法的離散性能。下面是定位哈希桶數組的源碼:
// 代碼1
static final int hash(Object key) { // 計算key的hash值
int h;
// 1.先拿到key的hashCode值; 2.将hashCode的高16位參與運算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 代碼2
int n = tab.length;
// 将(tab.length - 1) 與 hash值進行&運算
int index = (n - 1) & hash;
整個過程本質上就是三步:
- 拿到 key 的 hashCode 值
- 将 hashCode 的高位參與運算,重新計算 hash 值
- 将計算出來的 hash 值與 (table.length - 1) 進行 & 運算
方法解讀:
對于任意給定的對象,隻要它的 hashCode() 傳回值相同,那麼計算得到的 hash 值總是相同的。我們首先想到的就是把 hash 值對 table 長度取模運算,這樣一來,元素的分布相對來說是比較均勻的。
但是
模運算消耗還是比較大
的,我們知道
計算機比較快的運算為位運算
,是以 JDK 團隊對取模運算進行了優化,使用上面代碼2的位與運算來代替模運算。這個方法非常巧妙,它通過 “(table.length -1) & h” 來得到該對象的索引位置,這個優化是基于以下公式:x mod 2^n = x & (2^n - 1)。我們知道 HashMap 底層數組的長度總是 2 的 n 次方,并且取模運算為 “h mod table.length”,對應上面的公式,可以得到該運算等同于“h & (table.length - 1)”。這是 HashMap 在速度上的優化,因為 & 比 % 具有更高的效率。
在 JDK1.8 的實作中,還
優化了高位運算的算法
,将 hashCode 的高 16 位與 hashCode 進行異或運算,主要是為了在 table 的 length 較小的時候,讓高位也參與運算,并且不會有太大的開銷。
下圖是一個簡單的例子:
當 table 長度為 16 時,table.length - 1 = 15 ,用二進制來看,此時低 4 位全是 1,高 28 位全是 0,與 0 進行 & 運算必然為 0,是以此時 hashCode 與 “table.length - 1” 的 & 運算結果隻取決于 hashCode 的低 4 位,在這種情況下,hashCode 的高 28 位就沒有任何作用,并且由于 hash 結果隻取決于 hashCode 的低 4 位,hash 沖突的機率也會增加。是以,在 JDK 1.8 中,将高位也參與計算,目的是為了降低 hash 沖突的機率。
4. get 方法
查找相應的節點,并傳回該節點的值。
節點可能是連結清單節點,也可能是紅黑樹節點。
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.對table進行校驗:table不為空 && table長度大于0 &&
// table索引位置(使用table.length - 1和hash值進行位與運算)的節點不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 2.檢查first節點的hash值和key是否和入參的一樣,如果一樣則first即為目标節點,直接傳回first節點
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 3.如果first不是目标節點,并且first的next節點不為空則繼續周遊
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// 4.如果是紅黑樹節點,則調用紅黑樹的查找目标節點方法getTreeNode
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 5.執行連結清單節點的查找,向下周遊連結清單, 直至找到節點的key和入參的key相等時,傳回該節點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 6.找不到符合的傳回空
return null;
}
步驟4 :如果是紅黑樹節點,則調用紅黑樹的查找目标節點方法 getTreeNode,見代碼塊1詳解。
4.1 代碼塊1:getTreeNode
從紅黑樹上查找節點。
final TreeNode<K,V> getTreeNode(int h, Object k) {
// 1.首先找到紅黑樹的根節點;2.使用根節點調用find方法
return ((parent != null) ? root() : this).find(h, k, null);
}
步驟1:首先找到紅黑樹的
根節點
;
步驟2:使用根節點調用 find 方法,見代碼塊2詳解。
4.2 代碼塊2:find
此方法是紅黑樹節點的查找。
/**
* 從調用此方法的節點開始查找, 通過hash值和key找到對應的節點
* 此方法是紅黑樹節點的查找, 紅黑樹是特殊的自平衡二叉查找樹
* 平衡二叉查找樹的特點:左節點<根節點<右節點
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
// 1.将p節點指派為調用此方法的節點,即為紅黑樹根節點
TreeNode<K,V> p = this;
// 2.從p節點開始向下周遊
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
// 3.如果傳入的hash值小于p節點的hash值,則往p節點的左邊周遊
if ((ph = p.hash) > h)
p = pl;
else if (ph < h) // 4.如果傳入的hash值大于p節點的hash值,則往p節點的右邊周遊
p = pr;
// 5.如果傳入的hash值和key值等于p節點的hash值和key值,則p節點為目标節點,傳回p節點
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null) // 6.p節點的左節點為空則将向右周遊
p = pr;
else if (pr == null) // 7.p節點的右節點為空則向左周遊
p = pl;
// 8.将p節點與k進行比較
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) && // 8.1 kc不為空代表k實作了Comparable
(dir = compareComparables(kc, k, pk)) != 0)// 8.2 k<pk則dir<0, k>pk則dir>0
// 8.3 k<pk則向左周遊(p指派為p的左節點), 否則向右周遊
p = (dir < 0) ? pl : pr;
// 9.代碼走到此處, 代表key所屬類沒有實作Comparable, 直接指定向p的右邊周遊
else if ((q = pr.find(h, k, kc)) != null)
return q;
// 10.代碼走到此處代表“pr.find(h, k, kc)”為空, 是以直接向左周遊
else
p = pl;
} while (p != null);
return null;
}
步驟8:将 p 節點與 k 進行比較。如果傳入的 key(即代碼中的參數 k)所屬的類實作了 Comparable 接口(kc 不為空,
comparableClassFor
方法見代碼塊3詳解),則将 k 跟 p 節點的 key 進行比較(kc 實作了 Comparable 接口,是以通過 kc 的比較方法進行比較),并将比較結果指派給 dir,如果 dir<0 則代表 k<pk,則向 p 節點的左邊周遊(pl);否則,向 p 節點的右邊周遊(pr)。
4.2 代碼塊3:comparableClassFor
static Class<?> comparableClassFor(Object x) {
// 1.判斷x是否實作了Comparable接口
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
// 2.校驗x是否為String類型
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
// 3.周遊x實作的所有接口
for (int i = 0; i < ts.length; ++i) {
// 4.如果x實作了Comparable接口,則傳回x的Class
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
5. put 方法
添加一個節點,有可能往連結清單上加,也有可能往紅黑樹上加。
由于存在舊值的情況,此時選擇覆寫,是以,首先要判斷是否存在舊值。
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;
// 1.校驗table是否為空或者length等于0,如果是則調用resize方法進行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2.通過hash值計算索引位置,将該索引位置的頭節點指派給p,如果p為空則直接在該索引位置新增一個節點即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// table表該索引位置不為空,則進行查找
Node<K,V> e; K k;
// 3.判斷p節點的key和hash值是否跟傳入的相等,如果相等, 則p節點即為要查找的目标節點,将p節點指派給e節點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 4.判斷p節點是否為TreeNode, 如果是則調用紅黑樹的putTreeVal方法查找目标節點
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 5.走到這代表p節點為普通連結清單節點,則調用普通的連結清單方法進行查找,使用binCount統計連結清單的節點數
for (int binCount = 0; ; ++binCount) {
// 6.如果p的next節點為空時,則代表找不到目标節點,則新增一個節點并插傳入連結表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 7.校驗節點數是否超過8個,如果超過則調用treeifyBin方法将連結清單節點轉為紅黑樹節點,
// 減一是因為循環是從p節點的下一個節點開始的
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 8.如果e節點存在hash值和key值都與傳入的相同,則e節點即為目标節點,跳出循環
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // 将p指向下一個節點
}
}
// 9.如果e節點不為空,則代表目标節點存在,使用傳入的value覆寫該節點的value,并傳回oldValue
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 用于LinkedHashMap
return oldValue;
}
}
++modCount;
// 10.如果插入節點後節點數超過門檻值,則調用resize方法進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict); // 用于LinkedHashMap
return null;
}
需要注意的步驟:
1.校驗 table 是否為空或者 length 等于0,如果是則調用
resize 方法進行初始化
,見resize方法詳解。
4.如果 p 節點不是目标節點,則判斷 p 節點是否為 TreeNode,如果是則調用紅黑樹的 putTreeVal 方法查找目标節點,見代
碼塊4
詳解。
7.校驗節點數是否超過 8 個,如果超過則調用
treeifyBin
方法 将連結清單節點轉為紅黑樹節點,見代
碼塊6
詳解。
5.1 代碼塊4:putTreeVal
紅黑樹的put操作,紅黑樹插入會同時維護原來的連結清單屬性, 即原來的next屬性。
/**
* 紅黑樹的put操作,紅黑樹插入會同時維護原來的連結清單屬性, 即原來的next屬性
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
// 1.查找根節點, 索引位置的頭節點并不一定為紅黑樹的根節點
TreeNode<K,V> root = (parent != null) ? root() : this;
// 2.将根節點指派給p節點,開始進行查找
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
// 3.如果傳入的hash值小于p節點的hash值,将dir指派為-1,代表向p的左邊查找樹
if ((ph = p.hash) > h)
dir = -1;
// 4.如果傳入的hash值大于p節點的hash值, 将dir指派為1,代表向p的右邊查找樹
else if (ph < h)
dir = 1;
// 5.如果傳入的hash值和key值等于p節點的hash值和key值, 則p節點即為目标節點, 傳回p節點
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 6.如果k所屬的類沒有實作Comparable接口 或者 k和p節點的key相等
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
// 6.1 第一次符合條件, 從p節點的左節點和右節點分别調用find方法進行查找, 如果查找到目标節點則傳回
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
// 6.2 否則使用定義的一套規則來比較k和p節點的key的大小, 用來決定向左還是向右查找
dir = tieBreakOrder(k, pk); // dir<0則代表k<pk,則向p左邊查找;反之亦然
}
TreeNode<K,V> xp = p; // xp指派為x的父節點,中間變量,用于下面給x的父節點指派
// 7.dir<=0則向p左邊查找,否則向p右邊查找,如果為null,則代表該位置即為x的目标位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 走進來代表已經找到x的位置,隻需将x放到該位置即可
Node<K,V> xpn = xp.next; // xp的next節點
// 8.建立新的節點, 其中x的next節點為xpn, 即将x節點插入xp與xpn之間
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
// 9.調整x、xp、xpn之間的屬性關系
if (dir <= 0) // 如果時dir <= 0, 則代表x節點為xp的左節點
xp.left = x;
else // 如果時dir> 0, 則代表x節點為xp的右節點
xp.right = x;
xp.next = x; // 将xp的next節點設定為x
x.parent = x.prev = xp; // 将x的parent和prev節點設定為xp
// 如果xpn不為空,則将xpn的prev節點設定為x節點,與上文的x節點的next節點對應
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 10.進行紅黑樹的插入平衡調整
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
6.1 第一次符合條件,從 p 節點的左節點和右節點分别調用 find 方法(見代碼塊2詳解)進行查找,如果查找到目标節點則傳回
6.2 否則使用定義的一套規則來比較 k 和 p 節點的 key 的大小,用來
決定向左還是向右查找
,見代
碼塊5
詳解。
10.進行紅黑樹的
插入平衡調整
,見
文末的解釋2
。
5.1.1 代碼塊5:tieBreakOrder
定義一套規則用于極端情況下比較兩個參數的大小。
// 用于不可比較或者hashCode相同時進行比較的方法, 隻是一個一緻的插入規則,用來維護重定位的等價性。
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
步驟7:将 table 該索引位置指派為新轉的 TreeNode 的頭節點 hd,如果該節點不為空,則以 hd 為根節點,建構紅黑樹,見代碼塊7詳解。
5.2 代碼塊6:treeifyBin
将連結清單節點轉為紅黑樹節點。
需要注意:連結清單超過8個時,不一定會轉為樹。當需要将解決 hash 沖突的連結清單轉變為紅黑樹時,需要判斷下此時數組容量,若是由于數組容量太小(小于 MIN_TREEIFY_CAPACITY )導緻的 hash 沖突太多,則不進行連結清單轉變為紅黑樹操作,轉為利用 resize() 函數對 hashMap 擴容
/**
* 将連結清單節點轉為紅黑樹節點
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 1.如果table為空或者table的長度小于64, 調用resize方法進行擴容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 2.根據hash值計算索引值,将該索引位置的節點指派給e,從e開始周遊該索引位置的連結清單
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
// 3.将連結清單節點轉紅黑樹節點
TreeNode<K,V> p = replacementTreeNode(e, null);
// 4.如果是第一次周遊,将頭節點指派給hd
if (tl == null) // tl為空代表為第一次循環
hd = p;
else {
// 5.如果不是第一次周遊,則處理目前節點的prev屬性和上一個節點的next屬性
p.prev = tl; // 目前節點的prev屬性設為上一個節點
tl.next = p; // 上一個節點的next屬性設定為目前節點
}
// 6.将p節點指派給tl,用于在下一次循環中作為上一個節點進行一些連結清單的關聯操作(p.prev = tl 和 tl.next = p)
tl = p;
} while ((e = e.next) != null);
// 7.将table該索引位置指派為新轉的TreeNode的頭節點,如果該節點不為空,則以以頭節點(hd)為根節點, 建構紅黑樹
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
7.将 table 該索引位置指派為新轉的 TreeNode 的頭節點 hd,如果該節點不為空,則以 hd 為根節點,建構紅黑樹,見代碼塊7詳解。
5.2.1 代碼塊7:treeify
建構紅黑樹
/**
* 建構紅黑樹
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// 1.将調用此方法的節點指派給x,以x作為起點,開始進行周遊
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next; // next指派為x的下個節點
x.left = x.right = null; // 将x的左右節點設定為空
// 2.如果還沒有根節點, 則将x設定為根節點
if (root == null) {
x.parent = null; // 根節點沒有父節點
x.red = false; // 根節點必須為黑色
root = x; // 将x設定為根節點
}
else {
K k = x.key; // k指派為x的key
int h = x.hash; // h指派為x的hash值
Class<?> kc = null;
// 3.如果目前節點x不是根節點, 則從根節點開始查找屬于該節點的位置
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 4.如果x節點的hash值小于p節點的hash值,則将dir指派為-1, 代表向p的左邊查找
if ((ph = p.hash) > h)
dir = -1;
// 5.如果x節點的hash值大于p節點的hash值,則将dir指派為1, 代表向p的右邊查找
else if (ph < h)
dir = 1;
// 6.走到這代表x的hash值和p的hash值相等,則比較key值
else if ((kc == null && // 6.1 如果k沒有實作Comparable接口 或者 x節點的key和p節點的key相等
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// 6.2 使用定義的一套規則來比較x節點和p節點的大小,用來決定向左還是向右查找
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p; // xp指派為x的父節點,中間變量用于下面給x的父節點指派
// 7.dir<=0則向p左邊查找,否則向p右邊查找,如果為null,則代表該位置即為x的目标位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 8.x和xp節點的屬性設定
x.parent = xp; // x的父節點即為最後一次周遊的p節點
if (dir <= 0) // 如果時dir <= 0, 則代表x節點為父節點的左節點
xp.left = x;
else // 如果時dir > 0, 則代表x節點為父節點的右節點
xp.right = x;
// 9.進行紅黑樹的插入平衡(通過左旋、右旋和改變節點顔色來保證目前樹符合紅黑樹的要求)
root = balanceInsertion(root, x);
break;
}
}
}
}
// 10.如果root節點不在table索引位置的頭節點, 則将其調整為頭節點
moveRootToFront(tab, root);
}
3.如果目前節點 x 不是根節點, 則從根節點開始查找屬于該節點的位置,該段代碼跟代碼塊2和代碼塊4的查找代碼類似。
8.如果 root 節點不在 table 索引位置的頭節點, 則将其調整為頭節點,見代碼塊8詳解。
5.2.1.1 代碼塊8:moveRootToFront
将root放到頭節點的位置
/**
* 将root放到頭節點的位置
* 如果目前索引位置的頭節點不是root節點, 則将root的上一個節點和下一個節點進行關聯,
* 将root放到頭節點的位置, 原頭節點放在root的next節點上
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
// 1.校驗root是否為空、table是否為空、table的length是否大于0
if (root != null && tab != null && (n = tab.length) > 0) {
// 2.計算root節點的索引位置
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// 3.如果該索引位置的頭節點不是root節點,則該索引位置的頭節點替換為root節點
if (root != first) {
Node<K,V> rn;
// 3.1 将該索引位置的頭節點指派為root節點
tab[index] = root;
TreeNode<K,V> rp = root.prev; // root節點的上一個節點
// 3.2 和 3.3 兩個操作是移除root節點的過程
// 3.2 如果root節點的next節點不為空,則将root節點的next節點的prev屬性設定為root節點的prev節點
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
// 3.3 如果root節點的prev節點不為空,則将root節點的prev節點的next屬性設定為root節點的next節點
if (rp != null)
rp.next = rn;
// 3.4 和 3.5 兩個操作将first節點接到root節點後面
// 3.4 如果原頭節點不為空, 則将原頭節點的prev屬性設定為root節點
if (first != null)
first.prev = root;
// 3.5 将root節點的next屬性設定為原頭節點
root.next = first;
// 3.6 root此時已經被放到該位置的頭節點位置,是以将prev屬性設為空
root.prev = null;
}
// 4.檢查樹是否正常
assert checkInvariants(root);
}
}
4.檢查樹是否正常,見代碼塊9詳解。
5.2.1.1.1 代碼塊9:checkInvariants
将傳入的節點作為根節點,周遊所有節點,校驗節點的合法性,主要是保證該樹符合紅黑樹的規則。
/**
* Recursive invariant check
*/
static <K,V> boolean checkInvariants(TreeNode<K,V> t) { // 一些基本的校驗
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
if (tp != null && t != tp.left && t != tp.right)
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
if (t.red && tl != null && tl.red && tr != null && tr.red) // 如果目前節點為紅色, 則該節點的左右節點不能同時為紅色
return false;
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}
6. resize 方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 1.老表的容量不為0,即老表不為空
if (oldCap > 0) {
// 1.1 判斷老表的容量是否超過最大容量值:如果超過則将門檻值設定為Integer.MAX_VALUE,并直接傳回老表,
// 此時oldCap * 2比Integer.MAX_VALUE大,是以無法進行重新分布,隻是單純的将門檻值擴容到最大
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 1.2 将newCap指派為oldCap的2倍,如果newCap<最大容量并且oldCap>=16, 則将新門檻值設定為原來的兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 2.如果老表的容量為0, 老表的門檻值大于0, 是因為初始容量被放入門檻值,則将新表的容量設定為老表的門檻值
else if (oldThr > 0)
newCap = oldThr;
else {
// 3.老表的容量為0, 老表的門檻值為0,這種情況是沒有傳初始容量的new方法建立的空表,将門檻值和容量設定為預設值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 4.如果新表的門檻值為空, 則通過新的容量*負載因子獲得門檻值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 5.将目前門檻值設定為剛計算出來的新的門檻值,定義新表,容量為剛計算出來的新容量,将table設定為新定義的表。
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 6.如果老表不為空,則需周遊所有節點,将節點指派給新表
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) { // 将索引值為j的老表頭節點指派給e
oldTab[j] = null; // 将老表的節點設定為空, 以便垃圾收集器回收空間
// 7.如果e.next為空, 則代表老表的該位置隻有1個節點,計算新表的索引位置, 直接将該節點放在該位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 8.如果是紅黑樹節點,則進行紅黑樹的重hash分布(跟連結清單的hash分布基本相同)
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 9.如果是普通的連結清單節點,則進行普通的重hash分布
Node<K,V> loHead = null, loTail = null; // 存儲索引位置為:“原索引位置”的節點
Node<K,V> hiHead = null, hiTail = null; // 存儲索引位置為:“原索引位置+oldCap”的節點
Node<K,V> next;
do {
next = e.next;
// 9.1 如果e的hash值與老表的容量進行與運算為0,則擴容後的索引位置跟老表的索引位置一樣
if ((e.hash & oldCap) == 0) {
if (loTail == null) // 如果loTail為空, 代表該節點為第一個節點
loHead = e; // 則将loHead指派為第一個節點
else
loTail.next = e; // 否則将節點添加在loTail後面
loTail = e; // 并将loTail指派為新增的節點
}
// 9.2 如果e的hash值與老表的容量進行與運算為非0,則擴容後的索引位置為:老表的索引位置+oldCap
else {
if (hiTail == null) // 如果hiTail為空, 代表該節點為第一個節點
hiHead = e; // 則将hiHead指派為第一個節點
else
hiTail.next = e; // 否則将節點添加在hiTail後面
hiTail = e; // 并将hiTail指派為新增的節點
}
} while ((e = next) != null);
// 10.如果loTail不為空(說明老表的資料有分布到新表上“原索引位置”的節點),則将最後一個節點
// 的next設為空,并将新表上索引位置為“原索引位置”的節點設定為對應的頭節點
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 11.如果hiTail不為空(說明老表的資料有分布到新表上“原索引+oldCap位置”的節點),則将最後
// 一個節點的next設為空,并将新表上索引位置為“原索引+oldCap”的節點設定為對應的頭節點
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 12.傳回新表
return newTab;
}
注意步驟:
2.老表的容量為 0,并且老表的門檻值大于 0:這種情況是建立 HashMap 時傳了初始容量,例如:new HashMap<>(32),使用這種方式建立 HashMap 時,由于 HashMap 沒有 capacity 屬性,是以此時的 capacity 會被暫存在 threshold 屬性。是以此時的 threshold 的值就是我們要新建立的 HashMap 的 capacity,是以将新表的容量設定為 threshold。
4.如果新表的門檻值為空,則通過新的容量 * 負載因子獲得門檻值(這種情況是初始化的時候傳了初始容量,跟第2點相同情況,或者初始容量設定的太小導緻老表的容量沒有超過 16 導緻的)。
8.如果是紅黑樹節點,則進行紅黑樹的重 hash 分布,見代碼塊10詳解。
9.1 如果 e 的 hash 值與老表的容量進行位與運算為 0,則說明 e 節點擴容後的索引位置跟老表的索引位置一樣(見疑問1詳解),進行連結清單拼接操作:如果 loTail 為空,代表該節點為第一個節點,則将 loHead 指派為該節點;否則将節點添加在 loTail 後面,并将 loTail 指派為新增的節點。
9.2 如果 e 的 hash 值與老表的容量進行位與運算為 1,則說明 e 節點擴容後的索引位置為:老表的索引位置+oldCap(見例子1詳解),進行連結清單拼接操作:如果 hiTail 為空,代表該節點為第一個節點,則将 hiHead 指派為該節點;否則将節點添加在 hiTail 後面,并将 hiTail 指派為新增的節點。
6.1 代碼塊10:split
紅黑樹擴容
/**
* 擴容後,紅黑樹的hash分布,隻可能存在于兩個位置:原索引位置、原索引位置+oldCap
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this; // 拿到調用此方法的節點
TreeNode<K,V> loHead = null, loTail = null; // 存儲索引位置為:“原索引位置”的節點
TreeNode<K,V> hiHead = null, hiTail = null; // 存儲索引位置為:“原索引+oldCap”的節點
int lc = 0, hc = 0;
// 1.以調用此方法的節點開始,周遊整個紅黑樹節點
for (TreeNode<K,V> e = b, next; e != null; e = next) { // 從b節點開始周遊
next = (TreeNode<K,V>)e.next; // next指派為e的下個節點
e.next = null; // 同時将老表的節點設定為空,以便垃圾收集器回收
// 2.如果e的hash值與老表的容量進行與運算為0,則擴容後的索引位置跟老表的索引位置一樣
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null) // 如果loTail為空, 代表該節點為第一個節點
loHead = e; // 則将loHead指派為第一個節點
else
loTail.next = e; // 否則将節點添加在loTail後面
loTail = e; // 并将loTail指派為新增的節點
++lc; // 統計原索引位置的節點個數
}
// 3.如果e的hash值與老表的容量進行與運算為非0,則擴容後的索引位置為:老表的索引位置+oldCap
else {
if ((e.prev = hiTail) == null) // 如果hiHead為空, 代表該節點為第一個節點
hiHead = e; // 則将hiHead指派為第一個節點
else
hiTail.next = e; // 否則将節點添加在hiTail後面
hiTail = e; // 并将hiTail指派為新增的節點
++hc; // 統計索引位置為原索引+oldCap的節點個數
}
}
// 4.如果原索引位置的節點不為空
if (loHead != null) { // 原索引位置的節點不為空
// 4.1 如果節點個數<=6個則将紅黑樹轉為連結清單結構
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
// 4.2 将原索引位置的節點設定為對應的頭節點
tab[index] = loHead;
// 4.3 如果hiHead不為空,則代表原來的紅黑樹(老表的紅黑樹由于節點被分到兩個位置)
// 已經被改變, 需要重新建構新的紅黑樹
if (hiHead != null)
// 4.4 以loHead為根節點, 建構新的紅黑樹
loHead.treeify(tab);
}
}
// 5.如果索引位置為原索引+oldCap的節點不為空
if (hiHead != null) { // 索引位置為原索引+oldCap的節點不為空
// 5.1 如果節點個數<=6個則将紅黑樹轉為連結清單結構
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
// 5.2 将索引位置為原索引+oldCap的節點設定為對應的頭節點
tab[index + bit] = hiHead;
// 5.3 loHead不為空則代表原來的紅黑樹(老表的紅黑樹由于節點被分到兩個位置)
// 已經被改變, 需要重新建構新的紅黑樹
if (loHead != null)
// 5.4 以hiHead為根節點, 建構新的紅黑樹
hiHead.treeify(tab);
}
}
}
2.如果 e 的 hash 值與老表的容量進行位與運算為 0,則說明 e 節點擴容後的索引位置跟老表的索引位置一樣(見例子1詳解),進行連結清單拼接操作:如果 loTail 為空,代表該節點為第一個節點,則将 loHead 指派為該節點;否則将節點添加在 loTail 後面,并将 loTail 指派為新增的節點,并統計原索引位置的節點個數。
3.如果 e 的 hash 值與老表的容量進行位與運算為 1,則說明 e 節點擴容後的索引位置為:老表的索引位置+oldCap(見例子1詳解),進行連結清單拼接操作:如果 hiTail 為空,代表該節點為第一個節點,則将 hiHead 指派為該節點;否則将節點添加在 hiTail 後面,并将 hiTail 指派為新增的節點,并統計索引位置為原索引 + oldCap 的節點個數。
4.1 如果節點個數 <= 6 個則将紅黑樹轉為連結清單結構,見代碼塊11詳解。
4.4 以 loHead 為根節點,建構新的紅黑樹,見代碼塊7詳解。
6.1.1 代碼塊11:untreeify
将紅黑樹節點轉為連結清單節點, 當節點<=6個時會被觸發。
由于紅黑樹的擴容,本質也會像連結清單那樣,增加樹的數量,減少單個樹的節點數量,是以,會出現樹的節點個數變為<=6個的情況,此時需要進行結構轉換!
/**
* 将紅黑樹節點轉為連結清單節點, 當節點<=6個時會被觸發
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null; // hd指向頭節點, tl指向尾節點
// 1.從調用該方法的節點, 即連結清單的頭節點開始周遊, 将所有節點全轉為連結清單節點
for (Node<K,V> q = this; q != null; q = q.next) {
// 2.調用replacementNode方法建構連結清單節點
Node<K,V> p = map.replacementNode(q, null);
// 3.如果tl為null, 則代表目前節點為第一個節點, 将hd指派為該節點
if (tl == null)
hd = p;
// 4.否則, 将尾節點的next屬性設定為目前節點p
else
tl.next = p;
tl = p; // 5.每次都将tl節點指向目前節點, 即尾節點
}
// 6.傳回轉換後的連結清單的頭節點
return hd;
}
6.2 疑問1 擴容後,節點重 hash 為什麼隻可能分布在 “原索引位置” 與 “原索引 + oldCap 位置” ?
擴容代碼中,使用 e 節點的 hash 值跟 oldCap 進行位與運算,以此決定将節點分布到 “原索引位置” 或者 “
原索引 + oldCap 位置
” 上,這是為什麼了?
假設老表的容量為 16,即 oldCap = 16,則新表容量為 16 * 2 = 32,假設節點 1 的 hash 值為:0000 0000 0000 0000 0000 1111 0000 1010,節點 2 的 hash 值為:0000 0000 0000 0000 0000 1111 0001 1010,則節點 1 和節點 2 在老表的索引位置計算如下圖計算1,由于老表的長度限制,節點 1 和節點 2 的索引位置隻取決于節點 hash 值的最後 4 位。
再看計算2,計算2為新表的索引計算,可以知道如果兩個節點在老表的索引位置相同,則新表的索引位置隻取決于節點hash值倒數第5位的值,而此位置的值剛好為老表的容量值 16,此時節點在新表的索引位置隻有兩種情況:“原索引位置” 和 “原索引 + oldCap位置”,在此例中即為 10 和 10 + 16 = 26。
由于結果隻取決于節點 hash 值的倒數第 5 位,而此位置的值剛好為老表的容量值 16,是以此時新表的索引位置的計算可以替換為計算3,直接使用節點的 hash 值與老表的容量 16 進行位于運算,如果結果為 0 則該節點在新表的索引位置為原索引位置,否則該節點在新表的索引位置為 “原索引 + oldCap 位置”。
結果:可以看出,擴容後,節點 A 和節點 C 的先後順序跟擴容前是一樣的。是以,
即使此時有多個線程并發擴容,也不會出現死循環的情況
。當然,這
仍然改變不了 HashMap 仍是非并發安全
,在并發下,還是要使用 ConcurrentHashMap 來代替。
7. 總結
- HashMap 的底層是個 Node 數組(Node<K,V>[] table),在數組的具體索引位置,如果存在多個節點,則可能是以連結清單或紅黑樹的形式存在。
- 增加、删除、查找鍵值對時,定位到哈希桶數組的位置是很關鍵的一步,源碼中是通過下面3個操作來完成這一步:1)拿到 key 的 hashCode 值;2)将 hashCode 的高位參與運算,重新計算 hash 值;3)将計算出來的 hash 值與 “table.length - 1” 進行 & 運算。
- HashMap 的
;實際能存放的節點個數(threshold,即觸發擴容的門檻值)= capacity * load factor。預設初始容量(capacity)是 16,capacity 必須為 2 的幂次方;預設負載因子(load factor)是 0.75
- HashMap 在觸發擴容後,
。例如 capacity 為16,索引位置 5 的節點擴容後,隻可能分布在新表 “索引位置5” 和 “索引位置21(5+16)”。門檻值會變為原來的 2 倍,并且會對所有節點進行重 hash 分布,重 hash 分布後節點的新分布位置隻可能有兩個:“原索引位置” 或 “原索引+oldCap位置”
- 導緻 HashMap 擴容後,同一個索引位置的節點重 hash 最多分布在兩個位置的根本原因是:1)table的長度始終為 2 的 n 次方;2)索引位置的計算方法為 “(table.length - 1) & hash”。HashMap 擴容是一個比較耗時的操作,定義 HashMap 時盡量給個接近的初始容量值。
- HashMap 有 threshold 屬性和 loadFactor 屬性,但是沒有 capacity 屬性。初始化時,如果傳了初始化容量值,該值是存在 threshold 變量,并且 Node 數組是在第一次 put 時才會進行初始化,初始化時會将此時的 threshold 值作為新表的 capacity 值,然後用 capacity 和 loadFactor 計算新表的真正 threshold 值。
- 當同一個索引位置的節點在增加後達到 9 個時,并且此時數組的長度大于等于 64,則會
,轉成紅黑樹節點後,其實連結清單的結構還存在,通過 next 屬性維持。連結清單節點轉紅黑樹節點的具體方法為源碼中的 treeifyBin 方法。而如果數組長度小于64,則不會觸發連結清單轉紅黑樹,而是會進行擴容。觸發連結清單節點(Node)轉紅黑樹節點(TreeNode)
- 當同一個索引位置的節點在移除後達到 6 個時,并且該索引位置的節點為紅黑樹節點,會
。紅黑樹節點轉連結清單節點的具體方法為源碼中的 untreeify 方法。觸發紅黑樹節點轉連結清單節點
- HashMap 在
,JDK 1.8 之前存在死循環的根本原因是在擴容後同一索引位置的節點順序會反掉。JDK 1.8 之後擴容不再有死循環的問題
- HashMap 是
的,在并發場景下使用 ConcurrentHashMap 來代替。非線程安全
參考:《史上最詳細的 JDK 1.8 HashMap 源碼解析》