HashSet 如何保证元素不重复？

简化版

HashSet 内部就是一个 HashMap：你存的元素当作 Map 的 key，value 统一填一个固定的占位对象 PRESENT。所以「元素不重复」完全由 HashMap key 的去重规则决定——靠 hashCode 定位桶、equals 判等。

详细版

HashSet.add(e) 的本质是 map.put(e, PRESENT)：

private static final Object PRESENT = new Object();  // 所有 value 共用的哑对象
private transient HashMap<E, Object> map;

public boolean add(E e) {
    return map.put(e, PRESENT) == null;   // put 返回 null 说明是新 key，添加成功
}

HashMap 的 key 天生不重复：put 一个已存在的 key（hash 相同且 equals 为 true）只会覆盖 value、size 不增。反映到 Set 上就是「重复元素加不进去」，add 返回 false。

推论：自定义对象放进 HashSet，必须同时正确重写 equals 和 hashCode：

只重写 equals 不重写 hashCode → 两个「相等」的对象 hashCode 不同 → 落到不同桶 → Set 里出现「重复」元素；
只重写 hashCode 不重写 equals → 定位到同一个桶后无法判等 → 去重失效。

完整版教学

一、为什么用 Map 来实现 Set

这是个经典的「复用」设计：Set 的核心需求（去重 + 快速判断是否存在）恰好就是 Map key 的能力。Map 的 key 本来就不重复、本来就能 O(1) 判断存在与否。既然轮子已经有了，HashSet 就没必要再造一个哈希表，直接用 HashMap 当内部存储，元素当 key，value 拿个哑对象 PRESENT 占位即可。

同理，LinkedHashSet 内部是 LinkedHashMap（有序），TreeSet 内部是 TreeMap（排序）。JDK 的 Set 全家桶都是对应 Map 的「壳」。理解了这点，Set 的所有行为（去重规则、是否有序、能否放 null）都能从对应 Map 推出来。

二、去重的两步：hashCode 先、equals 后

HashSet 判断一个元素是否已存在，走的是 HashMap 的查找逻辑：

用元素的 hashCode() 算出桶下标——先定位到哪个桶；
在桶内用 equals() 逐个比对——再确认是不是同一个。

所以两个方法缺一不可。举个反例：

class Point {
    int x, y;
    // 只重写了 equals，没重写 hashCode
    public boolean equals(Object o) { /* 比 x,y */ }
}

Set<Point> set = new HashSet<>();
set.add(new Point(1, 1));
set.add(new Point(1, 1));   // 逻辑上重复，但 hashCode 不同 → 落不同桶 → 被当成新元素
System.out.println(set.size());  // 2！去重失败

两个「相等」的 Point 因为默认 hashCode 基于地址、各不相同，被分到不同桶，第二步 equals 根本没机会执行，于是重复元素混了进来。

三、可变元素的坑

和 HashMap key 一样，元素放进 HashSet 后，不要修改参与 equals/hashCode 的字段：

Set<User> set = new HashSet<>();
User u = new User(1, "a");
set.add(u);
u.setId(2);              // 改了参与 hashCode 的字段
set.contains(u);         // false！对象还在按 id=1 算的旧桶，却用新 hash 去查
set.remove(u);           // 也可能删不掉

对象仍留在旧桶，但新 hash 指向别的桶，于是「找不到、删不掉」，甚至一直占着内存造成泄漏。

记忆点：能作哈希 key/Set 元素的对象，参与相等判断的字段应当不可变（用 final）。这就是 String、包装类天生适合当元素的原因。

四、null、顺序和复杂度都从底层 Map 推导

HashSet 使用 HashMap，因此通常允许一个 null 元素：null 被作为 Map 的 null key 存放，多次 add(null) 仍只有一个。它不承诺迭代顺序，扩容或 JDK 实现变化都可能改变输出；若要求插入顺序用 LinkedHashSet，要求比较排序和范围视图用 TreeSet。

Set 实现	底层核心	顺序	平均增删查	null 边界
`HashSet`	`HashMap`	不保证	O(1)	通常允许一个
`LinkedHashSet`	`LinkedHashMap`	插入顺序	O(1)	通常允许一个
`TreeSet`	`TreeMap`/红黑树	比较顺序	O(log n)	取决于比较器，通常不接受
`CopyOnWriteArraySet`	写时复制列表	插入快照顺序	查找 O(n)	适合小型读多写少集合

“Set 不重复”也不是全世界统一的相等概念：HashSet 用 equals/hashCode，TreeSet 用 compare/compareTo 是否为 0。若两套契约不一致，同一批对象放入两种 Set 可能得到不同 size。

五、用测试验证相等契约

假设准备 1000 个业务 id，但每个 id 构造两份对象，正确实现 equals/hashCode 后放入 HashSet，最终 size 应为 1000；若只重写 equals 而保留身份 hash，size 可能接近 2000。这个测试能直接暴露相等对象被分到不同桶的问题。

User a = new User(42, "A");
User b = new User(42, "A");
assertTrue(a.equals(b));
assertEquals(a.hashCode(), b.hashCode());
assertEquals(1, new HashSet<>(List.of(a, b)).size());

测试还应覆盖字段修改边界。对象入 Set 后改变参与判等的字段，再调用 contains/remove 可能失败；这不是 Set 丢了对象，而是调用方改变了通往原桶的 hash 路径。

六、常见误区与追问

误区：HashSet 自己维护了一套独立哈希结构。 它把元素作为 HashMap key，value 统一使用 PRESENT 占位对象。
误区：只重写 equals 就能去重。 相等对象若 hashCode 不同会先落入不同桶，equals 没有比较机会。
误区：HashSet 的当前遍历顺序可以写进业务协议。 实现不承诺顺序，扩容和版本变化都可能打乱观察结果。
追问：add 为什么返回 boolean？ 底层 put 返回 null 表示此前没有等价 key，Set 据此返回是否真正新增。
追问：HashSet 能放几个 null？ 语义上只能一个，因为 null 作为同一个 Map key，后续添加被判为重复。
追问：为什么改元素字段后 remove 失败？ remove 用新 hash 去新桶查找，而节点仍挂在入集合时的旧桶。

记忆钩子：Set 的“重复”不是肉眼看起来一样，而是底层判等协议认为一样；协议和字段稳定性共同决定去重结果。

七、加强记忆

HashSet 是 HashMap 的薄封装：元素充当 key，PRESENT 充当统一 value，hashCode 先选桶、equals 再确认等价，因此两种方法必须基于同一组稳定字段。顺序、null 和复杂度也都能从底层 Map 推导；LinkedHashSet 保插入序，TreeSet 按比较结果去重。把对象加入哈希 Set 后不要改变参与判等的字段，并用容器级测试验证 equals/hashCode 契约。

简化版

详细版