深度解析 JDK 源碼：HashMap 與 HashSet 的 Hash 存儲機制

集合實質存儲的是對象引用。HashMap、HashSet 均採用 Hash 算法決定存儲位置，實現快速存取。本文通過 JDK 源碼（src.zip）深度剖析其核心機制。

HashMap 存儲流程

put(K key, V value) 關鍵步驟：

1. key == null → putForNullKey 特殊處理。
2. 計算 hash = hash(key.hashCode())，hash() 為擾動函數：h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);
3. index = indexFor(hash, table.length)，indexFor = h & (length-1)。table.length 總是 2 的 n 次方，此位運算等價取模且極快，保證索引落在數組範圍內。
4. 遍歷 table[index] 鏈表：若 e.hash == hash && (e.key == key || key.equals(e.key)) → 覆蓋 value，返回舊值；否則進入下一節點。
5. 鏈表末端未找到 → addEntry(hash, key, value, index)：新 Entry 插入鏈表頭（new Entry(hash, key, value, oldHead)），size++，若超 threshold → resize(2 * table.length) 擴容。

關鍵設計細節

• Entry 鏈表頭插法：新元素插頭，舊元素後移，最近訪問的在鏈頭，利於熱點數據快速命中。
• 容量總是 2 的冪：構造器中 capacity = 1; while (capacity < initialCapacity) capacity <<= 1; 保證。指定 initialCapacity 為 2 的冪可省計算開銷。
• 負載因子：默認 0.75，平衡空間與查詢時間。threshold = capacity * loadFactor。關注空間可調大，關注速度可調小。
• 預設初始容量 16：無參構造器 HashMap() 等價 HashMap(16, 0.75f)。

HashMap 讀取流程

get(Object key)：同樣計算 hash、index，遍歷鏈表比對 hash 與 equals，命中返回 value，否則 null。無哈希衝突時 O(1)；衝突嚴重退化為 O(n)。

HashSet 實現：極薄封裝層

HashSet 內部持有 HashMap<E, Object> map，所有元素作為 key 存儲，value 統一為靜態常量 PRESENT = new Object()。核心方法直接委派：

• add(e) → map.put(e, PRESENT) == null
• contains(o) → map.containsKey(o)
• remove(o) → map.remove(o) == PRESENT
• iterator() → map.keySet().iterator()

本質上 HashSet 就是鍵集視圖的 HashMap。

equals() 與 hashCode() 契約：避坑指南

向 HashMap 放 key 或向 HashSet 放元素時，必須同時重寫 equals() 和 hashCode()，且保持一致：

• equals(true) → hashCode() 必須相等
• 參與 hashCode() 計算的屬性，必須參與 equals() 比較

反面教材

class Name { String first, last; ...  // 重寫 equals 比較 first+last，未重寫 hashCode }
Set<Name> s = new HashSet<>();
s.add(new Name("abc","123"));
s.contains(new Name("abc","123")); // false！默認 hashCode 不同，視為不同對象

正確示範

class Name {
    String first, last;
    public boolean equals(Object o) { ... 比較 first ... }
    public int hashCode() { return first.hashCode(); } // 僅 first 參與
}
HashSet<Name> set = new HashSet<>();
set.add(new Name("abc","123"));
set.add(new Name("abc","456")); // 不會添加，因 first 相同視為重複
// set 僅含第一個元素

調優建議

• 預知數據量大 → 指定較大 initialCapacity（2 的冪），避免多次 resize()。
• 內存緊張 → 適當調大 loadFactor（如 0.85），犧牲查詢速度換空間。
• 查詢頻繁、內存充裕 → 調小 loadFactor（如 0.5），降低衝突概率。