HashMap 核心原理與 JDK 7 源碼深度解析：數組+鏈表、擴容機制、哈希均勻化

HashMap 核心原理與 JDK 7 源碼深度解析：數組+鏈表、擴容機制、哈希均勻化

HashMap 是面試必考、生產高頻的核心集合。本文從哈希表基礎理論出發，逐行剖析 JDK 7 HashMap 源碼：put/get 流程、hash() 擾亂函數、indexFor() 定位、resize() 擴容遷移、長度為 2 的冪設計哲學，最後證明 equals/hashCode 契約的必要性。

一、哈希表為何快：O(1) 的秘密

• 數組：下標定位 O(1)，但擴容/插入刪除 O(n)
• 鏈表：增刪 O(1)，但查找 O(n)
• 哈希表：數組 + 鏈表，key → hash → index → bucket → 遍歷鏈表，理想情況 O(1)

二、JDK 7 核心字段

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // 主幹數組
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key; V value; Entry<K,V> next; int hash; // 單向鏈表節點
}
int size;                    // 實際 KV 對數
int threshold;               // 擴容閾值 = capacity * loadFactor
final float loadFactor = 0.75f; // 負載因子
int modCount;                // 快速失效計數器

三、put(K,V) 全流程

public V put(K key, V value) {
    if (table == EMPTY_TABLE) inflateTable(threshold); // 首次分配
    if (key == null) return putForNullKey(value);      // null 鍵固定 table[0]
    int hash = hash(key);                              // 擾亂計算
    int i = indexFor(hash, table.length);              // 定位桶索引
    for (Entry<K,V> 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.1 hash(Object) — 擾亂函數

final int hash(Object k) {
    int h = hashSeed;
    if (h != 0 && k instanceof String) return sun.misc.Hashing.stringHash32((String)k);
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12); // 高位混入低位
    return h ^ (h >>> 7) ^ (h >>> 4);
}

目的：將 hashCode() 的高位信息混入低位，減少碰撞。

4.2 indexFor(int h, int length) — 定位索引

static int indexFor(int h, int length) { return h & (length - 1); }

length 為 2 的冪 → length-1 低位全 1 → & 運算等價於取模，且保留低位差異，分佈更均勻。

4.3 inflateTable(int toSize) — 首次/擴容分配

int capacity = roundUpToPowerOf2(toSize); // 向上取 2 的冪
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];

五、擴容遷移 resize() 與 transfer()

void transfer(Entry[] newTable, boolean rehash) {
    for (Entry<K,V> e : table) {
        while (e != null) {
            Entry<K,V> next = e.next;
            if (rehash) e.hash = (e.key == null) ? 0 : hash(e.key);
            int i = indexFor(e.hash, newTable.length);
            e.next = newTable[i]; // 頭插法，順序反轉
            newTable[i] = e;
            e = next;
        }
    }
}

關鍵洞察：長度雙倍擴容 → length-1 只多一個高位 1 → 原索引高位為 0 的節點留在原桶，為 1 的遷移到新桶，最小化遷移開銷。

六、為何長度必須是 2 的冪？

1. h & (length-1) 等價取模，位運算比除法快
2. length-1 低位全 1，保證 hash 低位每一位變化都影響索引，分佈均勻
3. 擴容時只新增一個高位，舊節點要么留原桶，要么移新桶，遷移邏輯簡單高效

七、get(Object) 與 equals/hashCode 契約

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

驗證 e.hash == hash 的必要性：若 key.equals() 返回 true 但 hashCode() 不同 (違反契約)，不應匹配，否則會從錯誤桶取出錯誤值。

八、經典反例：重寫 equals 忘寫 hashCode

class Person { int id;
    @Override public boolean equals(Object o) { return o instanceof Person && id == ((Person)o).id; }
    // 缺失 hashCode()
}
Map<Person,String> map = new HashMap<>();
map.put(new Person(1), "喬峰");
map.get(new Person(1)); // 返回 null！因為 hashCode 不同，落入不同桶

鐵律：equals() 相等 → hashCode() 必須相等；hashCode() 相等 → equals() 不一定相等 (允許碰撞)。