Java 深度研究：HashMap 實現原理全解析 - 從拉鏈法到擴容重雜湊

HashMap 是 Java 集合框架中最高頻使用的鍵值對容器。本文基於 JDK 8 源碼，深入剖析其資料結構（陣列+鏈表/紅黑樹）、存取核心演算法、哈希衝突解決、擴容與重雜湊、null 鍵特殊處理、Treeify 樹化閾值等核心機制，並附關鍵源碼註解。

一、核心資料結構：拉鏈法

HashMap 底層是 Node<K,V>[] table 陣列，每個桶位是一條鏈表（或紅黑樹）。

transient Node<K,V>[] table;  // 長度永遠是 2 的冪次

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;  // 鏈表指標
    // ...
}

JDK 8 優化：鏈表長度超過 TREEIFY_THRESHOLD = 8 且陣列長度 ≥ 64 時，轉為紅黑樹，最壞查找從 O(n) 降為 O(log n)。

二、存取核心演算法

1. 雜湊值計算 hash(Object key)

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

高 16 位參與運算，減少哈希衝突，提升分佈均勻度。

2. 索引定位 indexFor / (n-1) & hash

// 陣列長度 n 永遠是 2 的冪次，n-1 低位全 1
// hash & (n-1) 等價 hash % n，但位運算極快
int index = (n - 1) & hash;

3. put(K key, V value) 完整流程

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. 首次使用或擴容後 lazy 初始化 table
    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. 鍵已存在（hash 相等且 key equals），覆蓋舊值
        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;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                    break;  // 找到重複鍵
                }
                p = e;
            }
        }
        if (e != null) {  // 覆蓋舊值
            V oldValue = e.value;
            if (!onlyIfAbsent) e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    ++modCount;
    // 6. 尺寸超過閾值觸發擴容
    if (++size > threshold)
        resize();
    return null;
}

4. get(Object key) 查找流程

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

三、null 鍵特殊處理

• hash(null) = 0，永遠落在 table[0]
• 鏈表中允許一個 key == null 的節點
• putForNullKey/getForNullKey 專門處理

四、擴容與重雜湊 resize()

觸發條件

size > threshold，其中 threshold = capacity * loadFactor（預設 0.75）。

擴容邏輯

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    if (oldCap >= MAXIMUM_CAPACITY) {  // 1<<30
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    int newCap = oldCap << 1;  // 2倍擴容
    Node<K,V>[] newTab = (Node<K,V>[]) new Node[newCap];
    transfer(newTab);          // 核心：重新計算索引遷移節點
    table = newTab;
    threshold = (int)(newCap * loadFactor);
    return newTab;
}

遷移核心 transfer()（JDK 7 風格，JDK 8 優化為 resize() 內聯）

void transfer(Node<K,V>[] newTab) {
    Node<K,V>[] src = table;
    int newCap = newTab.length;
    for (int j = 0; j < src.length; j++) {
        Node<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Node<K,V> next = e.next;
                // 重新計算索引：高位參與運算，元素可能留在原桶或移到 newCap+oldCap
                int i = (newCap - 1) & e.hash;
                e.next = newTab[i];
                newTab[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

關鍵優化：JDK 8 利用 e.hash & oldCap 判斷節點是否需移動，避免重新計算完整 hash，形成「低位不變、高位決定遷移」的高效遷移。

五、初始容量規則

public HashMap(int initialCapacity, float loadFactor) {
    // 找到 >= initialCapacity 的最小 2 的冪次
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
    table = new Node[capacity];
}

確保 capacity 為 2 的冂次，保證 hash & (n-1) 等價取模。

六、哈希衝突解決方案對比

七、JDK 7 vs JDK 8 關鍵差異

八、總結

HashMap 以拉鏈法 + 位運算索引 + 2 的冂次擴容 + 紅黑樹樹化 實現高效鍵值存取。核心亮點：

1. hash() 高低位混合減少衝突
2. (n-1) & hash O(1) 索引定位
3. 尾插法 + 擴容高位判斷避免死循環與重算
4. 鏈表轉紅黑樹保證極端情況 O(log n)
5. null 鍵固定桶位 0 特殊處理

理解這些機制，能指導適當設定 initialCapacity 避免頻繁擴容、選擇良好 hashCode() 實現均勻分佈、排查生產環境效能抖動。

1. 上一篇文章： Java 基礎：反射機制核心 API 與實戰應用完整指南
2. 下一篇文章： Java 集合框架全景圖解：Set/List/Map 核心實現類深度對比與選型指南

Java 相關知識

精通 Eclipse 3.4：工作台核心概念與客製化完整指南

本文為 Eclipse 新手量身打造，詳細解析 Eclips

Java 封裝機制深度解析：訪問修飾符、this 關鍵字、內部類四種形式與最佳實踐

封裝核心三步驟 屬性 private 隱藏。 提供 pub

深度解析 HashMap 核心原理與手寫實現

HashMap 是 Java 開發中使用頻率最高的集合類之一

jBPM 4.0 開發指南：第 2 章 流程虛擬機核心原理

第 2 章 流程虛擬機核心原理 2.1 核心設計理念 為支