Set 如何保证元素不重复的？

结论先行：不同 Set 实现靠不同机制判重。HashSet 把元素当作 HashMap 的 key，用 hashCode 定位桶、再用 equals 确认；TreeSet 靠 compareTo / Comparator 返回 0 判定重复；LinkedHashSet 继承 HashSet 并额外维护插入顺序；CopyOnWriteArraySet 则退化为 equals 线性扫描。核心契约只有一句：equals 相等的对象，hashCode 必须相等。

1. 一张表看全家族

2. HashSet.add 的真身

// HashSet 内部就是一个 HashMap，value 是全局共享的占位对象
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT) == null; // put 返回旧值，null 说明是新增
}

add("a") → map.put("a", PRESENT)
              │
              ├─ 桶为空 → 新建节点，返回 null → add 返回 true
              │
              └─ 桶中找到 equals 相同的 key
                     → 覆盖 value，返回旧 value（PRESENT）
                     → add 返回 false，size 不变

remove 同样委托给 map.remove(e) == PRESENT，contains 就是 map.containsKey(e)。所以 HashSet 的去重能力完全来自 HashMap 的键唯一性。

3. 两个条件缺一不可

• hashCode 不同：落到不同桶，equals 根本不会被调用，集合认为是两个不同元素。
• hashCode 相同：进入同一个桶，再逐个 equals 比较，相等则覆盖、不等则挂到链上。

只重写 equals 不重写 hashCode，两个“相等”的对象会落到不同桶，于是都被保留——去重直接失效。

4. 代码：不重写 hashCode 的后果

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class SetDemo {
    static class User {
        final String name;
        User(String name) { this.name = name; }

        @Override public boolean equals(Object o) {
            return o instanceof User && Objects.equals(name, ((User) o).name);
        }
        // 故意不重写 hashCode，继承 Object 的地址相关实现
    }

    public static void main(String[] args) {
        Set<User> users = new HashSet<>();
        users.add(new User("Tom"));
        users.add(new User("Tom"));
        System.out.println(users.size()); // 输出：2，去重失败

        Set<String> names = new HashSet<>();
        names.add("Tom");
        names.add(new String("Tom"));
        System.out.println(names.size()); // 输出：1，String 已正确实现两个方法
    }
}

5. TreeSet 的判重是“比较结果为 0”

• 元素必须实现 Comparable，或在构造时传入 Comparator，否则抛 ClassCastException。
• 只要 compareTo 返回 0 就视为重复，哪怕 equals 返回 false。
• 因此要求比较逻辑与 equals 保持一致，否则会出现“看起来不相等却被去重”的诡异现象。
• 自然排序下不接受 null；允许 null 需要自定义比较器。

import java.util.Set;
import java.util.TreeSet;

public class TreeSetDemo {
    public static void main(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("b");
        set.add("a");
        set.add("b");                 // compareTo 返回 0，被忽略
        System.out.println(set);      // 输出：[a, b]
        System.out.println(set.first()); // 输出：a
    }
}

6. 常见坑

• 可变对象入 Set 后修改参与 hash 的字段：hash 变了，contains 和 remove 都定位不到，元素变成“幽灵”，等价于内存泄漏。
• HashSet 允许一个 null 元素；TreeSet 自然排序下不允许。
• Set.of(...) 不可变，传入重复元素直接抛 IllegalArgumentException，不是静默去重。
• 用 stream().distinct() 去重，内部是 LinkedHashSet，会保留首次出现的顺序。
• 并发去重用 ConcurrentHashMap.newKeySet()，比 Collections.synchronizedSet 吞吐更好。
• 需要“去重 + 保留顺序”时选 LinkedHashSet，不要用 HashSet 再自己排序。

常见追问

• HashSet 的 value 为什么用同一个 Object？ 只关心 key，共享一个占位对象可以省内存，add 靠返回值是否为 null 判断新增。
• HashSet 的迭代顺序稳定吗？ 不保证，扩容会改变桶位，顺序随之变化。
• 如何按插入顺序去重？ LinkedHashSet；它通过 LinkedHashMap 的双向链表维护顺序。
• 为什么 Set 没有 get(int index)？ 没有下标语义，取元素只能迭代。
• equals / hashCode 的契约是什么？ 自反、对称、传递、一致；equals 相等则 hashCode 必须相等，反之不要求。
• HashSet 和 TreeSet 怎么选？ 只要去重且不在乎顺序用 HashSet；需要排序或范围查询用 TreeSet。

小结

Set 的去重不是“比较所有元素”，而是把判重下沉到 Map 的 key：哈希系靠 hashCode 找到桶、再用 equals 确认；树系靠比较器返回 0。记住两条硬规则——重写 equals 必须重写 hashCode；可变对象不要当 Set 元素。这样多数 Set 相关的追问都能顺势展开。