HashMap

基于JDK8。
HashMap在我們的日常開(kāi)發(fā)中是十分常用的鍵值對(duì)集合,我們來(lái)深入探究下HashMap的設(shè)計(jì)。

1、HashMap的繼承體系

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable

2、HashMap底層數(shù)據(jù)結(jié)構(gòu)

這里先把答案給出。
稍后再去探究，為什么使用鏈表處理哈希沖突，JDK8為什么引入紅黑樹(shù)，紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)有什么特點(diǎn)，為什么會(huì)用64, 8, 6這幾個(gè)數(shù)字作為閾值？為什么元素個(gè)數(shù)達(dá)到容量的0.75倍時(shí)就擴(kuò)容？

JDK8之前 是數(shù)組 + 鏈表 。

JDK8 是數(shù)組 + 鏈表|紅黑樹(shù)。

鏈表的主要目的是解決哈希沖突（hash collision）問(wèn)題。

JDK8的HashMap鏈表轉(zhuǎn)換為紅黑樹(shù)的條件：
鏈表長(zhǎng)度 >= 8
數(shù)組容量 >= 64

紅黑樹(shù)轉(zhuǎn)換回鏈表的條件：
紅黑樹(shù)節(jié)點(diǎn)數(shù) <= 6

3、HashMap的構(gòu)造函數(shù)

①、無(wú)參構(gòu)造

// 加載因子，用于控制哈希表的擴(kuò)容頻率
final float loadFactor;// 默認(rèn)的加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {// 使用默認(rèn)的加載因子this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}

②、有參構(gòu)造1 和 有參構(gòu)造2 (可以自定義初始容量和負(fù)載因子)

// 加載因子，用于控制哈希表的擴(kuò)容頻率
final float loadFactor;// 默認(rèn)的加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 哈希表的最大容量    2的30次方   1,073,741,824   10億多
static final int MAXIMUM_CAPACITY = 1 << 30;// 擴(kuò)容閾值，當(dāng)哈希表中元素個(gè)數(shù)超過(guò)這個(gè)值時(shí)，會(huì)觸發(fā)擴(kuò)容
int threshold;/*** 有參構(gòu)造函數(shù)1：只接受初始容量參數(shù)* @param initialCapacity 初始容量*/
public HashMap(int initialCapacity) {// 調(diào)用另一個(gè)構(gòu)造函數(shù)，使用默認(rèn)加載因子this(initialCapacity, DEFAULT_LOAD_FACTOR);
}/*** 有參構(gòu)造函數(shù)2：接受初始容量和加載因子參數(shù)* @param initialCapacity 初始容量* @param loadFactor 加載因子*/
public HashMap(int initialCapacity, float loadFactor) {// 檢查初始容量是否為負(fù)數(shù)，如果是負(fù)數(shù)，拋出非法參數(shù)異常if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);// 如果初始容量超過(guò)最大容量，則將初始容量設(shè)置為最大容量if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;// 檢查加載因子是否有效，如果小于等于0或不是一個(gè)有效數(shù)字，則拋出非法參數(shù)異常if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " + loadFactor);// 設(shè)置實(shí)例的加載因子this.loadFactor = loadFactor;// 根據(jù)初始容量計(jì)算擴(kuò)容閾值this.threshold = tableSizeFor(initialCapacity);
}/*** 計(jì)算大于等于給定容量的最小2的冪次方值* @param cap 給定的容量值* @return 大于等于cap的最小2的冪次方值*/
static final int tableSizeFor(int cap) {int n = cap - 1;// 將所有位置為1的位向右傳播n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;// 確保返回值在合法范圍內(nèi)return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

這里再拋一個(gè)問(wèn)題，為什么我們傳自定義大小的容量，HashMap要調(diào)用tableSizeFor方法取大于等于自定義容量的最小2的冪次方值。
比如我們傳入35，tableSizeFor計(jì)算得出36 ，HashMap就使用36作為容量。這個(gè)問(wèn)題也在后面進(jìn)行探究。

③、有參構(gòu)造3(接受一個(gè)Map參數(shù))

這個(gè)構(gòu)造方法就比較復(fù)雜了，涉及添加元素和擴(kuò)容等操作，暫時(shí)就不展開(kāi)了，后面單獨(dú)去看添加元素和擴(kuò)容操作。

// 加載因子，用于控制哈希表的擴(kuò)容頻率
final float loadFactor;// 默認(rèn)的加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 哈希表的最大容量，2的30次方，即1,073,741,824（10億多）
static final int MAXIMUM_CAPACITY = 1 << 30;// 哈希表的底層數(shù)組，存儲(chǔ)鍵值對(duì)
transient Node<K,V>[] table;// 擴(kuò)容閾值，當(dāng)哈希表中元素個(gè)數(shù)超過(guò)這個(gè)值時(shí)，會(huì)觸發(fā)擴(kuò)容
int threshold;/*** 有參構(gòu)造函數(shù)3：接受一個(gè)Map參數(shù)* @param m 初始化時(shí)用的Map*/
public HashMap(Map<? extends K, ? extends V> m) {// 使用默認(rèn)加載因子this.loadFactor = DEFAULT_LOAD_FACTOR;// 將傳入的Map中的所有元素添加到當(dāng)前HashMap中putMapEntries(m, false);
}/*** 將指定的Map中的所有元素添加到當(dāng)前HashMap中* @param m 指定的Map* @param evict 是否驅(qū)逐舊元素（此參數(shù)在其他上下文中使用，這里傳入false）*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {// 獲取指定Map的大小int s = m.size();if (s > 0) {// 如果當(dāng)前哈希表還未初始化（即底層數(shù)組為空）if (table == null) { // 預(yù)先調(diào)整大小// 計(jì)算預(yù)期的擴(kuò)容閾值，公式為：(指定Map的大小 / 加載因子) + 1float ft = ((float)s / loadFactor) + 1.0F;// 如果計(jì)算結(jié)果小于最大容量，則取計(jì)算結(jié)果，否則取最大容量int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 如果計(jì)算結(jié)果大于當(dāng)前的擴(kuò)容閾值，則更新擴(kuò)容閾值if (t > threshold)threshold = tableSizeFor(t);}// 如果當(dāng)前哈希表已初始化，并且指定Map的大小超過(guò)了當(dāng)前的擴(kuò)容閾值else if (s > threshold)// 擴(kuò)容哈希表resize();// 將指定Map中的每個(gè)鍵值對(duì)添加到當(dāng)前哈希表中for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = e.getValue();// 使用putVal方法添加鍵值對(duì)putVal(hash(key), key, value, false, evict);}}
}/*** 計(jì)算給定鍵的哈希值* @param key 給定的鍵* @return 哈希值*/
final int hash(Object key) {int h;// 計(jì)算哈希值，并進(jìn)行哈希擾動(dòng)，增加哈希分布的隨機(jī)性return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

可以看到這里的final int hash(Object key)方法是對(duì)鍵的hashCode進(jìn)行二次hash的方法。

JDK 8之前版本的哈希方法：

static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}

JDK 7的hash方法通過(guò)異或操作 (^) 和右移操作 (>>>) 對(duì)原始哈希碼進(jìn)行擾動(dòng)，以減少?zèng)_突。

JDK 8版本的哈希方法

/*** 計(jì)算給定鍵的哈希值* @param key 給定的鍵* @return 哈希值*/
final int hash(Object key) {int h;// 計(jì)算哈希值，并進(jìn)行哈希擾動(dòng)，增加哈希分布的隨機(jī)性return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

JDK 8 通過(guò)將哈希碼右移16位并與原始哈希碼異或 (h = key.hashCode() ^ (key.hashCode() >>> 16)) 來(lái)擾動(dòng)哈希碼，提高哈希分布的隨機(jī)性。

JDK 8的擾動(dòng)方式計(jì)算步驟更簡(jiǎn)單高效，有助于減少哈希沖突，提高哈希表的性能。

4、拉鏈法解決哈希沖突

什么是拉鏈法？

拉鏈法就是數(shù)組和鏈表結(jié)合，每個(gè)數(shù)組的元素存儲(chǔ)的是一個(gè)鏈表（或在JDK 8中鏈表長(zhǎng)度超過(guò)一定閾值時(shí)使用紅黑樹(shù)）。當(dāng)發(fā)生哈希沖突時(shí)，只需要將新的元素插入鏈表或樹(shù)中。

上圖中a,c,d元素由于哈希沖突，就組成了一個(gè)鏈表，當(dāng)我們查找d時(shí)，先計(jì)算出下標(biāo)index是1，發(fā)現(xiàn)鏈表的頭是a不是d，就繼續(xù)向下遍歷鏈表直到找到d為止。

動(dòng)畫(huà)演示拉鏈法解決哈希沖突：

拉鏈法有哪些好處？ 還有其他解決哈希沖突的方式嗎？

拉鏈法解決哈希沖突的優(yōu)點(diǎn)：

• ①.簡(jiǎn)單高效：拉鏈法實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單，每個(gè)數(shù)組元素存儲(chǔ)的是一個(gè)鏈表。當(dāng)發(fā)生哈希沖突時(shí)，只需要將新的元素插入鏈表中，插入和查找操作的平均時(shí)間復(fù)雜度較低。

• ②、空間利用率高：拉鏈法在沖突發(fā)生時(shí)不需要額外的數(shù)組空間，只需在鏈表中插入新節(jié)點(diǎn)，節(jié)省空間。

• ③、動(dòng)態(tài)擴(kuò)展：JDK8使用的鏈表和紅黑樹(shù)都能動(dòng)態(tài)地?cái)U(kuò)展，不需要預(yù)先分配大量?jī)?nèi)存，并且在元素很多時(shí)可以通過(guò)擴(kuò)容數(shù)組(哈希表)來(lái)降低每個(gè)鏈表的長(zhǎng)度，維持高效的查找性能。

• ④、易于實(shí)現(xiàn)的擴(kuò)容機(jī)制：在拉鏈法中，擴(kuò)容只需重新分配一個(gè)更大的數(shù)組，然后重新哈?，F(xiàn)有的元素。這一過(guò)程較為簡(jiǎn)單(實(shí)際上JDK通過(guò)特殊的手段讓重新計(jì)算擴(kuò)容后的元素位置變得簡(jiǎn)單，這個(gè)手段就是數(shù)組(哈希表)的容量永遠(yuǎn)都是2的整數(shù)倍)，不需要處理復(fù)雜的元素遷移問(wèn)題。

其他解決哈希沖突的方式(了解下)：

再哈希法（Rehashing）：
????使用不同的哈希函數(shù)重新計(jì)算發(fā)生沖突的元素的位置。再哈希法會(huì)在原哈希函數(shù)發(fā)生沖突時(shí)，使用一個(gè)新的哈希函數(shù)重新計(jì)算索引,需要再次計(jì)算哈希值，性能較低，特別是多次哈希沖突的情況下。

Cuckoo Hashing（布谷鳥(niǎo)哈希）：
????使用兩個(gè)或更多的哈希函數(shù)和兩個(gè)或更多的哈希表。當(dāng)一個(gè)位置發(fā)生沖突時(shí)，將現(xiàn)有元素移到它的另一個(gè)可能位置（類似于布谷鳥(niǎo)在鳥(niǎo)巢中下蛋），如果新位置也有沖突，則繼續(xù)遷移，直到找到一個(gè)空位或達(dá)到遷移限制。

開(kāi)放地址法（Open Addressing）：

• 線性探測(cè)（Linear Probing）：當(dāng)發(fā)生沖突時(shí)，按固定步長(zhǎng)（通常為1）向前探測(cè)下一個(gè)位置，直到找到一個(gè)空位或回到原位置。
• 二次探測(cè)（Quadratic Probing）：探測(cè)步長(zhǎng)按平方序列增長(zhǎng)（如1, 4, 9, 16…），以減少聚集效應(yīng)。
• 雙重散列（Double Hashing）：使用兩個(gè)不同的哈希函數(shù)，當(dāng)?shù)谝粋€(gè)哈希函數(shù)發(fā)生沖突時(shí)，用第二個(gè)哈希函數(shù)計(jì)算探測(cè)步長(zhǎng)。

線性散列法（Linear Hashing）：
????一種動(dòng)態(tài)哈希方法，通過(guò)漸進(jìn)式地?cái)U(kuò)展哈希表來(lái)處理沖突。在需要擴(kuò)展時(shí)，不是一次性重新分配整個(gè)哈希表，而是漸進(jìn)地調(diào)整部分元素的位置。

Hopscotch Hashing（跳躍哈希）：
????結(jié)合開(kāi)放地址法和鏈表法的優(yōu)點(diǎn)。當(dāng)沖突發(fā)生時(shí)，在一定范圍內(nèi)探測(cè)并交換元素，使得鏈表的元素能保持接近原位置，減少查找路徑長(zhǎng)度。

5、HashMap的put方法

（涉及到擴(kuò)容、樹(shù)化、反樹(shù)化等操作）

HashMap的屬性注釋

HashMap的屬性太多了，每次都在方法上面加上一些類的屬性比較麻煩，這里把所有的屬性都注釋下。

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable { // 默認(rèn)初始容量，即2的4次方，即哈希表的默認(rèn)大小為16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// 哈希表的最大容量，即2的30次方，即1073741824static final int MAXIMUM_CAPACITY = 1 << 30;// 默認(rèn)的加載因子，即哈希表的裝填因子，默認(rèn)為0.75static final float DEFAULT_LOAD_FACTOR = 0.75f;// 樹(shù)化閾值，當(dāng)鏈表長(zhǎng)度 >= 8且 容量>=64時(shí)，鏈表轉(zhuǎn)為紅黑樹(shù)static final int TREEIFY_THRESHOLD = 8;// 反樹(shù)化閾值，當(dāng)紅黑樹(shù)節(jié)點(diǎn)數(shù)量小于等于6時(shí)，紅黑樹(shù)轉(zhuǎn)為鏈表static final int UNTREEIFY_THRESHOLD = 6;// 最小樹(shù)化容量，即哈希表的最小容量為64時(shí)，鏈表可以轉(zhuǎn)為紅黑樹(shù)static final int MIN_TREEIFY_CAPACITY = 64;// 哈希表的底層數(shù)組，存儲(chǔ)鍵值對(duì)，也就是HashMap底層的數(shù)組類型是Node<K,V> transient Node<K,V>[] table;// 鍵值對(duì)集合的視圖，用于遍歷哈希表中的所有鍵值對(duì)transient Set<Map.Entry<K,V>> entrySet;// 哈希表中元素的數(shù)量transient int size;// 哈希表結(jié)構(gòu)修改的次數(shù)，用于迭代器快速失敗機(jī)制transient int modCount;// 哈希表擴(kuò)容閾值，當(dāng)哈希表中元素個(gè)數(shù)超過(guò)這個(gè)值時(shí)會(huì)觸發(fā)擴(kuò)容int threshold;// 加載因子，用于控制哈希表的擴(kuò)容頻率final float loadFactor;}

put方法

public V put(K key, V value) {// 調(diào)用putVal方法將鍵值對(duì)插入到哈希表中return putVal(hash(key), key, value, false, true);
}

putVal方法

boolean evict,該參數(shù)指示當(dāng)前的操作是否在創(chuàng)建模式下。如果為 false，表示哈希表處于創(chuàng)建模式；如果為 true，表示哈希表處于正常操作模式。此參數(shù)通常在調(diào)整哈希表大小時(shí)使用，以避免在創(chuàng)建模式中觸發(fā)刪除操作。

evict 參數(shù)為 false 的情況：
在哈希表初始化或擴(kuò)容時(shí)，通過(guò) putMapEntries 方法調(diào)用 putVal，設(shè)置 evict 為 false。

evict 參數(shù)為 true 的情況：
正常操作（非創(chuàng)建模式）下，插入或更新元素時(shí)，evict 為 true，允許執(zhí)行淘汰策略。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab;  // 哈希表(數(shù)組)Node<K,V> p;      // 當(dāng)前處理的節(jié)點(diǎn)int n, i;         // n為表的長(zhǎng)度，i為計(jì)算出的索引// 如果哈希表為空或哈希表的長(zhǎng)度為0，則進(jìn)行擴(kuò)容操作if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 計(jì)算哈希值對(duì)應(yīng)的索引，如果該索引處沒(méi)有節(jié)點(diǎn)，則創(chuàng)建新節(jié)點(diǎn)if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e;  // 臨時(shí)節(jié)點(diǎn)，用于存儲(chǔ)當(dāng)前節(jié)點(diǎn)或找到的目標(biāo)節(jié)點(diǎn)K k;          // 臨時(shí)變量，用于存儲(chǔ)節(jié)點(diǎn)的鍵// 判斷第一個(gè)節(jié)點(diǎn)的哈希值和鍵是否與插入的相同if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))e = p;  else if (p instanceof TreeNode)// 如果當(dāng)前節(jié)點(diǎn)是樹(shù)節(jié)點(diǎn)，則調(diào)用樹(shù)節(jié)點(diǎn)的插入方法e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 如果當(dāng)前節(jié)點(diǎn)不是樹(shù)節(jié)點(diǎn) 遍歷鏈表進(jìn)行插入操作for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {// 如果當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空，表示到達(dá)鏈表末端p.next = newNode(hash, key, value, null); // 在鏈表末尾插入新的節(jié)點(diǎn)// 如果鏈表長(zhǎng)度超過(guò)樹(shù)化閾值 8 ，則 調(diào)用treeifyBin // 在 treeifyBin 中會(huì)判斷 哈希表容量是否 >=64 如果 哈希表容量>=64 則樹(shù)化，否則先擴(kuò)容  // 注意 binCount 從 0 開(kāi)始計(jì)數(shù)，表示遍歷鏈表時(shí)訪問(wèn)的節(jié)點(diǎn)數(shù)，但插入新節(jié)點(diǎn)時(shí)實(shí)際的節(jié)點(diǎn)總數(shù)是 binCount + 1// TREEIFY_THRESHOLD - 1 = 8-1 = 7  所以binCount=7時(shí)  節(jié)點(diǎn)總數(shù)是 8 正好達(dá)到了閾值if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);break;}// 如果找到哈希值相同并且鍵相同的節(jié)點(diǎn)if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))break; // 結(jié)束循環(huán)// 移動(dòng)到鏈表的下一個(gè)節(jié)點(diǎn),繼續(xù)下一次循環(huán)p = e; }}// 如果找到了相同的鍵，則更新值if (e != null) {V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;// 插入后進(jìn)行后續(xù)處理  可以給HashMap的子類做擴(kuò)展  afterNodeAccess(e);return oldValue;}}// 增加修改次數(shù)++modCount;// 如果當(dāng)前元素個(gè)數(shù)超過(guò)閾值，則進(jìn)行擴(kuò)容操作if (++size > threshold)resize();// 插入后進(jìn)行后續(xù)處理 可以給HashMap的子類做擴(kuò)展  afterNodeInsertion(evict);return null;
}

putTreeVal方法

添加紅黑樹(shù)節(jié)點(diǎn)

// 在紅黑樹(shù)中插入一個(gè)新的節(jié)點(diǎn)，或者返回已存在的節(jié)點(diǎn)
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {// kc是用于比較的類Class<?> kc = null;// searched表示是否已經(jīng)搜索過(guò)樹(shù)boolean searched = false;// 如果當(dāng)前節(jié)點(diǎn)有父節(jié)點(diǎn)，則獲取樹(shù)的根節(jié)點(diǎn)，否則使用當(dāng)前節(jié)點(diǎn)TreeNode<K,V> root = (parent != null) ? root() : this;// 從根節(jié)點(diǎn)開(kāi)始遍歷樹(shù)for (TreeNode<K,V> p = root;;) {// dir表示比較方向，ph是當(dāng)前節(jié)點(diǎn)的哈希值，pk是當(dāng)前節(jié)點(diǎn)的鍵int dir, ph; K pk;// 如果當(dāng)前節(jié)點(diǎn)的哈希值大于待插入節(jié)點(diǎn)的哈希值，dir設(shè)為-1（左子樹(shù)）if ((ph = p.hash) > h)dir = -1;// 如果當(dāng)前節(jié)點(diǎn)的哈希值小于待插入節(jié)點(diǎn)的哈希值，dir設(shè)為1（右子樹(shù)）else if (ph < h)dir = 1;// 如果當(dāng)前節(jié)點(diǎn)的哈希值等于待插入節(jié)點(diǎn)的哈希值，比較鍵else if ((pk = p.key) == k || (k != null && k.equals(pk)))// 鍵相同，返回當(dāng)前節(jié)點(diǎn)return p;// 如果kc為null，嘗試獲取k的可比較類else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||// 使用可比較類比較鍵，結(jié)果為0表示鍵相同(dir = compareComparables(kc, k, pk)) == 0) {// 如果還沒(méi)有搜索過(guò)子樹(shù)if (!searched) {TreeNode<K,V> q, ch;// 標(biāo)記為已搜索searched = true;// 在左子樹(shù)和右子樹(shù)中查找if (((ch = p.left) != null &&(q = ch.find(h, k, kc)) != null) ||((ch = p.right) != null &&(q = ch.find(h, k, kc)) != null))// 找到節(jié)點(diǎn)則返回return q;}// 使用tie-break規(guī)則決定插入方向dir = tieBreakOrder(k, pk);}// 保存當(dāng)前節(jié)點(diǎn)為xpTreeNode<K,V> xp = p;// 根據(jù)dir決定向左還是向右if ((p = (dir <= 0) ? p.left : p.right) == null) {// 創(chuàng)建一個(gè)新節(jié)點(diǎn)Node<K,V> xpn = xp.next;TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);// 插入到左子樹(shù)或者右子樹(shù)if (dir <= 0)xp.left = x;elsexp.right = x;// 更新鏈表結(jié)構(gòu)xp.next = x;x.parent = x.prev = xp;if (xpn != null)((TreeNode<K,V>)xpn).prev = x;// 平衡樹(shù)并將根節(jié)點(diǎn)移動(dòng)到數(shù)組前端moveRootToFront(tab, balanceInsertion(root, x));// 返回null表示插入成功return null;}}
}

treeifyBin 方法

將哈希桶中的鏈表轉(zhuǎn)換為紅黑樹(shù)

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 檢查哈希表是否為空，或者表的長(zhǎng)度是否小于最小樹(shù)化容量// MIN_TREEIFY_CAPACITY 是一個(gè)常量（通常為64），表示樹(shù)化所需的最小表大小if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)// 如果條件滿足，則調(diào)整哈希表大小，而不是樹(shù)化resize();else if ((e = tab[index = (n - 1) & hash]) != null) {// 如果計(jì)算出的索引處的桶不為空，則進(jìn)行樹(shù)化操作// 初始化樹(shù)節(jié)點(diǎn)列表的頭和尾TreeNode<K,V> hd = null, tl = null;do {// 將當(dāng)前鏈表節(jié)點(diǎn)轉(zhuǎn)換為樹(shù)節(jié)點(diǎn)TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)// 如果這是第一個(gè)節(jié)點(diǎn)，將其設(shè)為頭節(jié)點(diǎn)hd = p;else {// 否則，將當(dāng)前節(jié)點(diǎn)鏈接到前一個(gè)節(jié)點(diǎn)p.prev = tl;tl.next = p;}// 將尾節(jié)點(diǎn)移動(dòng)到當(dāng)前節(jié)點(diǎn)tl = p;// 繼續(xù)處理下一個(gè)節(jié)點(diǎn)，直到鏈表結(jié)束} while ((e = e.next) != null);// 將樹(shù)化后的頭節(jié)點(diǎn)放入桶中，并調(diào)用樹(shù)化方法if ((tab[index] = hd) != null)hd.treeify(tab);}
}

Node<K,V>靜態(tài)內(nèi)部類

HashMap的數(shù)組中保存的就是Node<K,V>

static class Node<K,V> implements Map.Entry<K,V> {final int hash;  // 鍵的哈希值final K key;     // 鍵V value;         // 值Node<K,V> next;  // 指向下一個(gè)節(jié)點(diǎn)    這里可以看出 是單向鏈表結(jié)構(gòu)Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}
}

resize方法

擴(kuò)容方法

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; // 獲取當(dāng)前哈希表int oldCap = (oldTab == null) ? 0 : oldTab.length; // 獲取當(dāng)前哈希表的容量，如果為空則為0int oldThr = threshold; // 獲取當(dāng)前的擴(kuò)容閾值int newCap, newThr = 0; // 聲明新的容量和新的擴(kuò)容閾值// 如果當(dāng)前哈希表的容量大于0if (oldCap > 0) {// 如果當(dāng)前容量已經(jīng)達(dá)到最大值，則將擴(kuò)容閾值設(shè)為最大整數(shù)值，并返回當(dāng)前表if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE; // 將閾值設(shè)為最大整數(shù)值return oldTab; // 返回當(dāng)前表}// 如果當(dāng)前容量未達(dá)到最大值else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // 將容量和擴(kuò)容閾值翻倍}// 如果當(dāng)前容量為0但擴(kuò)容閾值大于0（即初始化時(shí)的情況）else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr; // 將新容量設(shè)為當(dāng)前的閾值else { // 否則使用默認(rèn)初始值newCap = DEFAULT_INITIAL_CAPACITY; // 使用默認(rèn)初始容量newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 根據(jù)默認(rèn)負(fù)載因子和默認(rèn)初始容量計(jì)算新的擴(kuò)容閾值}// 如果新的擴(kuò)容閾值為0，根據(jù)負(fù)載因子和新容量計(jì)算新的擴(kuò)容閾值if (newThr == 0) {float ft = (float)newCap * loadFactor; // 計(jì)算新的擴(kuò)容閾值newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); // 根據(jù)新容量和負(fù)載因子計(jì)算新的閾值，確保不超過(guò)最大容量}threshold = newThr; // 更新擴(kuò)容閾值@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 創(chuàng)建新的哈希表table = newTab; // 更新哈希表引用// 如果舊表不為空，將舊表中的元素重新散列到新表中if (oldTab != null) {for (int j = 0; j < oldCap; ++j) { // 遍歷舊表Node<K,V> e;if ((e = oldTab[j]) != null) { // 如果舊表的當(dāng)前桶不為空oldTab[j] = null; // 釋放舊表的當(dāng)前桶if (e.next == null) // 如果桶中只有一個(gè)節(jié)點(diǎn)newTab[e.hash & (newCap - 1)] = e; // 重新計(jì)算索引并放入新表else if (e instanceof TreeNode) // 如果桶中是紅黑樹(shù)節(jié)點(diǎn)((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 拆分紅黑樹(shù)else { // 否則是鏈表節(jié)點(diǎn)Node<K,V> loHead = null, loTail = null; // 定義低位鏈表的頭尾節(jié)點(diǎn)Node<K,V> hiHead = null, hiTail = null; // 定義高位鏈表的頭尾節(jié)點(diǎn)Node<K,V> next;do {next = e.next; // 暫存下一個(gè)節(jié)點(diǎn)if ((e.hash & oldCap) == 0) { // 根據(jù)舊容量的高位判斷新索引if (loTail == null) // 如果低位鏈表為空loHead = e; // 設(shè)置低位鏈表的頭節(jié)點(diǎn)elseloTail.next = e; // 追加到低位鏈表的尾部loTail = e; // 更新低位鏈表的尾節(jié)點(diǎn)}else { // 如果是高位鏈表if (hiTail == null) // 如果高位鏈表為空hiHead = e; // 設(shè)置高位鏈表的頭節(jié)點(diǎn)elsehiTail.next = e; // 追加到高位鏈表的尾部hiTail = e; // 更新高位鏈表的尾節(jié)點(diǎn)}} while ((e = next) != null); // 遍歷鏈表中的所有節(jié)點(diǎn)if (loTail != null) { // 如果低位鏈表不為空loTail.next = null; // 斷開(kāi)鏈表newTab[j] = loHead; // 將低位鏈表放入新表}if (hiTail != null) { // 如果高位鏈表不為空hiTail.next = null; // 斷開(kāi)鏈表newTab[j + oldCap] = hiHead; // 將高位鏈表放入新表}}}}}return newTab; // 返回新的哈希表
}

split方法

split 方法用于在哈希表擴(kuò)容時(shí)，重新分配紅黑樹(shù)節(jié)點(diǎn)到新的哈希表桶中。
在拆分過(guò)程中，原桶中的紅黑樹(shù)節(jié)點(diǎn)被分配到兩個(gè)鏈表中。
低位鏈表和高位鏈表分別表示原桶和新桶中的元素。
這是為了保證新哈希表的負(fù)載均勻性，并且避免在擴(kuò)容過(guò)程中造成哈希沖突過(guò)多。

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {TreeNode<K,V> b = this; // 當(dāng)前樹(shù)節(jié)點(diǎn)// 初始化低位和高位鏈表的頭尾節(jié)點(diǎn)TreeNode<K,V> loHead = null, loTail = null;TreeNode<K,V> hiHead = null, hiTail = null;int lc = 0, hc = 0; // 低位和高位鏈表的節(jié)點(diǎn)計(jì)數(shù)// 遍歷當(dāng)前樹(shù)節(jié)點(diǎn)的所有節(jié)點(diǎn)for (TreeNode<K,V> e = b, next; e != null; e = next) {next = (TreeNode<K,V>)e.next; // 暫存下一個(gè)節(jié)點(diǎn)e.next = null; // 斷開(kāi)當(dāng)前節(jié)點(diǎn)的 next 引用// 根據(jù) bit 的值決定節(jié)點(diǎn)放入低位鏈表還是高位鏈表if ((e.hash & bit) == 0) {if ((e.prev = loTail) == null) // 如果低位鏈表尾節(jié)點(diǎn)為空，說(shuō)明是第一個(gè)節(jié)點(diǎn)loHead = e; // 設(shè)置低位鏈表的頭節(jié)點(diǎn)elseloTail.next = e; // 否則將當(dāng)前節(jié)點(diǎn)連接到尾節(jié)點(diǎn)loTail = e; // 更新低位鏈表的尾節(jié)點(diǎn)++lc; // 低位鏈表節(jié)點(diǎn)計(jì)數(shù)增加} else {if ((e.prev = hiTail) == null) // 如果高位鏈表尾節(jié)點(diǎn)為空，說(shuō)明是第一個(gè)節(jié)點(diǎn)hiHead = e; // 設(shè)置高位鏈表的頭節(jié)點(diǎn)elsehiTail.next = e; // 否則將當(dāng)前節(jié)點(diǎn)連接到尾節(jié)點(diǎn)hiTail = e; // 更新高位鏈表的尾節(jié)點(diǎn)++hc; // 高位鏈表節(jié)點(diǎn)計(jì)數(shù)增加}}// 如果低位鏈表不為空if (loHead != null) {// 如果低位鏈表的節(jié)點(diǎn)數(shù)小于等于閾值，轉(zhuǎn)換為鏈表結(jié)構(gòu)if (lc <= UNTREEIFY_THRESHOLD)tab[index] = loHead.untreeify(map); // 將低位鏈表轉(zhuǎn)換為普通鏈表并放入新表else {tab[index] = loHead; // 否則直接將低位鏈表放入新表if (hiHead != null) // 如果高位鏈表不為空，說(shuō)明原來(lái)是紅黑樹(shù)結(jié)構(gòu)loHead.treeify(tab); // 將低位鏈表重新組織為紅黑樹(shù)結(jié)構(gòu)}}// 如果高位鏈表不為空if (hiHead != null) {// 如果高位鏈表的節(jié)點(diǎn)數(shù)小于等于閾值 默認(rèn)是6，轉(zhuǎn)換為鏈表結(jié)構(gòu)if (hc <= UNTREEIFY_THRESHOLD)tab[index + bit] = hiHead.untreeify(map); // 將高位鏈表轉(zhuǎn)換為普通鏈表并放入新表else {tab[index + bit] = hiHead; // 否則直接將高位鏈表放入新表if (loHead != null) // 如果低位鏈表不為空，說(shuō)明原來(lái)是紅黑樹(shù)結(jié)構(gòu)hiHead.treeify(tab); // 將高位鏈表重新組織為紅黑樹(shù)結(jié)構(gòu)}}
}// 樹(shù)轉(zhuǎn)化為鏈表
final Node<K,V> untreeify(HashMap<K,V> map) {Node<K,V> hd = null, tl = null; // 初始化新的鏈表頭節(jié)點(diǎn)和尾節(jié)點(diǎn)// 遍歷當(dāng)前的樹(shù)節(jié)點(diǎn)，將其轉(zhuǎn)換為鏈表節(jié)點(diǎn)for (Node<K,V> q = this; q != null; q = q.next) {Node<K,V> p = map.replacementNode(q, null); // 將樹(shù)節(jié)點(diǎn)轉(zhuǎn)換為普通鏈表節(jié)點(diǎn)if (tl == null) // 如果鏈表尾節(jié)點(diǎn)為空，說(shuō)明是第一個(gè)節(jié)點(diǎn)hd = p; // 設(shè)置鏈表頭節(jié)點(diǎn)elsetl.next = p; // 否則將當(dāng)前節(jié)點(diǎn)連接到尾節(jié)點(diǎn)的 next 引用tl = p; // 更新鏈表尾節(jié)點(diǎn)}return hd; // 返回新的鏈表頭節(jié)點(diǎn)
}

afterNodeAccess方法

// 在節(jié)點(diǎn)訪問(wèn)后進(jìn)行的回調(diào)方法
void afterNodeAccess(Node<K,V> p) {// 此方法在訪問(wèn)節(jié)點(diǎn)后被調(diào)用，具體的實(shí)現(xiàn)可以在子類中覆蓋  // 體現(xiàn)了面向?qū)ο笤O(shè)計(jì)原則中的 開(kāi)閉原則，對(duì)修改關(guān)閉對(duì)擴(kuò)展開(kāi)放
}

afterNodeInsertion方法

// 在節(jié)點(diǎn)插入后進(jìn)行的回調(diào)方法
void afterNodeInsertion(boolean evict) {// 此方法在插入節(jié)點(diǎn)后被調(diào)用，具體的實(shí)現(xiàn)可以在子類中覆蓋// 體現(xiàn)了面向?qū)ο笤O(shè)計(jì)原則中的 開(kāi)閉原則，對(duì)修改關(guān)閉對(duì)擴(kuò)展開(kāi)放
}

HashMap的put方法執(zhí)行流程圖示

這里有個(gè)點(diǎn)需要注意下：

// 如果onlyIfAbsent是false 或者 oldValue 是null  就會(huì)新值替換舊值
if (!onlyIfAbsent || oldValue == null)e.value = value;

所以調(diào)用HashMap的 putIfAbsent方法時(shí)要注意，如果key已存在且舊值是null ，那么即使key存在也會(huì)替換舊值。
代碼示例：

public static void main(String[] args) {Map<String, String> hashMap = new HashMap<>(0);hashMap.put("a",null);hashMap.put("b","b");System.out.println("putIfAbsent之前"+hashMap);// 之前的 key  a 對(duì)應(yīng)的 value 是null 所以仍然會(huì)替換hashMap.putIfAbsent("a","123");// 之前的 key  b 對(duì)應(yīng)的 value  是b 所以不會(huì)替換hashMap.putIfAbsent("b","123");System.out.println("putIfAbsent之后"+hashMap);}

執(zhí)行結(jié)果：

putIfAbsent之前{a=null, b=b}
putIfAbsent之后{a=123, b=b}

6、HashMap如何計(jì)算key的索引位置

下面是putVal方法內(nèi)的一段源碼，可以看到 索引 i = (n - 1) & hash, 也就是索引等于 哈希表(數(shù)組)的長(zhǎng)度 & key調(diào)用 hash(key)方法得到的值。

 int n, i;         // n為表的長(zhǎng)度，i為計(jì)算出的索引// 如果表為空或表的長(zhǎng)度為0，則進(jìn)行擴(kuò)容操作
if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 計(jì)算哈希值對(duì)應(yīng)的索引，如果該索引處沒(méi)有節(jié)點(diǎn)，則創(chuàng)建新節(jié)點(diǎn)
if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);

這里我們?cè)賮?lái)探討上面提過(guò)的哈希表容量的問(wèn)題。

為什么HashMap的容量設(shè)計(jì)成總是2的整數(shù)倍？

• ①、更高效的計(jì)算索引： 我們一般計(jì)算索引都是使用 key的哈希值對(duì)容量求余數(shù)，也就是 hash%容量 ，在計(jì)算機(jī)內(nèi)部直接使用%求余性能比較低，就像我們直接使用乘法符號(hào)計(jì)算2乘2 (2*2) 和使用移位運(yùn)算符 2 << 1 得到的結(jié)果是一致的，但是移位運(yùn)算比直接 使用乘法符號(hào)計(jì)算快的多，這是由計(jì)算機(jī)操作系統(tǒng)本身對(duì)算術(shù)運(yùn)算的設(shè)計(jì)規(guī)則決定的。

由于 table.length 總是 2 的冪次方，那么 table.length - 1 就是一個(gè)全為 1 的二進(jìn)制數(shù)，這樣可以高效地與哈希值進(jìn)行按位與運(yùn)算，快速得到索引。

當(dāng)容量n 是2的整數(shù)倍時(shí) 計(jì)算 索引 i = (n - 1) & hash 和 i = hash%n 結(jié)果是一樣的。這也就解釋了 HashMap的容量設(shè)計(jì)成2的整數(shù)倍的第一個(gè)好處。
比如： 容量 n = 16 ， hash = 3 ， 索引 i = (16-1) & 3 = 3;

索引 i = 3%16 也等于3。

• ②、更好的哈希分布： 將容量設(shè)置為 2 的冪次方，有助于避免哈希碰撞，并使得哈希值的低位和高位都能有效參與到索引計(jì)算中。因?yàn)槭褂冒次慌c運(yùn)算時(shí)，所有位都能參與到索引的計(jì)算中，如果容量不是 2 的冪次方，那么某些位可能永遠(yuǎn)不會(huì)參與到計(jì)算中，這會(huì)導(dǎo)致哈希分布不均勻，增加哈希沖突的概率。

• ③、高效的擴(kuò)容操作: 這點(diǎn)設(shè)計(jì)是真的厲害，在擴(kuò)容時(shí)，新的容量也是 2 的冪次方，這樣可以保持上述優(yōu)點(diǎn)。而且擴(kuò)容后，舊表中的元素可以很容易地重新分配到新表中，只需根據(jù)元素的哈希值和新表的容量重新計(jì)算索引即可。這使得擴(kuò)容操作更加高效。

擴(kuò)容時(shí)只需要檢查元素的哈希值的新增位是 0 還是 1 來(lái)決定它是留在原索引位置還是移動(dòng)到新索引位置：

if ((e.hash & oldCap) == 0) {// 留在原索引位置
} else {// 移動(dòng)到新索引位置// 新索引的位置 =  舊索引位置 + 舊容量
}

更精妙的是，新索引的位置直接就等于 舊位置 + 舊容量。
這里舉個(gè)例子計(jì)算一下：

1.如果 (e.hash & oldCap) == 0，元素留在原索引位置。
2.如果 (e.hash & oldCap) != 0，元素移動(dòng)到新索引位置：舊索引位置 + 舊容量。假設(shè)擴(kuò)容前哈希表長(zhǎng)度為8 ,  擴(kuò)容后哈希表長(zhǎng)度為16情況2舉例說(shuō)明：假設(shè) a的hash值為10擴(kuò)容前a的索引位置： i = 10&(8-1) = 10%8 = 2擴(kuò)容后a的索引位置： 
先計(jì)算 10&8 = 2 != 0 , 新索引位置 i = 舊索引位置(2) + 舊容量(8) = 10如果我們直接計(jì)算新索引位置 i = 10&(16-1) = 10%16 = 10 和上面計(jì)算結(jié)果一致情況2舉例說(shuō)明：
假設(shè) b的hash值為2擴(kuò)容前b的索引位置： i = 2&(8-1) = 2%8 = 2擴(kuò)容后b的索引位置： 
先計(jì)算 2&8 = 0 == 0 , 新索引位置 i = 舊索引位置(2)如果我們直接計(jì)算新索引位置 i = 2&(16-1) = 2%16 = 2 和上面計(jì)算結(jié)果一致

還有一些其他好處：
????容量總是 2 的冪次方使得很多實(shí)現(xiàn)細(xì)節(jié)變得簡(jiǎn)單而高效。比如計(jì)算容量、計(jì)算閾值、擴(kuò)容等操作都可以利用位運(yùn)算來(lái)實(shí)現(xiàn)，減少了代碼的復(fù)雜度和運(yùn)行時(shí)的開(kāi)銷。

????由于哈希表的負(fù)載因子通常設(shè)定為 0.75，當(dāng)容量為 2 的冪次方時(shí)，可以保證在觸發(fā)擴(kuò)容時(shí)，哈希表的裝載程度接近于最佳狀態(tài)，避免了過(guò)度擴(kuò)容或者裝載過(guò)高導(dǎo)致的性能問(wèn)題。

7、HashMap的get方法

// 獲取指定鍵的值
public V get(Object key) {// 調(diào)用 getNode 方法查找鍵對(duì)應(yīng)的節(jié)點(diǎn)，如果找到則返回節(jié)點(diǎn)的值，否則返回 nullNode<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}// 根據(jù) hash 值和鍵查找節(jié)點(diǎn)
final Node<K,V> getNode(int hash, Object key) {// 定義一些局部變量Node<K,V>[] tab;       // 哈希表Node<K,V> first, e;    // 鏈表中的節(jié)點(diǎn)int n;                 // 哈希表的長(zhǎng)度K k;                   // 節(jié)點(diǎn)中的鍵// 如果哈希表不為空并且長(zhǎng)度大于 0，并且對(duì)應(yīng)哈希桶中第一個(gè)節(jié)點(diǎn)不為空if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 檢查第一個(gè)節(jié)點(diǎn)if (first.hash == hash && // 比較鍵是否相等（引用相等或者內(nèi)容相等）((k = first.key) == key || (key != null && key.equals(k))))// 如果第一個(gè)節(jié)點(diǎn)就是我們要找的，直接返回return first;// 如果第一個(gè)節(jié)點(diǎn)不是我們要找的，并且有后續(xù)節(jié)點(diǎn)if ((e = first.next) != null) {// 如果是樹(shù)節(jié)點(diǎn)（紅黑樹(shù)）if (first instanceof TreeNode)// 在樹(shù)中查找節(jié)點(diǎn)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 否則在鏈表中查找do {// 比較每一個(gè)節(jié)點(diǎn)的哈希值和鍵if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 找到匹配的節(jié)點(diǎn)return e;} while ((e = e.next) != null);  // 遍歷鏈表}}// 如果沒(méi)有找到，返回 nullreturn null;
}

紅黑樹(shù)的查找 getTreeNode 方法就不看了，感興趣的可以自己到源碼里看。
后續(xù)寫(xiě)數(shù)據(jù)結(jié)構(gòu)和算法之類的文章會(huì)再看這類實(shí)現(xiàn)特定數(shù)據(jù)結(jié)構(gòu)的源碼。

8、HashMap的remove方法

/*** 根據(jù)指定的鍵從HashMap中移除鍵值對(duì)。* 如果鍵存在，則移除該鍵值對(duì)并返回其對(duì)應(yīng)的值；否則返回null。** @param key 要移除的鍵* @return 被移除的值，如果鍵不存在則返回null*/
public V remove(Object key) {// 調(diào)用removeNode方法執(zhí)行移除操作，并返回被移除節(jié)點(diǎn)的值Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
}/*** 從HashMap中移除指定哈希值和鍵的節(jié)點(diǎn)，并可選擇性匹配值。* 此方法是HashMap移除元素的核心實(shí)現(xiàn)。** @param hash 鍵的哈希值* @param key 要移除的鍵* @param value 要匹配的值，如果為null則不匹配值* @param matchValue 是否進(jìn)行值匹配* @param movable 是否允許節(jié)點(diǎn)移動(dòng)* @return 如果成功移除則返回被移除的節(jié)點(diǎn)，否則返回null*/
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;// 如果HashMap的表不為空，并且長(zhǎng)度大于0，并且在計(jì)算的索引位置有節(jié)點(diǎn)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;// 如果索引位置的節(jié)點(diǎn)就是我們要找的節(jié)點(diǎn)if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) {node = p;} // 否則檢查鏈表的下一個(gè)節(jié)點(diǎn)（包括紅黑樹(shù)的情況）else if ((e = p.next) != null) {if (p instanceof TreeNode) {// 在紅黑樹(shù)結(jié)構(gòu)中查找節(jié)點(diǎn)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);} else {// 在鏈表中查找節(jié)點(diǎn)do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}// 如果找到了節(jié)點(diǎn)，并且不需要匹配值或值匹配成功if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode) {// 如果是紅黑樹(shù)節(jié)點(diǎn)，移除樹(shù)節(jié)點(diǎn)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);} else if (node == p) {// 如果節(jié)點(diǎn)是鏈表的頭節(jié)點(diǎn)，直接更新表的索引位置tab[index] = node.next;} else {// 否則，更新前驅(qū)節(jié)點(diǎn)的next引用，跳過(guò)當(dāng)前節(jié)點(diǎn)p.next = node.next;}// 更新HashMap的結(jié)構(gòu)修改計(jì)數(shù)和大小++modCount;--size;// 調(diào)用節(jié)點(diǎn)移除后的處理方法afterNodeRemoval(node);// 返回被移除的節(jié)點(diǎn)return node;}}// 如果沒(méi)有找到匹配的節(jié)點(diǎn)，返回nullreturn null;
}

9、HashMap的迭代器

????由于HashMap是數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)，所以HashMap的迭代器只能循環(huán)數(shù)組，從0索引位置開(kāi)始循環(huán)找到第一個(gè)非空的Node節(jié)點(diǎn)，如果該節(jié)點(diǎn)的next不會(huì)空，就繼續(xù)使用Node節(jié)點(diǎn)的next去一個(gè)一個(gè)遍歷元素，如果next為空了，再往下循環(huán)數(shù)組直到找到下一個(gè)非空的Node節(jié)點(diǎn)繼續(xù)使用next遍歷。
所以HashMap的迭代器會(huì)循環(huán)遍歷所有的數(shù)組Node節(jié)點(diǎn)，以及Node節(jié)點(diǎn)鏈接的鏈表或紅黑樹(shù)的全部元素。

abstract class HashIterator {// 下一個(gè)要返回的節(jié)點(diǎn)Node<K,V> next;        // 當(dāng)前的節(jié)點(diǎn)Node<K,V> current;     // 用于快速失敗的期望修改計(jì)數(shù)int expectedModCount;  // 當(dāng)前槽的索引int index;             // 構(gòu)造方法HashIterator() {// 初始化期望的修改計(jì)數(shù)，等于當(dāng)前的修改計(jì)數(shù)expectedModCount = modCount;// 獲取哈希表Node<K,V>[] t = table;// 初始化當(dāng)前節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)為nullcurrent = next = null;// 初始化索引為0index = 0;// 如果哈希表不為空并且大小大于0，推進(jìn)到第一個(gè)非空的槽if (t != null && size > 0) { // 循環(huán)直到找到第一個(gè)非空的槽do {} while (index < t.length && (next = t[index++]) == null);}}// 判斷是否有下一個(gè)元素public final boolean hasNext() {return next != null;}// 獲取下一個(gè)節(jié)點(diǎn)final Node<K,V> nextNode() {// 臨時(shí)變量t用于存儲(chǔ)哈希表Node<K,V>[] t;// e用于存儲(chǔ)當(dāng)前的下一個(gè)節(jié)點(diǎn)Node<K,V> e = next;// 如果哈希表的修改計(jì)數(shù)與期望的修改計(jì)數(shù)不同，拋出并發(fā)修改異常if (modCount != expectedModCount)throw new ConcurrentModificationException();// 如果下一個(gè)節(jié)點(diǎn)為空，拋出沒(méi)有元素異常if (e == null)throw new NoSuchElementException();// 將當(dāng)前節(jié)點(diǎn)設(shè)為下一個(gè)節(jié)點(diǎn)，如果下一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空，繼續(xù)尋找下一個(gè)非空的槽if ((next = (current = e).next) == null && (t = table) != null) {// 循環(huán)直到找到下一個(gè)非空的槽do {} while (index < t.length && (next = t[index++]) == null);}// 返回當(dāng)前的節(jié)點(diǎn)return e;}}

10、HashMap的一些常見(jiàn)問(wèn)題

①、JDK8為什么引入紅黑樹(shù)？

HashMap采用哈希表的結(jié)構(gòu)存儲(chǔ)鍵值對(duì)，鍵通過(guò)哈希函數(shù)被映射到數(shù)組的某個(gè)索引位置。理想情況下，哈希函數(shù)將鍵均勻地分布在數(shù)組的各個(gè)位置上，但在實(shí)際應(yīng)用中，不同的鍵可能會(huì)被映射到同一個(gè)索引位置，導(dǎo)致哈希沖突。

在JDK8之前，HashMap在處理哈希沖突時(shí)使用的是鏈表。即在同一個(gè)索引位置上存儲(chǔ)多個(gè)鍵值對(duì)時(shí)，這些鍵值對(duì)會(huì)被存儲(chǔ)在一個(gè)鏈表中。這意味著，當(dāng)多個(gè)鍵被映射到同一個(gè)位置時(shí)，查詢、插入或刪除操作的時(shí)間復(fù)雜度會(huì)隨著鏈表長(zhǎng)度的增加而增加，最壞情況下達(dá)到O(n)，其中n是鏈表中的元素?cái)?shù)量。

為了優(yōu)化在哈希沖突嚴(yán)重情況下的性能，JDK8引入了紅黑樹(shù)。當(dāng)鏈表長(zhǎng)度大于等于8時(shí)，且哈希表容量大于等于64時(shí)。鏈表會(huì)轉(zhuǎn)換為紅黑樹(shù)。

紅黑樹(shù)是一種自平衡二叉搜索樹(shù)，具有以下特點(diǎn)：
平衡性：紅黑樹(shù)通過(guò)一系列的旋轉(zhuǎn)和顏色變化來(lái)保持樹(shù)的平衡，使得樹(shù)的高度始終保持在O(log n)。
查詢效率：由于紅黑樹(shù)的高度是O(log n)，因此在紅黑樹(shù)中的查詢、插入和刪除操作的時(shí)間復(fù)雜度是O(log n)，比鏈表的O(n)更高效。

②、紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)有什么特點(diǎn) ？

樹(shù)結(jié)構(gòu)有以下特點(diǎn)：
查找效率高：
通過(guò)樹(shù)形結(jié)構(gòu)（如二叉查找樹(shù)、紅黑樹(shù)、B樹(shù)等），可以在O(log n)時(shí)間內(nèi)完成查找操作，比線性結(jié)構(gòu)（如數(shù)組、鏈表）高效。

保持?jǐn)?shù)據(jù)有序：
樹(shù)結(jié)構(gòu)能夠在插入和刪除操作后保持?jǐn)?shù)據(jù)的有序性，適用于需要頻繁更新和檢索的數(shù)據(jù)集。

表示層次結(jié)構(gòu)：
樹(shù)結(jié)構(gòu)用于表示具有層次關(guān)系的數(shù)據(jù)，如XML/HTML文檔、組織結(jié)構(gòu)圖、文件系統(tǒng)等。

高效插入和刪除：
樹(shù)結(jié)構(gòu)支持高效的插入和刪除操作，特別是自平衡樹(shù)，通過(guò)旋轉(zhuǎn)和重新平衡操作，能夠在O(log n)時(shí)間內(nèi)完成插入和刪除。

紅黑樹(shù)的特點(diǎn)

• 節(jié)點(diǎn)顏色：每個(gè)節(jié)點(diǎn)都被標(biāo)記為紅色或黑色。
• 根節(jié)點(diǎn)：根節(jié)點(diǎn)始終是黑色。
• 葉子節(jié)點(diǎn)：所有葉子節(jié)點(diǎn)（即空節(jié)點(diǎn)）都是黑色。
• 紅色規(guī)則：紅色節(jié)點(diǎn)不能有兩個(gè)連續(xù)的紅色父節(jié)點(diǎn)和子節(jié)點(diǎn)。
• 黑色規(guī)則：從任一節(jié)點(diǎn)到其每個(gè)葉節(jié)點(diǎn)的所有路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)。
  這些規(guī)則確保紅黑樹(shù)在最壞情況下也能保持O(log n)的時(shí)間復(fù)雜度。通過(guò)插入和刪除操作后的旋轉(zhuǎn)和重新著色，紅黑樹(shù)能夠保持平衡，避免退化成線性結(jié)構(gòu)。

二叉查找樹(shù)（BST）與紅黑樹(shù)（Red-Black Tree）的區(qū)別:

特點(diǎn)	普通二叉查找樹(shù)（BST）	紅黑樹(shù)（Red-Black Tree）
基本定義	每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，左子節(jié)點(diǎn)小于父節(jié)點(diǎn)，右子節(jié)點(diǎn)大于父節(jié)點(diǎn)	一種自平衡的二叉查找樹(shù)，附加了紅黑節(jié)點(diǎn)的顏色屬性
平衡性	不保證平衡，可能會(huì)退化成線性結(jié)構(gòu)	保持平衡，通過(guò)顏色和旋轉(zhuǎn)操作維持
最壞情況時(shí)間復(fù)雜度	O(n)，退化成鏈表時(shí)	O(log n)
平均情況時(shí)間復(fù)雜度	O(log n)	O(log n)
插入復(fù)雜度	O(log n)（平均情況），O(n)（最壞情況）	O(log n)
刪除復(fù)雜度	O(log n)（平均情況），O(n)（最壞情況）	O(log n)
查詢復(fù)雜度	O(log n)（平均情況），O(n)（最壞情況）	O(log n)
結(jié)構(gòu)維護(hù)	插入和刪除不涉及復(fù)雜的維護(hù)操作	插入和刪除需要進(jìn)行旋轉(zhuǎn)和重新著色來(lái)維持平衡
使用場(chǎng)景	簡(jiǎn)單的插入、查找操作，數(shù)據(jù)相對(duì)有序時(shí)性能較好	需要頻繁插入、刪除和查找操作時(shí)性能穩(wěn)定
退化情況	當(dāng)插入數(shù)據(jù)按順序（升序或降序）時(shí)會(huì)退化成線性結(jié)構(gòu)	通過(guò)自平衡機(jī)制，避免退化

普通的二叉查找樹(shù)（BST）會(huì)在以下情況下退化成線性結(jié)構(gòu)：
當(dāng)節(jié)點(diǎn)按順序（升序或降序）插入時(shí)，每個(gè)節(jié)點(diǎn)都只有一個(gè)子節(jié)點(diǎn)，導(dǎo)致樹(shù)變成一條“鏈”。
例如，插入序列為1, 2, 3, 4, 5時(shí)，BST會(huì)退化成：

③、負(fù)載因子為什么是0.75？

在空間占用與查詢時(shí)間之間取得較好的權(quán)衡。
大于這個(gè)值，空間節(jié)省了，但鏈表可能就會(huì)比較長(zhǎng)影響性能。
小于這個(gè)值，沖突減少了，但擴(kuò)容就會(huì)更頻繁，空間占用多。
綜合考慮實(shí)際使用場(chǎng)景和對(duì)性能的要求，0.75加載因子是經(jīng)驗(yàn)上比較成熟和常用的選擇。
這個(gè)值在大多數(shù)情況下能夠保證HashMap在性能和空間利用率之間取得合理的平衡。

數(shù)學(xué)概率方面：
hash 值如果足夠隨機(jī)，則在 hash 表內(nèi)按泊松分布，在負(fù)載因子 0.75 的情況下，長(zhǎng)度超過(guò)8的鏈表出現(xiàn)概率是0.00000006，選擇8就是為了讓樹(shù)化幾率足夠小。

添加第一個(gè)元素時(shí)，默認(rèn)情況下HashMap容量是16，負(fù)載因子是0.75 。
16*0.75=12 ，也就是第一次擴(kuò)容的閾值為12。
當(dāng)添加第13個(gè)元素的時(shí)候，13>12，HashMap容量擴(kuò)容為32；

public static void main(String[] args) throws Exception {HashMap<String, String> map = new HashMap<>();// 獲取 HashMap 內(nèi)部的 table 數(shù)組長(zhǎng)度Field tableField = HashMap.class.getDeclaredField("table");tableField.setAccessible(true); // 設(shè)置可訪問(wèn)私有字段map.put("1","123");Object[] table = (Object[]) tableField.get(map);System.out.println(table.length);  // 16map.put("2","123");map.put("3","123");map.put("4","123");map.put("5","123");map.put("6","123");map.put("7","123");map.put("8","123");map.put("9","123");map.put("10","123");map.put("11","123");map.put("12","123");Object[] table1 = (Object[]) tableField.get(map);System.out.println(table1.length);  // 16map.put("13","123");Object[] table2 = (Object[]) tableField.get(map);System.out.println(table2.length);  // 32}

④、為什么數(shù)組長(zhǎng)度≥64且鏈表長(zhǎng)度 ≥8才樹(shù)化？

空間和時(shí)間的折中考慮：
紅黑樹(shù)比鏈表占用更多的內(nèi)存空間，因?yàn)闃?shù)節(jié)點(diǎn)通常比鏈表節(jié)點(diǎn)大。因此，在選擇將鏈表轉(zhuǎn)換成樹(shù)時(shí)，需要權(quán)衡空間和時(shí)間效率。
只有在鏈表長(zhǎng)度較大時(shí)，大于等于閾值8，才值得為了提升時(shí)間效率而犧牲一定的空間。

并不是所有長(zhǎng)度大于等于8的鏈表都會(huì)立即樹(shù)化，只有當(dāng)鏈表長(zhǎng)度大于等于8且數(shù)組(哈希表)長(zhǎng)度大于等于64時(shí)才會(huì)樹(shù)化。如果鏈表長(zhǎng)度大于等于8但是數(shù)組長(zhǎng)度小于64，此時(shí)會(huì)進(jìn)行擴(kuò)容重新散列，而不是樹(shù)化。 因?yàn)閿?shù)組長(zhǎng)度小于64說(shuō)明此時(shí)的數(shù)組容量還很小，此時(shí)應(yīng)該考慮擴(kuò)容把元素重新散列到更大的哈希表中以減少哈希沖突來(lái)提升性能。

⑤、多線程下HashMap寫(xiě)操作可能出現(xiàn)哪些問(wèn)題？

JDK8之前可能會(huì)出現(xiàn)：
擴(kuò)容死鏈(頭插法導(dǎo)致)，丟失數(shù)據(jù)。

JDK8的HashMap的鏈表采用了尾插法不會(huì)出現(xiàn)擴(kuò)容死鏈問(wèn)題，仍然可能會(huì)出現(xiàn)丟失數(shù)據(jù)問(wèn)題。

JDK1.8之前并發(fā)擴(kuò)容死鏈問(wèn)題，動(dòng)畫(huà)演示：

這個(gè)動(dòng)畫(huà)我畫(huà)了快3小時(shí) ┭┮﹏┭┮ ，多看幾遍 我相信就能很容易理解擴(kuò)容死鏈形成的過(guò)程了。

最終形成了 a.next=b, b.next=a 的這種死鏈：

此時(shí)當(dāng)我們?cè)僬{(diào)用查找方法，比如 key c 的索引也是1 ，HashMap就會(huì)遍歷這個(gè)死鏈，發(fā)現(xiàn)a不是b不是 再往下遍歷又到了a、b，a，b 無(wú)線循環(huán)下去，就會(huì)導(dǎo)致 本次 get?的調(diào)用陷入死循環(huán)。

丟失數(shù)據(jù)問(wèn)題，代碼演示：

public static void main(String[] args) throws Exception {HashMap<String, String> map = new HashMap<>();// 默認(rèn)容量16Thread t1 = new Thread(() -> {map.put("a","a"); // hash值 97  索引位置 i = (16-1) & 97 = 1map.put("b","b"); // hash值 98  索引位置 i = (16-1) & 98 = 2},"t1");Thread t2 = new Thread(() -> {map.put("1","1");  // hash值  49 索引位置 i = (16-1) & 49 = 1map.put("2","2");   // hash值 50  索引位置 i = (16-1) & 50 = 2},"t2");t2.setName("t2");t1.start();t2.start();t1.join();t2.join();System.out.println(map);}

可以看到 key “a” 和 “1” 會(huì)出現(xiàn)哈希沖突，key “b” 和 “2” 會(huì)出現(xiàn)哈希沖突。
正常情況下應(yīng)該得到的結(jié)果是：

{1=1, a=a, 2=2, b=b}

現(xiàn)在我們演示下出問(wèn)題的情況：
首先打斷點(diǎn)，斷點(diǎn)的條件設(shè)置為 線程名稱是 t1或者t2才走斷點(diǎn)。(因?yàn)镴VM啟動(dòng)的時(shí)候也會(huì)調(diào)用putVal方法，不加條件可能會(huì)斷點(diǎn)到很多其他線程的調(diào)用)

斷點(diǎn)條件代碼：Thread.currentThread().getName().equals("t1")||Thread.currentThread().getName().equals("t2")

①、debug運(yùn)行代碼，先走t1線程的斷點(diǎn) map.put("a","a"); // hash值 97 索引位置 i = (16-1) & 97 = 1
注意讓t1只走到判斷 索引位置為空的if條件里先不給數(shù)組賦值

②、此時(shí)選t2線程，此時(shí)由于 key "1"的索引位置也是1 ，而t1線程 還沒(méi)來(lái)得及給數(shù)組的這個(gè)1位置賦值
所以t2線程也進(jìn)入了if代碼塊內(nèi) 。
此時(shí)讓t2線程繼續(xù)往下走一步賦值 map.put("1","1"); // hash值 49 索引位置 i = (16-1) & 49 = 1 , 數(shù)組的 tab[1] = (“1”,“1”)了

③、再返回t1線程，此時(shí)的tab[1] 已經(jīng)有值了，是上面 t2線程賦的值。

這個(gè)時(shí)候讓t1線程繼續(xù)賦值就把 t2 線程在索引位置1 處賦的值覆蓋掉了。

④、我們?cè)僦貜?fù)上面的操作，再走t1進(jìn)if語(yǔ)句內(nèi)不賦值，然后等t2賦值后，t1再賦值。
最終就能得到丟失數(shù)據(jù)的結(jié)果。

{a=a, b=b}

可以看到 和正常情況的 {1=1, a=a, 2=2, b=b} 相比 丟失了t2線程put的數(shù)據(jù)。

⑥、JDK8之前的put方法和之后的put方法有什么區(qū)別 ？

• 1、鏈表插入行為不同：鏈表插入節(jié)點(diǎn)時(shí)，JDK8之前是頭插法，JDK8是尾插法。
• 2、擴(kuò)容行為不同：JDK8之前是大于等于閾值且沒(méi)有空位時(shí)才擴(kuò)容，而JDK8是大于閾值就擴(kuò)容.
• 3、鏈表和紅黑樹(shù)轉(zhuǎn)化：JDK8之前只有鏈表，JDK8引入紅黑樹(shù)。

⑦、HashMap的紅黑樹(shù)什么情況下會(huì)退化成鏈表？

退化情況1: 在擴(kuò)容時(shí)如果拆分樹(shù)時(shí)，樹(shù)元素個(gè)數(shù)<=6則會(huì)退化為鏈表。

在HashMap進(jìn)行擴(kuò)容時(shí)，會(huì)對(duì)現(xiàn)有的桶進(jìn)行重新分配元素。如果一個(gè)桶中原本是紅黑樹(shù)節(jié)點(diǎn)（TreeNode），而在進(jìn)行擴(kuò)容時(shí)，樹(shù)中節(jié)點(diǎn)的數(shù)量少于等于6個(gè)，HashMap會(huì)選擇將這些節(jié)點(diǎn)轉(zhuǎn)換為鏈表形式。這是因?yàn)閷?duì)于數(shù)量較少的節(jié)點(diǎn)來(lái)說(shuō)，使用鏈表而不是紅黑樹(shù)可能會(huì)更節(jié)省空間和操作成本。
對(duì)應(yīng)代碼：

if (loHead != null) {// 如果低位鏈表頭結(jié)點(diǎn)不為空if (lc <= UNTREEIFY_THRESHOLD)// 如果低位鏈表的節(jié)點(diǎn)數(shù)小于等于UNTREEIFY_THRESHOLD (默認(rèn)是6)，將其退化成鏈表tab[index] = loHead.untreeify(map);else {// 否則，保持為紅黑樹(shù)tab[index] = loHead;if (hiHead != null) // 如果高位鏈表頭結(jié)點(diǎn)也不為空，保持紅黑樹(shù)結(jié)構(gòu)loHead.treeify(tab);}
}if (hiHead != null) {// 如果高位鏈表頭結(jié)點(diǎn)不為空if (hc <= UNTREEIFY_THRESHOLD)// 如果高位鏈表的節(jié)點(diǎn)數(shù)小于等于UNTREEIFY_THRESHOLD (默認(rèn)是6)，將其退化成鏈表tab[index + bit] = hiHead.untreeify(map);else {// 否則，保持為紅黑樹(shù)tab[index + bit] = hiHead;if (loHead != null) // 如果低位鏈表頭結(jié)點(diǎn)也不為空，保持紅黑樹(shù)結(jié)構(gòu)hiHead.treeify(tab);}
}

退化情況2: remove 樹(shù)節(jié)點(diǎn)時(shí)，若 root、root.left、root.right、root.left.left有一個(gè)為 null，也會(huì)退化為鏈表。

在HashMap中刪除樹(shù)節(jié)點(diǎn)時(shí)，如果根節(jié)點(diǎn)或其子節(jié)點(diǎn)的左右子節(jié)點(diǎn)為null，則樹(shù)節(jié)點(diǎn)會(huì)退化為鏈表形式。
這是因?yàn)樵诩t黑樹(shù)中，根節(jié)點(diǎn)的左右子節(jié)點(diǎn)為null意味著紅黑樹(shù)的結(jié)構(gòu)不再成立，因此HashMap選擇將這部分節(jié)點(diǎn)轉(zhuǎn)換為鏈表以保持結(jié)構(gòu)的一致性和簡(jiǎn)單性。

對(duì)應(yīng)代碼：

final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {int n;if (tab == null || (n = tab.length) == 0)return; // 如果哈希表為空或長(zhǎng)度為零，直接返回int index = (n - 1) & hash; // 計(jì)算節(jié)點(diǎn)所在的桶索引TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;if (pred == null)tab[index] = first = succ; // 如果沒(méi)有前驅(qū)節(jié)點(diǎn)，將桶頭設(shè)置為后繼節(jié)點(diǎn)elsepred.next = succ; // 否則將前驅(qū)節(jié)點(diǎn)的 next 指向后繼節(jié)點(diǎn)if (succ != null)succ.prev = pred; // 如果有后繼節(jié)點(diǎn)，將其 prev 指向前驅(qū)節(jié)點(diǎn)if (first == null)return; // 如果桶頭為空，直接返回if (root.parent != null)root = root.root(); // 獲取紅黑樹(shù)的根節(jié)點(diǎn)if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) {tab[index] = first.untreeify(map); // 如果紅黑樹(shù)的結(jié)構(gòu)不再平衡，將其退化為鏈表return;}TreeNode<K,V> p = this, pl = left, pr = right, replacement;if (pl != null && pr != null) {TreeNode<K,V> s = pr, sl;while ((sl = s.left) != null)s = sl; // 找到后繼節(jié)點(diǎn)boolean c = s.red; s.red = p.red; p.red = c; // 交換顏色TreeNode<K,V> sr = s.right;TreeNode<K,V> pp = p.parent;if (s == pr) {p.parent = s;s.right = p; // 如果后繼節(jié)點(diǎn)是右子節(jié)點(diǎn)，調(diào)整關(guān)系} else {TreeNode<K,V> sp = s.parent;if ((p.parent = sp) != null) {if (s == sp.left)sp.left = p;elsesp.right = p;}if ((s.right = pr) != null)pr.parent = s; // 調(diào)整后繼節(jié)點(diǎn)與右子節(jié)點(diǎn)的關(guān)系}p.left = null;if ((p.right = sr) != null)sr.parent = p; // 調(diào)整右子節(jié)點(diǎn)與 p 的關(guān)系if ((s.left = pl) != null)pl.parent = s; // 調(diào)整左子節(jié)點(diǎn)與后繼節(jié)點(diǎn)的關(guān)系if ((s.parent = pp) == null)root = s;else if (p == pp.left)pp.left = s;elsepp.right = s; // 調(diào)整后繼節(jié)點(diǎn)與 p 父節(jié)點(diǎn)的關(guān)系if (sr != null)replacement = sr;elsereplacement = p; // 確定替代節(jié)點(diǎn)} else if (pl != null)replacement = pl; // 如果只有左子節(jié)點(diǎn)，替代節(jié)點(diǎn)為左子節(jié)點(diǎn)else if (pr != null)replacement = pr; // 如果只有右子節(jié)點(diǎn)，替代節(jié)點(diǎn)為右子節(jié)點(diǎn)elsereplacement = p; // 如果沒(méi)有子節(jié)點(diǎn)，替代節(jié)點(diǎn)為 pif (replacement != p) {TreeNode<K,V> pp = replacement.parent = p.parent;if (pp == null)root = replacement;else if (p == pp.left)pp.left = replacement;elsepp.right = replacement; // 調(diào)整替代節(jié)點(diǎn)與 p 父節(jié)點(diǎn)的關(guān)系p.left = p.right = p.parent = null; // 清空 p 的引用}TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement); // 平衡刪除操作if (replacement == p) { // 斷開(kāi) p 與其父節(jié)點(diǎn)的關(guān)系TreeNode<K,V> pp = p.parent;p.parent = null;if (pp != null) {if (p == pp.left)pp.left = null;else if (p == pp.right)pp.right = null;}}if (movable)moveRootToFront(tab, r); // 如果可移動(dòng)，將根節(jié)點(diǎn)移動(dòng)到桶頭
}