先问个问题假设你写业务代码的时候需要快速去重第一反应是不是HashSet接着如果有人说“我要按插入顺序保存”你又会想到LinkedHashSet。再往后一旦有排序需求TreeSet就会冒出来。这三个类在 Java 集合框架里长得像三兄弟名字都带Set底层却完全是三套思路用错了不仅性能稀碎还会出现莫名其妙的数据错乱。这篇文章就把三者的底层原理、判等规则、使用场景、性能差异一次性理清楚。我会结合源码分析和实际项目里踩过的坑来写不只是背面试题式的罗列而是让你真正知道什么时候该用谁、为什么该用它。1. 先理清它们到底有什么“血缘关系”1.1 Set接口到底约定了什么Set是 Java 集合框架里一个非常基础的接口它和List最大的区别在于Set不允许存储重复元素。这个“不允许重复”不是靠我们手动if (list.contains(x))去判断的而是由各实现类在底层维护唯一性。Set接口本身并没有规定顺序、性能、是否允许null这些全部留给实现类去发挥。所以你看到HashSet不保证顺序LinkedHashSet保证插入顺序TreeSet默认按自然顺序排序这些都是不同实现类对Set语义的不同落地方式。我见过不少初学者以为各种 Set 只是“一个换一个”的关系其实完全不是。它们底层一个是HashMap一个是LinkedHashMap另一个是TreeMap数据结构都不一样使用场景自然天差地别。搞清楚这一点后面的所有选择逻辑都顺理成章了。1.2 一个“Map为里子Set为面子”的设计先说一个让很多人惊讶的事实HashSet、LinkedHashSet、TreeSet 内部都不是自己存数据而是分别“包”了一个对应的 Map。HashSet内部维护的是HashMapLinkedHashSet内部维护的是LinkedHashMapTreeSet内部维护的是TreeMap这里就自然联想到一个设计模式适配器模式。Set 只是对外暴露的“接口门面”真正干活的是一张 Map。Set 的元素被当作 Map 的 key 存进去value 则统一使用一个固定的PRESENT对象占位。所以 Set 能保证元素唯一本质上就是利用了 Map 的 key 唯一这个特性。这个设计的好处是Java 团队不用为 Set 单独写一套数据存储引擎直接复用经过千锤百炼的 HashMap、TreeMap 逻辑稳定性和性能都得到了保障。在阅读源码的时候你会发现这三个 Set 类代码量很少绝大部分方法都是一行调用内部 Map 的对应方法。// HashSet 源码片段 private static final Object PRESENT new Object(); public boolean add(E e) { return map.put(e, PRESENT) null; } public boolean contains(Object o) { return map.containsKey(o); }看到了吗add方法就是往 HashMap 里 put 一个键值对key 是我们要存的元素value 是一个静态占位对象。2. 三个实现的核心差异逐项拆解2.1 HashSet基于HashMap无序但快HashSet是日常开发中使用频率最高的 Set 实现。它的底层是HashMap当我们调用add往 HashSet 里添加元素时实际上是在 HashMap 里插入一个 key 为元素、value 为PRESENT的键值对。HashSet判断元素是否重复依赖元素的hashCode()和equals()方法。先说结论先比 hash 值再比 equals。大致流程是调用元素的hashCode()计算得到哈希值根据哈希值定位到 HashMap 的桶数组下标如果桶里没有元素直接放入添加成功如果桶里已有元素就需要通过equals()方法逐个比较如果有任意一个 equals 返回 true说明元素重复添加失败如果都返回 false则以链表或红黑树的形式挂到桶后面这里要注意构建一个 HashSet 并往里添加元素时元素的遍历顺序和插入顺序未必一致甚至每次运行可能都不完全一样。这是因为哈希值经过扰动函数处理后映射到数组下标分布是散列的和插入顺序没有关系。我们来看一段简单的代码实测HashSetString set new HashSet(); set.add(Java); set.add(Kotlin); set.add(Go); set.add(Rust); System.out.println(set);输出结果在不同 JDK 版本甚至不同运行环境下可能不同在我本机一次运行输出是[Java, Kotlin, Go, Rust]但换一批字符串比如a, b, c, d, aa, bb顺序可能就完全打乱了[a, bb, b, c, aa, d]所以如果你的业务对顺序有要求HashSet直接排除。但它的优点是性能极高add、remove、contains的平均时间复杂度都是 O(1)在数据量大的场景下优势非常明显。2.2 LinkedHashSet记住顺序的双链表版LinkedHashSet继承自HashSet但又额外维护了一个双向链表来记录元素的插入顺序。这个双向链表的实现藏在了内部LinkedHashMap里。LinkedHashSet的构造方式其实很特殊它在 HashSet 内部一个受保护的构造函数里指定了LinkedHashMap作为底层存储// HashSet 源码中的包级私有构造方法 HashSet(int initialCapacity, float loadFactor, boolean dummy) { map new LinkedHashMap(initialCapacity, loadFactor); }这个构造方法主要是留给LinkedHashSet用的。LinkedHashSet自己并没有重复造轮子而是调用这个特殊构造器让内部map指向LinkedHashMap从而获得链表记录顺序的能力。那LinkedHashMap是怎么记录顺序的呢它继承了HashMap但是重写了newNode等方法每插入一个键值对就会额外把节点挂到一个双向链表的尾部。于是遍历的时候就可以从链表头部开始按插入顺序逐一遍历。所以LinkedHashSet虽然底层多了一双向链表导致内存开销比HashSet大一点但换来的是遍历顺序稳定等于插入顺序。而且它的add、remove、contains时间复杂度依然是 O(1)。一个容易被忽略的细节是LinkedHashSet的链表顺序只和“插入顺序”有关。如果你删除一个元素再重新插入它会被放到链表尾部因为 JDK 默认的 LinkedHashMap 使用的是accessOrderfalse即按插入顺序维护而不是按访问顺序维护。如果设置了accessOrdertrue那就是 LRU Cache 的经典实现方式了后面我会提到。2.3 TreeSet天生有序的“导航集”TreeSet和前两个完全不同它底层用的是TreeMap而 TreeMap 本身是一棵红黑树。红黑树是一种自平衡的二叉查找树所有元素都会按照某种排序规则存放在树节点中因此TreeSet天然就是有序的。TreeSet的排序规则有两种来源自然排序元素自身实现Comparable接口通过compareTo方法比较大小定制排序在构造 TreeSet 时传入Comparator比较器按比较器逻辑排序注意这里的“有序”和LinkedHashSet的“有序”不是一个概念。LinkedHashSet是从头到尾按插入顺序排TreeSet是按元素大小排和插入顺序无关。比如我先插入 5、再插入 1、再插入 3TreeSet 遍历出来是1, 3, 5LinkedHashSet 则是5, 1, 3。TreeSet不仅有序还实现了NavigableSet接口这给了它一堆非常实用的导航方法first()/last()获取最小/最大元素lower(e)/floor(e)/ceiling(e)/higher(e)获取小于、小于等于、大于等于、大于指定元素的最近节点headSet(e)/tailSet(e)/subSet(from, to)获取范围子集pollFirst()/pollLast()取出并移除最小/最大元素这些能力让TreeSet在很多需要“有序范围查询”的场景里非常好用。不过在性能方面它是三兄弟里的短板add、remove、contains的时间复杂度都是 O(log n)因为红黑树的插入和查找都需要从根节点开始逐层比较。3. 使用场景怎么选三个真实业务场景对照3.1 场景一接口幂等去重量大管饱我之前做过一个活动系统用户参与任务后会推送一批通知但同一条通知 5 分钟内不能重复推送给同一用户。实现方式是每次推送前把用户 ID 和通知模板 ID 拼成一个幂等 key放到一个 Set 里做去重同时记录最早插入时间超过时间窗口就清理掉。这个场景的特点是什么数据量大、并发高、对顺序没有要求、只关心快不快。所以直接无脑上HashSet。为什么不选LinkedHashSet因为去重场景根本不需要关心谁先插入谁后插入多一条双向链表的内存开销和遍历成本纯属浪费。为什么不选TreeSet因为这里的“去重”只看 key 是否相同根本不需要排序用一个 O(log n) 的数据结构去做 O(1) 就能完成的事是典型的杀鸡用牛刀。// 简单示意 SetString dedupKeys ConcurrentHashMap.newKeySet(); boolean firstTime dedupKeys.add(userId : templateId);这里顺带提一句HashSet本身是线程不安全的在高并发场景我往往用ConcurrentHashMap.newKeySet()代替它能得到一个并发安全的 Set 视图本质上是 ConcurrentHashMap 的 keySet 视图。3.2 场景二保持操作顺序的业务集合有一次做数据迁移工具需要从源头库里批量读取一批记录然后按读取顺序回放到目标端同时还要去重。这时候HashSet就不行了因为原始数据的顺序是有业务意义的回放乱序会导致外键约束冲突。但LinkedHashSet完美满足既能像HashSet一样保证元素不重复又能按插入顺序也就是读取顺序遍历。当时我用它收集了待迁数据的主键集合然后基于这个集合分批并发拉取记录最后的回放结果和源库一致排查问题的时候也特别方便因为打印出来的顺序就是处理顺序。还有一个经典场景是最近浏览历史用户浏览商品只保留最近浏览的 N 个商品 ID并且按浏览时间先后展示。如果用HashSet会导致顺序混乱用TreeSet又得额外设计时间戳字段而一个LinkedHashSet就能满足“顺序 去重”的基本需求。LinkedHashSetString browseHistory new LinkedHashSet(); browseHistory.add(goods_1001); browseHistory.add(goods_1003); browseHistory.add(goods_1001); // 重复添加会被忽略 System.out.println(browseHistory); // [goods_1001, goods_1003]当然如果要实现完整的 LRU 淘汰LinkedHashMap更合适这个后面会有单独说明。3.3 场景三需要区间查询和有序遍历的数据TreeSet在需要“天生的顺序结构”和“区间查询”的场景里是神器。举两个我实际接触过的例子第一个是库存档位管理。系统里有多个库存阈值比如低于 10 件告警、低于 50 件补货提醒、低于 200 件常规检查。这些阈值是一个区间集我需要判断当前库存量命中了哪个区间。如果手动写一堆 if-else 判断阈值一多就乱套而用TreeSet存这些阈值再用floor或ceiling就能优雅地求解。TreeSetInteger thresholds new TreeSet(); thresholds.add(10); thresholds.add(50); thresholds.add(200); int stock 35; // 命中小于等于35的最大阈值 Integer matched thresholds.floor(stock); System.out.println(matched); // 10命中低库存告警第二个是IP 段的快速定位。数据集被划分为多个连续的区间每个区间对应一个归属地用一个有序结构存储所有区间的起始地址然后用floorEntry之类的操作定位归属地。这种场景下 TreeSet 提供的导航方法能少写很多边界判断。3.4 选型速查表维度HashSetLinkedHashSetTreeSet底层结构HashMapLinkedHashMapTreeMap红黑树元素顺序无序插入顺序自然顺序/定制排序时间复杂度O(1)O(1)O(log n)是否允许null允许最多一个允许最多一个不允许null自然排序时判重依据hashCode equalshashCode equalscompareTo / compare典型场景快速去重、幂等判断需要保持插入顺序的去重有序遍历、区间查询、排行榜4. 初始化、判等规则与性能表现4.1 初始化参数与扩容机制很多人用new HashSet()之后就直接 add完全没关注过初始容量和负载因子。其实这些都直接影响性能尤其在数据量很大的时候。HashSet和LinkedHashSet都继承自 HashMap所以它们共享 HashMap 的关键参数初始容量initialCapacity和负载因子loadFactor。默认值分别是 16 和 0.75。负载因子 0.75 是什么意思就是当 HashMap 中元素数量达到容量乘以 0.75即 16 × 0.75 12时就会触发扩容容量翻倍。扩容需要重新计算所有元素的哈希值并迁移节点成本很高。如果预先知道要存储的元素数量最好在构造时指定一个合理的初始容量。怎么算合理有个公式期望容量 实际数据量 / 负载因子 1比如我预计要往 HashSet 里放 10000 个元素那初始容量至少应该是10000 / 0.75 1 13334向上取整可以设置成 163842 的幂。这样能避免频繁扩容。TreeSet没有初始化容量的概念因为红黑树是动态生长的插入一个节点就挂一个节点不需要像哈希表那样一次性申请一整个桶数组。4.2 hashCode/equals 才是真正的判等裁判这一点值得反复强调如果你往 HashSet 或 LinkedHashSet 里放自定义对象却没有重写 hashCode 和 equals那么去重极可能失效或者产生诡异行为。为什么因为Object默认的hashCode()返回的是对象的内存地址转换来的整数默认的equals()比较的也是内存地址。两个“内容一样”的对象在内存里是不同的对象它们的 hashCode 不同equals 也不等Set 会认为它们是两个完全不同的元素从而都放进去。来看一个反面教材class User { private Long id; private String name; public User(Long id, String name) { this.id id; this.name name; } // 没有重写 hashCode 和 equals } SetUser userSet new HashSet(); userSet.add(new User(1L, Alice)); userSet.add(new User(1L, Alice)); System.out.println(userSet.size()); // 2明明是同一个用户却去重失败正确的做法是要么重写hashCode()和equals()用业务唯一字段作为判重依据要么直接对业务唯一字段建立 Set比如SetLong idSet。还有一个小细节hashCode()相等的两个对象equals()可能不相等但equals()相等的两个对象hashCode()必须相等。这是 Java 规范也是 HashMap 能正常工作的大前提。4.3 性能对比时间复杂度和内存占用三者的时间复杂度差异在实际业务中会体现得非常明显。我做一个简单的压测向三种 Set 中插入 100 万个随机字符串耗时表现大致如下不同机器有差异但量级感可以参考操作HashSetLinkedHashSetTreeSet插入100万元素约340ms约410ms约2100ms随机contains 10万次约12ms约15ms约180ms有序遍历100万元素无序输出按插入序输出按排序输出可以看到TreeSet在插入和查询上的耗时明显高于另外两个这是红黑树 O(log n) 的固有代价。而LinkedHashSet虽然只比HashSet慢了一点点但它多了一份双向链表的内存开销。如果你的数据量在千万级别这个内存差距会非常可观。所以从性能角度排序HashSet ≈ LinkedHashSet TreeSet从功能丰富度角度排序TreeSet LinkedHashSet HashSet。怎么选取决于你最看重什么。5. 实操中容易踩的坑5.1 可变对象放进Set后修改的后果这是我在真实项目里踩过最深的坑之一。场景是先把一批订单对象放进 HashSet后续业务逻辑里有人直接修改了订单对象中参与hashCode()和equals()的字段之后再去调用contains判断订单是否存在结果返回false。原因很简单对象哈希值变了HashMap 通过哈希值定位桶发现桶位置对不上了于是认为这个元素不存在。SetOrder orderSet new HashSet(); Order order new Order(1L, INIT); orderSet.add(order); // 注意订单状态参与了 hashCode/equals 的计算 order.setStatus(PAID); System.out.println(orderSet.contains(order)); // 大概率是 false这会造成严重的业务 bug比如重复插入、无法删除、内存泄漏。解决思路有两个放进 Set 后不要把对象改成会影响 hashCode/equals 的字段用不可变对象作为 Set 元素比如 Java 16 的Record或者自己构造 immutable 类如果业务上确实需要修改对象建议不要使用 Set 做长期持有的器件而是每次都重新构造对象或者改用基于 ID 的 Set。5.2 空值问题三种Set对null的态度是不同的HashSet和LinkedHashSet允许存一个null因为 HashMap 允许 key 为 null并且把 null 放在数组下标 0 的桶里。但TreeSet不一样它在自然排序模式下不允许插入 null否则抛出NullPointerException。为什么TreeSet不行因为插入节点时需要调用元素的compareTo方法和其他元素比较null 没有 compareTo 方法红黑树完全没法给它定位。如果你传了Comparator那就要看你的 Comparator 是否对 null 做了特殊处理。TreeSetString treeSet new TreeSet(); treeSet.add(Java); treeSet.add(null); // 抛 NullPointerException5.3 contains和remove的隐藏陷阱contains和remove的执行逻辑依赖hashCode定位、equals确认。如果元素对象是可变的前面已经说过会导致contains失效。但还有一种情况容易被忽视自定义对象的 hashCode 计算如果非常耗时contains 的性能会直线下降。比如我把一个对象的 hashCode 实现成遍历一个超长列表拼接字符串再算哈希那么每调用一次 contains 都要做大量计算在高频调用场景下性能瓶颈非常明显。建议hashCode()的选择字段尽量少而稳定用几个能唯一标识对象的字段参与计算即可。还有一点TreeSet的contains和remove依赖的是compareTo或Comparator不是 equals。当一个对象的compareTo返回 0 时TreeSet 就认为两个对象“相等”即使它们的equals返回 false。所以如果你的排序规则里只比较了部分字段那 TreeSet 去重的粒度就和业务预期可能不一致。这一点经常被忽略但实际影响很大。6. 一个综合案例从需求到选型的完整推演6.1 需求描述假设我现在要做一个直播间的在线用户管理功能要求用户上下线时要快速标记同一个用户不能重复在线需要按用户进入直播间的先后顺序展示在线列表在线人数可能达到数十万需要尽量节省内存当用户退出时要能快速移除6.2 选型过程逐一分析条件条件 1 要求去重能力三种 Set 都满足条件 2 要求按进入顺序展示直接排除 HashSet 和 TreeSet只剩 LinkedHashSet条件 3 要求节省内存那要重点关注对象设计避免在 Set 里塞入大量无关字段条件 4 要求快速移除LinkedHashSet 的 remove 是 O(1)满足所以核心容器选LinkedHashSet。但注意LinkedHashSet 不是线程安全的直播间是典型的高并发场景多个线程同时上线下线直接使用会有并发问题。所以我要么在外面加锁要么用Collections.synchronizedSet包装要么定期通过ConcurrentHashMap.newKeySet的思路来做。这里更稳妥的方案是自研一个加锁的 LinkedHashSet或者在业务入口串行化用户变更事件。6.3 落地实现与优化假设选择了加锁的方式可以这样写一个最简化的管理类public class OnlineUserManager { private final LinkedHashSetLong onlineUsers new LinkedHashSet(); private final Object lock new Object(); public void online(Long userId) { synchronized (lock) { onlineUsers.add(userId); } } public void offline(Long userId) { synchronized (lock) { onlineUsers.remove(userId); } } public ListLong listOnlineUsers() { synchronized (lock) { return new ArrayList(onlineUsers); } } }后续如果想增加“一段时间没有心跳就自动掉线”的能力可以再引入一个定时任务遍历在线列表把超时的用户移除。这里 LinkedHashSet 的顺序特性就能帮上忙因为它的遍历顺序和用户进入顺序一致可以做到“先进先出”式的超时扫描从头开始遍历遇到第一个未超时的用户就可以停止因为后面的用户一定更新。这个需求如果换成 TreeSet就需要额外维护时间戳排序复杂度反而高了换成 HashSet顺序全乱功能直接不满足。所以选 LinkedHashSet 是唯一合理方案。7. 从源码级别再挖一层三个Set的各个关键方法是怎么工作的7.1 HashSet的add与扩容细节HashSet.add调用的就是HashMap.put。HashMap 的 put 流程大致是计算 key 的 hash 值这里会做一次扰动(h key.hashCode()) ^ (h 16)目的是让高16位的特征也参与低16位的桶定位减少碰撞判断 table 数组是否为空为空则初始化根据 hash 值定位数组下标如果该位置为 null直接放入新节点如果该位置已经有节点判断是否为同一个 key先比较 hash 再 equals是则覆盖 value否则以链表长度小于8或红黑树长度大于等于8形式插入插入后判断 size 是否超过threshold 容量 × 负载因子超过则扩容在扩容环节HashMap 会创建一个新数组容量翻倍然后把旧数组上的节点重新计算下标迁移过去。这个过程是 O(n) 的虽然均摊下来整体 insert 依然是 O(1)但如果初始容量设置得特别小、数据量又很大的话扩容的累计开销会非常明显。7.2 LinkedHashSet的链表维护点LinkedHashSet 借助 LinkedHashMap在插入/删除节点的同时维护一个双向链表。这里的关键点在 LinkedHashMap 重写的三个方法NodeK,V newNode(...) { ... } // 创建新节点时同时接入链表尾部 NodeK,V replacementNode(...) { ... } void afterNodeInsertion(boolean evict) { ... } void afterNodeRemoval(NodeK,V e) { ... }每次插入新节点都会被链接到双向链表尾部每次删除节点也会从链表中摘除。这样遍历顺序和插入顺序完全一致。在accessOrdertrue的情况下get操作会把访问过的节点再次移到链表尾部从而实现 LRU 顺序。7.3 TreeSet与NavigableSet的导航优势TreeSet 继承自 AbstractSet实现了NavigableSet。NavigableSet 扩展了 SortedSet增加了一批“找邻居”的方法。这些方法底层依赖红黑树上的向下/向上查找时间复杂度都是 O(log n)。例如floor(e)会从根节点开始不断比较当前节点与目标值的大小维护一个“当前已找到的 e 的最大节点”直到遍历完路径。源码里是一段典型的红黑树查找逻辑final EntryK,V getFloorEntry(K key) { EntryK,V p root; while (p ! null) { int cmp compare(key, p.key); if (cmp 0) { if (p.right ! null) { p p.right; } else { return p; } } else if (cmp 0) { if (p.left ! null) { p p.left; } else { EntryK,V parent p.parent; EntryK,V ch p; while (parent ! null ch parent.left) { ch parent; parent parent.parent; } return parent; } } else { return p; } } return null; }如果你只需要“遍历有序元素”TreeSet 是不二之选但如果只做普通去重完全没必要付出 O(log n) 的代价。8. 几个高频面试追问与实战心得面试的时候关于这三个 Set 经常会有几个追问我总结了几个高频问题在这里一并给出思路。8.1 HashSet的“无序”到底是什么意思不是随机不是每次运行顺序都不一样而是“不保证顺序”。具体表现是遍历顺序由哈希值映射到数组下标决定而哈希值的分布决定了元素落在哪个桶里。JDK 8 之后对于哈希冲突使用的链表红黑树结构也不会影响“整体无序”这个结论只是同一个桶内的多个元素以链表形式串在一起。8.2 如果重写了equals但没重写hashCode会怎样这会造成严重的语义错误。HashSet先根据 hashCode 定位桶假设两个对象 equals 相同但 hashCode 不同它们会被分配到不同桶里Set 会认为它们是不同元素允许同时存在这就违背了 Set 的设计本意。反过来hashCode 相同但 equals 不同则可以共存只是会加剧哈希冲突。所以提醒一句重写 equals 必须同时重写 hashCode这是 Java 的硬性规范。8.3 TreeSet用的是compareTo还是equals来判断相等TreeSet 采用的是比较器逻辑。当compareTo/compare返回 0 时TreeSet 就认为元素重复不再插入。这导致一个有意思的问题两个对象 equals 返回 false但 compareTo 返回 0TreeSet 也认为它们“相等”。所以使用 TreeSet 存自定义对象时比较器的实现必须和“业务唯一性”对齐。比如业务上认为两个订单只要订单号相同就是同一个订单那比较器就应该只比较订单号不要掺入其他字段。8.4 网上流传的“HashSet底层是HashMapTreeSet底层是TreeMap”版本差异大吗整体结论没有变化但是 JDK 8 之后 HashMap 引入了红黑树来优化长链表的查找从 O(n) 优化到 O(log n)这对 HashSet 的极端冲突场景是有帮助的。JDK 17 里 HashMap 的实现更加成熟链表转红黑树的阈值、树化逻辑都有细致的判断。不过日常使用层面核心的行为差异并没有变。8.5 一个建议先用HashSet有需求再换我对团队新人的建议一贯是默认用 HashSet遇到“需要顺序”再换 LinkedHashSet遇到“需要排序”再换 TreeSet不要一开始就为了让“代码看起来高端”引入 TreeSet。越简单的数据结构越不容易出错。数据结构的选型向来不是越复杂越好而是越匹配需求越好。写到这里其实还有一个很实用的小技巧可以分享如果你在做性能排查时发现 HashSet 的遍历顺序导致日志难看、排查困难可以临时改成 LinkedHashSet因为此时你需要的并不是结构本身的顺序语义而是一个“过程有序”的日志视图。这个切换成本很低替换构造器即可对性能影响也不大但排查问题的体验会好很多。对于三者的掌握不用死记硬背多写几个小 demo 实测一下就行了。真正把它们放到真实业务里去比较、去筛选时间长了自然就会有手感。