我在面试候选人时习惯先抛一个开放题“请说说 HashSet 是怎么去重的”十个有八个会回答“因为它重写了 equals 和 hashCode”。这个说法其实只对了一半——重写这两个方法是使用者的责任而不是 HashSet 自己重写的。更有意思的是哪怕你把这两个方法都写对了也照样可能在 Set 这个容器上栽跟头。这篇文章是站在“复习 实战”的角度把 Java 集合里的 Set 体系拆开揉碎。我会从底层结构讲起然后是去重机制、常见坑、面试追问链路、性能实测和选型建议一次把这块内容讲完。不管你是刚学 Java 的初学者还是准备跳槽的老手这篇文章都能给你一些能直接“抄作业”的东西。1. 复习之前先建立整体认知Set 三兄弟的真实分工1.1 一个最容易被忽略的起点Set 本身就是 Map 的“马甲”很多人学 Set 是跟 List 对比着记的List 有序可重复Set 无序不可重复。这个对比本身没错但对理解内部实现帮助不大。等你真正翻开 HashSet、LinkedHashSet、TreeSet 的源码会发现一个惊人的事实这三个 Set 实现类底层全都是 Map。HashSet 内部持有一个HashMapE, ObjectLinkedHashSet 继承自 HashSet内部实际用的是LinkedHashMapTreeSet 内部则是一个TreeMapE, Object。这条认知一旦建立很多平时记不住的问题就自然通了为什么 HashSet 允许 null因为 HashMap 允许 null key。为什么 HashSet 不保证顺序因为 HashMap 的桶位置由 hash 值决定扩容之后还会重新散列。为什么 LinkedHashSet 能保持插入顺序因为 LinkedHashMap 额外维护了一条双向链表。为什么 TreeSet 元素是有序的因为 TreeMap 本身就是红黑树按 key 的比较结果排序。所以复习 Set 的时候一定要先切换到这个视角你不是在看一套独立的容器你是在看 Map 的“换皮版本”。Set 元素只是 Map 的 keyvalue 统一是一个占位对象。1.2 HashSet、LinkedHashSet、TreeSet 的差异锚点下面这张表是我自己复习时常用的“差异锚点”把三个实现类的关键维度放在一起对比比单读文档清楚得多。对比维度HashSetLinkedHashSetTreeSet底层结构HashMapLinkedHashMapTreeMap红黑树是否允许 null允许允许默认不允许见 5.1元素顺序不保证可能变化按插入顺序按自然顺序或 Comparator时间复杂度平均 O(1)平均 O(1)O(log n)适用场景高频去重、判重需要稳定顺序的去重有序元素、范围查询记住一个关键差异HashSet 系的性能靠的是哈希TreeSet 的性能靠的是比较。哈希一般比比较快所以绝大多数场景下HashSet 都是默认选择。1.3 从源码层验证HashSet 怎样用 HashMap 实现我直接贴一段精简过的 HashSet 源码你看完就明白我说的“马甲”是什么意思了public class HashSetE extends AbstractSetE implements SetE { // 底层就是一个 HashMap private transient HashMapE, Object map; // 所有 value 共用一个占位对象 private static final Object PRESENT new Object(); public HashSet() { map new HashMap(); } public boolean add(E e) { // 第一次 put 返回 null说明原来没有返回 true // 如果原来已经有相同 keyput 会返回旧 valuePRESENT返回 false 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; } }注意add为什么返回 boolean因为底层put返回的是“同 key 之前的旧 value”。第一次放入时旧值为 null所以返回 true重复放入时旧值是 PRESENT所以返回 false。这个返回值是你用add判断是否重复的最直接手段。LinkedHashSet 的初始化很有意思它走的是 HashSet 一个 package-private 构造器专门用来把底层 map 换成 LinkedHashMappublic class LinkedHashSetE extends HashSetE { public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); // true 表示用 LinkedHashMap } }2. 去重机制深挖hashCode 与 equals 如何决定元素是否“重复”2.1 一次 add 操作在后端 HashMap 里的完整路径这是整个 Set 体系最核心的机制我必须把一条完整的调用链走给你看。假设有一个User对象要放进 HashSet调用user.hashCode()得到一个 int 值HashMap 内部做一次扰动处理降低碰撞概率hash key.hashCode() ^ (key.hashCode() 16)用扰动后的 hash 与数组长度做与运算(n - 1) hash定位到具体的桶桶是空的直接放入add 返回 true桶不为空顺着链表或红黑树查找先比较 hash 值hash 不等直接跳过hash 相等再调用equals做精确认证如果找到相等的 key用新 value 替换旧 valuemap.put返回旧 valueHashSet 的 add 返回 false。一句话总结就是hashCode 负责“快速定位”equals 负责“最终确认”。两个对象只有 hash 相等且 equals 为 true才会被判定为“重复”。2.2 hashCode 和 equals 的约定关系这两者的关系是 Java 面试里最经典的基础题但它背后藏着一个经常被误解的方向。正确的约定是如果两个对象equals为 true那么它们的hashCode必须相等如果两个对象hashCode相等equals不一定为 true如果两个对象hashCode不相等那么equals必然为 false。很多人只记住了“先比 hashCode 再比 equals”但对“equals 相等时 hashCode 必须相等”这条理解不深。这条约定的原因其实很直观HashMap 需要通过 hashCode 把对象快速定位到同一个桶里如果 equals 相等但 hashCode 不同两个“内容相同”的对象就会被分配进不同桶HashSet 里就会同时出现两个逻辑上重复的元素去重失效。2.3 实战案例User 去重成功与失败的内存表现我用一个真实感很强的例子来讲。假设现在有一个User类业务上规定“id 相同就算同一个用户”class User { private Integer id; private String name; public User(Integer id, String name) { this.id id; this.name name; } Override public boolean equals(Object o) { if (this o) return true; if (!(o instanceof User)) return false; User user (User) o; return Objects.equals(id, user.id); } Override public int hashCode() { return Objects.hash(id); } }测试一下HashSetUser set new HashSet(); set.add(new User(1, 张三)); set.add(new User(1, 李四)); System.out.println(set.size()); // 输出 1因为两个 User 的 id 都是 1equals 为 truehashCode 也相等所以被 HashSet 判定为重复元素最终只保留一个。这个行为符合预期。现在把hashCode()方法注释掉再跑一次输出就会变成 2。这就是“只重写 equals 不重写 hashCode”导致去重失效的典型症状。我在评审代码时这种 bug 见的频率相当高。注意Objects.hash(id)这种写法虽然省事但底层会创建数组并逐个计算频繁调用时会有一定开销。如果元素数量巨大可以考虑自己手写基于数字字段的散列算法比如31 * id这种经典模式。3. 我踩过的坑可变对象进 Set 之后“凭空消失”3.1 一个线上问题的现场还原从重复数据到内存泄漏有段时间我们系统里有个“按订单号去重”的组件实现方式是先把订单对象放入 HashSet再在后面做判重和清理。业务逻辑里有个很隐蔽的动作订单对象的状态字段会在处理过程中被修改。问题就来了。第一个订单进来size 是 1第二个订单号相同的订单进来居然没被判定为重复size 变成了 2。更诡异的是后面用contains去查第一个订单对象返回 false用remove删除也删不掉。内存里那个对象就像“幽灵”一样占着一个桶位但通过任何正常 API 都访问不到它。这种情况本质是一个内存泄漏因为 HashSet 强引用着这些永远无法被查到的对象。3.2 hashCode 漂移的完整链路解析这个问题的技术术语可以叫“hashCode 漂移”。完整链路是这样的对象 A 放入 HashSet当时它的状态值 hash 为 100被放进了桶 X外部业务逻辑修改了 A 的某个字段而这个字段参与了 hashCode 计算之后调用contains(A)此时重新计算 hashCode假设得到 200HashMap 顺着桶 Y 去找桶 Y 里自然没有 A于是 contains 返回 false但实际上 A 就在桶 X 里躺着只是没人去那里看它。这里的核心问题是HashSet 在元素放入那一刻就把桶位置定死了它没有“感知对象状态变化并迁移桶位”的机制。对象自己变了但容器里的索引没有跟着变整个对象就成了“信息孤岛”。3.3 修改了 Set 中元素状态后那些不可预测的行为结合上面那个案例我再补充几种更诡异的现象如果修改的是 equals 方法会读取的字段但 hashCode 没变那么会出现两个“当前状态已经不相等”的对象在 HashSet 里仍然被认为是重复的如果修改的是 hashCode 依赖的字段就会出现“查不到”和“删不掉”同时存在的状态如果 HashSet 扩容了原有的桶位置可能重新散列这个“幽灵对象”又会跟着迁移到新桶但仍然查不到。另外遍历 Set 时如果贸然用集合的remove方法还会撞上ConcurrentModificationException。原因是迭代器内部维护了一个 modCount 预期值集合结构一旦变化就会校验失败。正确做法是用迭代器自己的remove()或者遍历结束后统一删除。综合这些经验我的原则是凡是放进 Set / HashSet 的自定义对象要么设计成不可变类要么只允许用业务主键比如 id参与 hashCode 和 equals其他可变字段一概不碰。这样能从根上避开整个“哈希漂移”家族的问题。4. 日常开发里 Set 的正确打开方式与反模式4.1 给 List 去重三种写法与性能差异Set 最常用的场景就是把 List 去重。这里根据“是否需要保序”划分三种写法第一种不关心顺序ListString list Arrays.asList(a, b, a, c); ListString distinct new ArrayList(new HashSet(list));第二种需要保持原顺序ListString distinct new ArrayList(new LinkedHashSet(list));第三种Java 8 之后用 StreamListString distinct list.stream().distinct().collect(Collectors.toList());stream().distinct()底层走的是equals逻辑比较直接但它在并行流里的开销和去重效率并不算最优。实测下来如果数据量上了十万级LinkedHashSet的“构造 回填”写法通常比distinct()更快。原因是 LinkedHashSet 充分利用了哈希表的 O(1) 定位而 Stream 的 distinct 在串行流中是一个个元素走 concurrent 哈希逻辑机制上更重。如果你需要按对象某个字段去重用TreeSet加Comparator是个很讨巧的写法SetUser distinctUsers new TreeSet(Comparator.comparing(u - u.id)); distinctUsers.addAll(users);注意这种写法判断“重复”的标准变成了 Comparator 的返回值是否为 0而不是 equals。所以 TreeSet 里同时放“id 相同但 name 不同”的两个对象会被当成同一个元素处理。4.2 集合运算交集、差集、并集的一次性实现Set 在集合运算上的表达力是 List 完全比不了的。Java 直接给你提供了三个现成方法SetInteger a new HashSet(Arrays.asList(1, 2, 3, 4)); SetInteger b new HashSet(Arrays.asList(3, 4, 5, 6)); // 交集 a.retainAll(b); // a 变成 [3, 4] // 差集 a.removeAll(b); // a 变成 [1, 2] // 并集 a.addAll(b); // a 变成 [1, 2, 3, 4, 5, 6]这里有一个必须强调的细节这三个方法都会直接修改调用者集合。如果不想破坏原集合先复制一份再操作。比如SetInteger temp new HashSet(a); temp.retainAll(b); // temp 是交集结果a 和 b 都原封不动4.3 反模式预警什么时候不该用 SetSet 不是万能的下面这些场景用它就是给自己埋雷需要按下标访问元素Set 没有get(index)的概念只能遍历。如果你既要快速判重又要随机访问应该考虑LinkedHashSet转 List或者直接用LinkedHashMap做辅助索引需要存储重复数据这不用解释语义上就冲突元素数量巨大但根本没有去重需求哈希结构有额外内存开销纯存储用ArrayList更经济依赖元素顺序且顺序会频繁变化Set 的有序实现TreeSet、LinkedHashSet各有各的限制一个按排序规则走一个锁定插入顺序想自由调整顺序还是用 List。写代码前先问一句我到底是要“去重”“判重”还是“有序遍历”想清楚这个选型基本就错不了。5. 面试追问链路从 HashSet 到 HashMap 再到红黑树5.1 为什么 HashSet 允许 null而 TreeSet 不允许这是面试里很常见的对比问题。先说 HashSet它的底层是 HashMap而 HashMap 对 null key 做了特殊处理。在计算 hash 时null 的 hash 值被硬编码为 0static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }所以 null 会落到数组的 0 号桶单例 null 元素完全可以正常存取。TreeSet 就不一样了。它的底层 TreeMap 是红黑树任何一次插入和查找都要走比较逻辑而默认的null.compareTo(...)调用会直接抛出 NullPointerException。所以 TreeSet 不允许 null 是结构决定的不是设计者拍脑袋定的。5.2 TreeSet 的排序与 Comparable / Comparator 的配合TreeSet 排序有两种来源元素类实现Comparable接口提供“自然排序”TreeSet 构造时传入Comparator由外部定义比较规则。两者同时存在时Comparator优先。绝大多数情况下我更推荐传Comparator。原因有两个第一比较规则经常随业务变化写死在实体类里不灵活第二Comparator.comparingInt(...)这种链式写法比手写 compareTo 简洁得多也不容易出错。举个例子按字符串长度排序并去重TreeSetString treeSet new TreeSet(Comparator.comparingInt(String::length)); treeSet.add(java); treeSet.add(集合); treeSet.add(set); System.out.println(treeSet); // 输出按长度升序排列的集合这里有个容易忽略的坑如果两个字符串长度相等Comparator 返回 0TreeSet 就会把它们当成“同一个元素”。比如“java”和“code”长度都是 4后者就无法加入。这种判定标准跟 equals 完全无关业务上如果出现“长度不同内容相同”的数据TreeSet 的去重语义会跟你开个大玩笑。5.3 追问到底层Java 8 之后桶内红黑树与查询复杂度面试官问你“HashSet 的时间复杂度是 O(1)”这只是一个“平均”答案。真想答得漂亮你要知道 Java 8 之后 HashMap 在极端情况下的优化当链表长度超过 8且数组长度不小于 64 时链表会转成红黑树红黑树的查询时间复杂度是 O(log n)于是 HashSet 的最坏情况从 O(n) 降到了 O(log n)如果 hashCode 设计得很差比如所有对象都返回 1所有元素会挤在同一个桶里HashSet 就会退化成一棵“定制的树”性能远低于正常水平。这个问题最好的展开方式是“反例”如果一个对象的 hashCode 恒为 1HashSet 还能正常工作吗能但插入十万个元素的时间会从几十毫秒恶化到几百毫秒甚至更多。所以 hashCode 的散列质量直接决定 HashSet 的性能上限。6. 性能实测与选型建议别靠感觉用数据说话6.1 十万级元素插入与判重一次简单测试记录为了不让“性能”停留在嘴上我自己写过一个非常简单的基准测试向三种 Set 中分别插入 10 万个随机字符串然后做 10 万次 contains 判重。环境是普通笔记本电脑、JDK 17不搞 JMH 那种严格基准但相对趋势是有参考价值的。操作HashSetLinkedHashSetTreeSet插入 10 万元素最快略慢于 HashSet明显慢一截contains 判重 10 万次最快接近 HashSet最慢内存占用最低多了链表指针略高树节点开销最大结论不意外HashSet 全面占优。LinkedHashSet 因为多维护一条双向链表插入时多一次指针操作但差距不大。TreeSet 每次插入都要进行红黑树旋转和比较数据量一上来差距就非常明显。所以没有特殊需求默认选 HashSet。6.2 按业务场景选型的决策表我把自己的选型习惯整理成一张表你以后可以直接对照业务场景推荐实现核心原因去重不关心顺序HashSet性能最好去重要求保持插入顺序LinkedHashSet链表记录插入序需要有序遍历 / 范围查询TreeSet红黑树天然有序元素全是枚举类型EnumSet位向量实现极快且省内存需要不可变集合Set.of()安全、不可修改多线程并发访问的高频读写ConcurrentHashMap.newKeySet()分段锁/无锁读比同步 Set 更好6.3 几个容易被忽略的 Set 周边 API最后补充几个日常用得上但容易被忽略的 APISet.copyOf(collection)Java 10 引入返回不可变 Set元素必须非 nullCollections.newSetFromMap(new ConcurrentHashMap())得到一个基于 ConcurrentHashMap 的并发 SetConcurrentHashMap.newKeySet()Java 8 引入语义同上但写法更直接Set.of(...)创建不可变 Set如果传入重复元素会直接抛出IllegalArgumentException这其实是好事能在运行早期暴露问题。注意Set.of()和Set.copyOf()返回的不可变集合在 add 或 remove 时会抛UnsupportedOperationException。如果你拿到一个“能正常初始化”的 Set下意识以为可以改这一步最容易翻车。最后再分享一个我个人的实操习惯凡是要放进 Set 的自定义对象第一件事就是把它设计成不可变的至少保证参与 hashCode 和 equals 的字段是业务主键。这个习惯帮我避开了“元素凭空消失”、内存泄漏、并发修改异常这一整串问题。Java 集合框架本身不复杂真正让它在生产环境里出问题的大多是“怎么用”的分寸而不是“它是谁”的知识。希望这篇复习笔记能帮你把 Set 这块彻底钉死。