Java Set 去重核心原理：hashCode() 與 equals() 雙重檢查機制深度解析

Set 判斷物件相等的兩步驟規則

1. 第一關：hashCode() 比較
   • 若 hashCode() 不相等 → 直接判定為不同物件，結束比較
   • 若 hashCode() 相等 → 進入第二關 (必須，否則效能災難)
2. 第二關：equals() 比較
   • 若 equals() 返回 false → 判定為不同物件
   • 若 equals() 返回 true → 判定為相同物件，Set 拒絕加入

注意：hashCode() 相等 不代表 物件相等 (雜湊碰撞)；但 equals() 相等 必須 暗示 hashCode() 相等 (契約)。

兩類物件的不同表現

1. 一般類別 (未覆寫 hashCode/equals)

• 繼承 Object 預設實作
• hashCode()：本地方法，通常根據記憶體位址 計算
• equals()：比較參考位址 (this == obj)
• 結果：new User(1) 與 new User(1) → 不同物件 (位址不同)，可同時存入 Set

2. 封裝類/String 等 (已覆寫 hashCode/equals)

• String、Integer、Long 等已覆寫
• hashCode()：基於內容 計算 (如字元陣列)
• equals()：比較內容
• 結果："hello" 與 "hello" → 相同物件，第二個被拒

程式碼驗證

// 一般類別：未覆寫
class Plain { int id; Plain(int id){this.id=id;} }

// 正確覆寫類別
class Correct {
    int id;
    Correct(int id){this.id=id;}
    @Override public boolean equals(Object o) {
        return o instanceof Correct && id == ((Correct)o).id;
    }
    @Override public int hashCode() { return Objects.hash(id); }
}

public class SetEqualityDemo {
    public static void main(String[] args) {
        Set<Plain> plainSet = new HashSet<>();
        plainSet.add(new Plain(1));
        plainSet.add(new Plain(1)); // 不同位址，視為不同
        System.out.println("Plain Set 大小: " + plainSet.size()); // 2
        
        Set<Correct> correctSet = new HashSet<>();
        correctSet.add(new Correct(1));
        correctSet.add(new Correct(1)); // 內容相同，視為相同
        System.out.println("Correct Set 大小: " + correctSet.size()); // 1
        
        Set<String> strSet = new HashSet<>();
        strSet.add("hello");
        strSet.add(new String("hello")); // 內容相同
        System.out.println("String Set 大小: " + strSet.size()); // 1
    }
}

HashMap/HashSet 內部儲存邏輯圖解

新增元素 e:
1. 計算 h = e.hashCode()
2. 索引桶位: index = (n-1) & h  (n 為陣列長度，2的冪)
3. 遍歷該桶位鏈表/紅黑樹:
   FOR each node in bucket:
       IF node.hash == h AND (node.key == e OR node.key.equals(e)):
           // 找到相同鍵 → 覆蓋值 / 拒絕加入 (Set)
           RETURN
   // 遍歷完未找到 → 新增節點到桶位
   ADD new Node(e, PRESENT) to bucket

效能啟示

• hashCode() 是效能關鍵：好的雜湊分佈 → 桶位元素少 → equals() 呼叫少 → O(1) 平均
• 劣質 hashCode() (如恆傳回 1) → 退化為鏈表 → O(n) 線性掃描
• 最佳實踐：使用 Objects.hash(fields...)、Arrays.hashCode()、或 IDE 自動產生

總結：正確使用 Set 的鐵律

1. 放入 Set 的物件類別必須同時覆寫 hashCode() 與 equals()
2. 兩者基於相同的業務關鍵欄位 (如 ID、唯一業務鍵)
3. 滿足契約：a.equals(b) → a.hashCode() == b.hashCode()
4. 欄位最好不可變，避免進入 Set 後修改導致找不到
5. String、包裝類、LocalDate 等 JDK 類別已正確實作，可直接放心使用