Java HashSet 深度解析：HashMap 底層實現、核心 API、遍歷與序列化機制

一、HashSet 核心定位

• 無序、不重複集合，底層封裝 HashMap<E, Object>。
• 所有元素作為 HashMap 的 Key 存儲，Value 統一為 PRESENT = new Object()。
• 允許 一個 null 元素。
• 非線程安全，迭代器 Fail-Fast。
• 基本操作 add/remove/contains 平均 O(1)。

二、構造函數與容量/負載因子

// 預設：容量 16，負載因子 0.75
new HashSet<>();

// 指定初始容量（避免擴容）
new HashSet<>(1024);

// 指定容量與負載因子
new HashSet<>(1024, 0.9f);

// 從集合複製（自動計算合適容量）
new HashSet<>(existingCollection);

容量計算細節：Math.max((int)(c.size()/0.75f) + 1, 16)，確保不超過負載因子觸發擴容，且為 2 的冪（HashMap 要求）。

三、核心 API 與源碼映射

四、遍歷方式與效能

1. Iterator（推薦，O(n)）

for (Iterator it = set.iterator(); it.hasNext(); ) {
    E e = it.next();
}

2. 增強 for（語法糖，內部用 Iterator）

for (E e : set) { ... }

3. toArray + 索引（不推薦，額外陣列分配）

Object[] arr = set.toArray();
for (int i = 0; i < arr.length; i++) { ... }

五、序列化機制細節

private void writeObject(ObjectOutputStream s) throws IOException {
    s.defaultWriteObject();
    s.writeInt(map.capacity());      // 容量
    s.writeFloat(map.loadFactor());  // 負載因子
    s.writeInt(map.size());          // 實際大小
    for (E e : map.keySet()) s.writeObject(e); // 寫入所有元素
}

private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    int capacity = s.readInt();
    float loadFactor = s.readFloat();
    map = new HashMap<>(capacity, loadFactor); // 重建 HashMap
    int size = s.readInt();
    for (int i = 0; i < size; i++) {
        @SuppressWarnings("unchecked") E e = (E) s.readObject();
        map.put(e, PRESENT);
    }
}

關鍵點：序列化保存「容量、負載因子、元素」，反序列化重建 HashMap，不保存 modCount、table 結構，保證跨版本相容。

六、LinkedHashSet：有序版 HashSet

• 繼承 HashSet，構造函數傳 dummy=true 創建 LinkedHashMap。
• 維護雙向鏈表，**保持插入順序**（或訪問順序 accessOrder=true）。
• 迭代順序 = 插入順序，適合 LRU 快取實現。

七、常見陷阱

• 可變物件作元素：加入後修改影響 hashCode/equals → 找不到/重複。元素必須不可變或不修改關鍵欄位。
• 大量數據預估容量：new HashSet<>(expectedSize) 避免多次擴容 Rehash。
• 多線程：用 Collections.synchronizedSet(new HashSet<>()) 或 ConcurrentHashMap.newKeySet() (Java 8+)。

八、總結

HashSet = HashMap Key 視圖，O(1) 去重神器；
元素不可變、預估容量、非線程安全；
需有序用 LinkedHashSet，高併發用 ConcurrentHashMap.newKeySet()。