【面试干货】HashSet 和 TreeSet 的区别

💖The Begin💖点点关注，收藏不迷路💖

在Java的集合框架中，HashSet 和 TreeSet 都是常用的 Set 接口的实现类，但它们之间存在显著的区别。

1、实现方式

HashSet

• 实现方式：HashSet 是由一个哈希表来实现的，利用哈希码对元素进行存储。
• 特点：由于哈希表的无序性，HashSet 中的元素也是无序的。

TreeSet

• 实现方式：TreeSet 是由一个树形结构（通常是红黑树）来实现的。
• 特点：由于树形结构的有序性，TreeSet 中的元素是有序的，且默认是自然排序，也可以通过比较器进行自定义排序。

2、性能

添加、删除和查找操作的时间复杂度

HashSet

• 时间复杂度：对于 add(), remove(), contains() 等操作，HashSet 的时间复杂度接近 O(1)，因为哈希表提供了快速查找元素的能力。但是，请注意这是基于平均情况的复杂度，在最坏情况下，哈希表可能需要遍历链表中的多个元素，时间复杂度可能达到 O(n)。

TreeSet

• 时间复杂度：由于 TreeSet 是基于树形结构实现的，对于 add(), remove(), contains() 等操作，其时间复杂度是 O(logn)，其中 n 是 TreeSet 中的元素数量。

3、元素唯一性

HashSet 和 TreeSet 都保证了元素的唯一性，即集合中不会存在重复的元素。

4、迭代顺序

HashSet

由于是无序的，迭代 HashSet 的元素时，元素的顺序是不确定的。

TreeSet

由于是有序的，迭代 TreeSet 的元素时，元素会按照某种顺序（自然顺序或自定义顺序）进行排列。

5、使用场景

HashSet

适用于需要快速查找元素且不需要关心元素顺序的场景。

TreeSet

适用于需要保持元素顺序的场景，比如排序集合中的元素或找出集合中的最小值和最大值。

6、示例代码

package com.example;import java.util.HashSet;
import java.util.TreeSet;public class SetExample {public static void main(String[] args) {HashSet<Integer> hashSet = new HashSet<>();TreeSet<Integer> treeSet = new TreeSet<>();// 添加元素hashSet.add(3);hashSet.add(1);hashSet.add(4);hashSet.add(2);treeSet.add(3);treeSet.add(1);treeSet.add(4);treeSet.add(2);// 打印元素System.out.println("HashSet中的元素（无序）：" + hashSet); // 输出元素的顺序可能是不确定的System.out.println("TreeSet中的元素（有序）：" + treeSet); // 输出元素的顺序是确定的，按照升序排列}
}

注意：

虽然 HashSet 的 add(), remove(), contains() 方法的时间复杂度通常被认为是 O(1)，但在实际使用中，由于哈希冲突和链表过长等因素，性能可能会受到影响。

因此，在需要高性能的场景下，需要仔细考虑是否使用 HashSet。

💖The End💖点点关注，收藏不迷路💖