一、开场：同一张门票为什么不能重复入场

周末早上，游乐园刚开门，检票口已经排起长队。游客小李拿着编号为 VIP-1001 的电子票，工作人员核验后在入场名单上盖了一个章，小李顺利进入园区。

过了一会儿，又有人拿着一张内容完全相同的 VIP-1001 来检票。闸机没有因为“又来了一张票”就增加一条记录，而是亮起红灯：这个票号已经入过园，不能重复登记。

这份只记录唯一票号的入场名单，很像 Java 中的 HashSet：

• 每张门票是一个元素；
• 入场名单是一个 HashSet；
• add 是登记入场；
• contains 是查询是否来过；
• remove 是撤销登记；
• 相同门票不能出现两次；
• 名单只关心“有没有”，不负责记录第几个入场；
• 检票员根据票的哈希值先找登记区域，再用 equals 核对身份。

先记住本文的总纲：

HashSet 是一份只保留唯一元素的快速名单。hashCode 决定先去哪个登记区寻找，equals 决定找到的到底是不是同一张票。

本文以 Java SE 25 和 OpenJDK JDK 25 为背景。HashSet 的公开行为比较稳定，但底层 HashMap、桶、链表和红黑树属于当前实现细节，业务代码不应该依赖这些细节。

二、Set 解决什么问题，它和 List 有什么不同

如果我们用 ArrayList 保存所有扫码记录，同一张票扫两次，列表就会留下两条：

List<String> scanRecords = new ArrayList<>();
scanRecords.add("VIP-1001");
scanRecords.add("VIP-1001");

System.out.println(scanRecords);
// [VIP-1001, VIP-1001]

Set<String> admitted = new HashSet<>();
admitted.add("VIP-1001");
admitted.add("VIP-1001");

System.out.println(admitted.size());
// 1

List 和 Set 不是谁淘汰谁，它们解决的问题不同：

对比项	List	Set
核心问题	按顺序保存一串数据	保存一组不重复的数据
重复元素	允许	不允许
下标	有，例如 get(0)	没有
顺序	List 接口有明确的顺序语义	取决于具体实现
常见实现	ArrayList、LinkedList	HashSet、LinkedHashSet、TreeSet
生活类比	每一次扫码流水	已经入园的唯一名单

如果需求是“记录游客每一次进出闸机的流水”，应该选 List；如果需求是“判断某张票今天是否已经使用”，Set 更贴切：

• 关心发生了几次、先后顺序：List；
• 只关心有没有、要去重：Set；
• 还要根据编号找到额外信息：Map。

三、add、contains、remove：别忽略返回值

HashSet 方法不多，但布尔返回值很有用：

Set<String> admitted = new HashSet<>();

boolean first = admitted.add("A001");   // true
boolean again = admitted.add("A001");   // false
boolean exists = admitted.contains("A001"); // true
boolean removed = admitted.remove("A001");  // true
boolean missing = admitted.remove("A999");  // false

System.out.println(first);
System.out.println(again);
System.out.println(exists);
System.out.println(removed);
System.out.println(missing);

// 在同一个业务流程中直接使用 add 的返回值
if (admitted.add(ticketNo)) {
    System.out.println("首次入园，闸机放行");
} else {
    System.out.println("门票已经使用，拒绝重复入园");
}

add 返回 true，表示集合真的发生了变化；返回 false，表示已经存在相等元素。检票业务完全可以利用这个结果。

没有必要先 contains，再 add。add 本身就会完成判重，还会告诉我们是否添加成功。先查后加不仅写得啰嗦，在并发场景里，两步操作之间还可能被其他线程插入数据。

remove 返回 false 也不是异常，只说明名单中没有这个元素。

四、HashSet 没有下标，也不保证遍历顺序

HashSet 不是“删除了重复项的 ArrayList”。它没有 get(0)，也没有“第一个添加的元素必须第一个输出”的承诺：

Set<String> rides = new HashSet<>();
rides.add("旋转木马");
rides.add("摩天轮");
rides.add("过山车");

for (String ride : rides) {
    System.out.println(ride);
}

rides.add(null);
rides.add(null);
System.out.println("size = " + rides.size());

// 错误思路：依赖 toString 的顺序
assert set.toString().equals("[A, B, C]");

// 正确思路：验证元素和数量
assert set.size() == 3;
assert set.containsAll(Set.of("A", "B", "C"));

HashSet 允许一个 null。第二次添加 null 会被视为重复，不会增加 size。但别把“HashSet 允许 null”错误推广到所有 Set：例如 Set.of(...) 不接受 null，ConcurrentHashMap.newKeySet() 也不接受 null。

不要根据一次输出推断顺序。换一批元素、改变容量或升级 JDK 后，顺序都可能变化。看起来稳定不等于 API 保证稳定。

测试 HashSet 时应该验证元素和数量，不能依赖 toString() 恰好呈现出的顺序。

如果业务确实要求保持插入顺序，使用 LinkedHashSet；如果要求按照自然顺序或比较器排序，使用 TreeSet。容器名字不是装饰，它表达的是不同契约。

五、HashSet 为什么能去重：它把元素放进了 HashMap 的 Key

在当前 OpenJDK JDK 25 实现中，HashSet 内部维护了一个 HashMap。集合元素作为 Map 的 Key，所有 Key 共用一个无业务意义的占位 Value：

public class HashSet<E> extends AbstractSet<E> {
    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 本来就不能重复：当新 Key 与旧 Key 相等时，put 更新的是同一个映射，而不是再创建一份 Key。HashSet 正好借用了这个能力。它不需要保存票价、游客地址等额外 Value，于是统一放入 PRESENT 占位对象。

可以把内部结构想成下面这样：

HashSet
  └─ HashMap
       ├─ Key = "A001"  → Value = PRESENT
       ├─ Key = "A002"  → Value = PRESENT
       └─ Key = "A003"  → Value = PRESENT

这里需要分清两层知识：

• HashSet 不允许重复、允许一个 null、不保证迭代顺序，是公开 API 描述；
• 使用 HashMap、共享 PRESENT，是当前 OpenJDK 的实现方式。

阅读源码可以借助实现理解原理，但业务代码应依赖公开契约。

六、add、contains、remove 的精简源码路径

有了“元素就是 Map 的 Key”这个认识，HashSet 的几个方法就很容易理解：

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

public boolean contains(Object o) {
    return map.containsKey(o);
}

public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

添加 A001 时，大致会经历：

1. 取得 A001 的 hashCode；
2. HashMap 对哈希值做扰动，让高位信息也参与定位；
3. 根据数组长度计算桶位置；
4. 桶为空就直接放入；
5. 桶不为空则比较哈希值，再调用 equals；
6. 找到相等 Key 就判定重复，否则继续处理冲突；
7. 必要时扩容并重新分布节点。

contains 和 remove 也走类似定位路径。因此 HashSet 的“快”来自哈希定位，而不是它把所有元素从头到尾比较一遍。

Oracle Java SE 25 文档说明：假设哈希函数能适当地分散元素，add、remove、contains 和 size 可以提供常数时间性能。如果所有门票都被分到一个窗口，再先进的大厅也会排成长队。

七、hashCode 先带路，equals 再验明正身

假设游乐园有 16 个登记窗口，票号计算后被引导到 5 号窗口。检票员不必翻完整本名单，只需查看 5 号窗口负责的记录。这就是 hashCode 的价值。

但是哈希值不是身份证号码，不同对象完全可能得到相同哈希值。所以到了窗口以后，还必须使用 equals 做最终确认。

自定义对象放进 HashSet 时，通常需要让 equals 和 hashCode 表达同一套业务身份：

import java.util.Objects;

public final class Ticket {
    private final String ticketNo;
    private final String visitorName;

    public Ticket(String ticketNo, String visitorName) {
        this.ticketNo = ticketNo;
        this.visitorName = visitorName;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Ticket that)) return false;
        return Objects.equals(ticketNo, that.ticketNo)
                && Objects.equals(visitorName, that.visitorName);
    }

    @Override
    public int hashCode() {
        return Objects.hash(ticketNo, visitorName);
    }
}

// 如果身份只是值组合，也可以改用更简洁的 record
record TicketValue(String ticketNo, String visitorName) {}

Set<TicketValue> tickets = new HashSet<>();
System.out.println(tickets.add(new TicketValue("V001", "小李"))); // true
System.out.println(tickets.add(new TicketValue("V001", "小李"))); // false
System.out.println(tickets.size()); // 1

最重要的规则是：

如果两个对象 equals 为 true，它们的 hashCode 必须相同。

反过来不成立：哈希值相同的两个对象，equals 可以是 false。这叫哈希冲突，是正常现象，不是程序出错。

只重写 equals、不重写 hashCode 会怎样？两张业务上相同的票可能被带到不同窗口，HashSet 没有机会让它们见面，最终错误地保留两份。只重写 hashCode、不重写 equals 也不能完成业务判重，因为到了同一个窗口以后，它们仍会被当作不同对象。

Java 的 record 很适合表达不可变值对象，它会根据组件生成匹配的 equals 和 hashCode，代码块中的 TicketValue 就是更精简的替代方案。

八、哈希冲突不等于重复：桶、链表和树

为了观察冲突，我们故意让所有对象返回相同哈希值：

record CollisionTicket(String ticketNo) {
    @Override
    public int hashCode() {
        return 7;
    }
}

Set<CollisionTicket> set = new HashSet<>();
set.add(new CollisionTicket("C001"));
set.add(new CollisionTicket("C002"));

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

虽然两个对象的哈希值都是 7，但票号不同，record 生成的 equals 会返回 false，所以它们都能进入集合。

在当前 JDK 25 的 HashMap 实现中，冲突节点会落在同一个桶中。桶内节点较少时使用链式结构；冲突足够多并满足容量条件时，可以树化为红黑树，以改善极端情况下的查询性能。常见源码常量包括树化阈值 8、退化阈值 6、允许树化的最小表容量 64。

这些数字适合帮助我们读懂 JDK 25 源码，却不属于 HashSet 的跨版本 API 承诺。面试中可以说明版本背景，业务代码不能写成“因为阈值永远是 8，所以我要依赖第 8 个元素触发某种行为”。

也不要让 hashCode 返回随机数，它会破坏同一对象多次计算的一致性。好的哈希实现应该：

• 相等对象产生相同哈希值；
• 对象用于判等的状态不变时，哈希值保持稳定；
• 尽量让不同对象均匀分散；
• 计算成本不过高。

九、最隐蔽的坑：修改元素后，它在名单里“失踪”了

游乐园把编号为 M001 的票登记在 5 号窗口。入园后，我们直接把这张票的编号改成 M999。再次查询时，系统根据新编号把我们带到 12 号窗口，当然找不到原来留在 5 号窗口的记录。

下面的代码能够稳定复现这个问题：

class MutableTicket {
    String ticketNo;

    MutableTicket(String ticketNo) {
        this.ticketNo = ticketNo;
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof MutableTicket that
                && Objects.equals(ticketNo, that.ticketNo);
    }

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

Set<MutableTicket> set = new HashSet<>();
MutableTicket ticket = new MutableTicket("M001");
set.add(ticket);

ticket.ticketNo = "M999";
System.out.println(set.contains(ticket)); // false
System.out.println(set.remove(ticket));   // false
System.out.println(set.size());           // 1

对象明明还占着集合的一个位置，却无法按新哈希值找到。继续添加它甚至可能让同一个对象引用出现在内部结构的不同位置，形成更混乱的状态。

Set 接口文档明确提醒：对象作为集合元素期间，如果修改了会影响 equals 比较的状态，其行为未定义。

解决思路按推荐程度排列：

1. 优先使用不可变对象，身份字段声明为 final；
2. 使用 record 表达不可变值；
3. 如果必须修改，先用旧状态从 Set 删除，修改后再重新加入；
4. 不要把频繁变化的展示字段纳入业务身份；
5. 数据库实体需要谨慎设计 equals/hashCode，尤其是保存前后才产生 ID 的对象。

一句话记忆：进 HashSet 的“身份证字段”要稳定。

十、遍历时删除：fail-fast 是报警器，不是并发锁

下面的增强 for 实际使用迭代器。循环过程中直接调用集合的 remove，会改变集合结构：

Set<String> rides =
        new HashSet<>(Set.of("过山车", "摩天轮", "碰碰车"));

for (String ride : rides) {
    if (ride.equals("摩天轮")) {
        rides.remove(ride); // 通常抛 ConcurrentModificationException
    }
}

// 正确：通过当前迭代器删除
Iterator<String> iterator = rides.iterator();
while (iterator.hasNext()) {
    String ride = iterator.next();
    if (ride.equals("摩天轮")) {
        iterator.remove();
    }
}

// 条件删除还可以写成：
rides.removeIf(ride -> ride.contains("车"));

正确方式之一是使用当前迭代器的 remove；单纯按条件删除时，还可以考虑 removeIf。

HashSet 迭代器是 fail-fast 的：创建迭代器以后，如果检测到集合被迭代器自身 remove 以外的方式结构性修改，会尽快抛出 ConcurrentModificationException。

但它只是帮助发现 Bug 的报警器，不是线程安全保证。JavaDoc 也强调，不能编写依赖这个异常来保证程序正确性的代码。多线程同时操作普通 HashSet 时，即使某次没有抛异常，也不代表数据安全。

十一、容量和负载因子：不是越大越快

默认构造器创建的 HashSet，其底层 HashMap 使用默认初始容量 16 和负载因子 0.75。注意，“初始容量 16”并不等于构造对象时立刻分配完整的 16 个桶，当前实现会延迟到首次添加元素时创建表。

当已用空间接近“容量 × 负载因子”时，HashMap 通常需要扩容。容量太小会频繁扩容；容量过大又会浪费空间，并拖慢遍历。

Java SE 25 HashSet 文档指出，遍历成本与“元素数量 + 底层 HashMap 容量”有关。也就是说，只放 10 个元素却预留百万级容量，遍历时可能为过多空桶付出代价。

JDK 25 可以用 HashSet.newHashSet(expectedElements) 按预期元素数创建集合：

HashSet<String> visitors = HashSet.newHashSet(10_000);

for (int i = 0; i < 10_000; i++) {
    visitors.add("V-" + i);
}

这里传入的是预计元素数量，比自己把 10,000 误当底层桶数量更直观。它会结合默认负载因子计算合适容量，减少装入预期数据期间的扩容。

数据量不大时，直接 new HashSet<>() 通常足够。只有批量导入且能较准确估算数量时，预设容量才更有价值。调优前先测量，不要把容量当成越大越好的“性能按钮”。

十二、HashSet、LinkedHashSet、TreeSet 和并发 Set 怎么选

常见 Set 的选择可以先看是否需要顺序：

需求	建议实现	主要特点
快速去重，不关心顺序	HashSet	常规首选
去重并保持插入顺序	LinkedHashSet	维护遇到元素的先后顺序
去重并自动排序	TreeSet	自然顺序或 Comparator
多线程高并发添加和查询	ConcurrentHashMap.newKeySet()	并发 Set
枚举值集合	EnumSet	针对枚举优化

示例：

Set<String> noOrder = new HashSet<>();
Set<String> insertionOrder = new LinkedHashSet<>();
Set<String> sorted = new TreeSet<>();
Set<String> concurrent = ConcurrentHashMap.newKeySet();

noOrder.add("B");
noOrder.add("A");

insertionOrder.add("B");
insertionOrder.add("A"); // 遍历顺序 B、A

sorted.add("B");
sorted.add("A");         // 遍历顺序 A、B

concurrent.add("A001");  // 支持并发更新，不接受 null

普通 HashSet 不是线程安全的。如果多线程共享并且至少一个线程会修改，可根据场景选择：

• 在创建时用 Collections.synchronizedSet(new HashSet<>()) 包装，并按文档要求在遍历时同步；
• 使用 ConcurrentHashMap.newKeySet() 获得适合并发读写的 Set；
• 更简单的办法是缩小共享范围，让每个线程使用自己的局部 Set，最后再合并。

不要因为看到了 ConcurrentModificationException 就认为“给普通 HashSet 捕获一下异常”可以解决并发问题。异常捕获修复不了丢数据、可见性和竞态条件。

十三、完整实验：游乐园入场名单

下面是一段可以直接使用 JDK 25 编译运行的完整小实验。它验证重复票、内容相等的对象、哈希冲突、可变对象陷阱和安全删除：

import java.util.*;

public class ParkAdmissionDemo {
    record Ticket(String no, String visitor) {}

    record CollisionTicket(String no) {
        @Override
        public int hashCode() {
            return 7;
        }
    }

    static final class MutableTicket {
        String no;

        MutableTicket(String no) {
            this.no = no;
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof MutableTicket that
                    && Objects.equals(no, that.no);
        }

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

    public static void main(String[] args) {
        Set<Ticket> admitted = new HashSet<>();
        System.out.println(admitted.add(new Ticket("A001", "小李")));
        System.out.println(admitted.add(new Ticket("A001", "小李")));
        System.out.println("唯一门票数：" + admitted.size());

        Set<CollisionTicket> collisions = new HashSet<>();
        collisions.add(new CollisionTicket("C001"));
        collisions.add(new CollisionTicket("C002"));
        System.out.println("冲突但不相等：" + collisions.size());

        Set<MutableTicket> mutableSet = new HashSet<>();
        MutableTicket mutable = new MutableTicket("M001");
        mutableSet.add(mutable);
        mutable.no = "M999";
        System.out.println("修改后能找到吗：" + mutableSet.contains(mutable));

        Set<String> rides =
                new HashSet<>(Set.of("过山车", "摩天轮", "碰碰车"));
        Iterator<String> iterator = rides.iterator();
        while (iterator.hasNext()) {
            if (iterator.next().equals("摩天轮")) {
                iterator.remove();
            }
        }
        System.out.println("安全删除后：" + rides);
    }
}

编译运行：

javac ParkAdmissionDemo.java
java ParkAdmissionDemo

预期的关键结果是：

• 第一次登记返回 true；
• 相同门票再次登记返回 false；
• 两个哈希值相同但内容不同的对象都能保留；
• 修改参与哈希计算的字段后，contains 返回 false；
• 使用 Iterator.remove 能完成安全删除。

十四、常见误区集中纠正

误区一：HashSet 完全无序，所以每次输出一定不同

“不保证顺序”不是“故意随机”。某次运行顺序可能稳定，但代码不能依赖它。

误区二：hashCode 相同就是同一个元素

哈希相同只代表可能落在同一位置，最终仍要通过 equals 判断。

误区三：只重写 equals 就够了

相等对象必须有相同哈希值，因此两者通常要成对重写。

误区四：把对象放进 HashSet 后可以随便改

普通字段可以根据业务谨慎修改；凡是参与 equals/hashCode 的身份字段，在对象留在 Set 期间应保持稳定。

误区五：初始容量越大性能越好

容量过大浪费内存，还可能增加遍历空桶的成本。按预期元素量合理设置即可。

误区六：fail-fast 能保证线程安全

它只能尽力暴露错误修改，不能代替同步或并发集合。

误区七：去重以后再转 List，顺序自然会保留

new ArrayList<>(new HashSet<>(source)) 不能保证保留原顺序。需要顺序去重时，可以使用 LinkedHashSet，或者使用 Stream 的 distinct 并理解流的有序性。

十五、总结口诀

最后用一组口诀收尾：

名单只留一份，HashSet 专管去重；
哈希先找窗口，equals 再认人物；
相等哈希必同，哈希相同未必重复；
没有下标保证，也别押注遍历顺序；
身份字段别乱改，否则原桶寻不出；
循环删除用迭代器，多线程换并发容器；
容量按需预估，实现细节不当契约。

HashSet 真正难的地方不在 add 会不会写，而在于能否正确回答三个问题：

1. 业务上什么才算“同一个元素”？
2. 参与 equals/hashCode 的字段在集合中是否稳定？
3. 需求到底需不需要顺序和线程安全？

想清楚这三个问题，HashSet 才会成为代码中简单、快速、可靠的唯一名单。

参考资料

1. Oracle Java SE 25：HashSet API
2. Oracle Java SE 25：Set API
3. Oracle Java SE 25：HashMap API
4. Oracle Java SE 25：ConcurrentHashMap API
5. OpenJDK JDK 25：HashSet.java
6. OpenJDK JDK 25：HashMap.java

本文完整示例使用 JDK 25 编译运行。源码片段为了突出主线进行了精简；具体桶结构、扩容和树化策略属于当前实现，实际开发应依赖公开 API，并以目标 JDK 版本源码和测试结果为准。

---

• 个人小游戏