一、三种 Set 的底层机制

在讨论性能之前，我们必须先理解它们各自是怎么工作的。机制决定了性能，这是一切分析的起点。

HashSet：基于哈希表的无序去重

HashSet 的底层是一个 HashMap。当我们往 HashSet 中添加元素时，JVM 会先调用元素的 hashCode 方法计算哈希值，再根据哈希值找到对应的桶（bucket）。如果桶中已经存在相同的元素（通过 equals 方法判断），则添加失败，去重完成。

由于哈希值的分布是随机的，所以 HashSet 不保证任何顺序。你插入的顺序和遍历时的顺序完全无关。这也是它性能最优的根本原因——插入和查找的时间复杂度都是 O(1)，只要哈希函数分布均匀，几乎不会出现冲突。

但这里有一个隐含的代价：当哈希表的填充因子超过阈值时，会触发扩容。扩容意味着重新计算所有元素的哈希桶位置，这是一个相对耗时的操作。不过这属于均摊成本，在大量插入的场景下，平均到每次操作的开销依然很小。

LinkedHashSet：带链表的有序 HashSet

LinkedHashSet 本质上是 HashSet 的一个扩展。它在哈希表的基础上，额外维护了一条双向链表，记录了元素的插入顺序。每次插入新元素时，除了正常的哈希操作，还会把这个元素挂到链表尾部。

因此，LinkedHashSet 既保留了 HashSet 的去重能力，又保证了遍历顺序与插入顺序一致。代价是什么？每多维护一个链表节点，就多一份内存开销，同时插入操作也多了一次链表指针的维护。但这个开销在大多数场景下是可以接受的。

TreeSet：基于红黑树的排序去重

TreeSet 的底层是一棵红黑树（一种自平衡二叉搜索树）。元素不是通过哈希值定位的，而是通过比较大小来确定位置。添加元素时，TreeSet 会调用元素的 compareTo 方法（或者外部传入的 Comparator）来决定元素应该放在树的哪个位置。

由于树的结构特性，TreeSet 中的元素始终保持排序状态。插入、删除、查找的时间复杂度都是 O(log n)。相比 HashSet 的 O(1)，这个差距在小数据量下不明显，但当数据量上升到十万、百万级别时，差异会非常显著。

另外，TreeSet 有一个特殊限制：元素必须实现 Comparable 接口，或者在创建 TreeSet 时传入 Comparator。这意味着你不能往 TreeSet 里丢任意对象，类型必须支持比较。

---

二、测试方案设计

为了让对比更有说服力，我设计了一组贴近真实场景的测试。测试环境为 JDK 17，单线程运行，堆内存设置充足，避免 GC 干扰。

测试分为三个维度：

第一，插入性能。 分别向三种 Set 中插入 1 万、10 万、50 万、100 万个整数，记录耗时。整数的哈希值就是自身，不存在哈希冲突，这是对 HashSet 最有利的场景。

第二，查找性能。 在插入完成后，对每个 Set 执行 10 万次 contains 查询，统计总耗时。

第三，遍历性能。 对三种 Set 分别进行全量遍历，记录遍历耗时。这个维度主要体现 LinkedHashSet 的顺序优势和 TreeSet 的排序开销。

所有测试重复运行 5 次，取平均值，消除偶然波动。

---

三、实测数据与分析

插入性能对比

数据非常直观。HashSet 在所有数据量下都是最快的，这符合 O(1) 的理论预期。LinkedHashSet 比 HashSet 慢大约 20% 左右，这个差距来自于链表维护的额外开销，但整体仍在同一量级。

TreeSet 的表现则完全不同。在 1 万数据量时，它已经是 HashSet 的 4 倍；到了 100 万数据量，差距扩大到 8 倍以上。这就是 O(log n) 和 O(1) 在大数据量下的真实差距。如果你的去重场景涉及百万级数据，TreeSet 的插入开销是不可忽视的。

查找性能对比

查找性能的趋势与插入完全一致。HashSet 依然领先，TreeSet 依然落后。值得注意的是，LinkedHashSet 的查找性能和 HashSet 几乎一样——因为查找时并不需要遍历链表，只需要走哈希表的逻辑。链表只在遍历时才发挥作用。

遍历性能对比

遍历方面，HashSet 和 LinkedHashSet 差距极小。但 TreeSet 明显更慢，原因在于红黑树的中序遍历需要不断跳转节点，CPU 缓存命中率较低。而哈希表的桶数组在内存中是连续的，遍历时缓存友好度更高。

另外，TreeSet 的遍历结果是排序后的，如果你本身就需要有序数据，这个"额外工作"对你来说是有价值的。但如果你不需要排序，这个开销就是纯浪费。

---

四、内存占用对比

性能不只是时间，内存也是关键指标。我用 JVM 内存分析工具对三种 Set 在存储 100 万整数后的堆内存占用做了测量。

HashSet 的内存占用最小，因为它只需要存储哈希表的桶数组和链表节点（处理冲突时）。LinkedHashSet 多了一套双向链表，内存占用比 HashSet 高出约 15%~20%。TreeSet 的内存占用最高，因为每个树节点除了存储元素本身，还需要维护左右子节点指针和颜色标记，整体比 HashSet 高出约 40%~50%。

在内存敏感的场景下（比如移动端应用或嵌入式环境），这个差距需要认真考虑。

---

五、什么时候该选哪个？

测试数据讲完了，回到实际选型。我的建议如下：

选 HashSet，当你只关心去重，不关心顺序。 这是绝大多数场景的默认选择。比如做数据清洗、临时去重、作为其他数据结构的中间结果。它最快、最省内存，没有理由不用它。

选 LinkedHashSet，当你需要去重且保持插入顺序。 典型场景包括：去重后需要按原始顺序展示给用户、需要保持队列的先后关系、或者去重后的结果要和之前的操作顺序对应。多出来的那 20% 性能损耗，换来的是顺序的确定性，这笔交易很划算。

选 TreeSet，当你需要去重且保持排序。 比如做排行榜去重、按时间排序后去重、或者需要随时获取最大最小值。但请务必注意数据量。如果数据量在万级以下，TreeSet 完全可用；一旦到了十万级以上，就要认真评估性能影响。如果数据量在百万级，建议换思路——先用 HashSet 去重，再转成列表排序，往往比直接用 TreeSet 更高效。

---

六、一些容易被忽略的细节

在实际使用中，还有几个坑值得提醒：

第一，自定义对象的 hashCode 和 equals 必须配对实现。 很多人只重写了 equals，忘了重写 hashCode，导致 HashSet 去重失效。这不是 Set 的问题，是使用方式的问题，但排查起来非常耗时。

第二，TreeSet 对 null 值的处理。 HashSet 允许一个 null 元素，LinkedHashSet 也允许一个，但 TreeSet 不允许 null。因为 null 无法参与比较，会直接抛出异常。如果你的数据中可能出现 null，TreeSet 需要额外处理。

第三，并发场景下都不能直接用。 这三种 Set 都不是线程安全的。如果在多线程环境下使用，需要用 Collections 工具类包装，或者改用 ConcurrentHashMap 衍生的并发 Set。这又是另一个话题了。

第四，初始容量的设置。 HashSet 和 LinkedHashSet 都支持指定初始容量。如果你提前知道数据量，设置一个合理的初始容量可以避免扩容，提升性能。TreeSet 不支持初始容量设置，因为树的结构是动态生长的。

---

七、总结

去重看似简单，但 Set 的选型直接影响程序的运行效率和内存消耗。一张表总结核心结论：

没有最好的 Set，只有最合适的 Set。理解底层原理，结合实测数据，根据你的具体场景做选择，这才是一个工程师该有的选型思维。希望这篇文章能帮你在下次遇到去重需求时，少走一点弯路。