日常开发里只要一聊到集合去重HashSet、LinkedHashSet、TreeSet 这三位基本就是被拉出来对比得最多的对象。很多人背了八股文知道 HashSet 无序、LinkedHashSet 按插入序、TreeSet 能排序可真到了项目里选型还是会纠结这个场景用哪个换一个会不会更好为什么线上偶现遍历顺序不一样其实这几个 Set 的差别不只是“有序无序”这么简单背后连着的底层数据结构、性能特征、适用场景、甚至一些隐蔽的坑都值得彻底捋一遍。这篇文章我不打算复制 Javadoc也不准备搞那种“左边是区别表格、右边是背诵口诀”的速成教学。我就按实际使用经验来拆先看底层结构怎么设计再上手跑代码对比行为然后聊一些常见但容易被忽视的坑最后给出一套我个人项目里的选型建议。无论你是刚学集合框架的 Java 新人还是已经写了两三年 CRUD 想进阶的工程师这一篇基本能帮你把三个 Set 的账算清楚。1. 先搞懂三个 Set它们到底怎么存元素1.1 HashSet最简单的 Set背后站着 HashMapHashSet 的源码里其实没有太多自己的逻辑核心就是维护了一个 HashMap。你往 HashSet 里 add 一个元素底层实际上是在这个 HashMap 里放入一个键值对key 就是你添加的元素value 是一个被所有键共享的固定常量PRESENT。这个设计我觉得是整个 Set 系列理解成本最低的点集合判重本质上还是在用一个哈希表判断“这个 key 在不在”。知道了这一层很多行为就能顺藤摸瓜地理解。比如 HashSet 为什么不保证顺序因为底层 HashMap 决定桶位置的逻辑是基于 key 的 hashCode 计算出数组下标再结合容量、负载因子算出来的。你看到的结果就是元素在“桶数组”里的分布跟插入先后没有关系。这里要注意网上很多人说 HashSet 完全随机排列这个说法其实不准确。它是确定性的同一个 JVM、同一组元素、没有发生扩容连续遍历输出顺序是稳定一致的。但你不能依赖这个顺序因为只要换一个初始容量、负载因子或者元素 hash 值发生变化输出就完全另一副面孔了。源码里另一个容易被忽略的点是它内部的DEFAULT_INITIAL_CAPACITY是 16DEFAULT_LOAD_FACTOR是 0.75。平时不管是因为量小感觉不到但如果你往 HashSet 里塞了上百万条数据频繁扩容会导致性能肉眼可见地下降。扩容不只是数组拷来拷去而是所有元素要重新计算下标重新分布这个开销非常可观。1.2 LinkedHashSetHashSet 加了一条隐形的链子LinkedHashSet 继承自 HashSet但它重写了内部的构造逻辑实际用的是 LinkedHashMap。你可以把它理解成在 HashSet 的哈希表结构之上额外串了一条双向链表这条链表专门用来维护元素的插入顺序。所以 LinkedHashSet 的“有序”和 TreeSet 的“有序”是两种完全不同的概念。LinkedHashSet 保证的只是“迭代顺序等于元素第一次被加入时的顺序”也就是 insertion order。如果一个元素被重复添加重复操作不会让它再移动位置迭代顺序依然以首次插入为准。这个特性在需要“保持原始顺序但又要去重”的业务里非常实用比如你解析一个配置列表后面可能把内容放到 Set 里做唯一性校验同时还要保证展示顺序和配置顺序一致这时候 LinkedHashSet 就是顺手的选择。代价就是多了一组前驱/后继指针和对应的链表维护逻辑。容量大了以后内存占用比 HashSet 高出一些插入性能也会因为要维护指针而有一点损耗。一般场景下这两者差距很小但不代表没有后面我用数据来验证。1.3 TreeSet有序背后的红黑树引擎TreeSet 的底层是 TreeMap严格说是基于红黑树实现的 NavigableMap。红黑树的核心特点就是自动维持平衡保证插入、删除、查找的时间复杂度都稳定在 O(log n)。因为用的是树结构TreeSet 的元素必须具有“可比性”。要么元素实现了 Comparable 接口要么你在创建 TreeSet 时显式传入 Comparator。这一点是三个 Set 里最容易编译期通过、运行期爆炸的地方。很多人第一次用 TreeSet直接 add 一个自定义对象代码没编译报错一运行就抛 ClassCastException原因就是对象根本没实现比较逻辑。TreeSet 还有个经常被忽略但很香的能力它实现了 NavigableSet提供了一系列范围操作。比如subSet(from, to)可以取出一个区间内的视图headSet(to)取小于某个值的所有元素tailSet(from)取大于等于某个值的元素还有pollFirst()、pollLast()这样的队列式方法。这些 API 在需要做排序集合、区间统计、排行榜截取等场景里能让代码简洁不少。2. 三步吃透核心区别顺序、性能、额外能力2.1 顺序保证从“无序”到“插入序”再到“排序序”这个问题虽然老生常谈但我觉得还是值得展开讲因为很多人对“无序”的理解有偏差。HashSet 的无序准确说是“哈希序”。元素最终落在哪个桶取决于 hashCode 的散列结果和当前哈希表的容量。比如同一批字符串在不同 JDK 版本里 hashCode 的实现可能都一样但如果你设置的初始容量不同输出顺序就可能不同。我之前遇到过一个很有意思的线上问题一组设备 ID 用 HashSet 做判重测试环境输出顺序一直是固定的结果上生产后顺序变了。查到最后发现是测试环境 JDK 版本和生产环境不一致导致 String 的 hashCode 对某些中文字符的散列结果不同桶位置全乱了。所以对 Hash 结构永远不要把遍历顺序当成一种保证。LinkedHashSet 的顺序刚才说过是插入序。这里要特别强调一点它的链表顺序只跟“成功插入”那一刻有关。如果一个元素已经在集合里你再重复添加一次这个元素的顺序不会变。另外 LinkedHashSet 的迭代顺序会严格反映插入的先后关系哪怕你中途删除了一个元素剩余元素的相对顺序也不会被打乱。TreeSet 则是真正意义上的“排序序”或者叫自然序。元素的迭代顺序和插入顺序没有半点关系完全由 Comparator 或 Comparable 决定。这意味着即使你先插入 100再插入 1最后插入 50遍历结果依然是 1、50、100。如果你需要的是一个“始终有序”的集合TreeSet 是唯一选择。2.2 性能与复杂度不同场景的时间成本对比三个 Set 的性能差异根本在于底层数据结构的复杂度不同。我简单做个对比表方便你对照理解实现类底层结构添加/删除/查找平均耗时是否维护额外顺序内存占用趋势HashSetHashMap数组 链表 红黑树O(1)否较低但需要扩容冗余LinkedHashSetLinkedHashMap哈希表 双向链表O(1)链表维护带来少量开销是插入序多一份链表指针开销TreeSetTreeMap红黑树O(log n)是排序序节点结构更重占用更高注意 HashSet 的 O(1) 是平均复杂度前提是哈希函数足够均匀。如果 hashCode 设计糟糕大量元素挤到同一个桶里链表长度越来越长性能就会退化为 O(n)JDK 8 之后链表长度超过 8 会转成红黑树退化上限变成 O(log n)。这件事在自定义对象上尤其容易踩坑。LinkedHashSet 理论上比 HashSet 慢一点因为每次插入除了写哈希表还要维护链表指针。实际测试下来百万级数据量差距在 10% 到 15% 左右。这个损耗对绝大多数业务可以忽略但如果你的代码在一个超高 QPS 路径上而且元素量很大就值得认真考虑。TreeSet 的 O(log n) 复杂度决定了它在大数据量下一定比哈希结构慢。日志量到几十万条时感受很明显因为红黑树的插入伴随着变色和旋转操作频率虽然不高但每一步都有额外计算。TreeSet 不要当“万能有序容器”来用该选的时候选能不用的时候尽量用别的方式。2.3 空值与自定义对象看起来小、踩坑多的差异先看官方的“字面行为”HashSet 和 LinkedHashSet 都允许传入一个 null。TreeSet 默认不允许任何 null 元素add 的时候会直接抛 NullPointerException。原因是 TreeSet 在插入时就要调用 compareTo 或者 Comparator 的 compare 方法进行定位而 null 没法参与比较一调用就撞上空指针。如果你确实需要在 TreeSet 里放 null也不能解决得漂亮——你必须写一个特殊的 Comparator让它允许 null 参与比较但在遍历和后续操作里又可能因为 null 导致各种诡异的判定。我个人建议是别在 TreeSet 里用 null老老实实过滤掉再放进去。自定义对象是最值得说的点。HashSet 和 LinkedHashSet 判断对象是否重复依据是hashCode()和equals()两个方法。很多人的实践误区是只重写 equals不重写 hashCode然后发现去重完全失效。原理在于 HashMap 在添加元素时先计算 key 的 hashCode 定位到桶再通过 equals 跟桶内已有元素做精确比较。如果两个对象 equals 相等但 hashCode 不同它们会落到不同桶里equals 根本没机会参与比较重复对象自然全部进入集合。正确做法是重写 equals 的同时一定要重写 hashCode并使用相同的关联字段建议用 JDK 7 之后的Objects.hash()来生成。TreeSet 的自定义对象判定逻辑则完全依赖 Comparator / Comparable 的返回值equals 和 hashCode 在这里不重要只要 compare 返回 0就认为两个对象相同后续那个元素不会加入。这里有个非常隐蔽的坑一个对象的 compare 结果和它的 equals 结果如果不一致会导致集合行为前后矛盾。最典型的就是用某个业务字段去排序但这个业务字段又不是唯一的结果两个明明 equals 不同的对象因为 compare 相等被判定成同一个。帮人排查代码时这个坑见得太多了。3. 实操对比把三个 Set 放到同一个考场里跑一遍3.1 基础行为验证代码演示光说不练假把式我习惯先写一段很短的代码把一个场景同时丢给三个 Set 去跑。下面这段代码在本地一跑输出结果能直接展示三者的行为差异import java.util.*; public class SetCompareDemo { public static void main(String[] args) { ListString list Arrays.asList(banana, apple, cherry, apple, durian); SetString hashSet new HashSet(); SetString linkedHashSet new LinkedHashSet(); SetString treeSet new TreeSet(); for (String s : list) { hashSet.add(s); linkedHashSet.add(s); treeSet.add(s); } System.out.println(HashSet: hashSet); System.out.println(LinkedHashSet: linkedHashSet); System.out.println(TreeSet: treeSet); } }我本地跑了一次输出大概是HashSet: [banana, apple, durian, cherry] LinkedHashSet: [banana, apple, cherry, durian] TreeSet: [apple, banana, cherry, durian]注意 HashSet 的输出顺序在不同环境、不同字符集下可能不一样String 的 hashCode 对英文单词在不同 JDK 版本之间是基本一致的所以这里看着稳定但千万别以为这是保证。LinkedHashSet 的输出就是把重复的 apple 去掉其他顺序保持插入序banana、apple、cherry、durian。TreeSet 则直接按字典序排好了。这个实验里有一个非常容易忽略的细节TreeSet 的去重逻辑和 LinkedHashSet、HashSet 完全不一样。TreeSet 去重靠的是 compare 结果而这组数据是英文字符串compare 刚好和 equals 的判断一致所以重复的 apple 也被去掉了。如果换成一堆名字相同但 ID 不同的对象TreeSet 可能把“本不该去重”的数据给吞了这是下一部分要展开讲的坑。3.2 自定义对象的去重差异实验接着再用一个自定义对象来测你会看到三个 Set 的行为差异比单纯字符串大得多。先看不重写任何方法的版本class User { String name; int age; User(String name, int age) { this.name name; this.age age; } Override public String toString() { return name : age; } }然后往三个 Set 里分别 add 两个内容相同但对象不同的 UserListUser users Arrays.asList(new User(张三, 20), new User(张三, 20)); System.out.println(new HashSet(users).size()); System.out.println(new LinkedHashSet(users).size()); System.out.println(new TreeSet(users).size());如果你对 HashSet 的判重机制理解正确就会知道上面这段代码是先编译通过的但 TreeSet 那行会直接抛 ClassCastException因为 User 没有实现 Comparable也没有 Comparator。这类运行期异常一般只有在测试环境跑到才会被揪出来所以网上教程通常建议用 TreeSet 时尽量给一个 Comparator避免依赖对象默认比较能力。正确的做法是两个方法都考虑进去。如果希望 User 在 HashSet 和 LinkedHashSet 里去重就重写 equals 和 hashCode如果还需要放进 TreeSet 按 age 排序就额外传入 Comparator。SetUser hashSet new HashSet(); SetUser linkedHashSet new LinkedHashSet(); SetUser treeSet new TreeSet(Comparator.comparingInt(u - u.age)); for (User u : users) { hashSet.add(u); linkedHashSet.add(u); treeSet.add(u); } System.out.println(hashSet.size()); // 2 System.out.println(linkedHashSet.size()); // 2 System.out.println(treeSet.size()); // 1这里 TreeSet 输出 1 很容易被忽略原因是两个 User 的 age 都是 20Comparator 认为它们“相同”后一个被丢弃。这个行为本身不算 bug但暴露了 TreeSet 判重的本质比较器结果相同 重复。如果你期望它按“对象整体内容”去重就必须在 Comparator 里把所有判定字段都加进去比如先用 age 比较再用 name 比较。3.3 TreeSet 的范围查询演示这是 TreeSet 区别于其他两个 Set 的“高光时刻”。有时候业务需要把一个区间内的数据筛选出来用 TreeSet 写起来非常顺手TreeSetInteger treeSet new TreeSet(); treeSet.add(30); treeSet.add(10); treeSet.add(50); treeSet.add(20); treeSet.add(40); System.out.println(treeSet.subSet(20, false, 50, true)); // [30, 40, 50] System.out.println(treeSet.headSet(30)); // [10, 20] System.out.println(treeSet.tailSet(30)); // [30, 40, 50] System.out.println(treeSet.first()); // 10 System.out.println(treeSet.last()); // 50 System.out.println(treeSet.pollFirst()); // 10 System.out.println(treeSet); // [20, 30, 40, 50]subSet支持布尔参数控制含不含边界headSet和tailSet同理。我做后台管理系统的数据看板时有一个需求是根据分数区间把用户分档原先用 List 排序再手动截取代码又长又容易漏边界改成 TreeSet 之后逻辑一下清楚很多。当然这只是演示不是让你把数据库查询结果全塞进 TreeSet 再筛选。数据量小可以用数据量大还是老老实实用 SQL 的 BETWEEN。3.4 LinkedHashSet 的访问序是假的别混淆网上有文章会把 LinkedHashMap 的 accessOrder 特性也“顺水推舟”地说成 LinkedHashSet 也有。这里可以负责任地提醒一句LinkedHashSet 不支持 accessOrder。你去翻源码会发现 LinkedHashSet 根本没有提供可以直接设置 accessOrder 的构造器它的构造器底层固定按插入序去创建 LinkedHashMap。想在 Java 里实现 LRU 缓存直接上 LinkedHashMap 或者 Caffeine别在 LinkedHashSet 上钻牛角尖。这个点挺冷门但面试偶尔会有陷阱题问 LinkedHashSet 能不能实现 LRU。你如果只知道 LinkedHashMap 能实现 LRU忍不住回答“LinkedHashSet 也可以”就掉坑了。4. 常见问题与排查技巧实录4.1 去重失效先查 hashCode 和 equals这个坑太多人踩了我单独拿出来讲。业务需求是“按订单号去重”于是建了一个 Order 类只重写了 equals没重写 hashCode结果线上出现大量重复订单提示。你如果也遇到这个问题优先去看自定义对象有没有同时实现这两个方法。我用一个简单的排查路径来说先把 Order 对象放进 HashSet之后调试时看 HashSet 的 table 数组。如果两个内容相同的对象出现在不同的桶里那就说明 hashCode 没有按预期返回相同值。再看对象的 hashCode 是否依赖了会变化的字段比如用了一个可变字段去生成 hashCode而集合里已经有元素时又改了那个字段那后面再去判重就全乱套了。日常最佳实践是重写 equals 的字段必须原封不动地用来生成 hashCode并且不要用可变字段做这些判重核心。推荐直接用Objects.hash(name, age)这种写法省得手写result 31 * result ...的低级错误。4.2 遍历顺序“飘忽不定”到底是不是 bug接到过类似线上反馈同一批数据第一次遍历顺序和第二次不一样怀疑代码有并发问题。其实绝大多数情况下不是 bug而是 HashSet 本身的扩散顺序在“捣乱”。比如第一次运行往 HashSet 里添加元素时发生了一次扩容第二次运行时你以为加载的数据一样但可能某个初始参数变了或者 JDK 内部对 String 哈希的随机种子发生了变化桶位置就全不一样。还有一种情况是有人在单元测试里断言了 HashSet 的遍历顺序测试偶尔过、偶尔挂。这就是典型的“哈希序不稳定”问题解决方法是把断言对象从 Set 改成 List或者用 LinkedHashSet 保持插入序又或者显式排序后再断言。别在测试里硬编码一个哈希结构的输出顺序那等于跟稻草人打架。4.3 LinkedHashSet 比 HashSet 慢数据量越大越明显我之前做百万级数据入库时顺手用 LinkedHashSet 做临时去重。当时觉得无非就是多维护一个顺序慢不了多少。结果跑完一看时间LinkedHashSet 比 HashSet 慢了 12% 左右。这个差距主要来自维护双向链表的指针操作每次插入都要多几次引用赋值。如果你的业务根本不关心插入顺序优先用 HashSet。不要总想着“反正差距不大”在数据量大、路径热、内存紧张的多重因素叠加下这点差距也会被放大。4.4 TreeSet 的 add 慢不代表它就是错的有人拿 TreeSet 和 HashSet 比插入性能比完得出结论 TreeSet 太慢弃用。这种对比其实没意义。红黑树的 O(log n) 再慢也比手动排序一个 List 再手动去重高效得多。遇到“需要持续保持有序”的场景TreeSet 是结构化地帮你解决问题不是做无意义的性能比拼。举一个实际例子网关做一些简单的规则引擎匹配规则按优先级排序规则会动态增删。用 List 加 Collections.sort 也能跑但是每次增删都要全量排序而 TreeSet 能在插入时就维护好整体顺序取首条规则直接first()就拿到了。复杂度的差异在这种“数据量小但操作频繁”的场景里尤其明显。4.5 线程安全三个 Set 默认都不安全HashSet、LinkedHashSet、TreeSet 都是非线程安全的。多线程环境下要么加锁要么使用并发容器。这里有一条实用的迁移路径原来的 HashSet 并发场景优先考虑ConcurrentHashMap.newKeySet()这个返回的就是一个支持并发读写的 Set实现方式也是基于 ConcurrentHashMap。原来的 TreeSet 并发场景可以用ConcurrentSkipListSet。它是基于跳表实现的并发有序 Setapi 和方法语义跟 TreeSet 很接近。不建议用 Collections.synchronizedSet 这种整锁方案因为锁粒度太大并发高时会把吞吐直接压下来。但如果只是低并发、代码改动成本要最低那也无所谓。5. 我的选型经验与几个容易忽略的细节5.1 按业务诉求决定不按“谁更高级”决定选型这事最怕的是盲目追新或者追求功能强大。我的习惯是先把业务需求拆成三个问题第一需不需要保持原始顺序不需要直接 HashSet又快又省内存。需要选 LinkedHashSet因为它能保留首次添加顺序常用于配置解析、缓存 key 保序等场景。第二需不需要“按值排序”需要优先考虑 TreeSet。比如排行榜、区间筛选、有序规则集合。不需要别碰 TreeSet因为它的结构成本和操作成本都更高。第三数据量大概多大对内存敏不敏感如果明确知道要去重几百万条数据且内存有限HashSet 是首选。如果数据量在几百条级别顺序又很重要LinkedHashSet 的性能劣势完全可以忽略。这三个问题过完答案基本就出来了。最忌讳的是“因为 TreeSet 更强所以用 TreeSet”这是把需求反过来了。5.2 给 HashSet 设置合适的初始容量这是一个写起来容易但很多人不做的优化。默认容量 16负载因子 0.75意味着容量到 12 就触发扩容。如果你要做十万级数据去重中间会扩容很多次虽然 final 结果是自动的但性能损耗是实打实的。初始化前如果能评估出元素量 N直接用new HashSet(N / 0.75 1)之类的公式来指定容量避免扩容。比如预计 100 万条数据初始容量可以设成100_0000 / 0.75 1也就是 133_3334 左右。这个细节在批处理任务里效果很明显。LinkedHashSet 也可以指定初始容量构造方法和 HashSet 类似。TreeSet 不需要关心这个东西因为红黑树是按需创建节点不存在“桶数组扩容”的概念。5.3 用可变对象做 Set 元素是隐患这个我之前吃过亏必须重点提。如果你把一个对象放进 HashSet之后再修改这个对象中参与 hashCode 计算的字段那么它在新 hash 下的桶位置和旧桶位置可能不一致结果就是这个对象存在于 Set 里但用 contains 方法查不到。TreeSet 也一样如果对象放进集合后影响排序的字段变了树结构不会自动重新调整位置。后续遍历顺序可能错乱甚至出现一些搜索操作找不到已经存在的元素。所以使用这些 Set 时能放不可变对象就放不可变对象。实在要用可变对象至少保证加入集合后不要修改参与 hashCode 或 compare 的字段。这是好多人都存在的技术债不爆则已一爆就是奇怪难查的线上问题。5.4 关于重复添加的一个冷知识很多人以为往 Set 里重复添加元素会“没反应”其实 add 方法会返回一个 boolean 值。如果元素已经存在add 返回 false并且集合内容不变。这个返回值在处理“第一次出现”的场景里很有用。我写过一段逻辑从日志里解析出用户 ID要统计哪些用户事件序列的首次出现时间。当时就用set.add(eventId)的返回值判断是不是第一次见到这个 ID是第一次才记录时间戳。比先contains再add少了一次哈希查找代码也更紧凑。5.5 面试角度如何用一句话讲清三者的关系如果只是应对面试可以这样表达HashSet 是基于哈希表的无序集合LinkedHashSet 在哈希表基础上增加了链表用于维护插入顺序TreeSet 基于红黑树实现元素按自然序或自定义比较器排序。但放到实际项目里还要补一句选择哪一个不取决于“哪个功能更多”而取决于业务必须满足的顺序和查询语义是什么。把这句话说出来面试官通常就能判断你是背过定义还是真正理解。6. 总结与个人实操心得写到这里基本把三者的底层原理、行为差异、使用场景和常见坑都过了一遍。最后说点我自己的习惯供你参考。最初几年我写代码一遇到去重就下意识用 HashSet追求“快”。后来有一次做运营后台的导入功能顾问要求“保留原始Excel顺序且不能有重复行”我第一版用 HashSet结果顺序乱了被测试逗了一下午。改成 LinkedHashSet 之后代码一行没多问题直接没了。从那以后我就记住了先想语义再选数据结构而不是反过来。TreeSet 我平时用得相对少但一旦用到就是“对上场景”的时候。比如紧急维护一个按到期时间排序的定时任务集合TreeSet 的 first() 可以帮我快速拿到最近到期的任务比我手动维护一个最小堆优雅不少。当然数据量上去了还是上延迟队列或者专门的任务调度组件但小规模的场景里它足够利落。另外一个小技巧是当你需要同时具备“去重”和“范围查询”能力时可以组合使用主集合用 HashSet 维护唯一性辅助用 TreeSet 维护有序视图。两个 Set 指向同一批对象写入时双写读取时按需选。这样虽然牺牲了一点写入开销但查询时两边都很快。不过这只适合读多写少的场景写多的就别这么折腾了。如果有条件建议自己打开 IDE把 HashSet、LinkedHashSet、TreeSet 的源码都点进去读一遍。不用全读懂重点看 add 方法、构造方法、以及它内部组合的 Map/树结构。读完之后你会发现网上那些零零碎碎的面试题突然之间变成了一个完整的图景。数据结构这种东西理解了底层才是真正记住了。