JDK 1.7 HashMap 源碼深度剖析：存儲結構、核心方法、擴容機制與性能優化

JDK 1.7 HashMap 源碼深度剖析

HashMap 是 Java 集合框架中使用頻率最高的鍵值存儲結構。JDK 1.7 版本採用 數組 + 鏈表 經典結構，其源碼設計蘊含豐富的工程智慧。本文從存儲模型、核心方法 (put/get)、哈希計算、擴容機制、性能調優五個維度深度解析。

存儲結構模型

HashMap 內部結構 (JDK 1.7)
┌─────────────────────────────────────┐
│ transient Entry<K,V>[] table        │  ← 主數組 (桶數組)
└─────────────────────────────────────┘
        │
        ▼ 索引計算: index = hash & (length - 1)
┌─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │ ... │ n-1 │  ← 每個位置稱作「桶」
└─────┴─────┴─────┴─────┴─────┘
        │
        ▼ 同一桶內採用「頭插法」單向鏈表
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ Entry   │───►│ Entry   │───►│ Entry   │───► null
│ key, value   │    │ key, value   │    │ key, value   │
│ hash, next   │    │ hash, next   │    │ hash, next   │
└──────────────┘    └──────────────┘    └──────────────┘

核心字段

// 默認初始容量 16 (必須是 2 的冪次)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

// 最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默認負載因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 存儲數據的桶數組
transient Entry<K,V>[] table;

// 實際鍵值對數量
transient int size;

// 擴容閾值 = capacity * loadFactor
int threshold;

// 修改次數 (用於 fail-fast 迭代器)
transient int modCount;

核心方法源碼解析

1. put(K key, V value) - 插入/更新

public V put(K key, V value) {
    // 1. 表為空時初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    
    // 2. key 為 null 特殊處理 (存放在 table[0])
    if (key == null)
        return putForNullKey(value);
    
    // 3. 計算 hash 值 (關鍵：二次哈希)
    int hash = hash(key);
    
    // 4. 計算桶索引
    int i = indexFor(hash, table.length);
    
    // 5. 遍歷鏈表檢查 key 是否已存在
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;        // 更新值
            e.recordAccess(this);   // LinkedHashMap 回調
            return oldValue;        // 返回舊值
        }
    }
    
    // 6. 不存在則新增
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

2. hash(Object k) - 二次哈希算法

final int hash(Object k) {
    int h = hashSeed; // 隨機種子，防止哈希碰撞攻擊
    
    // String 類型優化路徑
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    
    h ^= k.hashCode(); // 獲取對象 hashCode
    
    // 關鍵：擾動函數 (補充高位信息到低位)
    // 目的：減少哈希碰撞，使分布更均勻
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

擾動函數原理圖解

假設原始 hashCode: 0x80000000 (只有最高位 1)
h >>> 20: 0x00000800
h >>> 12: 0x00080000
h ^= (h>>>20) ^ (h>>>12): 0x80080800  (高位信息傳播到低位)
...
最終結果: 低位包含更多信息熵，indexFor 計算更分散

3. indexFor(int h, int length) - 索引計算

static int indexFor(int h, int length) {
    // 斷言: length 必須是 2 的冪次
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length - 1); // 位運算替代取模
}

為什麼用位運算 & (length-1) 替代 % length？

示例: h=21 (10101), length=16 (10000), length-1=15 (01111)
21 % 16 = 5
21 & 15 = 10101 & 01111 = 00101 = 5  ✅ 結果相同，速度快數十倍

4. addEntry - 新增節點與擴容觸發

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 擴容條件: size >= threshold 且 目標桶非空 (說明發生碰撞)
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length); // 容量翻倍
        hash = (null != key) ? hash(key) : 0; // 重新計算 hash (因 length 變了)
        bucketIndex = indexFor(hash, table.length); // 重新計算索引
    }
    createEntry(hash, key, value, bucketIndex);
}

5. 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); // 核心遷移邏輯
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                // 關鍵：頭插法 - 新節點插在鏈表頭部
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

⚠️ 多線程環境下的致命缺陷：鏈表成環

線程 A 執行到 e.next = newTable[i] 時掛起
線程 B 完成遷移，鏈表順序反轉
線程 A 恢復執行，將舊 next 指向新頭節點
結果：形成環狀鏈表 → get() 死循環 → CPU 100%

這是 JDK 1.8 改為尾插法 + 紅黑樹的核心原因之一

6. get(Object key) - 查找邏輯

final Entry<K,V> getEntry(Object key) {
    if (size == 0) return null;
    
    int hash = (key == null) ? 0 : hash(key);
    // 直接定位桶，遍歷鏈表
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
         e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

初始化容量計算：roundUpToPowerOf2

private static int roundUpToPowerOf2(int number) {
    // 返回大於等於 number 的最小 2 的冪次
    return number >= MAXIMUM_CAPACITY 
        ? MAXIMUM_CAPACITY 
        : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

// Integer.highestOneBit 實現原理
public static int highestOneBit(int i) {
    i |= (i >> 1);
    i |= (i >> 2);
    i |= (i >> 4);
    i |= (i >> 8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

(number - 1) << 1 = 9 << 1 = 18 (10010)
i |= i>>1: 10010 | 01001 = 11011
i |= i>>2: 11011 | 00110 = 11111
i |= i>>4: 11111 | 00001 = 11111
...
i - (i>>>1): 11111 - 01111 = 10000 = 16 ✅

// ❌ 差：默認 16，存 1000 個元素會擴容 6 次 (16→32→64→128→256→512→1024)
Map<String, Object> map = new HashMap<>();

// ✅ 好：預估 1000，初始容量 1024 (2^10)，零擴容
Map<String, Object> map = new HashMap<>(1024);

// ✅ 更精確：構造函數會自動 roundUpToPowerOf2
new HashMap<>(1000) → 實際 capacity = 1024
new HashMap<>(1024) → 實際 capacity = 1024

// 自定義負載因子
Map<String, Object> map = new HashMap<>(1024, 0.5f);