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

深度解析 Java HashMap 源碼：核心機制與實現原理

編輯：Java 相關知識

HashMap 概述

HashMap 是 Java 集合框架中最常用的映射實現之一，基於哈希表數據結構構建。每個元素以鍵值對形式存儲，內部採用單向鏈表解決哈希衝突，當容量不足超過閾值時會自動擴容。需要注意的是，HashMap 不是線程安全的，僅適用於單線程環境；多線程場景下建議使用 ConcurrentHashMap。此外，HashMap 實現了 Serializable 和 Cloneable 接口，支持序列化與克隆操作。

核心屬性與構造函數

關鍵常量

DEFAULT_INITIAL_CAPACITY = 16：默認初始容量，必須是 2 的冪次
MAXIMUM_CAPACITY = 1 << 30：最大容量限制
DEFAULT_LOAD_FACTOR = 0.75f：默認加載因子，平衡空間利用率與查找效率

核心字段

transient Entry[] table;      // 存儲數據的 Entry 數組
transient int size;           // 實際存儲的鍵值對數量
int threshold;                // 擴容閾值 = capacity * loadFactor
final float loadFactor;       // 加載因子
transient volatile int modCount; // 修改次數，用於 fail-fast 機制

四種構造函數

HashMap 提供四種構造方式，核心邏輯都是將用戶指定容量調整為不小於該值的最小 2 的冪次，並計算閾值。無參構造使用默認值 16 和 0.75。

核心方法深度解析

哈希計算與索引定位

HashMap 的高效核心在於其哈希算法與索引計算：

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);
}

hash() 通過多次無符號右移與異或運算，將高位信息混合到低位，減少哈希碰撞。indexFor() 利用位與運算替代取模，因容量始終是 2 的冪次，h & (length-1) 等價於 h % length 但效率更高。

get 方法：查找流程

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;
}

key 為 null 時固定存放在 table[0] 的鏈表中
非 null key 先計算 hash，定位數組索引，再遍歷鏈表比對 key

put 方法：插入與更新邏輯

public V put(K key, V value) {
    if (key == null) return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    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;
}

關鍵點：

鏈表頭插法：新節點總是插入鏈表頭部
key 存在則更新 value 並返回舊值
插入後檢查 size 是否達到 threshold，觸發擴容

擴容機制：resize 與 transfer

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 e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

擴容會重新計算所有元素在新數組中的位置，是耗時操作。建議預估數據量預設初始容量以提升性能。

Entry 節點結構

static class Entry implements Map.Entry {
    final K key;
    V value;
    Entry next;
    final int hash;
    // 構造函數、getKey、getValue、setValue、equals、hashCode 等方法
}

Entry 實現了 Map.Entry 接口，包含 key、value、hash、next 指針，構成單向鏈表節點。