1. 概述
在本文中，我们将比较java.util.Set接口的两个最流行的Java实现–HashSet和TreeSet。
2. 差异
HashSet和TreeSet是同一分支的叶子，但它们在一些重要问题上有所不同。
2.1 顺序
HashSet以随机顺序存储对象，而TreeSet应用元素的自然顺序。让我们看下面的例子：
@Test
public void givenTreeSet_whenRetrievesObjects_thenNaturalOrder() {
Set<String> set = new TreeSet<>();
set.add("Tuyucheng");
set.add("is");
set.add("Awesome");
assertEquals(3, set.size());
assertTrue(set.iterator().next().equals("Awesome"));
}
将String对象添加到TreeSet后，我们看到第一个是“Awesome”，尽管它是在最后添加的。使用HashSet完成的类似操作不能保证元素的顺序随时间保持不变。
2.2 空对象
另一个区别是HashSet可以存储空对象，而TreeSet不允许：
@Test(expected = NullPointerException.class)
public void givenTreeSet_whenAddNullObject_thenNullPointer() {
Set<String> set = new TreeSet<>();
set.add("Tuyucheng");
set.add("is");
set.add(null);
}
@Test
public void givenHashSet_whenAddNullObject_thenOK() {
Set<String> set = new HashSet<>();
set.add("Tuyucheng");
set.add("is");
set.add(null);
assertEquals(3, set.size());
}
如果我们尝试将null对象存储在TreeSet中，该操作将导致抛出NullPointerException。唯一的例外是在Java 7中，允许在TreeSet中恰好有一个null元素。
2.3 性能
简单地说，HashSet比TreeSet快。
HashSet为add()、remove()和contains()等大多数操作提供恒定时间性能，而TreeSet提供的时间为log(n)。
通常，我们可以看到将元素添加到TreeSet中的执行时间比HashSet要长得多。
请记住，JVM可能没有预热，因此执行时间可能会有所不同。此处提供了关于如何使用各种Set实现来设计和执行微基准测试的很好的讲解。
2.4 实现的法
TreeSet具有丰富的功能，可实现其他方法，例如：
- pollFirst()：返回第一个元素，如果Set为空则返回null
- pollLast()：检索并删除最后一个元素，如果Set为空则返回null
- first()：返回第一项
- last()：返回最后一项
- ceiling()：返回大于或等于给定元素的最小元素，如果没有这样的元素则返回null
- lower()：返回严格小于给定元素的最大元素，如果没有这样的元素则返回null
上面提到的方法使得TreeSet比HashSet更容易使用并且更强大。
3. 相似之处
3.1 唯一元素
TreeSet和HashSet都保证元素的无重复集合，因为它是通用Set接口的一部分：
@Test
public void givenHashSetAndTreeSet_whenAddDuplicates_thenOnlyUnique() {
Set<String> set = new HashSet<>();
set.add("Tuyucheng");
set.add("Tuyucheng");
assertTrue(set.size() == 1);
Set<String> set2 = new TreeSet<>();
set2.add("Tuyucheng");
set2.add("Tuyucheng");
assertTrue(set2.size() == 1);
}
3.2 非同步
所描述的Set实现都不是同步的。这意味着如果多个线程并发访问一个Set，并且至少有一个线程修改了它，那么它必须在外部同步。
3.3 快速失败迭代器
TreeSet和HashSet返回的Iterator是快速失败的。
这意味着在创建Iterator之后任何时候对Set的任何修改都将抛出ConcurrentModificationException：
@Test(expected = ConcurrentModificationException.class)
public void givenHashSet_whenModifyWhenIterator_thenFailFast() {
Set<String> set = new HashSet<>();
set.add("Tuyucheng");
Iterator<String> it = set.iterator();
while (it.hasNext()) {
set.add("Awesome");
it.next();
}
}
4. 使用哪个实现？
两种实现都满足集合概念的约定，因此这取决于我们可能使用哪种实现的上下文。
以下是需要记住的几个要点：
- 如果我们想保持元素排序，我们需要使用TreeSet
- 如果我们更看重性能而不是内存消耗，我们应该选择HashSet
- 如果我们内存不足，我们应该选择TreeSet
- 如果我们想根据自然顺序访问彼此相对接近的元素，我们可能要考虑TreeSet，因为它具有更大的局部性
- HashSet的性能可以使用initialCapacity和loadFactor进行调整，这对于TreeSet是不可能的
- 如果我们想保留插入顺序并从恒定时间访问中受益，我们可以使用LinkedHashSet
5. 总结
在本文中，我们介绍了TreeSet和HashSet之间的异同。
与往常一样，本教程的完整源代码可在GitHub上获得。
Post Directory
