概述
在 Java 集合框架中,Set 是处理去重需求的常用接口。然而,HashSet、LinkedHashSet 和 TreeSet 这三个实现类往往让人难以抉择。明明都能去重,为何要设计三种?理清它们的底层原理与实际场景,能帮你彻底告别选型纠结。
底层实现决定行为
要分清三者,关键在于理解它们的'底层靠山'——即底层数据结构。它们并非独立存在,而是基于其他集合封装而成:
| 集合类 | 底层实现 | 核心特点 |
|---|---|---|
| HashSet | HashMap(哈希表) | 无序、去重、查询快 |
| LinkedHashSet | LinkedHashMap | 有序(插入顺序)、去重 |
| TreeSet | TreeMap(红黑树) | 有序(自然排序/自定义排序)、去重 |
简而言之,底层结构直接决定了性能表现与有序性特征,而去重则是 Set 接口的通用能力。
关键差异对比
仅了解底层原理还不够,实际开发中更关注使用体验。从有序性、性能、去重规则、特殊能力四个维度拆解,差异一目了然。
1. 有序性:谁记住了顺序?
- HashSet:完全无序。存储时依赖元素的 hashCode 分配位置,取出的顺序与插入顺序无关,甚至两次遍历顺序都可能不同(极端情况如扩容后)。
- LinkedHashSet:记住'插入顺序'。底层比 HashSet 多了个双向链表,会记录元素插入的先后顺序,遍历时按插入顺序输出。
- TreeSet:自带'排序能力'。不按插入顺序,而是按元素的大小排序。默认是自然排序(整数从小到大、字符串字典序),也支持自定义排序规则(通过 Comparator)。
示例:插入元素 [3,1,2,4]
- HashSet 遍历结果:可能是 [1,2,3,4] 也可能是 [3,1,4,2](取决于 hash 分配)
- LinkedHashSet 遍历结果:固定是 [3,1,2,4](插入顺序)
- TreeSet 遍历结果:固定是 [1,2,3,4](自然排序)
2. 性能:谁更快?看操作场景
性能主要看增删改查的时间复杂度,底层结构直接影响结果:
| 操作 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| 新增(add) | O(1)(平均) | O(1)(平均) | O(log n) |
| 查询(contains) | O(1)(平均) | O(1)(平均) | O(log n) |
| 删除(remove) | O(1)(平均) | O(1)(平均) | O(log n) |
| 遍历(iterator) | O(n) | O(n) | O(n) |
关键结论:
- 追求'快'选前两者:HashSet 和 LinkedHashSet 的核心操作都是 O(1),比 TreeSet 的 O(log n) 快。
- LinkedHashSet 略慢于 HashSet:因为要维护双向链表,插入和删除时需额外调整节点,但日常场景下差异极小。
3. 去重规则:怎么判断'元素相同'?
三者都能去重,但判断逻辑有细微差异:
- :两步判断。


