HashSet 是最常用的去重集合。它基于 HashMap 实现，把元素作为 HashMap 的 key 存储，从而利用 key 唯一性保证元素不重复。

当你需要快速判断“某个元素是否出现过”，或者需要对数据去重时，HashSet 通常是首选。

1. 核心特点

特点	说明
元素唯一	不允许重复元素
基于 HashMap	元素作为 key，value 是固定占位对象
允许一个 null	和 HashMap 的 null key 类似
不保证顺序	遍历顺序不等于插入顺序
平均操作快	add、contains、remove 平均 O(1)
非线程安全	并发写入需要额外同步

示例：

Set<Long> userIds = new HashSet<>();
userIds.add(1L);
userIds.add(1L);
userIds.add(2L);

System.out.println(userIds.size()); // 2

2. 底层结构

HashSet 内部持有一个 HashMap。

HashSet
┌────────────────────────┐
│ map: HashMap<E,Object> │
└───────────┬────────────┘
            ▼
HashMap
key = 元素
value = PRESENT 固定对象

概念化代码：

private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();

添加元素：

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

HashMap key 不重复，所以 HashSet 元素不重复。

3. add 流程

set.add(element)
  │
  ▼
以 element 为 key 放入 HashMap
  │
  ├─ key 不存在：插入，返回 true
  └─ key 已存在：覆盖占位值，返回 false

示例：

Set<String> set = new HashSet<>();
System.out.println(set.add("A")); // true
System.out.println(set.add("A")); // false

第二次返回 false，表示集合没有发生变化。

4. contains 流程

set.contains(element);

本质：

map.containsKey(element);

查找过程与 HashMap 查 key 一样：

计算 hash
  │
  ▼
定位桶
  │
  ▼
比较 hash 和 equals

所以自定义对象放入 HashSet 时，必须正确实现 equals 和 hashCode。

5. equals/hashCode 决定去重语义

示例：

public class User {
    private Long id;
    private String name;
}

如果没有重写 equals/hashCode：

Set<User> users = new HashSet<>();
users.add(new User(1L, "Tom"));
users.add(new User(1L, "Tom"));

System.out.println(users.size()); // 可能是 2

因为默认按对象引用判断相等。

如果业务语义是“id 相同就是同一个用户”，应按 id 重写：

@Override
public boolean equals(Object obj) {
    if (this == obj) {
        return true;
    }
    if (!(obj instanceof User other)) {
        return false;
    }
    return Objects.equals(id, other.id);
}

@Override
public int hashCode() {
    return Objects.hash(id);
}

6. 可变对象风险

不要修改已放入 HashSet 的对象中参与 hashCode 的字段。

User user = new User(1L, "Tom");
Set<User> users = new HashSet<>();
users.add(user);

user.setId(2L);
System.out.println(users.contains(user)); // 可能是 false

过程：

add 时：id=1 -> 桶 A
修改后：id=2 -> 查找桶 B
对象仍在桶 A，contains 失败

Set 中元素最好是不可变对象，或者至少不要修改参与相等判断的字段。

7. 遍历顺序

HashSet 不保证遍历顺序：

Set<Integer> set = new HashSet<>();
set.add(3);
set.add(1);
set.add(2);

System.out.println(set); // 不要依赖输出顺序

如果需要保留插入顺序：

Set<Integer> set = new LinkedHashSet<>();

如果需要排序：

Set<Integer> set = new TreeSet<>();

8. HashSet、LinkedHashSet、TreeSet

实现	底层	顺序	复杂度	适合场景
HashSet	HashMap	不保证	平均 O(1)	快速去重
LinkedHashSet	LinkedHashMap	插入顺序	平均 O(1)	去重并保留顺序
TreeSet	TreeMap	排序	O(log n)	去重并排序

选择原则：

只要去重 -> HashSet
去重且保留输入顺序 -> LinkedHashSet
去重且排序/范围查询 -> TreeSet

9. HashSet 与 List 去重

常见写法：

List<Long> userIds = List.of(3L, 1L, 3L, 2L);
Set<Long> set = new HashSet<>(userIds);

如果还要保留原顺序：

Set<Long> set = new LinkedHashSet<>(userIds);
List<Long> result = new ArrayList<>(set);

结果：

输入：[3, 1, 3, 2]
输出：[3, 1, 2]

10. 容量设置

如果预计元素数量较大，可以指定初始容量：

Set<Long> set = new HashSet<>(expectedSize * 4 / 3 + 1);

原因是底层 HashMap 默认负载因子是 0.75。预估容量可以减少扩容。

11. 线程安全

HashSet 不是线程安全的。

简单同步包装：

Set<String> set = Collections.synchronizedSet(new HashSet<>());

并发场景更常见选择：

Set<String> set = ConcurrentHashMap.newKeySet();

这会创建基于 ConcurrentHashMap 的并发 Set。

12. 常见使用场景

场景	示例
去重	用户 ID 去重
判断存在	黑名单、白名单
差集	找出未处理 ID
交集	找共同标签
防重复处理	已消费消息 ID

交集：

Set<Long> a = new HashSet<>(List.of(1L, 2L, 3L));
Set<Long> b = new HashSet<>(List.of(2L, 3L, 4L));

a.retainAll(b);
System.out.println(a); // [2, 3]，顺序不保证

差集：

a.removeAll(b);

并集：

a.addAll(b);

Tips 快问快答

Q：HashSet 底层是什么？ A：底层是 HashMap，元素作为 key。

Q：HashSet 的 value 是什么？ A：一个固定的占位对象，业务上不关心。

Q：HashSet 怎么判断重复？ A：依赖元素的 hashCode 和 equals。

Q：为什么两个内容相同的对象都进了 Set？ A：通常是没有按业务字段正确重写 equals/hashCode。

Q：HashSet 有序吗？ A：不保证顺序。需要插入顺序用 LinkedHashSet，需要排序用 TreeSet。

Q：HashSet 可以放 null 吗？ A：可以放一个 null。

Q：修改 Set 中对象字段有风险吗？ A：有。如果字段参与 hashCode/equals，修改后可能导致找不到该元素。

Q：HashSet 操作一定是 O(1) 吗？ A：平均接近 O(1)，冲突严重时会变慢。

Q：并发 Set 怎么创建？ A：常用 ConcurrentHashMap.newKeySet()。

Q：List 去重并保留顺序怎么做？ A：使用 new LinkedHashSet<>(list)，再转回 List。