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

HashMap 底層原理深度解析：數據結構、存取流程、擴容機制與性能優化

編輯：Java 相關知識

前言：HashMap 的核心地位

HashMap 是 Java 集合框架中使用頻率最高的 Map 實現，基於哈希表，以鍵值對存儲，支持快速存取。本文將從定義、構造參數、數據結構、put/get 核心流程、哈希算法優化、擴容機制等維度，深度剖析其底層原理（基於 JDK 8 前版本，即數組+鏈表結構）。

一、類定義與繼承體系

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable

實現 Map 接口，定義鍵值映射規範；
繼承 AbstractMap，提供基礎實現，減少開發工作量；
實現 Cloneable、Serializable，支持克隆與序列化。

二、構造函數與關鍵參數

三個構造函數，核心參數兩個：

初始容量：哈希表創建時的桶數組長度，默認 16；
負載因子：衡量填滿程度的閾值，默認 0.75。觸發擴容條件：size >= capacity * loadFactor。

參數影響：負載因子越大，空間利用率越高但鏈表越長（查詢慢）；越小則越稀疏（空間浪費）。默認 0.75 為時空平衡經驗值，通常無需修改。

三、數據結構：數組 + 鏈表（鏈表散列）

HashMap 數據結構示意圖

底層為 Entry[] table 數組，每個元素為鏈表頭節點；
Entry 為內部類，包含 key、value、next 指針、hash 值；
鍵值對作為整體 (Entry) 存儲，value 附屬於 key；
數組長度始終為 2 的 n 次方（構造函數中 capacity <<= 1 保證）。

四、存儲實現：put(key, value) 核心流程

public V put(K key, V value) {
    if (key == null) return putForNullKey(value);  // null 鍵特殊處理，存放 table[0]
    int hash = hash(key.hashCode());               // (1) 計算擾動後哈希值
    int i = indexFor(hash, table.length);          // (2) 計算數組索引
    for (Entry 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);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);                 // 插入新節點
    return null;
}

關鍵點解析

鍵去重：遍歷鏈表，hash 相等且 key.equals() 為真則覆蓋，保證鍵唯一；

哈希擾動函數：

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 的 n 次方，length-1 二進制全為 1，h & (length-1) 等價於 h % length，但位運算比取模快得多；
為什麼長度必須是 2 的 n 次方？
- 若 length=16，length-1=15 (1111)，低位 & 運算保留原哈希低位，高位歸零，分布均勻；
- 若 length=15，length-1=14 (1110)，最低位恆為 0，導致索引 1、3、5... 永遠無數據，空間浪費 + 碰撞激增。

插入節點與擴容：addEntry()

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e); // 头插法，新節點指向舊頭
    if (size++ >= threshold) resize(2 * table.length);     // 擴容觸發
}

頭插法：新節點插入鏈頭，舊節點後移，優雅構建鏈表；
擴容代價大：需重新計算所有鍵在新數組中的索引並復制，預知數據量時預設 initialCapacity 可避免頻繁擴容。

五、讀取實現：get(key) 流程

public V get(Object key) {
    if (key == null) return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

核心邏輯：計算哈希 → 定位索引 → 遍歷鏈表匹配鍵 → 返回值。Entry 將鍵值作為整體存儲，使得存取邏輯高度內聚。