【集合】JDK1.8 HashMap 底層數據結構深度解析

一、核心數據結構：為什么是 "數組 + 鏈表 + 紅黑樹"？?

HashMap 的底層設計本質是用空間換時間，通過哈希表的快速定位特性，結合鏈表和紅黑樹處理沖突，平衡查詢與插入效率。?

1.1 基礎容器：哈希桶數組（Node [] table）?

數組角色：作為哈希表的 "骨架"，每個下標對應一個哈希桶（bucket），通過哈希值直接定位元素所在桶的位置，實現 O (1) 級別的快速訪問。?

Node 節點結構：數組中存儲的是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;    // 下一個節點引用（用于鏈表）
}

這里的next字段是實現鏈表的關鍵，當多個元素哈希沖突時，會通過該字段串成鏈表。?

1.2 解決沖突：鏈表的作用?

當兩個不同的 key 計算出相同的哈希值（即哈希沖突）時，HashMap 會將新元素以鏈表節點的形式 "掛" 在同一哈希桶的尾部。這種處理方式稱為鏈地址法，是哈希表解決沖突的經典方案。?

1.3 性能優化：紅黑樹的引入?

JDK1.8 之前，HashMap 僅用數組 + 鏈表的結構，當哈希沖突嚴重時（如大量元素集中在同一桶中），鏈表會退化為 "長鏈"，此時查詢時間復雜度會從 O (1) 退化到 O (n)。?

為解決這個問題，JDK1.8 引入了紅黑樹（TreeNode）：當鏈表長度超過閾值（默認 8）且數組長度≥64 時，鏈表會自動轉為紅黑樹，將查詢時間復雜度優化到 O (log n)。?

二、關鍵機制解析：哈希、擴容與樹化?

2.1 哈希函數：如何計算元素在數組中的位置？?

HashMap 的高效查詢依賴于哈希值的精準計算，核心步驟分為兩步：?

① 計算 key 的哈希值（擾動函數）

static final int hash(Object key) {int h;// 1. 取key的hashCode值；2. 高16位與低16位異或（擾動處理）return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

為什么要做擾動處理？?

若直接使用key.hashCode()的低幾位計算索引，當哈希值的高位變化大但低位變化小時，容易導致哈希沖突（例如hashCode=0x0001FFFF和0x0002FFFF，低 16 位相同）。通過高 16 位與低 16 位異或，能讓高位信息參與哈希計算，減少沖突概率。?

② 計算數組索引

// n為數組長度（必須是2的冪）
int index = (n - 1) & hash;

這里用(n-1) & hash代替取模運算（hash % n），因為當 n 是 2 的冪時，兩者結果等價，但位運算效率更高。?

2.2 擴容機制：數組不夠用了怎么辦？?

當 HashMap 中的元素數量超過閾值（threshold = 容量 × 負載因子）時，會觸發擴容（resize），將數組長度翻倍（新容量 = 舊容量 ×2）。?

擴容的核心步驟：?

????????（1）計算新容量與新閾值：默認初始容量為 16，負載因子 0.75，初始閾值 = 16×0.75=12。擴容后新容量 = 32，新閾值 = 32×0.75=24。?

????????（2）創建新數組：長度為新容量。?

????????（3）遷移舊元素：將舊數組中的元素重新計算索引，遷移到新數組中（JDK1.8 優化點：通過hash & oldCap判斷元素是否需要移動，避免重復計算哈希）。?

擴容時的元素遷移邏輯：?

若元素所在桶是單節點：直接計算新索引并放入新數組。?

若元素所在桶是鏈表：?

通過hash & oldCap將鏈表拆分為兩個子鏈表：?

結果為 0：元素留在原索引位置（新數組的j處）。?

結果為非 0：元素遷移到新索引位置（新數組的j + oldCap處）。?

若元素所在桶是紅黑樹：拆分樹節點為兩個子樹，若子樹長度≤6 則退化為鏈表。?

2.3 樹化與反樹化：鏈表和紅黑樹如何轉換？?

樹化（鏈表轉紅黑樹）的觸發條件：?

鏈表長度≥8（TREEIFY_THRESHOLD = 8）。?

數組長度≥64（MIN_TREEIFY_CAPACITY = 64）。?

若數組長度不足 64，會先觸發擴容而非樹化，避免在小容量數組上過度樹化浪費資源。?

反樹化（紅黑樹轉鏈表）的觸發條件：?

當紅黑樹的節點數量≤6（UNTREEIFY_THRESHOLD = 6）時，會自動退化為鏈表，減少樹結構帶來的維護成本。?

為什么閾值是 8 和 6？?

官方注釋提到，根據泊松分布，鏈表長度達到 8 的概率僅為 0.00000006（幾乎是小概率事件），此時樹化收益大于成本。?

用 6 作為反樹化閾值，是為了避免鏈表在 8 附近頻繁樹化 / 反樹化（ hysteresis 機制）。?

三、源碼直擊：put () 與 resize () 核心邏輯?

3.1 put () 方法：元素插入全流程

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 步驟1：數組為空則初始化（第一次put時觸發）if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 步驟2：計算索引，若桶為空則直接插入新節點if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// 步驟3：若桶中首個節點的key與插入key相同，直接覆蓋if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 步驟4：若桶中是紅黑樹，則調用樹插入方法else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 步驟5：若桶中是鏈表，遍歷鏈表尋找插入位置else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 鏈表長度≥8，觸發樹化if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);break;}// 找到相同key的節點，跳出循環if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 步驟6：若存在相同key的節點，替換valueif (e != null) {V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;// 步驟7：元素數量超過閾值，觸發擴容if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

3.2 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) {newCap = oldCap << 1; // 容量翻倍newThr = oldThr << 1; // 閾值翻倍} else if (oldThr > 0) {newCap = oldThr;} else {newCap = 16; // 默認初始容量newThr = 12; // 默認初始閾值（16*0.75）}// 創建新數組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;// 鏈表和紅黑樹的遷移邏輯（見上文）// ...}}}return newTab;
}