您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

IdentityHashMap 深度解析：基於同一性（==）的高性能 Map 實現原理

編輯：Java 綜合教學

前言

IdentityHashMap 是 Java 集合框架中一種特殊的 Map 實現：它通過 引用同一性（==） 而非 equals() 判斷鍵相等。這意味著兩個 equals() 返回 true 的對象，在 IdentityHashMap 中視為不同鍵。本文從初始化、存儲、查找、刪除四大核心流程，配合源碼與流程圖，深度剖析其獨特的線性探測數組存儲機制。

一、核心特徵速覽

特性	IdentityHashMap	HashMap
鍵比較方式	`key1 == key2`（引用同一性）	`key1.equals(key2)`（邏輯相等）
哈希計算	`System.identityHashCode(key)`	`key.hashCode()`
底層結構	單一 Object[] 數組（鍵值交替存放）	Node[] 數組 + 鏈表/紅黑樹
衝突解決	線性探測	鏈表/樹化
負載因子	固定 2/3	默認 0.75，可調
典型用途	對象身份追蹤、序列化、圖算法節點標記	通用鍵值存儲

二、初始化：容量對齊與雙倍數組

構造方法

public IdentityHashMap() {
    init(DEFAULT_CAPACITY); // 默認 32
}
public IdentityHashMap(int expectedMaxSize) {
    init(capacity(expectedMaxSize)); // 對齊到 2 的冪次
}
public IdentityHashMap(Map<? extends K, ? extends V> m) {
    this((int) ((1 + m.size()) * 1.1));
    putAll(m);
}

核心 init 邏輯

private void init(int initCapacity) {
    threshold = (initCapacity * 2) / 3; // 閾值 = 容量 * 2/3
    table = new Object[2 * initCapacity]; // 數組長度 = 2 * 容量（鍵值交替）
}

關鍵點：

capacity(expectedMaxSize) 將預期大小向上對齊到最近的 2 的冪次（如 10→16，100→128），保證模運算均勻分布。
數組長度為 2 * capacity，因為 table[2*i] 存鍵，table[2*i+1] 存值，**鍵值緊湊相鄰**，利於 CPU 緩存行命中。
閾值固定為容量的 2/3，達到閾值觸發擴容（數組長度翻倍）。

三、存儲：put(K key, V value) — 線性探測插入

public V put(K key, V value) {
    Object k = maskNull(key);           // null 鍵轉為特殊佔位對象
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);               // 計算初始索引：(hash & (len-1)) * 2
    Object item;
    while ((item = tab[i]) != null) {   // 線性探測：步長 2（跳過值位置）
        if (item == k) {                // 同一性比較：找到相同鍵
            V oldValue = (V) tab[i + 1];
            tab[i + 1] = value;
            return oldValue;
        }
        i = nextKeyIndex(i, len);       // i = (i + 2) % len
    }
    modCount++;
    tab[i] = k;                         // 空槽：存鍵
    tab[i + 1] = value;                 // 緊鄰存值
    if (++size >= threshold) resize(len);
    return null;
}

private static int nextKeyIndex(int i, int len) {
    return (i + 2 < len ? i + 2 : 0);   // 環狀數組，步長 2
}

流程圖解

IdentityHashMap put 流程圖

關鍵機制

maskNull(key)：同 EnumMap，用單例 NULL 佔位區分「鍵為 null」與「槽位為空」。
hash(k, len)：(System.identityHashCode(k) & (len/2 - 1)) * 2，結果為偶數，直接指向鍵槽位。
線性探測步長 2：每次檢查下一個鍵槽位（跳過值槽位），環狀繞回。
擴容保證終止：因擴容後數組長度翻倍，負載因子降至 1/3，探測必定能找到空槽或原鍵，避免死循環。

四、查找：get(Object key) — 同邏輯探測

public V get(Object key) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
    while (true) {
        Object item = tab[i];
        if (item == k) return (V) tab[i + 1]; // 同一性命中
        if (item == null) return null;        // 遇到空槽，鍵不存在
        i = nextKeyIndex(i, len);
    }
}

邏輯與 put 探測一致：同一性匹配返回值，遇 null 槽位判定不存在。

五、刪除：remove(Object key) — 雙清理 + closeDeletion

public V remove(Object key) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
    while (true) {
        Object item = tab[i];
        if (item == k) {
            modCount++;
            size--;
            V oldValue = (V) tab[i + 1];
            tab[i + 1] = null;  // 清值
            tab[i] = null;      // 清鍵
            closeDeletion(i);   // 關鍵：修復探測鏈
            return oldValue;
        }
        if (item == null) return null;
        i = nextKeyIndex(i, len);
    }
}