HashMap 源碼深度解析 (JDK 1.7)：佈局、擴容、線程不安全與面試高頻考點

HashMap 源碼深度解析 (JDK 1.7)：佈局、擴容、線程不安全與面試高頻考點

HashMap 是 Java 集合框架中使用頻率最高、面試考察最深的數據結構之一。基於 JDK 1.7.0_79 源碼，本文從類繼承體系、核心字段、關鍵方法、擴容機制、線程安全缺陷五個維度，逐行拆解源碼邏輯，並總結面試必備考點與 JDK 1.8 優化差異。

類結構與核心字段

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
    // 1. 默認初始容量 16 (2^4)
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 2. 最大容量 2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 3. 默認負載因子 0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 4. 空表單例 (延遲初始化優化)
    static final Entry[] EMPTY_TABLE = {};
    // 5. 核心存儲數組，長度永遠是 2 的冪
    transient Entry[] table = (Entry[]) EMPTY_TABLE;
    // 6. 當前鍵值對數量
    transient int size;
    // 7. 擴容閾值 = capacity * loadFactor
    int threshold;
    // 8. 負載因子
    final float loadFactor;
    // 9. 結構性修改次數 (fail-fast 依賴)
    transient int modCount;
    // 10. 替代哈希閾值 (應對哈希碰撞攻擊)
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
    transient int hashSeed = 0;
}

核心數據結構：數組 + 鏈表

• table：Entry 數組，每個槽位是鏈表頭節點。
• Entry：靜態內部類，包含 key、value、next、hash 四字段，實現單向鏈表。
• 索引計算：index = hash & (length - 1) (位運算替代取模，要求 length 為 2 的冪)。

關鍵方法源碼走讀

1. 構造函數與延遲初始化

public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); }
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0) throw new IllegalArgumentException();
    if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException();
    this.loadFactor = loadFactor;
    threshold = initialCapacity; // 暫存，inflateTable 時真正分配
    init(); // 鉤子方法，LinkedHashMap 覆寫
}
// 首次 put 時觸發 inflateTable(threshold) 真正分配數組

2. hash() 雙重擾動函數 (關鍵)

final int hash(Object k) {
    int h = hashSeed;
    if (h != 0 && k instanceof String) // 字符串專用哈希 (JDK 1.7 引入，1.8 移除)
        return sun.misc.Hashing.stringHash32((String) k);
    h ^= k.hashCode();           // 一次擾動：高位混入低位
    h ^= (h >>> 20) ^ (h >>> 12); // 二次擾動
    return h ^ (h >>> 7) ^ (h >>> 4); // 三次擾動
}

目的：降低哈希碰撞，防止惡意構造鍵導致鏈表退化為 O(n) 查找 (HashDoS 攻擊)。

3. put() 核心邏輯

public V put(K key, V value) {
    if (table == EMPTY_TABLE) inflateTable(threshold); // 首次擴容
    if (key == null) return putForNullKey(value);      // null key 固定放 table[0]
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    // 遍歷鏈表，key 相等則覆蓋
    for (Entry e = table[i]; e != null; e = e.next) {
        if (e.hash == hash && (e.key == key || key.equals(e.key))) {
            V old = e.value;
            e.value = value;
            e.recordAccess(this);
            return old;
        }
    }
    modCount++;
    addEntry(hash, key, value, i); // 頭插法
    return null;
}

4. 擴容 resize() — 線程不安全核心現場

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity)); // 關鍵：遷移數據
    table = newTable;
    threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry e : table) {
        while (e != null) {
            Entry next = e.next;
            if (rehash) e.hash = (e.key == null) ? 0 : hash(e.key);
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i]; // 頭插法
            newTable[i] = e;
            e = next;
        }
    }
}

致命缺陷：頭插法 + 並發 resize → 鏈表成環 → CPU 100% 死循環。
線程 A、B 同時遷移同一鏈表，A 執行 e.next = newTable[i] 後掛起，B 完成遷移，A 恢復繼續將已遷移節點再次接入，形成環。JDK 1.8 改為**尾插法**保持原順序，徹底解決。

5. get() 與 null key 處理

public V get(Object key) {
    if (key == null) return getForNullKey(); // 遍歷 table[0]
    Entry entry = getEntry(key);
    return entry == null ? null : entry.getValue();
}
final Entry getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key);
    for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key))))
            return e;
    }
    return null;
}

JDK 1.7 vs 1.8 核心差異對比

面試高頻考點速記卡

1. 為什麼負載因子 0.75？ 時間空間折中：0.5 空間浪費，1.0 碰撞過多；0.75 下泊松分佈鏈表長度期望極短。
2. 為什麼容量必須是 2 的冪？ hash & (n-1) 等價於取模，且分佈均勻；非 2 的冪會導致低位固定為 0，嚴重失衡。
3. HashMap 線程不安全具體表現？ 並發 resize 成環、數據覆蓋丟失、size 統計錯誤。
4. 如何解決？ Collections.synchronizedMap (鎖整張表)、ConcurrentHashMap (分段鎖/CAS)、JDK 1.8+ 原生安全。
5. 樹化閾值 8 的由來？ 泊松分佈下鏈表長度達 8 的概率 < 0.00000006，極小事件觸發樹化收益大於成本。

總結

HashMap 以「數組 + 鏈表/紅黑樹」實現 O(1) 平均查找，通過「2 的冪容量 + 擾動函數 + 負載因子擴容」平衡時空。JDK 1.7 頭插法導致的並發死循環是經典教訓，JDK 1.8 尾插法 + 樹化 + 擴容優化構建了工業級強健實現。掌握源碼邏輯，不僅為面試，更為理解分布式系統中一致性哈希、分片路由等高階架構奠基。