JDK 源碼級剖析：HashMap 與 HashSet 的 Hash 存儲機制

JDK 源碼級剖析：HashMap 與 HashSet 的 Hash 存儲機制

核心結論先行

• HashSet 底層即 HashMap：HashSet 內部持有 HashMap，元素作為 key 存入，value 統一為 PRESENT 靜態對象。
• 存儲決策僅看 key：put(K,V) 計算 key 的 hash 決定桶位置，value 只是附屬跟隨存入。
• 哈希沖突以鏈表/紅黑樹解決：同桶位置形成 Entry 鏈（JDK 8+ 超過閾值轉紅黑樹）。

1. HashMap.put 源碼邏輯（JDK 8 精簡版）

public V put(K key, V value) {
    if (key == null) return putForNullKey(value);
    int hash = hash(key.hashCode());           // 1. 擾動函數
    int i = indexFor(hash, table.length);      // 2. 定位桶索引
    for (Entry 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;                   // 3. key 相等 → 覆蓋 value
            return old;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);             // 4. key 不等 → 頭插法入鏈
    return null;
}

2. 關鍵輔助函數

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) {
        if (e.hash == hash && (e.key == key || key.equals(e.key)))
            return e.value;
    }
    return null;
}

無沖突時 O(1)；沖突時遍歷鏈表，最壞 O(k)（k 為鏈長）。

5. HashSet 核心源碼（精簡）

public class HashSet {
    private transient HashMap map;
    private static final Object PRESENT = new Object();

    public boolean add(E e) { return map.put(e, PRESENT) == null; }
    public boolean remove(Object o) { return map.remove(o) == PRESENT; }
    public Iterator iterator() { return map.keySet().iterator(); }
    // size/isEmpty/contains/clear 均委託 map
}

6. 實戰陷阱：equals/hashCode 契約

自定義類作 key 或存入 HashSet 必須同時重寫 equals() 與 hashCode()，且：

• equals(true) ⇒ hashCode() 相等（強制）
• hashCode() 相等 ⇏ equals(true)（允許沖突）

違反契約會導致：Set 中出現重複元素、Map 無法查找到已放入的 key。

7. 效能調優建議

• 預估數據量，構造時指定 initialCapacity 避免多次擴容。
• 高併發場景改用 ConcurrentHashMap。
• Key 類設計優質 hashCode()（如緩存計算結果、讓高位差異化）。