HashSet 与 TreeSet

17 Mar 2025 | 4 分钟阅读

在 Java 中，整个集合框架都建立在一组标准接口之上。提供了这些接口的几个标准实现（如 LinkedList、HashSet 和 TreeSet），我们可以直接使用。在本节中，我们将首先通过适当的示例讨论 **HashSet** 和 **TreeSet**。此外，还将讨论 **HashSet 和 TreeSet 之间的区别和相似之处**。

下图显示了集合框架中 HashSet 和 TreeSet 的层次结构。

HashSet

HashSet 是 Java 集合框架的通用类。它扩展了 AbstractSet 并实现了 Set 接口。它创建使用 **哈希表** 进行存储的集合。哈希表通过使用 **哈希** 机制来存储信息。

哈希使用信息内容来确定一个称为 **哈希码 (hash code)** 的唯一值。它用作存储与键相关联数据的索引。键到哈希码的转换是自动执行的。哈希的好处在于，即使对于大型集合，它也能使 add、contain、remove 和 size 操作的执行时间保持恒定。其操作搜索、插入和删除的时间复杂度为 **O(1)**。

HashSet 类不提供任何额外的显式方法。它使用其超类和接口的方法。需要注意的是，它不保证元素的顺序。

让我们通过一个 Java 程序来理解 HashSet。

HashSetExample.java

import java.util.HashSet; 
public class HashSetExample
{ 
public static void main(String[] args) 
{ 
//creating a HashSet
HashSet<String> hs = new HashSet<String>(); 
// add elements to HashSet 
hs.add("New York City"); 
hs.add("Houston"); 
hs.add("Tucson"); 
hs.add("Los Angeles"); 
hs.add("Chicago"); 
hs.add("Boston"); 
hs.add("Denver"); 
//adding a duplicate element to the HashSet
hs.add("Chicago"); 
//prints the HashSet element on the console  
System.out.println("HashSet elements are: "); 
for (String temp : hs) 
{ 
System.out.println(temp); 
} 
} 
}

输出

在上面的输出中，我们观察到两点。第一点是元素没有按自然顺序排序，第二点是重复元素 **Chicago** 已被删除。

TreeSet

TreeSet 是 Java 集合框架的一个类，它扩展了 AbstractSet 并实现了 Set、NavigableSet 和 SortedSet 接口。它创建使用树进行存储的集合。

TreeSet 是 Java 集合框架的通用类。它实现了 Set 接口。它在内部使用 **TreeMap** 来存储 TreeSet 元素。默认情况下，它按自然顺序（升序）对元素进行排序。排序顺序取决于我们提供的 Comparator。如果没有提供 Comparator，它会按自然顺序对元素进行排序。

与 HashSet 相比，它的性能较慢，因为 TreeSet 在每次插入和删除操作后都会对元素进行排序。

它使用 **compareTo()** 或 **compare()** 方法来比较元素。需要注意的是，TreeSet 的实现不是同步的。这意味着它不是线程安全的。如果多个线程并发访问 TreeSet 并且一个线程尝试修改 TreeSet，则必须在外部进行同步。

它不允许存储 null 元素。如果我们尝试插入 null 元素，它会抛出 **NullPointerException**。它比 HashSet 需要更多的内存，因为它还维护用于排序元素的比较器。

其操作搜索、插入和删除的时间复杂度为 **O(log n)**，这比 HashSet 高得多。它使用 **自平衡二叉搜索树 (Red-Black Tree)** 来实现 TreeSet。

让我们通过一个 Java 程序来理解 TreeSet。

TreeSetExample.java

import java.util.TreeSet; 
public class TreeSetExample
{ 
public static void main(String[] args) 
{ 
//creating a TreeSet 
TreeSet<String> ts= new TreeSet<String>(); 
//adding elements to TreeSet
ts.add("Dell"); 
ts.add("HP"); 
ts.add("Apple"); 
ts.add("Acer"); 
ts.add("Asus");
ts.add("Lenovo");
ts.add("Samsung");
//try to a duplicate element 
ts.add("Asus"); 
//prints the TreeSet elements on the console
System.out.println("TreeSet elements are: "); 
for (String temp : ts) 
{ 
System.out.println(temp); 
} 
} 
}

输出

在上面的输出中，我们观察到两点。第一点是元素按自然顺序排序，第二点是重复元素 **Asus** 已被删除。

我们已经深入理解了 HashSet 和 TreeSet。现在，我们将讨论它们之间的区别。