Java HashMap 深度解析：原理、源碼與最佳實踐

HashMap 核心特性概覽

HashMap 是 Java 集合框架中最常用的鍵值對存儲結構，底層基於散列表實現。它繼承自 AbstractMap，實現了 Map、Cloneable 與 Serializable 接口。需要注意的是，HashMap 非線程安全，且允許 null 鍵與 null 值，元素存儲順序不保證穩定。

性能由兩個關鍵參數決定：

• 初始容量：底層桶數組的長度，默認為 16（必須是 2 的冪次）。
• 加載因子：觸發擴容的負載閾值，默認 0.75，在時間與空間間取得平衡。

當元素數量超過 容量 × 加載因子 時，會觸發 rehash 操作，容量翻倍並重新分佈節點。

核心構造函數與 API

HashMap 提供四種構造方式：

// 默認構造
HashMap()
// 指定初始容量
HashMap(int capacity)
// 指定容量與加載因子
HashMap(int capacity, float loadFactor)
// 從現有 Map 複製
HashMap(Map<? extends K, ? extends V> map)

常用 API 包含 put/get/remove、containsKey/containsValue、keySet/values/entrySet、size/isEmpty/clear 等。

源碼核心機制深度剖析

數據結構：拉鏈法解決哈希衝突

HashMap 內部維護一個 Entry[] table 數組，每個桶位存放一個單向鏈表頭節點。Entry 節點包含 key、value、hash 及 next 指針，形成經典的「數組 + 鏈表」結構。

關鍵方法實現細節

哈希計算與索引定位

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
    return h & (length - 1); // length 為 2 的冪次，等價於取模
}

扰動函數將高位特徵混入低位，配合位運算實現均勻分佈。

put 流程與擴容機制

1. key 為 null 直接放入 table[0]；否則計算 hash 並定位索引。
2. 遍歷該桶鏈表，若 key 已存在則覆蓋 value 並返回舊值。
3. 不存在則以頭插法創建新節點，size++ 後檢查是否超過閾值，超過則 resize(2 * table.length)。

resize 會創建新數組，遍歷舊表將所有節點重新計算索引並遷移（JDK 7 為頭插法，可能導致鏈表倒序與併發死循環）。

get/containsKey 查找邏輯

同樣先計算 hash 定位桶，再遍歷鏈表比對 hash 與 key.equals()，命中返回 value 或 Entry，否則返回 null。

迭代器與 Fail-Fast 機制

HashIterator 內部維護 expectedModCount，遍歷時若檢測到 modCount 變更拋出 ConcurrentModificationException，保證單線程下的結構修改可感知。

三種遍歷方式與性能對比

for (Map.Entry<K,V> e : map.entrySet()) {
    K k = e.getKey(); V v = e.getValue();
}

for (K k : map.keySet()) {
    V v = map.get(k);
}

for (V v : map.values()) { ... }

entrySet 避免了二次查找，性能最優；keySet 需額外 get 開銷。

實戰示例

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("orange", 3);

System.out.println("Size: " + map.size());           // 3
System.out.println("Contains 'apple': " + map.containsKey("apple")); // true
System.out.println("Value: " + map.get("banana"));   // 2

map.remove("orange");
map.clear();
System.out.println(map.isEmpty());                  // true

總結與避坑指南

• 預估數據量時指定初始容量，減少 rehash 開銷：new HashMap<>((int)(n/0.75)+1)。
• 多線程環境請使用 ConcurrentHashMap 或 Collections.synchronizedMap。
• 鍵對象務必正確重寫 hashCode() 與 equals()，否則會導致查找失效。
• JDK 8 引入紅黑樹優化長鏈表（閾值 8），本文基於 JDK 7 源碼講解，核心原理相通。