您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

深入解析 Java HashMap 核心原理與實現機制

編輯：Java 相關知識

前言

HashMap 是 Java 開發者最常使用的集合類之一，它提供了鍵值對的高效存儲與檢索。然而，許多開發者僅停留在「會用」層面，對其內部運作機制知之甚少。本文將深入剖析 java.util.HashMap 的源碼實現（涵蓋 Java 7 與 Java 8），探討其數據結構、擴容機制、線程安全問題、鍵的不可變性要求，以及 Java 8 引入的紅黑樹優化，並分析記憶體佔用與性能調優要點。

核心數據結構：數組 + 鏈表（Java 7）

HashMap 實現了 Map<K, V> 接口，內部靜態類 Entry<K, V> 封裝鍵值對，包含以下字段：

final K key：鍵
V value：值
Entry<K, V> next：指向下一個 Entry 的引用，形成單向鏈表
int hash：鍵的哈希值緩存，避免重複計算

數據存儲在一個 Entry<K, V>[] 數組（稱為桶或槽）中，默認初始容量為 16。所有擁有相同哈希值（經過再哈希與取模運算後索引相同）的鍵值對會被放入同一個桶的鏈表中。

索引計算與再哈希

當調用 put() 或 get() 時，經過三步確定桶索引：

獲取鍵的 hashCode()。

執行再哈希函數，擾亂高位信息到低位，減少哈希碰撞。

// Java 7
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

// Java 8 簡化為
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

使用位掩碼 h & (length - 1) 計算索引，要求數組長度必須是 2 的冪次，這樣 length - 1 的二進制全為 1，可均勻分佈索引。

動態擴容機制

為了防止鏈表過長導致操作退化為 O(n)，HashMap 會在元素數量超過閾值（capacity * loadFactor，默認 16 × 0.75 = 12）時自動擴容：

創建新數組，容量翻倍（仍為 2 的冪次）。
重新計算所有現有 Entry 的索引並遷移（rehash）。
擴容後鏈表長度平均減半，提升 get/put/remove 效率。

注意：擴容是耗時操作，預估數據量大時應通過構造函數指定 initialCapacity 避免頻繁擴容。

線程安全與替代方案

HashMap 非線程安全。多線程並發 put 可能導致：

數據丟失或覆蓋。
鏈表形成環狀結構，導致 get() 無限循環。

解決方案：

Hashtable：所有方法同步，性能低下。
Collections.synchronizedMap()：同步包裝器，同樣鎖住整個 Map。
推薦 ConcurrentHashMap (Java 5+)：分段鎖（Java 7）或 CAS + synchronized + 紅黑樹（Java 8），僅鎖定桶級別，高並發下吞吐量遠超前兩者。

鍵的不可變性至關重要

若鍵對象在放入 Map 後被修改導致 hashCode() 改變，Map 將無法定位到原桶，造成數據「丟失」。

最佳實踐：使用 String、Integer 等不可變類作為鍵；自定義類作為鍵時，務必保證不可變，並正確重寫 equals() 和 hashCode()。

Java 8 關鍵優化：紅黑樹化

Java 8 將 Entry 重命名為 Node，並在桶節點數超過閾值（默認 8）時將鏈表轉換為紅黑樹（TreeNode），退化閾值為 6。紅黑樹屬於自平衡二叉搜索樹，查詢/插入/刪除複雜度從 O(n) 降為 O(log n)，極大改善哈希碰撞嚴重時的性能。

// 簡化結構
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; final K key; V value; Node<K,V> next;
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent, left, right, prev; boolean red;
}