聊到 Java 集合Set总是最容易被问到、也最容易被讲糊的一块。ArrayList大家多少都熟LinkedList背背书也能应付过去但一碰到HashSet、LinkedHashSet、TreeSet三兄弟很多人就会开始混乱到底哪个有序哪个能放null去重该用哪个面试官再追问一句“Set和List到底什么区别”回答往往就变成了“List有序Set无序”然后被一句“TreeSet不是有序吗”直接噎住。我最早学的时候也是靠背后来真正在项目里做过订单号去重、排行榜、操作记录保序这些需求才意识到这些选择根本不是记忆题而是由底层数据结构决定的。这篇文章就照着三个实现一层层拆开讲底层是什么、什么时候选谁、有哪些坑末尾再放几个我实际项目里直接用过的工具方法适合准备面试、做集合选型、或者想重新梳理 Java 集合体系的同学。1. 先把 Set 的行为模型立起来它和 List 的根本区别1.1 唯一性才是 Set 的身份证List和Set都是从Collection接口分化出来的但两者的“性格”完全不同。List允许重复元素并且每个元素都有下标你可以靠indexOf找位置也可以靠get(i)随机访问它的核心是“有序列表”。Set则是一个数学意义上的集合核心规则是“不允许重复”它不承诺你能用下标去访问元素也不保证元素之间的相对位置所有的设计都围绕唯一性展开。这个区别在 API 上最直观的体现就是add方法的返回值。List.add永远返回true因为列表不关心你是不是重复而Set.add如果加进去一个已经存在的元素会返回false并且不会改变集合内容。这个设计不是随意定的它就是Set整个语义的入口。后面我们看到的几乎所有去重逻辑都是靠这一层行为撑起来的。还有一个很多人忽略的点Set不是“一定乱序”而是“不保证顺序”。不同实现有不同策略HashSet不承诺、LinkedHashSet承诺插入顺序、TreeSet承诺按规则排序。所以面试时张口就说“Set 无序”是错的准确说法应该是“Set 的语义不依赖顺序顺序由具体实现决定”。1.2 三个实现三种秩序HashSet底层是哈希表所以它追求的是“快”遍历顺序不固定甚至同一个集合在扩容前后顺序都可能变化LinkedHashSet在哈希表基础上加了一条双向链表来记录插入顺序所以它既快又能保持“先来后到”TreeSet底层是一棵红黑树每次插入都按照比较器排序所以遍历出来永远是排好序的。三个实现的差异可以先用一张表看清楚实现底层结构遍历顺序能否放 null平均复杂度典型场景HashSetHashMap不保证允许一个 nulladd/remove/contains 都是 O(1)去重、白名单、快速判存在LinkedHashSetLinkedHashMap插入顺序允许一个 null绝大多数操作 O(1)有链表维护开销去重 保持原始顺序TreeSetTreeMap红黑树按比较器/自然顺序一般不允许add/remove/contains 都是 O(log n)自动排序、范围查询、排行榜这张表不是用来死记的它是后面所有选型判断的总纲。什么时候用哪个本质上就是看你要不要顺序、要哪种顺序、能接受多大的时间成本。1.3 理解 add 的返回值后续所有去重逻辑的起点很多人写去重代码时习惯if (!set.contains(x)) set.add(x)其实这个写法是多余的。Set.add自己就会判断重复并且返回 booleanSetString set new HashSet(); System.out.println(set.add(apple)); // true System.out.println(set.add(banana)); // true System.out.println(set.add(apple)); // false加不进去这个行为背后依赖的是元素的hashCode和equals。对HashSet来说先通过hashCode定位到桶再用equals在桶里比对对TreeSet来说则是通过Comparator或者Comparable.compareTo直接比较返回 0 就认为是同一个元素。搞懂这条链路很多诡异问题都能迎刃而解。2. HashSet最常用的去重容器底层其实是个 HashMap2.1 包装不是秘密HashSet 就是穿了马甲的 HashMapHashSet的源码其实很直白它内部维护了一个HashMap往HashSet里add的时候其实是把元素当作 key 放进HashMap而 value 统一用一个内部常量PRESENT占位。源码大概长这样private static final Object PRESENT new Object(); public boolean add(E e) { return map.put(e, PRESENT) null; } public boolean remove(Object o) { return map.remove(o) PRESENT; }map.put(e, PRESENT) null的意思是如果 key 之前不存在put返回 null说明这次 add 成功如果 key 已经存在put返回旧 value旧 value 就是PRESENT不是 null所以 add 返回 false。这段代码把“去重逻辑”直接复用了HashMap的键值唯一性所以说穿马甲并不夸张。既然底层是哈希表那就离不开两个参数初始容量和负载因子。默认初始容量是 16负载因子是 0.75意思是当元素个数超过16 * 0.75 12时哈希表就会扩容容量变成原来的两倍所有元素重新散列也就是 rehash。扩容本身是耗时的所以如果你提前能预估数据量就应该在创建的时候把容量设置好减少扩容次数。2.2 HashSet 的快建立在什么代价上HashSet的contains为什么快因为它是先算hashCode直接跳到对应的桶桶里顶多几个元素再用equals精确定位。这和ArrayList的线性扫描完全不同后者要一个个比过去数据量一上来差距非常明显。但这份快也有代价。哈希表本身是一张数组加链表/红黑树的结构每个节点除了存元素本身还要存哈希值、next 指针等信息内存占用比ArrayList高。而且如果你的元素hashCode写得烂大量元素撞到同一个桶里链表会变长查找效率会从 O(1) 退化到 O(n)严重时甚至会失去意义。所以使用HashSet的前提之一就是元素对象的hashCode和equals必须正确实现。2.3 实战什么时候无脑选它容量怎么给实际项目里最常见的HashSet用法就是去重和快速判存在。比如用户提交一批订单号要过滤掉重复的或者系统启动的时候加载一批封禁用户 ID 到内存后面每个请求都要判断当前用户是否在名单里。这种场景不需要顺序也不要求排序HashSet就是最优选择。有一个细节值得单独拿出来讲构造HashSet时传进去的参数是“初始容量”不是“预期元素个数”。很多人写new HashSet(1000)以为就能直接存 1000 个不扩容但默认负载因子是 0.75容量 1000 时阈值只有 750存到 751 个就会触发扩容。想不扩容初始容量应该按预期元素数 / 负载因子 1来算也就是int expectedSize 1000; SetString idSet new HashSet((int) (expectedSize / 0.75f) 1);这个写法看着麻烦但在批量导入、百万级去重场景里能省下不少扩容和 rehash 的时间。注意new HashSet(expectedSize)在预期元素较多时也会扩容别被构造器签名骗了。2.4 可变对象放进 HashSet后果比想象中严重这是非常隐蔽的一个坑。如果放入HashSet的对象是可变的而且你后来修改了参与hashCode计算的字段这个对象就会“迷失”在集合里它的哈希值变了但它在哈希表中的位置还是按旧哈希值算出来的于是contains找不到它remove也删不掉它相当于对象泄漏在集合里了。举个典型例子class User { String name; // 构造函数、getter、setter 省略 Override public int hashCode() { return name.hashCode(); } Override public boolean equals(Object o) { // 按 name 判断相等 } } User u new User(张三); SetUser userSet new HashSet(); userSet.add(u); u.setName(李四); // 修改了参与 hashCode 的字段 System.out.println(userSet.contains(u)); // false元素“丢了”我自己踩过类似的坑后给自己定了一条规矩凡是要放进HashSet、HashMapkey 位置的对象都尽量设计成不可变对象如果必须可变那就先remove再修改、修改完重新add不要让它待在集合里被改。3. LinkedHashSet既要唯一又要顺序它是 HashSet 的温和升级3.1 它究竟是怎么“记住”顺序的LinkedHashSet是HashSet的子类它在内部使用了一个LinkedHashMap。LinkedHashMap和普通HashMap最大的区别是每个节点上额外维护了before和after两个指针把所有节点串成一条双向链表从而能记录元素插入的先后顺序。这个设计的好处是它保留了HashSet的去重能力和大部分 O(1) 性能同时让遍历顺序稳定下来。每次迭代都是沿着链表走输出顺序就是你插入元素的顺序。注意这里的“插入顺序”有个细节如果往集合里重复添加一个已经存在的元素它不会改变这个元素在链表中的位置也就是说集合的遍历顺序完全由“首次插入”的时间决定。LinkedHashSetString set new LinkedHashSet(); set.add(A); set.add(B); set.add(A); // 加不进去也不会改变 A 的位置 for (String s : set) { System.out.print(s); // 输出 AB而不是 AAB }这一点特别适合回答面试题“如何去重且保持原来的顺序”。如果用HashSet去重顺序是不保证的如果用LinkedHashSet去重之后顺序还是和原始数据一致省了你手动排序的功夫。3.2 最典型的落地场景列表去重保序项目里最常见的需求就是“用户传了一串 ID可能重复我要把重复的去掉但是顺序不能变”。比如前端传了sku1, sku2, sku1, sku3, sku2后端希望最终得到sku1, sku2, sku3顺序跟用户提交的一致。用LinkedHashSet一行就解决了ListString raw Arrays.asList(sku1, sku2, sku1, sku3, sku2); LinkedHashSetString orderedUnique new LinkedHashSet(raw); ListString result new ArrayList(orderedUnique); // result [sku1, sku2, sku3]这种场景在订单去重、工单去重、用户最近浏览记录里很常见。还有一个扩展思路如果你想给LinkedHashMap做访问顺序排序LRU 缓存可以用LinkedHashMap的accessOrder参数但LinkedHashSet本身不支持它永远按插入顺序。如果你需要“最近访问过的唯一元素集合”那不能直接用标准LinkedHashSet得自己封装或换用其他结构。3.3 内存开销与性能边界天下没有免费的午餐。LinkedHashSet比HashSet多出来的就是每个节点上那两条链表指针。数据量小的时候无所谓但在百万级元素场景下这部分额外开销会很明显。如果你只需要去重、不需要顺序就不要为了“可能有用”去用LinkedHashSet如果顺序是业务必需那这点内存换稳定性是值得的。另外LinkedHashSet虽然遍历顺序稳定但它的删除操作也需要同时维护双向链表所以比纯HashSet多了一点常数级开销。不过这里说的性能差异在绝大多数业务场景里都可以忽略真正该关心的还是“业务上到底要不要顺序”。4. TreeSet自带排序和范围查询但别把它当普通 Set 用4.1 红黑树不是玄学是一棵“自动有序”的树TreeSet底层是一个TreeMap也就是一棵红黑树。红黑树是一种自平衡的二叉查找树插入、删除、查找的时间复杂度都在 O(log n)。它和哈希表最大的区别是元素一进去就会根据比较规则找到自己的位置整个树始终保持有序状态所以你从头遍历的时候天然就是排好序的。TreeSet不用hashCode和equals来判断重复它靠的是Comparator或者元素自身实现的Comparable。比较结果返回 0就认为两个元素是“同一个”后一个就加不进去。这一点是无数人踩坑的地方如果你有一个自定义类没有实现Comparable又没有给TreeSet指定Comparator那么add的时候会直接抛ClassCastException。这点和HashSet完全不同HashMap可以通过 equals 判断TreeSet 必须在比较层面把元素排好序。null在TreeSet里也是个敏感话题。默认情况下按自然排序的TreeSet不能放null因为它要调用compareTo而null.compareTo肯定空指针。就算你自定义了一个能容忍 null 的Comparator也不建议这么用这不是设计本意业务上很容易埋雷。4.2 TreeSet 的隐藏能力范围查询很多人只知道TreeSet能排序忽略了它还有一套非常实用的范围查询方法。NavigableSet接口提供了一组可以直接获取“比某个值小一点”“比某个值大一点”“某个区间内所有元素”的方法这在排行榜、区间筛选、时间线处理里非常有用。TreeSetInteger scores new TreeSet(); scores.addAll(Arrays.asList(88, 95, 60, 72, 100, 45)); System.out.println(scores.first()); // 45 System.out.println(scores.last()); // 100 System.out.println(scores.lower(60)); // 45严格小于 60 System.out.println(scores.floor(88)); // 88小于等于 88 System.out.println(scores.ceiling(90)); // 95大于等于 90 System.out.println(scores.higher(100)); // null严格大于 100 SetInteger pass scores.subSet(60, true, 100, true); // pass [60, 72, 88, 95, 100]其中lower、floor、ceiling、higher这几个方法本质上是二叉树上的一次查找效率是 O(log n)比先把整个集合遍历一遍再判断快得多。subSet还可以写成开区间、闭区间做“及格线 60 到满分 100”这类业务判断时非常直观。4.3 自定义 Comparator方便但也最容易埋雷自定义排序时TreeSet的写法很灵活比如按学生分数排序TreeSetStudent byScore new TreeSet( (a, b) - Integer.compare(a.score, b.score) );这样写确实能按分数从低到高遍历但有个致命问题如果两个学生分数相同compareTo返回 0TreeSet就会认为它们是同一个学生后一个直接加不进去。业务上如果只是“分数排名并且每人唯一”还能接受但如果学生数量多、分数段少你会莫名其妙地丢数据。我的习惯是不要在TreeSet的Comparator里只写一个业务排序字段。必须再补一个“唯一业务主键”作为兜底比较比如学生对象先比分数分数相同再比学号TreeSetStudent byScore new TreeSet((a, b) - { int scoreCompare Integer.compare(b.score, a.score); if (scoreCompare ! 0) return scoreCompare; return a.id.compareTo(b.id); });这样既保证了排序规则又不会因为分数相同就误判成同一个元素。记住一句话TreeSet里的“相等”和equals里的“相等”是两套规则Comparator 返回 0 时元素就没机会进入集合了。4.4 什么时候用 TreeSet 更顺手如果业务上需要“一边去重一边排序”比如后台要维护一个自动排序的在线用户列表用户下线就删除在线就加入并且希望列表永远按在线时长排序这时TreeSet就很合适。还有一个典型场景是“区间命中”例如一批预约时间段已经排好序让你判断某个时间点在不在某个区间内借助ceiling/floor能快速定位。但要提醒一句如果不需要去重只是想把一个List排序那直接用Collections.sort或者Stream.sorted就行了没必要为了排序而引入TreeSet。如果数据里允许重复TreeSet更是天生不适合因为它天然会把重复元素吃掉。5. Set 和 List 怎么选一张选型清单比背概念实用5.1 先问自己三个问题选List还是Set不需要背规则只要顺着业务问自己三个问题第一允不允许重复如果商品列表里同一个商品可以出现多次那一定是List如果业务语义上就不允许重复比如用户 ID、订单号、券码那一定是Set。第二要不要下标访问要不要频繁通过get(i)拿某个位置的元素如果列表像数组一样使用选List最好选ArrayList。Set没有get(index)方法想按位置拿数据必须转成数组或者List这是结构决定的不是 API 没做。第三除了唯一性还要不要顺序语义只要唯一、顺序无所谓上HashSet既要唯一又要保持插入顺序上LinkedHashSet既要唯一又要自动排序上TreeSet。如果既要重复又要排序那Set就出局了直接用List加排序。5.2 别小看 contains 的性能差距有一个非常典型的性能优化场景系统里有 10 万个历史订单每个请求都要判断“这个订单号是不是处理过”。如果你用一个ArrayList去存历史订单号那每次contains都是从头到尾一次线性扫描最坏情况要比较 10 万次百万并发下这显然是个灾难。正确做法是初始化时就用HashSetSetString processedOrderIds new HashSet(historyOrderIdList); if (processedOrderIds.contains(orderId)) { // 已处理 }这里有个很容易被忽视的好处把一个List构造进HashSet的时候重复元素会被自动过滤掉而且过滤过程只需要 O(n)。所以高频contains判断、大规模去重、黑白名单检查都应该首选Set而不是List。5.3 面试别再说“List 有序Set 无序”这句话错在了粒度上。List确实是有序的但它保证的是“插入顺序”和“下标访问”不是“排序顺序”。而Set这边HashSet是无序的LinkedHashSet是有序的TreeSet也是有序的所以不能一概而论。更准确的说法是List的顺序是“序列顺序”元素之间有前驱后继关系可以通过下标精确定位Set的顺序是“实现相关”HashSet不承诺、LinkedHashSet按插入顺序、TreeSet按比较规则排序。面试时把这句话说清楚比背一长条特例要有说服力得多。6. 高频面试题与实战踩坑记录6.1 这几道题几乎是必考先看一道最经典的HashSet为什么查询那么快回答思路应该是它底层是HashMap元素作为 key 存储先通过hashCode定位桶再用equals在桶内比对平均时间复杂度 O(1)。如果对方追问“哈希冲突怎么办”可以补一句JDK 8 以后当单桶链表长度超过 8、且哈希表容量大于等于 64 时链表会转成红黑树把最坏情况从 O(n) 降到 O(log n)但实际业务数据很难触发这个状态。第二道常考List去重并且保持顺序怎么做正确姿势是用LinkedHashSetListString list Arrays.asList(a, b, a, c); ListString unique new ArrayList(new LinkedHashSet(list));第三道TreeSet放自定义对象要注意什么要回答两个点要么对象实现Comparable要么给TreeSet传Comparator同时Comparator返回 0 会被判定为重复元素业务字段相同时一定要补唯一字段兜底。第四道HashSet线程安全吗不安全。多线程环境下可以用ConcurrentHashMap.newKeySet()得到一个线程安全的并发 Set或者用Collections.synchronizedSet(new HashSet())包一层但并发迭代时仍要注意外部同步。如果需要并发下的有序 Set可以考虑ConcurrentSkipListSet。第五道HashSet为什么允许一个 nullTreeSet为什么不允许因为HashMap允许 key 为 nullnull 会固定放在第一个桶所以HashSet最多放一个 nullTreeSet默认按自然排序比较元素拿 null 去 compareTo 会直接空指针。6.2 我真实踩过的坑整理成一张排查表现象可能原因解决思路放进去的对象contains 突然返回 false对象进入集合后参与 hashCode 的字段被改了把字段改成不可变或 remove 后修改再重新 addHashSet 构造后存不了预期数量频繁扩容把期望容量当成初始容量用了初始容量按 expectedSize / 0.75 1 设置TreeSet 丢数据Comparator 只比较了业务排序字段多个对象比较结果为 0在 Comparator 里追加唯一字段比较往 TreeSet add null 抛空指针自然排序无法比较 null加判空逻辑不要让 null 进入 TreeSet遍历 Set 的顺序和预期不一致用了 HashSet却希望它保持插入顺序换 LinkedHashSet需要排序用 TreeSet这张表我每次给项目做集合选型时都会在心里过一遍尤其是“可变对象放进 HashSet”和“Comparator 导致丢数据”这两条都是属于线上才会暴露、日志还特别难定位的问题。7. 我常用的 Set 工具方法可以直接抄进项目7.1 去重保序一个方法搞定因为项目里经常要处理“外部传进来的 ID 列表可能带重复但处理顺序不能乱”我封装了一个很小的静态方法public static T ListT distinctPreserveOrder(CollectionT source) { if (source null || source.isEmpty()) { return Collections.emptyList(); } return new ArrayList(new LinkedHashSet(source)); }这个方法背后就是LinkedHashSet既做了去重又保留了第一次出现的顺序。在接口入参清洗、批次任务 ID 过滤中非常实用。7.2 集合运算别把原数据改坏Set提供了retainAll、addAll、removeAll这些批量操作但它们会直接修改调用者。如果你后面还要用原始集合最好先复制一份SetString base new HashSet(Arrays.asList(a, b, c)); SetString other new HashSet(Arrays.asList(b, c, d)); SetString union new HashSet(base); union.addAll(other); // [a, b, c, d] SetString intersection new HashSet(base); intersection.retainAll(other); // [b, c] SetString difference new HashSet(base); difference.removeAll(other); // [a]这里最容易犯的错误是直接base.retainAll(other)结果把 base 改掉了后面想用它做差集时只能干瞪眼。先 new 一份再操作成本不高但能避免很多逻辑混乱。7.3 并发场景和不可变场景的补充选择如果多线程需要维护一个唯一的在线用户集合我不会用普通HashSet加手动锁而是直接用ConcurrentHashMap.newKeySet()它返回的是一个线程安全的Set实现底层复用ConcurrentHashMap的分段锁机制并发读写的表现比Collections.synchronizedSet更稳定。如果还需要并发下的有序去重可以用ConcurrentSkipListSet它底层是跳表功能接近TreeSet但支持并发。另外 JDK 9 以后引入了不可变集合Set.of(...)适合写死的小型常量集合但它有两个限制不能为 null元素重复会抛IllegalArgumentException。使用的时候心里有数就行别拿它去做大数据量动态去重。最后分享一个我自己多年养成的习惯看到集合相关的代码我不先看业务逻辑而是先判断这个数据结构承担的是什么职责。只去重HashSet去重且保序LinkedHashSet去重且排序TreeSet要下标、允许多值List。把这个判断内化成肌肉记忆之后写出来的代码基本不会在集合选型上翻车面试被问到这一块的时候也自然能从一个例子讲到另一个例子而不是干巴巴背概念。
