HashSet与TreeSet性能对比详解

IT行业相对于一般传统行业，发展更新速度更快，一旦停止了学习，很快就会被行业所淘汰。所以我们需要踏踏实实的不断学习，精进自己的技术，尤其是初学者。今天golang学习网给大家整理了《HashSet与TreeSet性能对比分析》，聊聊，我们一起来看看吧！

HashSet插入和查找通常比TreeSet快，因其基于哈希表实现，平均时间复杂度O(1)，而TreeSet基于红黑树，操作均为O(log n)；但哈希碰撞严重时HashSet可能退化。

HashSet插入和查找为什么通常比TreeSet快

因为 HashSet 底层用哈希表（HashMap）实现，平均时间复杂度是 O(1)；而 TreeSet 基于红黑树，所有操作都是 O(log n)。只要哈希函数分布均匀、负载因子不过高，HashSet 的散列定位几乎不随数据量增长变慢。

但要注意：哈希碰撞多时（比如大量 String 具有相同 hashCode()），HashSet 会退化为链表甚至红黑树（JDK 8+），此时单次操作可能接近 O(n) 或 O(log n) —— 这不是常态，但真实业务中若对象重写了弱 hashCode()，就容易踩中。

• HashSet 不保证顺序，也不支持范围查询
• TreeSet 自动按自然序或自定义 Comparator 排序，能高效做 headSet()、tailSet()、subSet()
• 如果只做“是否存在”判断且不要求有序，HashSet 几乎总是更优

TreeSet在什么场景下性能不可替代

当你需要动态维护一个有序集合，并频繁执行以下操作时，TreeSet 的 O(log n) 是刚性需求，HashSet 完全无法替代：

• 找最小/最大元素（first() / last()）—— O(1)，而 HashSet 得遍历
• 取前 K 小元素（用 iterator() 遍历前 K 个）—— O(K)，HashSet 无序，必须先转 List 再排序，O(n log n)
• 判断某值是否在某个区间内（subSet(from, to)）—— O(log n + size)，HashSet 只能全量扫描

例如实时风控中维护“最近 5 分钟的请求时间戳”，用 TreeSet 可以快速 tailSet(System.currentTimeMillis() - 300_000) 拿到有效集合，不用每次清空重建。

实测差异有多大：一个典型插入基准对比

插入 100 万个 Integer 对象（无重复），JDK 17 下典型结果：

HashSet: ~45 ms
TreeSet: ~120 ms

差距约 2–3 倍，且随着数据量增大，TreeSet 的对数增长仍稳定，而 HashSet 在扩容重哈希时会有偶发毛刺（如从 2^20 扩容到 2^21）。

但如果插入的是自定义对象，且 hashCode() 实现低效（比如反复拼接字符串再 hashCode()），HashSet 可能反而更慢；而 TreeSet 只依赖 compareTo() 或 Comparator，逻辑清晰可控。

• 别只看理论复杂度，实测要覆盖你的实际数据特征
• 避免在 hashCode() 或 compareTo() 中做 I/O、同步、复杂计算
• TreeSet 的内存占用略高（每个节点含红黑树指针），大数据量时需留意

迭代性能谁更快

单纯遍历全部元素，HashSet 通常略快（哈希桶数组顺序遍历），但差别微小；真正影响体验的是“遍历是否有序”：

• 如果你需要升序遍历结果，用 TreeSet 迭代是免费的（已排序）；用 HashSet 则必须额外 new ArrayList(set).sort()，成本是 O(n log n)
• TreeSet.iterator() 返回的是“有序视图”，不复制数据，但底层红黑树遍历有指针跳转开销，局部性不如数组
• 并发环境下二者都不安全；若需线程安全的有序集合，ConcurrentSkipListSet 是更合适的选择，而非包装 TreeSet

最常被忽略的一点：TreeSet 的 iterator() 是 fail-fast 的，但它的结构性修改（如 add()）不会影响正在迭代的其他线程——这点和 HashSet 一致；但很多人误以为“有序=线程安全”，结果在线上出现 ConcurrentModificationException 却查不到源头。

本篇关于《HashSet与TreeSet性能对比详解》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！