實用指南：HashMap 源碼逐行讀：hash 方法、衝突鏈表、紅黑樹閾值、擴容死鏈詳情 - 鏈表,紅黑樹,位異或,Python,後端開發 mb61c46a7ab1eee 博客

關鍵詞：HashMap、hash 算法、紅黑樹、鏈表、擴容死鏈、源碼、面試
適合人羣：Java 初中高級工程師 · 面試衝刺 · 代碼調優 · 架構設計
閲讀時長：40 min（≈ 6000 字）
版本環境：JDK 17（源碼行號對應 jdk-17+35，同時回顧 JDK 7 死鏈）

1. 開場白：面試四連擊，能抗算我輸

“HashMap 的 hash 方法為什麼要把高 16 位異或到低 16 位？”
“鏈表轉紅黑樹閾值為什麼是 8 而不是 7 或 9？”
“JDK 7 擴容死鏈如何形成？請現場畫圖。”
“紅黑樹退鏈表閾值 6，那為什麼不是 7？”

阿里 P8 面完 100 人，能把行號、 CPU 分支預測、泊松分佈串起來的不到 5 個。
線上事故：金融系統 JDK 7 時代 512 線程併發 put，觸發死鏈，CPU 100%，FullGC 每 2 min 一次，回滾包車。
背完本篇，你能手寫紅黑樹旋轉、復現死鏈環路、給出 3 種規避方案，讓面試官沉默。

2. 知識骨架：HashMap 全圖一張帶走

HashMap
├─Node[] table               // 底層數組
├─int threshold                   // 擴容閾值 = capacity * loadFactor
├─final float loadFactor          // 負載因子，默認 0.75f
├─static final int TREEIFY_THRESHOLD = 8
├─static final int UNTREEIFY_THRESHOLD = 6
├─static final int MIN_TREEIFY_CAPACITY = 64
└─static final int hash(Object key) // 擾動函數,v>

讀寫流程：
hash → (n-1) & hash 定位桶 → 鏈表 or 樹 → 衝突拉鍊 → 擴容 → 重新散列

3. 身世檔案：核心參數一表打盡

字段/常量	含義	默認值/備註
DEFAULT_INITIAL_CAPACITY	初始容量	16
MAXIMUM_CAPACITY	最大容量	1 << 30
DEFAULT_LOAD_FACTOR	負載因子	0.75f
TREEIFY_THRESHOLD	鏈表轉紅黑樹閾值	8
UNTREEIFY_THRESHOLD	紅黑樹退鏈表閾值	6
MIN_TREEIFY_CAPACITY	樹化最小表長度	64

4. 原理解碼：源碼逐行，行號指路

4.1 hash 算法：高 16 位異或，降低衝突（行號 340）

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

目的：讓高 16 位也參與 (n-1)&hash 運算，減少表長較小時的碰撞。

4.2 putVal 全流程（行號 631）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
  if ((tab = table) == null || (n = tab.length) == 0)
  n = (tab = resize()).length;                // ① 懶初始化
  if ((p = tab[i = (n - 1) & hash]) == null)
  tab[i] = newNode(hash, key, value, null);   // ② 桶空
  else {
  Node<K,V> e; K k;
    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    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) // 8-1=7
      treeifyBin(tab, hash);              // 行號 657
      break;
      }
      if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
      break;
      p = e;
      }
      }
      if (e != null) { // existing mapping
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
      e.value = value;
      afterNodeAccess(e);
      return oldValue;
      }
      }
      ++modCount;
      if (++size > threshold)
      resize();                                      // ⑥ 擴容
      afterNodeInsertion(evict);
      return null;
      }

4.3 treeifyBin()：鏈表轉紅黑樹（行號 757）

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)
    resize();                                       // 表長 < 64 優先擴容
    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)
        hd = p;
        else {
        p.prev = tl;
        tl.next = p;
        }
        tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
        hd.treeify(tab);                            // 真正樹化
        }
        }

先樹化鏈表節點，再構建紅黑樹；表長不足 64 則擴容退避。

4.4 擴容 resize()：2 倍容量 + 重散列（行號 699）

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int newCap, newThr = 0;
    if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = threshold << 1; // 2 倍閾值
    }
    else if (threshold > 0)
    newCap = threshold;           // 指定初始容量
    else {
    newCap = DEFAULT_INITIAL_CAPACITY; // 16
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12
    }
    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; // help GC
        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 { // 鏈表
          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 {                          // 原索引 + oldCap
                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;
                }

亮點：利用 (e.hash & oldCap) == 0 判斷新桶位置，避免重新取模。

4.5 紅黑樹退化鏈表（行號 798）

final boolean untreeify(HashMap<K,V> map, Node<K,V>[] tab) {
  // 樹節點數 ≤ 6 時退鏈表
  }

閾值 6 而非 7，避免在 6-7 之間頻繁樹化/退樹造成 CPU 抖動（泊松分佈 < 0.00005）。

5. 實戰復現：3 段代碼 + 壓測

5.1 哈希衝突測試：String 相近 key

Map<String,Integer> map = new HashMap<>(16);
  for (int i = 0; i < 20; i++) {
  map.put("Aa" + i, i);   // hash("Aa")=2112 相同前綴
  }
  System.out.println(map.size()); // 20

JProfiler 查看：同桶內鏈表長度 = 20，未樹化（表長 16 < 64）。

5.2 樹化與退化觀測

Map<Integer,String> map = new HashMap<>(64); // 指定 64 避免擴容
  // 生成 20 個 hash 衝突的 key
  for (int i = 0; i < 20; i++) {
  int hash = 12345; // 強制衝突
  map.put(new Key(hash, i), "v" + i);
  }

當 i = 8 時斷點：進入 treeifyBin()；
刪除至 6 個節點：觸發 untreeify()。

5. JDK 7 死鏈復現（單線程模擬）

// 使用 JDK 7 源碼拷貝
Map<Integer,Integer> map = new java7.HashHashMap<>(2, 0.75f);
  for (int i = 0; i < 5; i++) map.put(i, i); // 觸發多次擴容

斷點觀測：
transfer 方法內 Entry next = e.next; 與 e.next = newTable[i]; 形成環，導致 get() 死循環。

6. 線上事故：負載因子 1.0 引發 CPU 飆高

背景
日誌統計 Map<String,Long> 默認負載因子 0.75，數據量 2000 萬，運維誤改為 1.0 想“省內存”。

現象
CPU 使用率 +50%，RT P99 從 50 ms 漲到 500 ms。

根因
負載因子 1.0 導致鏈表長度平均 8-12，大量桶遍歷；紅黑樹雖緩解，但 hash 衝突高時仍退化。

覆盤

壓測：0.75 vs 1.0，QPS 下降 40%。
修復：改回 0.75，並預擴容 new HashMap<>(1 << 24)。
防呆：代碼託管平台增加 .properties 參數校驗規則。

7. 面試 10 連擊：答案 + 行號

問題	答案
1. hash 方法高 16 位異或目的？	減少表長較小時的碰撞（行號 340）
2. 鏈表轉樹閾值？	8（行號 657）
3. 樹退鏈表閾值？	6（行號 798）
4. 最小樹化表長？	64（行號 757）
5. 為何閾值 8 和 6 不連續？	避免 6-7 之間頻繁樹化/退樹抖動
6. 擴容倍數？	2 倍（行號 703）
7. 重新散列算法？	`e.hash & oldCap == 0` 判斷新桶（行號 725）
8. JDK 7 死鏈根本原因？	頭插法 + 併發 transfer 形成環
9. 負載因子 1.0 影響？	鏈表長，查詢退化到 O(n)
10. 如何線程安全？	`ConcurrentHashMap`

8. 總結昇華：一張腦圖 + 三句話口訣

[腦圖文字版]
中央：HashMap
├─hash：高 16 位異或
├─鏈表：≥8 && 表≥64 轉樹
├─擴容：2 倍，重散列
└─死鏈：JDK 7 頭插環

口訣：
“高 16 位異或低，八六閾值樹退鏈；二倍擴容重散列，七版死鏈要記全。”

9. 下篇預告

下一篇《早期線程安全集合源碼速讀：Hashtable、Vector、Collections.synchronizedXxx》將帶你全表鎖、併發壓測、兼容遷移，敬請期待！

10. 互動專區

你在生產環境踩過 HashMap 樹化或死鏈坑嗎？評論區貼出堆棧 / GC 圖，一起源碼級排查！

mb61c46a7ab1eee 博客

mb61c46a7ab1eee 博客

博客 / 詳情