一、底层架构：两种截然不同的哲学
要理解时间复杂度的差异，必须先看透二者的底层架构。
HashSet的基石是哈希表。 它的内部实际上依托HashMap实现，每个元素作为键存储，值则是一个固定的占位对象。当你往HashSet中丢入一个元素时，系统会立即计算该元素的哈希值，根据哈希值定位到数组中的某个桶位。如果该桶位已经被占据，就通过链表或红黑树（JDK 8及之后）来解决冲突。整个过程如同快递分拣——根据地址编码直接找到对应货架，几乎不需要逐一翻找。
TreeSet的骨架是红黑树。 这是一种自平衡的二叉查找树，它通过严格的旋转与重新着色规则，确保树的高度始终维持在对数级别。每一个节点都携带颜色属性（红或黑），插入和删除时都会触发一系列调整操作，以维持树的平衡性。元素在TreeSet中不是"被丢进去"的，而是"被安放到正确位置"的——每一次插入都是一次有序归位。
两种架构，两种哲学：一个追求"直达"，一个追求"有序"。
二、时间复杂度：O(1) 与 O(log n) 的正面交锋
这是本文的核心战场。
HashSet：常数级的诱惑
HashSet的add、remove、contains三大核心操作，平均时间复杂度为O(1)。注意，这里说的是"平均"。在理想状态下，哈希函数分布均匀，每个桶位至多只有少量元素，定位几乎是瞬时完成的。
但"平均"二字暗藏玄机。当哈希冲突严重时——比如大量对象的哈希值聚集在同一个桶位——链表会不断拉长，JDK 8之后虽然会将过长的链表转化为红黑树，但单次操作的耗时可能逼近O(log n)甚至O(n)。更隐蔽的风险在于：如果自定义对象的hashCode方法实现拙劣（例如反复拼接字符串再计算哈希），HashSet的性能会大幅下滑，反而不如TreeSet稳定。
此外，HashSet在扩容时需要重新哈希所有元素，这是一个偶发但不可忽视的性能毛刺。从2的20次方扩容到2的21次方时，所有元素都要重新计算位置，这一刻的开销不可小觑。
TreeSet：对数级的稳健
TreeSet的add、remove、contains操作，时间复杂度稳定在O(log n)。这不是平均情况，而是最坏情况也如此。红黑树的性质决定了从根节点到任意叶子节点的路径长度不超过2log₂(n)，因此查找目标元素最多进行约20次比较（当n为100万时）。
更关键的是：TreeSet的remove操作并非"先查找再删除"的两步走，而是在树结构中直接定位目标节点并执行删除与再平衡，整个过程一气呵成，无需线性扫描，也无需重新排序。因为顺序性本就由树结构本身维护，删除一个节点后，旋转与重染色操作会在O(log n)时间内完成树的修复。
这种稳定性是HashSet无法企及的。无论数据如何分布，TreeSet的表现都如同节拍器一般精确可控。
三、有序性：TreeSet的独占领地
时间复杂度只是故事的一半。TreeSet真正不可替代的价值，在于它提供了一整套有序操作的方法体系。
HashSet是彻底无序的。你无法预知迭代时元素的出场顺序，也无法直接获取最小值或最大值。如果你需要从HashSet中找出最小元素，唯一的办法是遍历整个集合并自行比较——这是O(n)的代价。
TreeSet则天然有序。它提供first()和last()方法，获取最小和最大元素的时间复杂度仅为O(1)。它还提供higher()、lower()、ceiling()、floor()等方法，用于查找比某个值大或小的最近元素，这些操作统统是O(log n)。
更令人惊叹的是范围查询能力。TreeSet的subSet(from, to)和headSet(to)操作，基于红黑树的动态视图实现，时间复杂度为O(log n)构造视图加上O(m)遍历结果，且不复制元素。这意味着你可以高效地截取某个区间内的所有元素，而HashSet对此完全无能为力——它只能全量扫描。
举个实际场景：在实时风控系统中，你需要维护"最近5分钟内的所有请求时间戳"。用TreeSet的tailSet方法可以瞬间拿到有效集合，无需每次清空重建。而用HashSet？你只能遍历全部元素逐一判断，效率天差地别。
四、实测数据：数字不会说谎
根据JDK 17环境下的实测数据，向集合中插入100万个Integer对象（无重复）：
- HashSet耗时约45毫秒
- TreeSet耗时约120毫秒
差距约2到3倍。这个数字直观地印证了理论分析：HashSet在纯粹的插入场景中确实更快。但请注意，随着数据量继续增长，TreeSet的耗时增长是对数级的，曲线平缓；而HashSet在扩容重哈希时会出现偶发毛刺，曲线并非完全平滑。
如果插入的是自定义对象，且hashCode方法实现低效，HashSet可能反而更慢。TreeSet只依赖compareTo()或Comparator，逻辑清晰可控，性能表现更加可预期。
在内存占用方面，TreeSet略高于HashSet。红黑树的每个节点需要额外存储父节点、左右子节点引用以及颜色属性，而HashSet的哈希桶数组结构相对紧凑。在超大规模数据场景下，这一点值得留意。
五、迭代性能：细微之处见真章
单纯遍历全部元素时，HashSet通常略快一些，因为哈希桶数组的顺序遍历具有良好的缓存局部性。但这个差距微乎其微，几乎可以忽略。
真正拉开差距的是"有序遍历"。如果你需要升序输出结果，TreeSet的迭代器直接返回有序视图，零额外开销。而用HashSet？你必须先将元素转成List，再调用排序方法，成本是O(n log n)。当数据量达到百万级别时，这个开销将非常可观。
还有一个容易被忽略的细节：TreeSet的迭代器是fail-fast的，结构性修改会触发异常。但这和HashSet一致，并非TreeSet独有的问题。很多开发者误以为"有序就等于线程安全"，这是一个危险的误解——二者都不具备线程安全特性，在并发环境下都需要额外的同步措施。
六、选型指南：什么时候用谁？
经过以上全方位的对比，选型逻辑已经非常清晰：
选择HashSet的场景： 你只关心"元素是否存在"，对顺序毫无要求。典型场景包括去重、缓存键管理、快速判断某个值是否出现过。只要hashCode和equals方法实现正确，HashSet几乎总是更优选择。
选择TreeSet的场景： 你需要动态维护一个有序集合，并频繁执行以下操作——获取最小或最大元素、取前K个最小元素、判断某值是否在某个区间内、执行范围查询。这些操作在TreeSet上都是O(log n)级别，而在HashSet上要么无法实现，要么代价高昂。
如果你的业务同时需要有序和高并发，那么TreeSet和HashSet都不是最佳答案。ConcurrentSkipListSet才是那个更合适的选择——它基于跳表实现，既保持有序，又具备更好的并发特性。
七、结语
HashSet与TreeSet之争，本质上是"速度"与"秩序"之间的权衡。HashSet用哈希表换来了常数级的极速响应，代价是彻底放弃了顺序；TreeSet用红黑树守住了元素的有序尊严，代价是对数级的时间开销。
没有银弹，只有取舍。理解底层架构，看透时间复杂度的真实含义，你才能在每一个具体场景中做出最精准的技术决策。这，才是工程师的核心竞争力。
