HashMap 底層實現原理深度解析：數組+鏈表、擴容機制、JDK 7/8 差異與手寫 MyHashMap

核心數據結構

HashMap 基於數組 + 鏈表（JDK 8 引入紅黑樹優化）：

• 數組：Node<K,V>[] table，長度為 2 的冪次
• 鏈表/樹：解決哈希衝突，同一索引下掛載

關鍵常量（JDK 8）

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;      // 鏈表轉樹閾值
static final int UNTREEIFY_THRESHOLD = 6;    // 樹轉鏈表閾值
static final int MIN_TREEIFY_CAPACITY = 64;  // 最小樹化容量

核心操作流程

put(K key, V value)

1. key == null → 固定放入 table[0]
2. 計算 hash = hash(key) → index = (n-1) & hash
3. table[index] == null → 新建節點插入
4. 否則遍歷鏈表/樹：
   • key 相同（equals） → 覆蓋 value，返回舊值
   • 到達尾部 → 新節點接入（JDK 7 頭插法 / JDK 8 尾插法）
5. size++ 達到 threshold → resize()

get(Object key)

1. key == null → 查 table[0]
2. 計算 index → 遍歷鏈表/樹匹配 equals
3. 命中返回 value，否則 null

resize() 擴容機制

• 新容量 = 旧容量 * 2
• 重新計算所有節點索引（而非簡單遷移）
• JDK 7：頭插法導致鏈表反轉，高併發下可能成環 → 死循環
• JDK 8：尾插法保持原序，消除成環風險

JDK 7 vs JDK 8 關鍵差異

HashMap vs Hashtable 差異

手寫 MyHashMap 核心實現（教學版）

public class MyHashMap {
    static final int DEFAULT_CAPACITY = 16;
    static final float LOAD_FACTOR = 0.75f;
    
    transient Node[] table;
    int size, threshold;
    
    static class Node {
        final Object key;
        Object value;
        Node next;
        int hash;
        Node(int h, Object k, Object v, Node n) {
            hash = h; key = k; value = v; next = n;
        }
    }
    
    public MyHashMap() {
        table = new Node[DEFAULT_CAPACITY];
        threshold = (int)(DEFAULT_CAPACITY * LOAD_FACTOR);
    }
    
    int index(Object key) {
        return (key.hashCode() ^ (key.hashCode() >>> 16)) & (table.length - 1);
    }
    
    public void put(Object key, Object value) {
        if (key == null) { putNullValue(value); return; }
        int idx = index(key);
        for (Node e = table[idx]; e != null; e = e.next) {
            if (e.hash == key.hashCode() && (e.key == key || key.equals(e.key))) {
                e.value = value; return;
            }
        }
        addNode(idx, key, value, key.hashCode());
    }
    
    void addNode(int idx, Object key, Object value, int hash) {
        table[idx] = new Node(hash, key, value, table[idx]); // 頭插
        if (++size > threshold) resize();
    }
    
    void resize() {
        Node[] old = table;
        table = new Node[old.length * 2];
        threshold = (int)(table.length * LOAD_FACTOR);
        for (Node e : old) {
            while (e != null) {
                Node next = e.next;
                int idx = index(e.key);
                e.next = table[idx];
                table[idx] = e;
                e = next;
            }
        }
    }
    
    public Object get(Object key) {
        if (key == null) return getNullValue();
        int idx = index(key);
        for (Node e = table[idx]; e != null; e = e.next) {
            if (e.hash == key.hashCode() && (e.key == key || key.equals(e.key)))
                return e.value;
        }
        return null;
    }
    // ... remove, containsKey, size, clear 等
}

面試高頻考點總結

1. 為什麼容量是 2 的冪？ → (n-1) & hash 等價取模，均勻分布
2. 負載因子 0.75 權衡？ → 空間換時間，泊松分布下碰撞概率最低
3. JDK 8 為何引入紅黑樹？ → 防止惡意構造碰撞導致 O(n) 退化
4. 多線程下用什麼？ → ConcurrentHashMap 或 Collections.synchronizedMap
5. hashCode 與 equals 契約？ → 相等必同碼，同碼不必相等

深入理解 HashMap 底層，不僅是面試必備，更是排查生產環境性能問題、選擇正確集合類型的基石。

1. 上一篇文章： Selenium 自動化測試：Java 封裝軟斷言實現失敗不中斷、批量驗證最終匯總
2. 下一篇文章： Java Calendar 類完整指南：獲取時間字段、日期運算、月份陷阱與最佳實踐

Java 綜合教學

JavaScript DOM 核心概念與操作實戰指南

DOM 文檔對象模型核心解析 文檔對象模型（DOM）是瀏覽器

《Java 並發編程實戰》學習筆記（一）：線程基礎、Executor、Callable、優先級、Join、共享資源同步

《Java 並發編程實戰》學習筆記（一）：從線程創建到共享資

Swift 專案整合 MMDrawerController 實現側滑抽屜效果完整教學

MMDrawerController 簡介 MMDrawer

Renren-Security：基於 Spring+Shiro+MyBatis 的輕量級權限管理系統深度解析

項目定位 一套開箱即用、代碼生成驅動的後台權限管理框架，核心