1. 核心數據結構
JDK 1.7 及之前：數組 + 鏈表
JDK 1.8 及之后：數組 + 鏈表/紅黑樹（鏈表長度 ≥8 時轉紅黑樹，≤6 時退化為鏈表）
// JDK 1.8 的 Node 定義（鏈表節點）
static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next; // 鏈表指針
}// TreeNode 定義（紅黑樹節點）
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // 父節點TreeNode<K,V> left; // 左子樹TreeNode<K,V> right; // 右子樹TreeNode<K,V> prev; // 前驅節點boolean red; // 顏色標識
}2. 哈希函數設計
作用：將 Key 映射到數組索引，盡可能減少哈希沖突。
JDK 1.8 的優化：
static final int hash(Object key) {int h;// 高16位與低16位異或，提升散列性return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}索引計算：
index = (table.length - 1) & hash
-
長度取模優化：哈希表容量為 2 的冪次時，
(n-1) & hash?等效于?hash % n，但位運算更快。
3. put() 方法流程
-
計算哈希值：調用?
hash(key)。 -
初始化或擴容：若數組為空，調用?
resize()?初始化（默認容量 16，負載因子 0.75）。 -
定位桶位置：
index = (n-1) & hash。 -
處理哈希沖突：
-
鏈表插入：
-
JDK 1.7：頭插法（易導致死循環）。
-
JDK 1.8：尾插法（解決死循環問題）。
-
-
樹化處理：若鏈表長度 ≥8 且數組長度 ≥64，鏈表轉紅黑樹。
-
-
覆蓋或新增節點：
-
Key 已存在：覆蓋 Value，返回舊值。
-
Key 不存在：插入新節點，返回 null。
-
-
擴容檢查：若元素總數 > 閾值（容量 × 負載因子），觸發?
resize()。
4. 擴容機制（resize()）
觸發條件：元素數量超過閾值（容量 × 負載因子，默認 0.75）。
擴容流程：
-
新容量計算：舊容量 × 2（保證容量始終為 2 的冪次）。
-
遷移元素：
-
JDK 1.7：遍歷舊數組，重新哈希每個元素到新數組（頭插法）。
-
JDK 1.8：優化遷移邏輯，鏈表元素拆分為高位鏈和低位鏈（無需重新哈希）：
-
低位鏈：
原索引位置。 -
高位鏈：
原索引位置 + 舊容量。
-
-
優化原理：
由于新容量是舊容量的 2 倍，(newCap - 1) & hash?的結果僅取決于哈希值的第?log2(oldCap)?位是否為 1：
-
若為 0 → 索引不變（低位鏈）。
-
若為 1 → 索引 = 原索引 + 舊容量（高位鏈）。
5. 紅黑樹優化
樹化條件：
-
鏈表長度 ≥?
TREEIFY_THRESHOLD（默認 8）。 -
數組長度 ≥?
MIN_TREEIFY_CAPACITY（默認 64）。
退化條件：
-
紅黑樹節點數 ≤?
UNTREEIFY_THRESHOLD（默認 6）。
優勢：
-
鏈表查詢復雜度 O(n)，紅黑樹查詢復雜度 O(logn)，顯著減少哈希沖突時的性能損耗。
6. 關鍵參數與默認值
| 參數 | 默認值 | 說明 |
|---|---|---|
DEFAULT_INITIAL_CAPACITY | 16 | 默認初始容量 |
DEFAULT_LOAD_FACTOR | 0.75 | 負載因子（擴容閾值 = 容量 × 負載因子） |
TREEIFY_THRESHOLD | 8 | 鏈表轉紅黑樹的閾值 |
UNTREEIFY_THRESHOLD | 6 | 紅黑樹退化為鏈表的閾值 |
MIN_TREEIFY_CAPACITY | 64 | 允許樹化的最小數組長度 |
7. 性能優化建議
-
初始化容量：預估元素數量，避免頻繁擴容（如預計存 1000 元素，初始容量設為 2048）。
-
重寫 hashCode() 和 equals()：確保 Key 對象的哈希分布均勻且相等性判斷準確。
-
避免高頻修改：多線程場景使用?
ConcurrentHashMap。
總結
-
核心結構：數組 + 鏈表/紅黑樹，動態擴容優化性能。
-
哈希設計：高位異或、位運算取模、紅黑樹優化沖突。
-
線程安全：非線程安全，需使用替代方案。
-
實戰技巧：合理初始化容量、重寫哈希方法、避免并發操作。
