文章目錄
- 一、前置知識
-
- 紅黑樹定義
- 二、構造方法
-
- HashMap()
- HashMap(int initialCapacity, float loadFactor)
-
- tableSizeFor(int cap)：計算hashmap初始容量
- 三、put 方法源碼
-
- 1. put()
-
- hash(Object key)：計算key的hash值
- 2. putVal()
-
- 通過 hash 計算數組下标
- 3. resize()：擴容
-
- 擴容時計算數組下标
- 4. treeifyBin(tab, hash)：連結清單轉為紅黑樹
-
- treeify()：雙向連結清單轉為紅黑樹
-
- comparableClassFor()：是否實作了 Comparable 接口
- compareComparables()：調用Comparable接口的compareTo()方法
- tieBreakOrder()：當key的比較結果相同時，打破平衡（使比較結果不相等）
- 5. split()：分割紅黑樹
-
- untreeify()：雙向連結清單轉單向連結清單
- 6. putTreeVal()：往紅黑樹中插入節點
-
- find()：在紅黑樹中查找
- balanceInsertion()：（紅黑樹中插入值後）平衡紅黑樹
- rotateLeft()：左旋
- rotateRight()：右旋
- moveRootToFront()：将 root 節點放入數組中
- 總結
一、前置知識
紅黑樹定義
紅黑樹是每個結點都帶有顔色屬性的二叉查找樹，顔色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:
- 結點是紅色或黑色。
- 根結點是黑色。
- 所有葉子都是黑色。（葉子是NIL結點）
- 每個紅色結點的兩個子結點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的紅色結點）
- 從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點。
二、構造方法
HashMap()
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 如果指定的容量大于 1 << 30, 則指定為最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 将非2的幂次的容量，指定為2的幂次
// hashmap的容量是2的幂，如果傳入的參數不是2的幂，則會算出比該參數大的最小的2的幂次的數；例如，傳入3，則容量4；傳入12，則容量16
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor(int cap)：計算hashmap初始容量
static final int tableSizeFor(int cap) {
// 減1之後，用最高位的 1 把後面每一位都變成 1，此時再加1時，就是2的幂次
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;
}
三、put 方法源碼
1. put()
public V put(K key, V value) {
// 計算 key 的 hash 值
return putVal(hash(key), key, value, false, true);
}
hash(Object key)：計算key的hash值
/**
* 計算 key.hashCode() 并将散列的高位散布 (XOR) 到低位。
* 因為該表使用二次方掩碼，是以僅在目前掩碼以上的位上有所不同的散列集将始終發生沖突。 （在已知的例子中有一組 Float 鍵在小表中儲存連續的整數。）
* 是以我們應用一個轉換來向下傳播較高位的影響。在位擴充的速度、效用和品質之間存在權衡。
* 因為許多常見的哈希集已經合理分布（是以不會從傳播中受益），并且因為我們使用樹來處理 bins 中的大量沖突，是以我們隻是以最便宜的方式對一些移位的位進行 XOR 以減少系統損失，以及合并最高位的影響，否則由于表邊界而永遠不會在索引計算中使用這些位。
*/
static final int hash(Object key) {
int h;
// key hashcode 的值(32位)，高16位與低16位按位異或
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
2. putVal()
該方法主要考慮以下幾種情況：
放值前：
- 初始化時，未指定 HashMap 的容量，設定預設容量為 16
存放值時：
- 數組節點上沒有存任何 key，即沒有發生 hash 碰撞
- 數組節點的 key 和新 put 的 key 一樣
- 數組節點是紅黑樹
- 數組節點是連結清單
放完後：
- 檢查 hashmap 中所有元素個數，超過 負載因子*容量，則擴容
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 通路局部變量而不是類屬性的了解：通路棧空間比通路堆空間更快（逃逸分析、棧上配置設定）
// tab：數組；p：point，指針，目前通路的節點；n：數組大小；i：k hash值對應的數組下标
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// 初始化時，未指定 HashMap 的容量，容量為 0，需先擴容
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 數組上的節點中沒有存值
tab[i] = newNode(hash, key, value, null);
else {
// e：hashmap 中存在key和新插入key相同的舊節點
// k：舊節點的 key
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 數組節點上的 key 和新插入的 key 一緻
e = p;
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
// 當第9個插入完成後（此時binCount=7），連結清單轉成紅黑樹
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 周遊連結清單時發現的相同key的情況
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// 存在舊的值，如果是 put() 方法，就替換，如果是 putIfAbsent() 方法就不替換
e.value = value;
afterNodeAccess(e);
// 傳回舊值
return oldValue;
}
}
++modCount;
if (++size > threshold)
// 如果數組中元素個數大于 容量*負載因子，則擴容
resize();
afterNodeInsertion(evict);
return null;
}
通過 hash 計算數組下标
通過 hash 值計算對應的數組下标：
(n - 1) & hash
n 是數組大小，是 2 的幂，對應的二進制就是最高位是 1，其餘位全是 0
我對該算法的了解：
- n-1 後，每個位上的值必須都是 1，是以 n 必須是 2 的幂
- 因為該算法隻是取 int 的低位，是以在計算 hash 值的時候，将高16位與低16位進行異或運算，減少高位不同而低位相同産生的 hash 碰撞
3. resize()：擴容
/**
* 初始化或表大小 * 2。
* 如果為空，則在最大值中保持的初始容量目标。
* 否則，數組大小*2，hashmap 中每個元素必須保持在相同的索引中或者在新表的2的幂的偏移中
*/
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) {
if (oldCap >= MAXIMUM_CAPACITY) {
// 數組已經是最大容量的情況，不擴容，擴容門檻指派為最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量*2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 擴容後容量<最大容量且舊容量>=16時，擴充門檻*2
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 設定預設容量大小是 16，擴容門檻（容量*負載因子）是12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 擴容門檻為 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) {
// 如果舊的數組中有值
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
// 數組中是連結清單的情況
// 高位和低位的了解：擴容後，原先相同hash的key，隻會被分到新數組的兩個位置，大的位置叫高位，小的位置叫低位
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;
}
擴容時計算數組下标
4. treeifyBin(tab, hash)：連結清單轉為紅黑樹
/**
* 替換給定哈希的索引處所有連結清單節點，除非表太小，在這種情況下會擴容。
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 如果數組沒有被初始化或者數組長度小于64，擴容
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// hd(head)：頭結點 tl(tail)：尾結點
TreeNode<K,V> hd = null, tl = null;
do {
// 将 Node 結點轉換為 TreeNode 結點
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);
}
}
treeify()：雙向連結清單轉為紅黑樹
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) { // x/this：雙向連結清單頭節點
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) { // 紅黑樹根節點
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph; //dir：辨別大小（負數插入左子樹中，正數插入右子樹中）；ph：父節點hash值；pk：父節點key
K pk = p.key;
if ((ph = p.hash) > h) //要插入的節點hash值比父節點小（往左繼續疊代）
dir = -1;
else if (ph < h) //要插入的節點hash值比父節點大（往右繼續疊代）
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) || // hash相同但key不相同，且沒有實作Comparable接口
(dir = compareComparables(kc, k, pk)) == 0) // 或者key實作了Comparable接口，調用compareTo()方法傳回0
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root); //root節點放入數組中，且root節點是雙向連結清單頭節點
}
comparableClassFor()：是否實作了 Comparable 接口
是否實作了
Comparable
接口，如果實作了則傳回對應的
Class
對象，沒有實作則傳回
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) // String類型直接傳回
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) && // 如果實作了Comparable接口就繼續往下走
(as = p.getActualTypeArguments()) != null && //擷取Comparable<>中的泛型數組
as.length == 1 && as[0] == c) // 泛型長度是1且類型是c，則傳回
return c;
}
}
}
return null; // 沒有實作Comparable則傳回Null
}
ParameterizedType 和使用：
- ParameterizedType 參數化類型及其父類 Type 詳解
compareComparables()：調用Comparable接口的compareTo()方法
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
tieBreakOrder()：當key的比較結果相同時，打破平衡（使比較結果不相等）
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) ? // 類名也相同的情況比較位址hash
-1 : 1);
return d;
}
5. split()：分割紅黑樹
/**
* 将紅黑樹中的節點拆分為低位和高位的雙向連結清單，如果紅黑樹裡結點數太少，則退化為單向連結清單。
*/
final void split(java.util.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;
// lc(low count)：低位結點數量 hc(high count)：高位結點數量
int lc = 0, hc = 0;
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) {
if (lc <= UNTREEIFY_THRESHOLD)
// 如果低位連結清單結點數量少于6，則紅黑樹退化為單向連結清單
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);
}
}
}
untreeify()：雙向連結清單轉單向連結清單
final Node<K,V> untreeify(java.util.HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
// q 是數組中的紅黑樹結點
for (Node<K,V> q = this; q != null; q = q.next) {
// 将 TreeNode 對象替換為 Node 對象（紅黑樹結點轉換為單向連結清單結點）
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
6. putTreeVal()：往紅黑樹中插入節點
與 treeify() 方法相比：
- treeify()：
- 對紅黑樹根節點的判斷
- putTreeVal()：
- 多了 key 值相同時的判斷
紅黑樹插入後平衡調整規則：
規定新插入的節點是紅色：
- 根節點直接插入，變為黑色
- 如果父節點是黑色，則直接插入
- 如果父節點是紅色：
- 叔叔節點是空或黑色，旋轉加變色
- 叔叔節點是紅色，父節點和叔叔節點變黑色，祖父節點變紅色
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) { //this：TreeNode；h：要插入的key的hash值；k：要插入的key；v：要插入的value
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this; //找到root節點
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk; //dir：正負辨別大小；ph：父節點hash值；pk：父節點key
if ((ph = p.hash) > h) //要插入的節點hash值比父節點小（往左繼續疊代）
dir = -1;
else if (ph < h) //要插入的節點hash值比父節點大（往右繼續疊代）
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk))) //key值相同
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) || // hash相同但key不相同，且沒有實作Comparable接口
(dir = compareComparables(kc, k, pk)) == 0) { // 或者key實作了Comparable接口，調用compareTo()方法傳回0
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; // 查到了相同的key，就傳回
}
dir = tieBreakOrder(k, pk); //打破要插入節點和父節點相等的狀态（類名排序，類名相同時identityHashCode排序）
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) { //<=0時走左邊，>0時走右邊
// 當周遊到葉子節點時
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); //建立節點，next節點指向xpn（雙向連結清單角度看，新節點插到了父節點後面）
if (dir <= 0)
xp.left = x; //葉子節點指派
else
xp.right = x;
xp.next = x; //父節點next指針指向新節點
x.parent = x.prev = xp; //新節點的parent和prev指針指向父節點
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x; // 雙向連結清單指針調整
moveRootToFront(tab, balanceInsertion(root, x)); // 平衡紅黑樹後，并root節點放入數組中，且root節點是雙向連結清單頭節點
return null;
}
}
}
find()：在紅黑樹中查找
final TreeNode<K,V> find(int h, Object k, Class<?> kc) { // h：被查找key的hash；k：被查找的key；kc：被查找的key的Class對象
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) //往左周遊
p = pl;
else if (ph < h) //往右周遊
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 找到了對應的Key
return p; //将找到的Key傳回
// 下面都是hash沖突的情況
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0) //key實作了Comparable接口的情況
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null) //比較不出大小來，先右子樹繼續周遊
return q;
else //最後左子樹周遊
p = pl;
} while (p != null);
return null; // 沒有查到傳回null
}
balanceInsertion()：（紅黑樹中插入值後）平衡紅黑樹
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, // 紅黑樹根節點
TreeNode<K,V> x) { // 新插入的節點
x.red = true; //新插入的節點是紅色的
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //xp：父節點；xpp：祖父節點；xppl：祖父節點左孩子結點；xppr：祖父節點右孩子節點
if ((xp = x.parent) == null) { //新插入的節點是根節點的情況
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null) //父節點是黑的，或者父節點是根節點
return root;
//以下都是父節點是紅色的情況
if (xp == (xppl = xpp.left)) { //xp 在 xpp 左子樹的情況（如下圖）
if ((xppr = xpp.right) != null && xppr.red) { // 如圖1，叔叔（右）節點是紅色的
xppr.red = false; //叔叔節點和父節點變黑
xp.red = false;
xpp.red = true; //祖父節點變紅，如圖2
x = xpp; //繼續疊代
}
else { // 圖3
if (x == xp.right) {
root = rotateLeft(root, x = xp); //左旋 圖4
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true; // 圖5
root = rotateRight(root, xpp); //右旋，如圖6
}
}
}
}
else { // 在右子樹的情況與上面處理類似
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp); // 先右旋
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp); // 再左旋
}
}
}
}
}
}
rotateLeft()：左旋
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null) // 圖2
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r; // 圖3
r.left = p; // 圖4
p.parent = r;
}
return root;
}
rotateRight()：右旋
與左旋操作相反
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
moveRootToFront()：将 root 節點放入數組中
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) {
Node<K,V> rn;
tab[index] = root; // 數組中放root節點
// 将root節點從雙向連結清單中删除
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
// root節點放到first節點前面（雙向連結清單頭節點）
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
總結
- 容量是2的幂次，當存的數達到 容量*0.75 時，擴容
- 數組先存單向連結清單，連結清單上的節點個數超過8時，如果數組大小沒有達到64，則擴容，否則連結清單轉換成雙向連結清單（仍然存在）再轉換成紅黑樹
- 擴容時，如果紅黑樹中的節點個數小于等于6，則紅黑樹退化成單向連結清單