概述
JDK 1.8對HashMap進行了比較大的優化，底層實作由之前的“數組+連結清單”改為“數組+連結清單+紅黑樹”，本文就HashMap的幾個常用的重要方法和JDK 1.8之前的死循環問題展開學習讨論。JDK 1.8的HashMap的資料結構如下圖所示，當連結清單節點較少時仍然是以連結清單存在，當連結清單節點較多時（大于8）會轉為紅黑樹。
幾個點：
先了解以下幾個點，有利于更好的了解HashMap的源碼和閱讀本文。
- 頭節點指的是table表上索引位置的節點，也就是連結清單的頭節點。
- 根結點（root節點）指的是紅黑樹最上面的那個節點，也就是沒有父節點的節點。
- 紅黑樹的根結點不一定是索引位置的頭結點。
- 轉為紅黑樹節點後，連結清單的結構還存在，通過next屬性維持，紅黑樹節點在進行操作時都會維護連結清單的結構，并不是轉為紅黑樹節點，連結清單結構就不存在了。
- 在紅黑樹上，葉子節點也可能有next節點，因為紅黑樹的結構跟連結清單的結構是互不影響的，不會因為是葉子節點就說該節點已經沒有next節點。
- 源碼中一些變量定義：如果定義了一個節點p，則pl為p的左節點，pr為p的右節點，pp為p的父節點，ph為p的hash值，pk為p的key值，kc為key的類等等。源碼中很喜歡在if/for等語句中進行指派并判斷，請注意。
- 連結清單中移除一個節點隻需如下圖操作，其他操作同理。
Java集合篇：HashMap原理詳解（JDK1.8）概述幾個點：基本屬性定位哈希桶數組索引位置get方法put方法resize方法remove方法死循環問題JDK 1.8擴容過程HashMap和Hashtable的差別：總結： - 紅黑樹在維護連結清單結構時，移除一個節點隻需如下圖操作（紅黑樹中增加了一個prev屬性），其他操作同理。注：此處隻是紅黑樹維護連結清單結構的操作，紅黑樹還需要單獨進行紅黑樹的移除或者其他操作。
-
Java集合篇：HashMap原理詳解（JDK1.8）概述幾個點：基本屬性定位哈希桶數組索引位置get方法put方法resize方法remove方法死循環問題JDK 1.8擴容過程HashMap和Hashtable的差別：總結： - 源碼中進行紅黑樹的查找時，會反複用到以下兩條規則：1）如果目标節點的hash值小于p節點的hash值，則向p節點的左邊周遊；否則向p節點的右邊周遊。2）如果目标節點的key值小于p節點的key值，則向p節點的左邊周遊；否則向p節點的右邊周遊。這兩條規則是利用了紅黑樹的特性（左節點<根結點<右節點）。
- 源碼中進行紅黑樹的查找時，會用dir（direction）來表示向左還是向右查找，dir存儲的值是目标節點的hash/key與p節點的hash/key的比較結果。
基本屬性
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 預設容量16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 預設負載因子0.75
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8; // 連結清單節點轉換紅黑樹節點的門檻值, 8個節點轉
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6; // 紅黑樹節點轉換連結清單節點的門檻值, 6個節點轉
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64; // 轉紅黑樹時, table的最小長度
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> { // 基本hash節點, 繼承自Entry
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;
}
}
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
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);
}
// ...
}
定位哈希桶數組索引位置
不管增加、删除、查找鍵值對，定位到哈希桶數組的位置都是很關鍵的第一步。前面說過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：
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;
// table不為空 && table長度大于0 && table索引位置(根據hash值計算出)不為空
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; // first的key等于傳入的key則傳回first對象
if ((e = first.next) != null) { // 向下周遊
if (first instanceof TreeNode) // 判斷是否為TreeNode
// 如果是紅黑樹節點，則調用紅黑樹的查找目标節點方法getTreeNode
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 走到這代表節點為連結清單節點
do { // 向下周遊連結清單, 直至找到節點的key和傳入的key相等時,傳回該節點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null; // 找不到符合的傳回空
}
- 先對table進行校驗，校驗是否為空，length是否大于0
- 使用table.length - 1和hash值進行位與運算，得出在table上的索引位置，将該索引位置的節點指派給first節點，校驗該索引位置是否為空
- 檢查first節點的hash值和key是否和入參的一樣，如果一樣則first即為目标節點，直接傳回first節點
- 如果first的next節點不為空則繼續周遊
- 如果first節點為TreeNode，則調用getTreeNode方法（見下文代碼塊1）查找目标節點
- 如果first節點不為TreeNode，則調用普通的周遊連結清單方法查找目标節點
- 如果查找不到目标節點則傳回空
代碼塊1：getTreeNode方法
final TreeNode<K,V> getTreeNode(int h, Object k) {
// 使用根結點調用find方法
return ((parent != null) ? root() : this).find(h, k, null);
}
- 找到調用此方法的節點的樹的根節點
- 使用該樹的根節點調用find方法（見下文代碼塊2）
代碼塊2：find方法
/**
* 從調用此方法的結點開始查找, 通過hash值和key找到對應的節點
* 此處是紅黑樹的周遊, 紅黑樹是特殊的自平衡二叉查找樹
* 平衡二叉查找樹的特點：左節點<根節點<右節點
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this; // this為調用此方法的節點
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h) // 傳入的hash值小于p節點的hash值, 則往p節點的左邊周遊
p = pl; // p指派為p節點的左節點
else if (ph < h) // 傳入的hash值大于p節點的hash值, 則往p節點的右邊周遊
p = pr; // p指派為p節點的右節點
// 傳入的hash值和key值等于p節點的hash值和key值,則p節點為目标節點,傳回p節點
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null) // p節點的左節點為空則将向右周遊
p = pr;
else if (pr == null) // p節點的右節點為空則向左周遊
p = pl;
else if ((kc != null ||
// 如果傳入的key(k)所屬的類實作了Comparable接口,則将傳入的key跟p節點的key比較
(kc = comparableClassFor(k)) != null) && // 此行不為空代表k實作了Comparable
(dir = compareComparables(kc, k, pk)) != 0)//k<pk則dir<0, k>pk則dir>0
p = (dir < 0) ? pl : pr; // k < pk則向左周遊(p指派為p的左節點), 否則向右周遊
// 代碼走到此處, 代表key所屬類沒有實作Comparable, 直接指定向p的右邊周遊
else if ((q = pr.find(h, k, kc)) != null)
return q;
else// 代碼走到此處代表上一個向右周遊（pr.find(h, k, kc)）為空, 是以直接向左周遊
p = pl;
} while (p != null);
return null;
}
- 将p節點指派為調用此方法的節點
- 如果傳入的hash值小于p節點的hash值，則往p節點的左邊周遊
- 如果傳入的hash值大于p節點的hash值，則往p節點的右邊周遊
- 如果傳入的hash值等于p節點的hash值，并且傳入的key值跟p節點的key值相等, 則該p節點即為目标節點，傳回p節點
- 如果p的左節點為空則向右周遊，反之如果p的右節點為空則向左周遊
- 如果傳入的key（即代碼中的參數變量k）所屬的類實作了Comparable接口（kc不為空，comparableClassFor方法見下文代碼塊3），則将傳入的key跟p節點的key進行比較（kc實作了Comparable接口，是以通過kc的比較方法進行比較），并将比較結果指派給dir，如果dir<0則代表k<pk，則向p節點的左邊周遊（pl）；否則，向p節點的右邊周遊（pr）。
- 代碼走到此處，代表key所屬類沒有實作Comparable，是以直接指定向p的右邊周遊，如果能找到目标節點則傳回
- 代碼走到此處代表與第7點向右周遊沒有找到目标節點，是以直接向左邊周遊
- 以上都找不到目标節點則傳回空
代碼塊3：comparableClassFor方法
/**
* Returns x's Class if it is of the form "class C implements
* Comparable<C>", else null.
*/
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
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;
}
如果x實作了Comparable接口，則傳回 x的Class。
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;
// table是否為空或者length等于0, 如果是則調用resize方法進行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通過hash值計算索引位置, 如果table表該索引位置節點為空則新增一個
if ((p = tab[i = (n - 1) & hash]) == null)// 将索引位置的頭節點指派給p
tab[i] = newNode(hash, key, value, null);
else { // table表該索引位置不為空
Node<K,V> e; K k;
if (p.hash == hash && // 判斷p節點的hash值和key值是否跟傳入的hash值和key值相等
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 如果相等, 則p節點即為要查找的目标節點，指派給e
// 判斷p節點是否為TreeNode, 如果是則調用紅黑樹的putTreeVal方法查找目标節點
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 走到這代表p節點為普通連結清單節點
for (int binCount = 0; ; ++binCount) { // 周遊此連結清單, binCount用于統計節點數
if ((e = p.next) == null) { // p.next為空代表不存在目标節點則新增一個節點插傳入連結表尾部
p.next = newNode(hash, key, value, null);
// 計算節點是否超過8個, 減一是因為循環是從p節點的下一個節點開始的
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);// 如果超過8個，調用treeifyBin方法将該連結清單轉換為紅黑樹
break;
}
if (e.hash == hash && // e節點的hash值和key值都與傳入的相等, 則e即為目标節點,跳出循環
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // 将p指向下一個節點
}
}
// e不為空則代表根據傳入的hash值和key值查找到了節點,将該節點的value覆寫,傳回oldValue
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 用于LinkedHashMap
return oldValue;
}
}
++modCount;
if (++size > threshold) // 插入節點後超過門檻值則進行擴容
resize();
afterNodeInsertion(evict); // 用于LinkedHashMap
return null;
}
- 校驗table是否為空或者length等于0，如果是則調用resize方法（見下文resize方法）進行初始化
- 通過hash值計算索引位置，将該索引位置的頭節點指派給p節點，如果該索引位置節點為空則使用傳入的參數新增一個節點并放在該索引位置
- 判斷p節點的key和hash值是否跟傳入的相等，如果相等, 則p節點即為要查找的目标節點，将p節點指派給e節點
- 如果p節點不是目标節點，則判斷p節點是否為TreeNode，如果是則調用紅黑樹的putTreeVal方法（見下文代碼塊4）查找目标節點
- 走到這代表p節點為普通連結清單節點，則調用普通的連結清單方法進行查找，并定義變量binCount來統計該連結清單的節點數
- 如果p的next節點為空時，則代表找不到目标節點，則新增一個節點并插傳入連結表尾部，并校驗節點數是否超過8個，如果超過則調用treeifyBin方法（見下文代碼塊6）将連結清單節點轉為紅黑樹節點
- 如果周遊的e節點存在hash值和key值都與傳入的相同，則e節點即為目标節點，跳出循環
- 如果e節點不為空，則代表目标節點存在，使用傳入的value覆寫該節點的value，并傳回oldValue
- 如果插入節點後節點數超過門檻值，則調用resize方法（見下文resize方法）進行擴容
代碼塊4：putTreeVal方法
/**
* Tree version of putVal.
* 紅黑樹插入會同時維護原來的連結清單屬性, 即原來的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;
// 查找根節點, 索引位置的頭節點并不一定為紅黑樹的根結點
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) { // 将根節點指派給p, 開始周遊
int dir, ph; K pk;
if ((ph = p.hash) > h) // 如果傳入的hash值小于p節點的hash值
dir = -1; // 則将dir指派為-1, 代表向p的左邊查找樹
else if (ph < h) // 如果傳入的hash值大于p節點的hash值,
dir = 1; // 則将dir指派為1, 代表向p的右邊查找樹
// 如果傳入的hash值和key值等于p節點的hash值和key值, 則p節點即為目标節點, 傳回p節點
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 如果k所屬的類沒有實作Comparable接口 或者 k和p節點的key相等
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) { // 第一次符合條件, 該方法隻有第一次才執行
TreeNode<K,V> q, ch;
searched = true;
// 從p節點的左節點和右節點分别調用find方法進行查找, 如果查找到目标節點則傳回
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;
}
// 否則使用定義的一套規則來比較k和p節點的key的大小, 用來決定向左還是向右查找
dir = tieBreakOrder(k, pk); // dir<0則代表k<pk，則向p左邊查找；反之亦然
}
TreeNode<K,V> xp = p; // xp指派為x的父節點,中間變量,用于下面給x的父節點指派
// 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節點
// 建立新的節點, 其中x的next節點為xpn, 即将x節點插入xp與xpn之間
TreeNode<K,V> x = map.newTreeNode(h, k, v, 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;
moveRootToFront(tab, balanceInsertion(root, x)); // 進行紅黑樹的插入平衡調整
return null;
}
}
}
- 查找目前紅黑樹的根結點，将根結點指派給p節點，開始進行查找
- 如果傳入的hash值小于p節點的hash值，将dir指派為-1，代表向p的左邊查找樹
- 如果傳入的hash值大于p節點的hash值， 将dir指派為1，代表向p的右邊查找樹
- 如果傳入的hash值等于p節點的hash值，并且傳入的key值跟p節點的key值相等, 則該p節點即為目标節點，傳回p節點
- 如果k所屬的類沒有實作Comparable接口，或者k和p節點的key使用compareTo方法比較相等：第一次會從p節點的左節點和右節點分别調用find方法（見上文代碼塊2）進行查找，如果查找到目标節點則傳回；如果不是第一次或者調用find方法沒有找到目标節點，則調用tieBreakOrder方法（見下文代碼塊5）比較k和p節點的key值的大小，以決定向樹的左節點還是右節點查找。
- 如果dir <= 0則向左節點查找（p指派為p.left，并進行下一次循環），否則向右節點查找，如果已經無法繼續查找（p指派後為null），則代表該位置即為x的目标位置，另外變量xp用來記錄查找的最後一個節點，即下文新增的x節點的父節點。
- 以傳入的hash、key、value參數和xp節點的next節點為參數，建構x節點（注意：xp節點在此處可能是葉子節點、沒有左節點的節點、沒有右節點的節點三種情況，即使它是葉子節點，它也可能有next節點，紅黑樹的結構跟連結清單的結構是互不影響的，不會因為某個節點是葉子節點就說它沒有next節點，紅黑樹在進行操作時會同時維護紅黑樹結構和連結清單結構，next屬性就是用來維護連結清單結構的），根據dir的值決定x決定放在xp節點的左節點還是右節點，将xp的next節點設為x，将x的parent和prev節點設為xp，如果原xp的next節點（xpn）不為空, 則将該節點的prev節點設定為x節點, 與上面的将x節點的next節點設定為xpn對應。
- 進行紅黑樹的插入平衡調整，見文末的解釋2。
代碼塊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;
}
定義一套規則用于極端情況下比較兩個參數的大小。
代碼塊6：treeifyBin方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// table為空或者table的長度小于64, 進行擴容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 根據hash值計算索引值, 周遊該索引位置的連結清單
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null); // 連結清單節點轉紅黑樹節點
if (tl == null) // tl為空代表為第一次循環
hd = p; // 頭結點
else {
p.prev = tl; // 目前節點的prev屬性設為上一個節點
tl.next = p; // 上一個節點的next屬性設定為目前節點
}
tl = p; // tl指派為p, 在下一次循環中作為上一個節點
} while ((e = e.next) != null); // e指向下一個節點
// 将table該索引位置指派為新轉的TreeNode的頭節點
if ((tab[index] = hd) != null)
hd.treeify(tab); // 以頭結點為根結點, 建構紅黑樹
}
}
- 校驗table是否為空，如果長度小于64，則調用resize方法（見下文resize方法）進行擴容。
- 根據hash值計算索引值，将該索引位置的節點指派給e節點，從e節點開始周遊該索引位置的連結清單。
- 調用replacementTreeNode方法（該方法就一行代碼，直接傳回一個建立的TreeNode）将連結清單節點轉為紅黑樹節點，将頭結點指派給hd節點，每次周遊結束将p節點指派給tl，用于在下一次循環中作為上一個節點進行一些連結清單的關聯操作（p.prev = tl 和 tl.next = p）。
- 将table該索引位置指派為新轉的TreeNode的頭節點hd，如果該節點不為空，則以hd為根結點，調用treeify方法（見下文代碼塊7）建構紅黑樹。
代碼塊7：treeify方法
final void treeify(Node<K,V>[] tab) { // 建構紅黑樹
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {// this即為調用此方法的TreeNode
next = (TreeNode<K,V>)x.next; // next指派為x的下個節點
x.left = x.right = null; // 将x的左右節點設定為空
if (root == null) { // 如果還沒有根結點, 則将x設定為根結點
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;
// 如果目前節點x不是根結點, 則從根節點開始查找屬于該節點的位置
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) // 如果x節點的hash值小于p節點的hash值
dir = -1; // 則将dir指派為-1, 代表向p的左邊查找
else if (ph < h) // 與上面相反, 如果x節點的hash值大于p節點的hash值
dir = 1; // 則将dir指派為1, 代表向p的右邊查找
// 走到這代表x的hash值和p的hash值相等，則比較key值
else if ((kc == null && // 如果k沒有實作Comparable接口 或者 x節點的key和p節點的key相等
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// 使用定義的一套規則來比較x節點和p節點的大小，用來決定向左還是向右查找
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p; // xp指派為x的父節點,中間變量用于下面給x的父節點指派
// dir<=0則向p左邊查找,否則向p右邊查找,如果為null,則代表該位置即為x的目标位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp; // x的父節點即為最後一次周遊的p節點
if (dir <= 0) // 如果時dir <= 0, 則代表x節點為父節點的左節點
xp.left = x;
else // 如果時dir > 0, 則代表x節點為父節點的右節點
xp.right = x;
// 進行紅黑樹的插入平衡(通過左旋、右旋和改變節點顔色來保證目前樹符合紅黑樹的要求)
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root); // 如果root節點不在table索引位置的頭結點, 則将其調整為頭結點
}
- 從調用此方法的節點作為起點，開始進行周遊，并将此節點設為root節點，标記為黑色（x.red = false）。
- 如果目前節點不是根結點，則從根節點開始查找屬于該節點的位置（該段代碼跟之前的代碼塊2和代碼塊4的查找代碼類似）。
- 如果x節點(将要插入紅黑樹的節點)的hash值小于p節點(目前周遊到的紅黑樹節點)的hash值，則向p節點的左邊查找。
- 與3相反，如果x節點的hash值大于p節點的hash值，則向p節點的右邊查找。
- 如果x的key沒有實作Comparable接口，或者x節點的key和p節點的key相等，使用tieBreakOrder方法（見上文代碼塊5）來比較x節點和p節點的大小，以決定向左還是向右查找（dir <= 0向左，否則向右）。
- 如果dir <= 0則向左節點查找（p指派為p.left，并進行下一次循環），否則向右節點查找，如果已經無法繼續查找（p指派後為null），則代表該位置即為x的目标位置，另外變量xp用來記錄最後一個節點，即為下文新增的x節點的父節點。
- 将x的父節點設定為xp，根據dir的值決定x決定放在xp節點的左節點還是右節點，最後進行紅黑樹的插入平衡調整。
- 調用moveRootToFront方法（見下文代碼塊8）将root節點調整到索引位置的頭結點。
代碼塊8：moveRootToFront方法
/**
* 如果目前索引位置的頭節點不是root節點, 則将root的上一個節點和下一個節點進行關聯,
* 将root放到頭節點的位置, 原頭節點放在root的next節點上
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) { // 如果root節點不是該索引位置的頭節點
Node<K,V> rn;
tab[index] = root; // 将該索引位置的頭節點指派為root節點
TreeNode<K,V> rp = root.prev; // root節點的上一個節點
// 如果root節點的下一個節點不為空,
// 則将root節點的下一個節點的prev屬性設定為root節點的上一個節點
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
// 如果root節點的上一個節點不為空,
// 則将root節點的上一個節點的next屬性設定為root節點的下一個節點
if (rp != null)
rp.next = rn;
if (first != null) // 如果原頭節點不為空, 則将原頭節點的prev屬性設定為root節點
first.prev = root;
root.next = first; // 将root節點的next屬性設定為原頭節點
root.prev = null;
}
assert checkInvariants(root); // 檢查樹是否正常
}
}
- 校驗root是否為空、table是否為空、table的length是否大于0。
- 根據root節點的hash值計算出索引位置，判斷該索引位置的頭節點是否為root節點，如果不是則進行以下操作将該索引位置的頭結點替換為root節點。
- 将該索引位置的頭結點指派為root節點，如果root節點的next節點不為空，則将root節點的next節點的prev屬性設定為root節點的prev節點。
- 如果root節點的prev節點不為空，則将root節點的prev節點的next屬性設定為root節點的next節點（3和4兩個操作是一個完整的連結清單移除某個節點過程）。
- 如果原頭節點不為空，則将原頭節點的prev屬性設定為root節點
- 将root節點的next屬性設定為原頭節點（5和6兩個操作将first節點接到root節點後面）
- root此時已經被放到該位置的頭結點位置，是以将prev屬性設為空。
- 調用checkInvariants方法（見下文代碼塊9）檢查樹是否正常。
代碼塊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;
}
将傳入的節點作為根結點，周遊所有節點，校驗節點的合法性，主要是保證該樹符合紅黑樹的規則。
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;
if (oldCap > 0) { // 老table不為空
if (oldCap >= MAXIMUM_CAPACITY) { // 老table的容量超過最大容量值
threshold = Integer.MAX_VALUE; // 設定門檻值為Integer.MAX_VALUE
return oldTab;
}
// 如果容量*2<最大容量并且>=16, 則将門檻值設定為原來的兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 老表的容量為0, 老表的門檻值大于0, 是因為初始容量被放入門檻值
newCap = oldThr; // 則将新表的容量設定為老表的門檻值
else { // 老表的容量為0, 老表的門檻值為0, 則為空表，設定預設容量和門檻值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { // 如果新表的門檻值為空, 則通過新的容量*負載因子獲得門檻值
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) { // 如果老表不為空, 則需周遊将節點指派給新表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) { // 将索引值為j的老表頭節點指派給e
oldTab[j] = null; // 将老表的節點設定為空, 以便垃圾收集器回收空間
// 如果e.next為空, 則代表老表的該位置隻有1個節點,
// 通過hash值計算新表的索引位置, 直接将該節點放在該位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 調用treeNode的hash分布(跟下面最後一個else的内容幾乎相同)
((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; // 存儲索引位置為:原索引+oldCap的節點
Node<K,V> next;
do {
next = e.next;
//如果e的hash值與老表的容量進行與運算為0,則擴容後的索引位置跟老表的索引位置一樣
if ((e.hash & oldCap) == 0) {
if (loTail == null) // 如果loTail為空, 代表該節點為第一個節點
loHead = e; // 則将loHead指派為第一個節點
else
loTail.next = e; // 否則将節點添加在loTail後面
loTail = e; // 并将loTail指派為新增的節點
}
//如果e的hash值與老表的容量進行與運算為1,則擴容後的索引位置為:老表的索引位置＋oldCap
else {
if (hiTail == null) // 如果hiTail為空, 代表該節點為第一個節點
hiHead = e; // 則将hiHead指派為第一個節點
else
hiTail.next = e; // 否則将節點添加在hiTail後面
hiTail = e; // 并将hiTail指派為新增的節點
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null; // 最後一個節點的next設為空
newTab[j] = loHead; // 将原索引位置的節點設定為對應的頭結點
}
if (hiTail != null) {
hiTail.next = null; // 最後一個節點的next設為空
newTab[j + oldCap] = hiHead; // 将索引位置為原索引+oldCap的節點設定為對應的頭結點
}
}
}
}
}
return newTab;
}
- 如果老表的容量大于0，判斷老表的容量是否超過最大容量值：如果超過則将門檻值設定為Integer.MAX_VALUE，并直接傳回老表（此時oldCap * 2比Integer.MAX_VALUE大，是以無法進行重新分布，隻是單純的将門檻值擴容到最大）；如果容量 * 2小于最大容量并且不小于16，則将門檻值設定為原來的兩倍。
- 如果老表的容量為0，老表的門檻值大于0，這種情況是傳了容量的new方法建立的空表，将新表的容量設定為老表的門檻值（這種情況發生在新建立的HashMap第一次put時，該HashMap初始化的時候傳了初始容量，由于HashMap并沒有capacity變量來存放容量值，是以傳進來的初始容量是存放在threshold變量上（檢視HashMap(int initialCapacity, float loadFactor)方法），是以此時老表的threshold的值就是我們要新建立的HashMap的capacity，是以将新表的容量設定為老表的門檻值。
- 如果老表的容量為0，老表的門檻值為0，這種情況是沒有傳容量的new方法建立的空表，将門檻值和容量設定為預設值。
- 如果新表的門檻值為空，則通過新的容量 * 負載因子獲得門檻值（這種情況是初始化的時候傳了初始容量，跟第2點相同情況，也隻有走到第2點才會走到該情況）。
- 将目前門檻值設定為剛計算出來的新的門檻值，定義新表，容量為剛計算出來的新容量，将目前的表設定為新定義的表。
- 如果老表不為空，則需周遊所有節點，将節點指派給新表。
- 将老表上索引為j的頭結點指派給e節點，并将老表上索引為j的節點設定為空。
- 如果e的next節點為空，則代表老表的該位置隻有1個節點，通過hash值計算新表的索引位置，直接将該節點放在新表的該位置上。
- 如果e的next節點不為空，并且e為TreeNode，則調用split方法（見下文代碼塊10）進行hash分布。
- 如果e的next節點不為空，并且e為普通的連結清單節點，則進行普通的hash分布。
- 如果e的hash值與老表的容量（為一串隻有1個為2的二進制數，例如16為0000 0000 0001 0000）進行位與運算為0，則說明e節點擴容後的索引位置跟老表的索引位置一樣（見例子1），進行連結清單拼接操作：如果loTail為空，代表該節點為第一個節點，則将loHead指派為該節點；否則将節點添加在loTail後面，并将loTail指派為新增的節點。
- 如果e的hash值與老表的容量（為一串隻有1個為2的二進制數，例如16為0000 0000 0001 0000）進行位與運算為1，則說明e節點擴容後的索引位置為：老表的索引位置＋oldCap（見例子1），進行連結清單拼接操作：如果hiTail為空，代表該節點為第一個節點，則将hiHead指派為該節點；否則将節點添加在hiTail後面，并将hiTail指派為新增的節點。
- 老表節點重新hash分布在新表結束後，如果loTail不為空（說明老表的資料有分布到新表上原索引位置的節點），則将最後一個節點的next設為空，并将新表上原索引位置的節點設定為對應的頭結點；如果hiTail不為空（說明老表的資料有分布到新表上原索引+oldCap位置的節點），則将最後一個節點的next設為空，并将新表上索引位置為原索引+oldCap的節點設定為對應的頭結點。
- 傳回新表。
代碼塊10：split方法
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;
for (TreeNode<K,V> e = b, next; e != null; e = next) { // 從b節點開始周遊
next = (TreeNode<K,V>)e.next; // next指派為e的下個節點
e.next = null; // 同時将老表的節點設定為空，以便垃圾收集器回收
//如果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; // 統計原索引位置的節點個數
}
//如果e的hash值與老表的容量進行與運算為1,則擴容後的索引位置為:老表的索引位置＋oldCap
else {
if ((e.prev = hiTail) == null) // 如果hiHead為空, 代表該節點為第一個節點
hiHead = e; // 則将hiHead指派為第一個節點
else
hiTail.next = e; // 否則将節點添加在hiTail後面
hiTail = e; // 并将hiTail指派為新增的節點
++hc; // 統計索引位置為原索引+oldCap的節點個數
}
}
if (loHead != null) { // 原索引位置的節點不為空
if (lc <= UNTREEIFY_THRESHOLD) // 節點個數少于6個則将紅黑樹轉為連結清單結構
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead; // 将原索引位置的節點設定為對應的頭結點
// hiHead不為空則代表原來的紅黑樹(老表的紅黑樹由于節點被分到兩個位置)
// 已經被改變, 需要重新建構新的紅黑樹
if (hiHead != null)
loHead.treeify(tab); // 以loHead為根結點, 建構新的紅黑樹
}
}
if (hiHead != null) { // 索引位置為原索引+oldCap的節點不為空
if (hc <= UNTREEIFY_THRESHOLD) // 節點個數少于6個則将紅黑樹轉為連結清單結構
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead; // 将索引位置為原索引+oldCap的節點設定為對應的頭結點
// loHead不為空則代表原來的紅黑樹(老表的紅黑樹由于節點被分到兩個位置)
// 已經被改變, 需要重新建構新的紅黑樹
if (loHead != null)
hiHead.treeify(tab); // 以hiHead為根結點, 建構新的紅黑樹
}
}
}
- 以調用此方法的節點開始，周遊整個紅黑樹節點（此處實際是周遊的連結清單節點，上文提過，紅黑樹節點也會同時維護連結清單結構）。
- 如果e的hash值與老表的容量（為一串隻有1個為2的二進制數，例如16為0000 0000 0001 0000）進行位與運算為0，則說明e節點擴容後的索引位置跟老表的索引位置一樣（見下文例子1），進行連結清單拼接操作：如果loTail為空，代表該節點為第一個節點，則将loHead指派為該節點；否則将節點添加在loTail後面，并将loTail指派為新增的節點，并統計原索引位置的節點個數。
- 如果e的hash值與老表的容量（為一串隻有1個為2的二進制數，例如16為0000 0000 0001 0000）進行位與運算為1，則說明e節點擴容後的索引位置為：老表的索引位置＋oldCap（見例子1），進行連結清單拼接操作：如果hiTail為空，代表該節點為第一個節點，則将hiHead指派為該節點；否則将節點添加在hiTail後面，并将hiTail指派為新增的節點，并統計索引位置為原索引+oldCap的節點個數。
- 如果原索引位置的節點不為空：如果當該索引位置節點數<=6個，調用untreeify方法（見下文代碼塊11）将紅黑樹節點轉為連結清單節點；否則将原索引位置的節點設定為對應的頭結點（即loHead結點），如果判斷hiHead不為空則代表原來的紅黑樹（老表的紅黑樹由于節點被分到兩個位置）已經被改變，需要重新建構新的紅黑樹，以loHead為根結點，調用treeify方法（見上文代碼塊7）建構新的紅黑樹。
- 如果索引位置為原索引+oldCap的節點不為空：如果當該索引位置節點數<=6個，調用untreeify方法（見下文代碼塊11）将紅黑樹節點轉為連結清單節點；否則将索引位置為原索引+oldCap的節點設定為對應的頭結點（即hiHead結點），如果判斷loHead不為空則代表原來的紅黑樹（老表的紅黑樹由于節點被分到兩個位置）已經被改變，需要重新建構新的紅黑樹，以hiHead為根結點，調用treeify方法（見上文代碼塊7）建構新的紅黑樹。
代碼塊11：untreeify方法
// 将紅黑樹節點轉為連結清單節點, 當節點<=6個時會被觸發
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null; // hd指向頭結點, tl指向尾節點
// 從調用該方法的節點, 即連結清單的頭結點開始周遊, 将所有節點全轉為連結清單節點
for (Node<K,V> q = this; q != null; q = q.next) {
// 調用replacementNode方法建構連結清單節點
Node<K,V> p = map.replacementNode(q, null);
// 如果tl為null, 則代表目前節點為第一個節點, 将hd指派為該節點
if (tl == null)
hd = p;
else // 否則, 将尾節點的next屬性設定為目前節點p
tl.next = p;
tl = p; // 每次都将tl節點指向目前節點, 即尾節點
}
return hd; // 傳回轉換後的連結清單的頭結點
}
- 從調用該方法的節點，即連結清單的頭結點開始周遊, 将所有節點全轉為連結清單節點
- 調用replacementNode方法建構連結清單節點
- 如果tl為null, 則代表目前節點為第一個節點，将hd指派為該節點，否則, 将尾節點的next屬性設定為目前節點p
- 每次都将tl節點指向目前節點, 即尾節點
- 傳回轉換後的連結清單的頭結點
例子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位置。
remove方法
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;
// 如果table不為空并且根據hash值計算出來的索引位置不為空, 将該位置的節點指派給p
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 如果p的hash值和key都與入參的相同, 則p即為目标節點, 指派給node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) { // 否則向下周遊節點
if (p instanceof TreeNode) // 如果p是TreeNode則調用紅黑樹的方法查找節點
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do { // 周遊連結清單查找符合條件的節點
// 當節點的hash值和key與傳入的相同,則該節點即為目标節點
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e; // 指派給node, 并跳出循環
break;
}
p = e; // p節點指派為本次結束的e
} while ((e = e.next) != null); // 指向像一個節點
}
}
// 如果node不為空(即根據傳入key和hash值查找到目标節點)，則進行移除操作
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) // 如果是TreeNode則調用紅黑樹的移除方法
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 走到這代表節點是普通連結清單節點
// 如果node是該索引位置的頭結點則直接将該索引位置的值指派為node的next節點
else if (node == p)
tab[index] = node.next;
// 否則将node的上一個節點的next屬性設定為node的next節點,
// 即将node節點移除, 将node的上下節點進行關聯(連結清單的移除)
else
p.next = node.next;
++modCount; // 修改次數+1
--size; // table的總節點數-1
afterNodeRemoval(node); // 供LinkedHashMap使用
return node; // 傳回被移除的節點
}
}
return null;
}
- 如果table不為空并且根據hash值計算出來的索引位置的值不為空，将該位置的節點指派給p。
- 如果p節點的hash值和key都與傳入的相同，則p即為目标節點，指派給node。
- 向下周遊節點，如果p是TreeNode則調用getTreeNode方法（見上文代碼塊1）查找節點，并指派給node。
- 周遊連結清單查找符合條件的節點，當節點的hash值和key與傳入的值相同，則該節點即為目标節點, 指派給node，并跳出循環。
- 如果node不為空，即根據傳入key和hash值查找到目标節點，判斷node是否為TreeNode，如果是則調用紅黑樹的移除方法removeTreeNode方法（見下文代碼塊12）。
- 如果node是該索引位置的頭結點則直接将該索引位置的值指派為node節點的next節點。
- 否則将node的上一個節點（p節點）的next節點設定為node的next節點，即将node節點移除，将node的上下節點進行關聯（連結清單的移除，可以看開頭的第7點）。
代碼塊12：removeTreeNode方法
這塊代碼比較長，目的就是移除調用此方法的節點，也就是該方法中的this節點。移除包括連結清單的處理和紅黑樹的處理。可以結合下文的圖解了解。
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
// 連結清單的處理start
int n;
if (tab == null || (n = tab.length) == 0) // table為空或者length為0直接傳回
return;
int index = (n - 1) & hash; // 根據hash計算出索引的位置
// 索引位置的頭結點指派給first和root
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
// 該方法被将要被移除的node(TreeNode)調用, 是以此方法的this為要被移除node節點,
// 則此處next即為node的next節點, prev即為node的prev節點
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null) // 如果node節點的prev節點為空
// 則将table索引位置的值和first節點的值指派為succ節點(node的next節點)即可
tab[index] = first = succ;
else
// 否則将node的prev節點的next屬性設定為succ節點(node的next節點)(連結清單的移除)
pred.next = succ;
if (succ != null) // 如果succ節點不為空
succ.prev = pred; // 則将succ的prev節點設定為pred, 與上面對應
if (first == null) // 如果此處first為空, 則代表該索引位置已經沒有節點則直接傳回
return;
// 如果root的父節點不為空, 則将root指派為根結點
// (root在上面被指派為索引位置的頭結點, 索引位置的頭節點并不一定為紅黑樹的根結點)
if (root.parent != null)
root = root.root();
// 通過root節點來判斷此紅黑樹是否太小, 如果是則調用untreeify方法轉為連結清單節點并傳回
// (轉連結清單後就無需再進行下面的紅黑樹處理)
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
// 連結清單的處理end
// 以下代碼為紅黑樹的處理, 上面的代碼已經将連結清單的部分處理完成
// 上面已經說了this為要被移除的node節點,
// 将p指派為node節點,pl指派為node的左節點,pr指派為node的右節點
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) { // node的左節點和右節點都不為空時
TreeNode<K,V> s = pr, sl; // s節點指派為node的右節點
while ((sl = s.left) != null)//向左一直查找,直到葉子節點,跳出循環時,s為葉子節點
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; //交換p節點和s節點(葉子節點)的顔色
TreeNode<K,V> sr = s.right; // s的右節點
TreeNode<K,V> pp = p.parent; // p的父節點
// 第一次調整start
if (s == pr) { // 如果p節點的右節點即為葉子節點
p.parent = s; // 将p的父節點指派為s
s.right = p; // 将s的右節點指派為p
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) { // 将p的父節點指派為s的父節點, 如果sp不為空
if (s == sp.left) // 如果s節點為左節點
sp.left = p; // 則将s的父節點的左節點指派為p節點
else // 如果s節點為右節點
sp.right = p; // 則将s的父節點的右節點指派為p節點
}
if ((s.right = pr) != null) // s的右節點指派為p節點的右節點
pr.parent = s; // p節點的右節點的父節點指派為s
}
// 第二次調整start
p.left = null;
if ((p.right = sr) != null) // 将p節點的右節點指派為s的右節點, 如果sr不為空
sr.parent = p; // 則将s右節點的父節點指派為p節點
if ((s.left = pl) != null) // 将s節點的左節點指派為p的左節點, 如果pl不為空
pl.parent = s; // 則将p左節點的父節點指派為s節點
if ((s.parent = pp) == null) // 将s的父節點指派為p的父節點pp, 如果pp為空
root = s; // 則p節點為root節點, 此時交換後s成為新的root節點
else if (p == pp.left) // 如果p不為root節點, 并且p是父節點的左節點
pp.left = s; // 将p父節點的左節點指派為s節點
else // 如果p不為root節點, 并且p是父節點的右節點
pp.right = s; // 将p父節點的右節點指派為s節點
if (sr != null)
replacement = sr; // 尋找replacement節點(用來替換掉p節點)
else
replacement = p; // 尋找replacement節點
}
else if (pl != null) // 如果p的左節點不為空,右節點為空,replacement節點為p的左節點
replacement = pl;
else if (pr != null) // 如果p的右節點不為空,左節點為空,replacement節點為p的右節點
replacement = pr;
else // 如果p的左右節點都為空, 即p為葉子節點, 替換節點為p節點本身
replacement = p;
// 第三次調整start
if (replacement != p) { // 如果p節點不是葉子節點
//将replacement節點的父節點指派為p節點的父節點, 同時指派給pp節點
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null) // 如果p節點沒有父節點, 即p為root節點
root = replacement; // 則将root節點指派為replacement節點即可
else if (p == pp.left) // 如果p節點不是root節點, 并且p節點為父節點的左節點
pp.left = replacement; // 則将p父節點的左節點指派為替換節點
else // 如果p節點不是root節點, 并且p節點為父節點的右節點
pp.right = replacement; // 則将p父節點的右節點指派為替換節點
// p節點的位置已經被完整的替換為替換節點, 将p節點清空, 以便垃圾收集器回收
p.left = p.right = p.parent = null;
}
// 如果p節點不為紅色則進行紅黑樹删除平衡調整
// (如果删除的節點是紅色則不會破壞紅黑樹的平衡無需調整)
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // 如果p節點為葉子節點, 則簡單的将p節點去除即可
TreeNode<K,V> pp = p.parent; // pp指派為p節點的父節點
p.parent = null; // 将p的parent節點設定為空
if (pp != null) { // 如果p的父節點存在
if (p == pp.left) // 如果p節點為父節點的左節點
pp.left = null; // 則将父節點的左節點指派為空
else if (p == pp.right) // 如果p節點為父節點的右節點
pp.right = null; // 則将父節點的右節點指派為空
}
}
if (movable)
moveRootToFront(tab, r); // 将root節點移到索引位置的頭結點
}
- 如果table為空或者length為0直接傳回。
- 根據hash值和length-1位于運算計算出索引的位置。
- 将索引位置的頭結點指派給first和root，removeTreeNode方法是被将要移除的節點node調用，是以removeTreeNode方法裡的this即為将要被移除的節點node，将node的next節點指派給succ節點，prev節點指派給pred節點。
- 如果node節點的prev節點為空，則代表要被移除的node節點為頭結點，則将table索引位置的值和first節點的值指派為node的next節點（succ節點）即可。
- 否則将node的prev節點（pred節點）的next節點設定為node的next節點（succ節點），如果succ節點不為空，則将succ的prev節點設定為pred，與前面對應（TreeNode連結清單的移除，見開頭第8點）。
- 如果進行到此first節點為空，則代表該索引位置已經沒有節點則直接傳回。
- 如果root的父節點不為空，則将root指派為根結點（root在上面被指派為索引位置的頭結點，索引位置的頭節點并不一定為紅黑樹的根結點）。
- 通過root節點來判斷此紅黑樹是否太小，如果太小則轉為連結清單節點并傳回（轉連結清單後就無需再進行下面的紅黑樹處理），連結清單維護部分到此結束，此前的代碼說明了，紅黑樹在進行移除的同時也會維護連結清單結構，之後的代碼為紅黑樹的移除節點處理。
- 上面已經說了this為将要被移除的node節點，将p節點指派為将要被移除的node節點（則此時p節點就是我們要移除的節點），pl指派為node的左節點, pr指派為node的右節點（方法的指令見開頭第6點），replacement變量用來存儲将要替換掉被移除的node節點。
- 如果p的左節點和右節點都不為空時，s節點指派為p的右節點；向s的左節點一直向左查找, 直到葉子節點，跳出循環時，s為葉子節點；交換p節點和s節點（葉子節點）的顔色（此文下面的所有操作都是為了實作将p節點和s節點進行位置調換，是以此處先将顔色替換）；sr指派為s節點的右節點，pp節點指派為p節點的父節點（指令規律見文章開頭第6點）。
- PS：下面的第一次調整和第二次調整是将p節點和s節點進行了位置調換，然後找出要替換掉p節點的replacement；第三次調整是将replacement節點覆寫掉p節點；這部分的代碼邏輯比較不容易了解透，建議自己動手畫圖模拟。（下文圖解1即為這三次調整的例子）
- 進行第一次調整：如果p節點的右節點即為葉子節點，将p的父節點指派為s，将s的右節點指派為p即可；否則，将p的父節點指派為s的父節點sp，并判斷sp是否為空，如果不為空，并判斷s是sp的左節點還是右節點，将s節點替換為p節點；将s的右節點指派為p節點的右節點pr，如果pr不為空則将pr的父節指派為s節點。
- 進行第二次調整：将p節點的左節點清空（上文pl已經儲存了該節點）；将p節點的右節點指派為s的右節點sr，如果sr不為空，則将sr的父節點指派為p節點；将s節點的左節點指派為p的左節點pl，如果pl不為空，則将p左節點的父節點指派為s節點；将s的父節點指派為p的父節點pp，如果pp為空，則p節點為root節點，此時交換後s成為新的root節點，将root指派為s節點；如果p不為root節點，并且p是父節點的左節點，将p父節點的左節點指派為s節點；如果p不為root節點，并且p是父節點的右節點，将p父節點的右節點指派為s節點；如果sr不為空，将replacement指派為sr節點，否則指派為p節點（為什麼sr是replacement的首選，p為備選？見解釋1）。
- 承接第10點的判斷，第10點~第12點為p的左右節點都不為空的情況需要進行的處理；如果p的左節點不為空，右節點為空，将replacement指派為p的左節點即可；如果p的右節點不為空，左節點為空，将replacement指派為p的右節點即可；如果p的左右節點都為空，即p為葉子節點, 将replacement指派為p節點本身。
- 進行第三次調整：如果p節點不是replacement（即p不是葉子節點），将replacement的父節點指派為p的父節點，同僚指派給pp節點；如果pp為空（p節點沒有父節點），即p為root節點，則将root節點指派為replacement節點即可；如果p節點不是root節點，并且p節點為父節點的左節點，則将p父節點的左節點指派為replacement節點；如果p節點不是root節點，并且p節點為父節點的右節點，則将p父節點的右節點指派為replacement節點；p節點的位置已經被完整的替換為replacement節點, 将p節點清空。
- 如果p節點不為紅色則進行紅黑樹删除平衡調整（如果删除的節點是紅色則不會破壞紅黑樹的平衡無需調整，見文末的解釋2）。
- 如果p節點為葉子節點，則簡單的将p節點移除：将pp指派為p節點的父節點，将p的parent節點設定為空，如果p的父節點pp存在，如果p節點為父節點的左節點，則将父節點的左節點指派為空，如果p節點為父節點的右節點，則将父節點的右節點指派為空。
- 如果movable為true，則調用moveRootToFront方法（見上文代碼塊8）将root節點移到索引位置的頭結點。
解釋1：為什麼sr是replacement的首選，p為備選？
解析：首先我們看sr是什麼？從代碼中可以看到sr第一次被指派時，是在s節點進行了向左窮周遊結束後，是以此時s節點是沒有左節點的，sr即為s節點的右節點。而從上面的三次調整我們知道，p節點已經跟s節點進行了位置調換，是以此時sr其實是p節點的右節點，并且p節點沒有左節點，是以要移除p節點，隻需要将p節點的右節點sr覆寫掉p節點即可，是以sr是replacement的首選，如果sr為空，則代表p節點為葉子節點，此時将p節點清空即可。
圖解1：removeTreeNode圖解
本圖解忽略紅黑樹的顔色，請注意。
下面的圖解是代碼中的最複雜的情況，即流程最長的那個，p節點不為根結點，p節點有左右節點，s節點不為pr節點，s節點有右節點。
解釋2：關于紅黑樹的平衡調整？
答：紅黑樹的操作涉及的操作比較複雜，三言兩語無法說清。有興趣的可以去單獨學習，本文由于篇幅關系暫不詳細介紹紅黑樹的具體操作，在這簡單的介紹：紅黑樹是一種自平衡二叉樹，擁有優秀的查詢和插入/删除性能，廣泛應用于關聯數組。
對比AVL樹，AVL要求每個結點的左右子樹的高度之差的絕對值（平衡因子）最多為1，而紅黑樹通過适當的放低該條件（紅黑樹限制從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長，結果是這個樹大緻上是平衡的），以此來減少插入/删除時的平衡調整耗時，進而擷取更好的性能，而這雖然會導緻紅黑樹的查詢會比AVL稍慢，但相比插入/删除時擷取的時間，這個付出在大多數情況下顯然是值得的。
在HashMap中的應用：HashMap在進行插入和删除時有可能會觸發紅黑樹的插入平衡調整（balanceInsertion方法）或删除平衡調整（balanceDeletion ）方法，調整的方式主要有以下手段：左旋轉（rotateLeft方法）、右旋轉（rotateRight方法）、改變節點顔色（x.red = false、x.red = true），進行調整的原因是為了維持紅黑樹的資料結構。
死循環問題
在Jdk 1.8以前，Java語言在并發情況下使用HashMap造成Race Condition，進而導緻死循環。程式經常占了100%的CPU，檢視堆棧，你會發現程式都Hang在了HashMap.get()這個方法上了，重新開機程式後問題消失。具體分析可以檢視這篇文章：疫苗：JAVA HASHMAP的死循環，有人将這個問題當成一個bug提給了Sun，但是Sun認為這并不是個bug，因為HashMap本來就不保證并發的線程安全性，在并發下，要用ConcurrentHashMap來代替。
那麼，在Jdk 1.8的時候，這個問題解決了嗎？
我們知道，Jdk 1.8以前，導緻死循環的主要原因是擴容後，節點的順序會反掉，如下圖：擴容前節點A在節點C前面，而擴容後節點C在節點A前面。
JDK 1.8擴容過程
JDK1.8 普通連結清單的擴容代碼，如下圖所示，在上文已經分析過了：主要是在一個do/while中處理同一個位置的所有節點。
前提：我們假設有3個節點，節點A，節點B，節點C，并且假設他們的hash值等于key值，則按上圖擴容的過程模拟如下。
先看下老表和新表計算索引位置的過程：（hash計算省略前面28位0，隻看最後4位）
具體擴容過程：
結果：可以看出，擴容後，節點A和節點C的先後順序跟擴容前是一樣的。是以，即使此時有多個線程并發擴容，也不會出現死循環的情況。當然，這仍然改變不了HashMap仍是非并發安全，在并發下，還是要使用ConcurrentHashMap來代替。
HashMap和Hashtable的差別：
- HashMap允許key和value為null，Hashtable不允許。
- HashMap的預設初始容量為16，Hashtable為11。
- HashMap的擴容為原來的2倍，Hashtable的擴容為原來的2倍加1。
- HashMap是非線程安全的，Hashtable是線程安全的。
- HashMap的hash值重新計算過，Hashtable直接使用hashCode。
- HashMap去掉了Hashtable中的contains方法。
- HashMap繼承自AbstractMap類，Hashtable繼承自Dictionary類。
總結：
- HashMap的底層是個Node數組（Node<K,V>[] table），在數組的具體索引位置，如果存在多個節點，則可能是以連結清單或紅黑樹的形式存在。
- 增加、删除、查找鍵值對時，定位到哈希桶數組的位置是很關鍵的一步，源碼中是通過下面3個操作來完成這一步：1）拿到key的hashCode值；2）将hashCode的高位參與運算，重新計算hash值；3）将計算出來的hash值與(table.length - 1)進行&運算。
- HashMap的預設初始容量（capacity）是16，capacity必須為2的幂次方；預設負載因子（load factor）是0.75；實際能存放的節點個數（threshold，即觸發擴容的門檻值）= capacity * load factor。
- HashMap在觸發擴容後，門檻值會變為原來的2倍，并且會進行重hash，重hash後索引位置index的節點的新分布位置最多隻有兩個：原索引位置或原索引+oldCap位置。例如capacity為16，索引位置5的節點擴容後，隻可能分布在新報索引位置5和索引位置21（5+16）。
- 導緻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個時，會觸發連結清單節點（Node）轉紅黑樹節點（TreeNode，間接繼承Node），轉成紅黑樹節點後，其實連結清單的結構還存在，通過next屬性維持。連結清單節點轉紅黑樹節點的具體方法為源碼中的treeifyBin(Node<K,V>[] tab, int hash)方法。
- 當同一個索引位置的節點在移除後達到6個時，并且該索引位置的節點為紅黑樹節點，會觸發紅黑樹節點轉連結清單節點。紅黑樹節點轉連結清單節點的具體方法為源碼中的untreeify(HashMap<K,V> map)方法。
- HashMap在JDK1.8之後不再有死循環的問題，JDK1.8之前存在死循環的根本原因是在擴容後同一索引位置的節點順序會反掉。
- HashMap是非線程安全的，在并發場景下使用ConcurrentHashMap來代替。
原部落格位址：https://blog.csdn.net/v123411739/article/details/78996181