HashSet 源碼深度剖析：基於 HashMap 的去重原理、序列化與遍歷機制

核心結構：封裝 HashMap

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object(); // 虛擬值

    public HashSet() { map = new HashMap<>(); }
    public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); }
    // ... 其他構造器委託 HashMap
}

核心方法委託映射

add() 與 put() 的去重細節

// HashMap.put 核心邏輯簡化
public V put(K key, V value) {
    Node<K,V>[] tab = table;
    int hash = hash(key);
    int i = (n - 1) & hash;
    for (Node<K,V> e = tab[i]; e != null; e = e.next) {
        if (e.hash == hash && (key == e.key || key.equals(e.key))) {
            V oldValue = e.value;
            e.value = value; // 覆蓋值
            return oldValue; // 返回舊值
        }
    }
    // ... 插入新節點
    return null; // 鍵不存在返回 null
}

因此：HashSet.add(e) 時，若元素已存在（equals 為 true），map.put 會覆蓋值（PRESENT 覆蓋 PRESENT），返回舊值非 null，add 返回 false → 不添加重複元素，且不改變原有元素引用。

equals/hashCode 契約實戰驗證

錯誤示例：只重寫 equals，不重寫 hashCode

class Name { String first, last;
    @Override public boolean equals(Object o) {
        if (this == o) return true;
        if (o instanceof Name) { Name n = (Name)o; return n.first.equals(first) && n.last.equals(last); }
        return false;
    }
    // 缺失 hashCode()
}
Set<Name> set = new HashSet<>();
set.add(new Name("abc", "123"));
System.out.println(set.contains(new Name("abc", "123"))); // 輸出 false！

原因：默認 hashCode() 基於對象地址，兩個 new Name(...) hashCode 不同 → 落入不同桶位 → contains 直接判定不存在，根本不調用 equals。

正確示例：同步重寫 equals + hashCode

class Name {
    String first, last;
    @Override public boolean equals(Object o) {
        if (this == o) return true;
        if (o instanceof Name) { Name n = (Name)o; return n.first.equals(first); } // 僅按 first 判等
        return false;
    }
    @Override public int hashCode() { return first.hashCode(); } // 僅按 first 計算 hash
    @Override public String toString() { return "Name[first=" + first + ", last=" + last + "]"; }
}
Set<Name> set = new HashSet<>();
set.add(new Name("abc", "123"));
set.add(new Name("abc", "456")); // first 相同，視為重複
System.out.println(set); // 輸出：[Name[first=abc, last=123]] 只有第一個

序列化機制

private void writeObject(ObjectOutputStream s) throws IOException {
    s.defaultWriteObject(); // 寫入非 transient 字段（無）
    s.writeInt(map.size()); // 寫入大小
    for (E e : map.keySet()) s.writeObject(e); // 依次寫入元素
}

private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    int size = s.readInt();
    map = new HashMap<>(Math.max((int)(size/.75f) + 1, 16));
    for (int i = 0; i < size; i++) map.put((E) s.readObject(), PRESENT); // 讀取元素重建 map
}

總結

1. HashSet = HashMap.keySet() 視角 + 固定值 PRESENT，所有操作委託 HashMap。
2. 去重核心：hashCode() 定桶，equals() 比鍵 —— 必須同步重寫，且邏輯一致。
3. 序列化：只序列化元素，反序列化時重建 HashMap，無容量膨脹問題。
4. 克隆：淺拷貝元素引用，新建 HashMap 逐個 put。

掌握源碼，面試手寫 HashSet、排查去重失效、優化初始容量皆不在話下。