75. Set 与 HashSet、LinkedHashSet

Set 只干一件事：去重

Set 和 List 相反，它的铁律是不允许重复元素。你往里加两个「苹果」，它只留一个。

Set<String> set = new HashSet<>();
set.add("苹果");
set.add("苹果"); // 重复，被忽略
set.add("香蕉");
System.out.println(set.size()); // 2，不是 3
```bash

> [!NOTE]
> Set 不保证顺序。同样的代码多跑几次，打印出来的顺序可能不一样，这是哈希表的正常现象，不是 bug。如果你需要顺序，看后面要讲的 LinkedHashSet。

## 怎么算「重复」

这是初学者最容易栽跟头的地方。Set 判断两个元素是否「相同」，靠的是两条约定：

1. `hashCode()` 相等（哈希值一样）。
2. `equals()` 返回 `true`。

只有两条都满足，才认定是同一个元素、被去重。可以这么理解：先靠 `hashCode` 快速分到同一个「桶」，再用 `equals` 精确比对是不是同一个。

```java
// 两个内容相同的字符串，equals 和 hashCode 都一致
set.add(new String("hi"));
set.add(new String("hi")); // 仍被视为重复，只留一个

自定义对象要重写契约

如果你往 Set 里放自己写的类，却没重写 equals 和 hashCode，那 JVM 只会按「内存地址」判断。两个内容完全相同的对象，会被当成两个不同的人。

record User(String id, String name) {} // record 自动生成 equals/hashCode

Set<User> users = new HashSet<>();
users.add(new User("1", "张三"));
users.add(new User("1", "张三")); // record 判定为相同，去重成功
```bash

> [!WARNING]
> 把自定义对象放进 HashSet 前，务必保证 `equals` 和 `hashCode` 是基于「业务字段」重写的（用 `record` 或 IDE 生成最省心）。否则去重永远不生效，查 bug 能查到怀疑人生。注意：改了对象里参与 `equals`/`hashCode` 的字段后，再放进 HashSet 就等于「搬了家」却还记着旧地址，查找会失灵。

## HashSet 为什么快

HashSet 底层是哈希表（本质是数组 + 链表/红黑树的结合）。存元素时先算哈希值，直接定位到对应的「桶」，查找、插入、删除平均都是一步到位，速度和数据量几乎无关。

```java
Set<Integer> ids = new HashSet<>();
ids.add(1001);
ids.add(1002);
boolean has = ids.contains(1001); // 极快，哪怕集合里有十万个元素

正因为它靠哈希定位，元素在桶里的位置由哈希值决定，所以 HashSet 不保序——你加的顺序和遍历出来的顺序没关系。这是它和 List 最大的区别之一。

LinkedHashSet：记住插入顺序

如果你既想要 Set 的去重，又想遍历时按「加进去的先后」来，用 LinkedHashSet。它在 HashSet 基础上加了一条链表，把元素按插入顺序串起来。

Set<String> set = new LinkedHashSet<>();
set.add("甲");
set.add("乙");
set.add("丙");
System.out.println(set); // [甲, 乙, 丙]，顺序稳定
```bash

代价是：多维护一条链表，内存占用略高、插入略慢一点点。日常绝大多数场景用 HashSet 就够了，只有「需要按插入顺序展示」时才上 LinkedHashSet，比如记录用户最近浏览过的商品。

> [!TIP]
> 选型一句话：只去重、不在乎顺序 → `HashSet`；去重还想保插入顺序 → `LinkedHashSet`。不要为了顺序无脑用 LinkedHashSet，那点额外开销积少成多也是浪费。

## Set 的常用方法

Set 接口的方法比 List 少，因为不能按下标操作：

```java
set.add("x");        // 加，重复返回 false
set.remove("x");     // 删
set.contains("x");   // 是否包含
set.size();          // 个数
set.isEmpty();       // 是否为空
set.clear();         // 清空

遍历就一种增强 for（或迭代器），没有 get(i) 这种按索引的玩法：

for (String s : set) {
    System.out.println(s);
}
```bash

## 用 Set 给 List 去重

一个常见需求：把 List 里的重复项去掉。最省事的办法是丢进 HashSet 再出来：

```java
List<String> raw = List.of("a", "a", "b", "c", "b");
Set<String> dedup = new LinkedHashSet<>(raw); // 保顺序去重
System.out.println(dedup); // [a, b, c]

HashSet 和 HashMap 的关系

细心的你会发现，HashSet 和下一章的 HashMap 名字很像。这不是巧合：HashSet 的内部，其实就是拿一个 HashMap 来装，把元素当键、值统一塞一个空对象。所以 HashSet 为什么快、为什么不保序，都和 HashMap 的哈希表机制一脉相承。先在这里埋个伏笔，学 Map 时你会恍然大悟。

再强调一遍 equals 和 hashCode 的配套关系：重写了 equals，就必须重写 hashCode；两个相等的对象，hashCode 必须相等。这条契约不只 Set 用，Map 的键也用。违反它，集合就会出各种诡异的「明明一样却查不到」的 bug，而且极难排查。

如果你只想临时判断一批数据里有没有重复，甚至不需要真的建一个 Set 对象——直接拿 new HashSet<>(list).size() 和原 list 的 size 比一比，就能知道去重后会少几个。这是排查重复数据的一个小巧思。

去重和顺序怎么兼得

有人会问：去重同时排序，怎么办？答案不是在一个 Set 里硬撑，而是组合使用：先 new HashSet<>(list) 去重，拿到 Set 后再转成 List 交给 Collections.sort 排序（排序详见第 80 章）。或者干脆用 TreeSet 一步到位自动排序，代价是元素必须可比。两条路都行，看你是要「加完再排序」还是「边加边要序」。

HashSet 允许放一个 null 元素（因为 null 也能当哈希表的键），但 LinkedHashSet 和 TreeSet 对 null 的态度不同，TreeSet 直接拒绝 null。所以一旦你的数据可能出现 null，用 Set 前先想清楚要不要、能不能放 null，避免运行时才爆。

一句话收尾

去重用 Set，判重靠 equals 和 hashCode 两条约定，这俩必须配套重写。记不住就先用记录类 record，编译器帮你把契约写好，省得日后踩去重失效的坑。

小结

Set 的核心是去重，判定靠 equals + hashCode 两条约定；HashSet 基于哈希表、查找极快但不保序，是默认首选；LinkedHashSet 额外保住插入顺序。下一章看能自动排序的 TreeSet。