Java集合框架Set详解：HashSet、LinkedHashSet、TreeSet原理与实战

1. 为什么说Set是Java集合框架里最容易被低估的一个先别急着看标题就划走。我做了十多年Java开发面试过几百个候选人发现一个特别有意思的现象问ArrayList和HashMap的区别几乎人人都能说上两句但问到Set很多人只会背一句无序、不可重复再往深里问就卡住了。这个现象其实暴露了一个问题很多人对Set的理解停留在概念层面根本没有真正吃透它的设计思想和适用场景。而在实际项目中Set的出镜率远比你想象的高——接口幂等性校验、敏感词过滤、数据去重、权限标签管理、订单号判重处处都有它的身影。Set是Java集合框架中Collection接口下的三大子接口之一和List、Queue并列。它的核心特征就两个不包含重复元素最多只允许一个null部分实现。听起来简单对不对但正是这看似简单的两个约束衍生出了三种行为差异巨大的实现类——HashSet、LinkedHashSet、TreeSet它们各自的服务端场景完全不同。这篇文章不打算写成一篇教科书式的API文档。我会带你从使用者的角度重新认识Set把底层原理、实现差异、实战用法、常见坑位一次讲透。无论你是刚接触Java基础的新手还是在面试前临时抱佛脚的求职者抑或是想系统梳理集合知识的老兵这篇文章应该都能给你一些启发。2. 三种经典实现HashSet、LinkedHashSet、TreeSet到底该选谁2.1 HashSet速度至上但没规矩HashSet是Set家族里最常用的实现底层基于HashMap实现。这一点是理解HashSet一切行为的关键。当你向HashSet添加元素时它内部实际上是把这个元素作为HashMap的keyvalue则统一使用一个固定的Object常量在JDK源码里叫PRESENT。也就是说所谓去重的本质是利用HashMap的key不能重复这一机制实现的效果。HashSet的查找、插入、删除操作平均时间复杂度都是O(1)。这个性能优势来源于哈希算法通过元素的hashCode值直接定位到数组桶位在桶内再通过equals方法查找是否有相同元素。整个过程不需要遍历整个集合所以数据量越大HashSet相对List的优势越明显。用生活场景来类比HashSet就像一个只认编号的储物柜。你存东西的时候管理员先看编号hashCode把东西放到对应编号的格子里取东西的时候同样根据编号直接过去拿不需要一间一间找。但是储物柜的排列顺序跟存放时间没有任何关系编号是几就放几号柜——这就是HashSet迭代时顺序随机的原因。HashSet有两个特性必须记住迭代顺序不保证稳定。今天运行是一个顺序明天可能是另一个顺序甚至同一个JVM实例里不同数据量的顺序也可能不同。允许null值但只能有一个。在需要快速去重、对顺序无要求的场景下HashSet是首选。比如判断用户是否访问过某个页面、收集一批ID用于批量查询前的去重等等。2.2 LinkedHashSet记住了你的来路LinkedHashSet是HashSet的子类它在HashSet的基础上额外维护了一个双向链表记录元素的插入顺序。这里有个很关键的细节LinkedHashSet复用了HashMap底层结构但节点类型变成了带有before和after指针的LinkedHashMap.Entry。每次插入元素时除了正常的哈希槽位存储还会把新节点挂到链表的尾部。因此当你遍历LinkedHashSet时顺序就是元素插入的顺序。用储物柜的比喻继续延伸LinkedHashSet是在储物柜旁边加了一个登记本每放一个东西就在登记本上记一笔按时间顺序把所有格子连起来看。虽然东西还是放在编号对应的格子里存储逻辑不变但当你需要查看存了哪些东西时可以按登记本从头到尾念一遍——顺序就固定下来了。这个特性让它天然适合需要去重但保留原始顺序的场景。典型的例子是爬虫抓取URL时去重、读取配置文件的去重并保持配置顺序、接口返回的消息ID去重等。LinkedHashSet的插入、删除、查找性能和HashSet相近都是O(1)但常数略大因为多了维护链表的开销。在元素数量级很大的时候这个差异可能体现出来但通常可以忽略。2.3 TreeSet进来自动排队TreeSet和前面两个实现有本质区别它底层基于TreeMap内部是一棵红黑树自平衡的二叉查找树。这意味着TreeSet中的元素一定是有序的但这个有序是元素的自然顺序自然排序或你指定的比较器顺序而不是插入顺序。TreeSet的时间复杂度为O(log n)因为红黑树的查找、插入、删除都需要从根节点出发逐层比较。在数据量较小时这个差距不明显但数据量到了百万级O(1)和O(log n)的差距就会显现。TreeSet带来的额外价值是可以直接获取有序集合first()获取最小的元素last()获取最大的元素headSet(toElement)获取小于指定元素的所有子集tailSet(fromElement)获取大于等于指定元素的所有子集subSet(fromElement, toElement)获取指定范围内的子集ceiling()/floor()/higher()/lower()获取相邻元素这些方法在处理区间查询、范围统计时极为方便。比如电商系统里需要实时获取当前所有在售商品中的最低价、最高价如果每次都在一个大List里遍历找代价不小直接用TreeSet维护价格排序首尾元素随手可得。使用TreeSet有一个硬性要求元素必须可比较。要么元素自身实现了Comparable接口要么你在构造TreeSet时传入一个自定义的Comparator。如果不满足这个条件运行时会直接抛出ClassCastException。注意是运行时异常编译期不会报错。2.4 一张表看懂如何选型把三个实现类的核心差异放在一张表里面试和实际选型时直接对照即可特性HashSetLinkedHashSetTreeSet底层结构HashMapHashMap 双向链表TreeMap红黑树是否有序无序按插入顺序按自然顺序/比较器排序允许null允许一个允许一个不允许自然排序时时间复杂度O(1)O(1)O(log n)适用场景快速去重去重保持插入顺序去重需要排序/范围查询提示TreeSet在Java 7及之后如果使用自然排序未指定Comparator插入null会抛出NullPointerException如果指定了Comparatornull是否允许取决于Comparator的实现。这点和HashMap家族HashSet/LinkedHashSet完全不同切记。3. 去重原理的两块基石hashCode和equals3.1 为什么hashCode决定了查找速度Set最核心的价值就是去重而去重这件事的判断逻辑并不在Set内部而是依赖你放入的元素自身的两个方法hashCode()和equals()。这个协作机制我拆开讲。当你往HashSet中添加一个元素时流程分为三步调用元素的hashCode()方法得到一个哈希值。根据哈希值计算数组下标底层是hash (table.length - 1)定位到具体的桶位。遍历该桶位上链表中已有的节点依次调用equals()方法判断是否有完全相同的元素如果equals()返回true说明元素已存在新元素不会被加入Set返回false表示添加失败。如果整条链表都没有相同元素则新元素被挂到桶位上添加成功。关键在于hashCode先进行一次粗筛equals再做精确判断。如果两个元素的hashCode不同Set会直接断定它们不同根本不会调用equals方法。这就像去图书馆找书先根据分类号hashCode锁定大概在哪个书架然后再在书架上逐本比对书名equals。分类号都不同肯定不是同一本书没必要逐字核对。3.2 equals的最终裁决hashCode负责把范围缩小但真正决定两个对象是否相等的是equals方法。这里有一个Java规范里定义的契约所有开发者都应该刻在脑子里如果两个对象equals返回true则它们的hashCode必须相同。如果两个对象hashCode相同equals不见得一定返回true哈希碰撞的正常情况。违反第一条契约的后果很严重当对象存入Set后如果hashCode不同equals相同Set会认为这是两个不同的对象去重就失效了。最常见的翻车操作是只重写equals不重写hashCode。举个例子。假设你有一个User类重写了equals方法规定用户ID相同就算同一个人。如果User类没有重写hashCode那么new两个id相同的User对象它们的hashCode来自Object的默认实现基于内存地址几乎不可能相同。HashSet判断的第一步就认定它们不同压根不会去调equals——去重逻辑直接失效。// 错误示范只重写equals不重写hashCode public class User { private String id; Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; User other (User) o; return Objects.equals(id, other.id); } // 没有重写hashCode } // 实际效果 SetUser users new HashSet(); users.add(new User(A001)); users.add(new User(A001)); // 集合里有两个同一个人去重失败这种错误在推荐用IDE自动生成hashCode和equals时不容易发生但一旦手工写过equals就很容易漏掉hashCode。强烈建议在IDE里使用Generate hashCode() and equals()功能自动生成别手写。3.3 重写时的黄金法则如果你需要为一个自定义对象设计equals和hashCode有几个实操层面的建议第一equals的重写要遵循对称性、传递性、一致性原则。也就是a.equals(b)和b.equals(a)结果要一致a等于b、b等于c时a要等于c对象不变时多次调用结果一致。第二hashCode重写时使用31作为乘法因子是一个常见做法。为什么是31因为31是奇素数乘法运算能被JVM优化成移位操作31 * i (i 5) - i性能更好。而且用素数做因子能有效减少哈希碰撞。具体的生成逻辑不用自己写IDE都能搞定。第三重写这两个方法时选择的字段应该是那些在业务上决定对象唯一性的字段。比如User类的id、订单类的orderNo而不是那些可变字段。如果用了可变字段做hashCode对象放入Set后该字段一改hashCode就变了后续在Set里就再也找不到它了。// 推荐的写法 public class User { private String id; private String name; Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; User user (User) o; return Objects.equals(id, user.id); } Override public int hashCode() { return Objects.hash(id); // 只用id来生成hash } }注意Objects.hash()底层会创建数组再装箱性能不如手写的31倍累加。对于高频插入的Set可以考虑手写hashCode但一般情况下Objects.hash的简洁性优先。4. 实战Set在真实项目里的高光时刻4.1 5分钟搞定去重List转Set的优雅姿势数据去重是Set最基础的用法但去重这两个字在实际业务里可以拆出很多变体。场景一批量导入Excel时用户上传的Excel里可能有重复的行。常规做法是遍历判断但用Set一行就能搞定ListString rawList readFromExcel(); SetString uniqueSet new HashSet(rawList); // 如果uniqueSet.size() ! rawList.size()说明有重复 if (uniqueSet.size() ! rawList.size()) { // 返回错误提示指出哪些条目重复 ListString duplicates rawList.stream() .filter(str - Collections.frequency(rawList, str) 1) .distinct().collect(Collectors.toList()); }这段代码有一个细节值得展开如果只是判断有没有重复比较size就够了但如果要给出哪些是重复的需要用stream的frequency统计。这个过滤器写法时间复杂度是O(n²)数据量上去了会慢更高效的做法是用Map手动计数这里仅作为示例。场景二接口幂等性处理。用户下单请求可能在网络重试时被提交两次我们通常会在请求入口处检查本次请求的幂等ID是否已经处理过。用一个Set维护处理过的幂等号配合过期清理机制比每次都去数据库查一张幂等表快得多。private final SetString PROCESSED_IDEMPOTENT_KEYS Collections.synchronizedSet(new HashSet()); public boolean isDuplicate(String idempotentKey) { boolean exists PROCESSED_IDEMPOTENT_KEYS.contains(idempotentKey); if (!exists) { PROCESSED_IDEMPOTENT_KEYS.add(idempotentKey); } return exists; }注意这里用了Collections.synchronizedSet包装因为HashSet本身是线程不安全的。实际生产中可以换成ConcurrentHashMap.newKeySet()性能更好。4.2 交集、并集、差集数据库大表关联和权限校验的好帮手Set提供的集合运算方法addAll、retainAll、removeAll在实际业务中非常实用我给出三个典型场景。用户标签筛选。假设系统里有VIP用户标签集合和活跃用户标签集合要找出既是VIP又活跃的用户就是一个交集运算SetLong vipUsers getUserIdsByTag(VIP); SetLong activeUsers getUserIdsByTag(ACTIVE); vipUsers.retainAll(activeUsers); // 结果保留在vipUsers中权限校验。判断用户是否有访问某个接口的权限本质上是判断用户的角色集合与接口要求的角色集合是否存在交集SetString userRoles getUserRoles(userId); SetString requiredRoles getRequiredRoles(interfacePath); boolean hasPermission !Collections.disjoint(userRoles, requiredRoles);Collections.disjoint是个容易被忽略的工具方法它的作用是判断两个集合是否存在交集返回true表示没有交集。这里的语义变成了如果两个集合没有交集就说明没有权限。数据同步的差集计算。在MySQL主表与搜索引擎索引之间做增量同步时需要找出数据库里有但索引里没有的ID用removeAll一行搞定SetLong dbIds getIdsFromDatabase(); SetLong indexIds getIdsFromSearchIndex(); SetLong needToAdd new HashSet(dbIds); needToAdd.removeAll(indexIds);这几个例子说完了你应该能感觉到Set不仅是个容器它本身就支持一些轻量的集合运算逻辑。在某些场景下用Set做内存计算比去数据库里跑复杂的关联SQL更快。4.3 并发场景下的Set选择别再乱用Collections.synchronizedSet并发编程中如果有多个线程同时读写一个Set有几种选择Collections.synchronizedSet(new HashSet())通过整把锁同步所有方法实现简单但并发量上来性能差。ConcurrentHashMap.newKeySet()基于分段锁JDK8以后是CASsynchronized锁桶读写并发度更高是推荐方案。CopyOnWriteArraySet底层是CopyOnWriteArrayList读多写少的场景适用。前两种的取舍我给你一个具体的参考维度如果你的Set主要是读操作contains、size偶尔写那么synchronizedSet就够了如果你的Set是高频写高频读比如实时维护一个在线用户集合那么强烈建议用ConcurrentHashMap.newKeySet()。// 推荐高性能并发Set SetString onlineUsers ConcurrentHashMap.newKeySet(); // 模拟用户上线/下线 onlineUsers.add(user_001); onlineUsers.add(user_002); onlineUsers.remove(user_001);说明一下ConcurrentHashMap.newKeySet()返回的是ConcurrentHashMap.KeySetView对象它和ConcurrentHashMap共用底层的分段锁机制所以并发性能明显优于对整体加锁的synchronizedSet。CopyOnWriteArraySet适合读非常频繁、写极少的场景比如缓存配置项集合。它的迭代器快照机制确保了遍历时不会抛出ConcurrentModificationException但每次写操作都会复制整个数组代价较高。5. 那些年我们踩过的Set坑5.1 可变对象放进Set之后事情就失控了这是我见过的最典型的Set使用事故。你把一个对象放进HashSet之后如果修改了它参与hashCode计算的字段这个对象的hashCode就变了。但它在Set中的存储位置桶位已经根据旧的hashCode确定了——它变成了一个迷失在集合里的元素。后果是contains()可能找不到它remove()可能删不掉它整个Set内部产生脏数据而且极难排查。class Product { private int id; private String name; // 假设hashCode基于id生成 } SetProduct products new HashSet(); Product p new Product(1, 手机); products.add(p); p.setId(2); // 修改了idhashCode变了 System.out.println(products.contains(p)); // 极可能输出false这个坑的预防方案只有一个放进Set的对象应当是不可变的。如果做不到不可变比如JavaBean的字段要支持修改那就在业务规则上约束——对象一旦加入Set不允许再修改其参与hashCode的字段。类似的坑在MySQL里也有你作为主键的字段如果在业务上被更新了会导致数据一致性问题。原理不同但逻辑相似——唯一标识一旦变更所有基于它的索引/散列结构都失效。5.2 自定义对象去重时equals和hashCode天各一方我面试时经常出这么一道题一个User对象equals方法基于id实现但hashCode基于name实现。往HashSet里添加两个id相同但name不同的对象集合里会留下几个元素答案是两个。因为两个对象的hashCode不同name不一样Set在第一步就认定它们不是同一个对象根本不会走到equals这一步。这个问题的本质是hashCode和equals的业务标识不一致。解决方案是确保两者的判断维度完全一致——hashCode里用的字段equals里要用同一组字段。如果你希望去重逻辑基于id name两个字段那么这两个方法都要基于这两个字段生成。5.3 大心大数据量的性能隐患初始容量别忽略Set尤其是HashSet有一个隐藏的构造函数参数初始容量和负载因子。默认的负载因子是0.75意味着当元素数量达到容量的75%时会触发扩容所有元素需要重新计算哈希位置rehash。假设你要向Set里放入10万个元素如果让HashSet从默认容量16开始自动扩容会经历多次rehash。每次rehash都要重新计算所有元素的哈希值并重新插入耗时线性增长整体性能可能下降数倍。解决方案是在已知数据规模时直接指定初始容量。由于负载因子是0.75初始容量经验值可以设置为期望元素数 / 0.75 1。比如知道要放10万个元素容量设置成100000 / 0.75 1 133334这样基本不需要扩容。int expectedSize 100_000; SetString urlSet new HashSet(expectedSize / 3 * 4 1); // 经典估算这里有个小知识点Kotlin和Guava都提供了Maps.newHashMapWithExpectedSize()这样的工具方法帮你计算JDK本身没有内置这个方法自己算一下也不难。TreeSet没有容积与负载因子概念因为它是树结构不需要hash扩容LinkedHashSet和HashSet一样需要关注初始容量。5.4 迭代时不要修改除非走迭代器不管是HashSet还是TreeSet在迭代过程中直接调用add或remove方法都会抛出ConcurrentModificationException。这是fail-fast机制在起作用——集合内部维护了一个modCount计数器每次结构修改都会递增迭代器持有预期的modCount一旦发现不一致就立刻抛异常。如果确实需要在遍历时删除元素有两个安全方式方式一使用迭代器的remove方法IteratorString it set.iterator(); while (it.hasNext()) { String s it.next(); if (需要删除的条件) { it.remove(); // 通过迭代器删除不会抛异常 } }方式二用removeIfJDK 8简化set.removeIf(s - 需要删除的条件);其中removeIf的底层也是用迭代器实现的两个方式等价。需要注意的是如果是synchronizedSet包装的Set迭代期间其他线程的并发修改依然可能触发异常这在多线程场景下要特别当心。5.5 元素类型不匹配的诡异异常TreeSet中存在类型不匹配的元素时会在运行时抛出ClassCastException。比如TreeSetObject set new TreeSet(); set.add(hello); set.add(123); // 抛 ClassCastException: String cannot be cast to Integer这个错误发生的原因在于红黑树的插入过程需要比较元素大小而字符串和数字之间没有可比性。编译器无法在代码编译期检测到这个问题因为Object类型在编译期被允许添加任意对象。在使用TreeSet时最好在声明时使用泛型限定元素类型并在添加元素前统一校验类型。如果确实要存放不同类型的对象比如模拟按照某种自定义规则混合排序需要提供一个能处理所有类型的Comparator。6. 关于Set的最后一个建议这一篇写了不少但To be honestSet的应用深度远不止于此。在JDK 9之后Set还有静态工厂方法Set.of()可以快速创建不可变集合在SpectrumJDK 21以后新特性出现之后集合操作类型——顺序、唯一性、并发安全性——的组合选择进一步丰富了熟悉Set背后的设计能让QuickPick更准确。最后分享一个小经验。如果你想真正理解Set的行为一个很好的方法是自己动手做实验把Timestamps套进HashSet用不同数量的元素反复测试迭代顺序稳定性自定义一个只重写equals不重写hashCode的类看看去重失效的现场把一个可变对象放入Set后修改字段观察contains的神奇变化。这些实验比背任何文档都印象深刻。踩过一次坑和看过别人踩坑是完全不同的两种成长速度。我在实际排查过三起线上事故后彻底弄明白Set的脾气一起是因为LinkedHashSet被意外用于排序场景结果顺序完全不对一起是自定义对象hashCode基于可变字段导致缓存中的权限数据全部失效还有一起是TreeSet配合默认比较器存储数据上游传了一个新类型字段直接ClassCastException。这三件事的共性是Set看起来使用简单但它的行为边界完全取决于你放入的元素类型和业务约束。如果你对Set还有疑问欢迎带着具体场景来讨论。毕竟集合框架这个工具箱里每个工具都有自己的脾气早一天摸透晚一天踩坑。