HashSet and TreeSet Comparison – HashSet和TreeSet的比较

最后修改: 2017年 4月 28日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.介绍

In this article, we’re going to compare two of the most popular Java implementations of the java.util.Set interface – HashSet and TreeSet.

在这篇文章中，我们将比较java.util.Set接口的两个最流行的Java实现–HashSet和TreeSet。

2. Differences

2.差异

HashSet and TreeSet are leaves of the same branch, but they differ in few important matters.

HashSet和TreeSet是同一个分支的叶子，但是它们在一些重要的事情上有所不同。

2.1. Ordering

2.1.订购

HashSet stores the objects in random order, whereas TreeSet applies the natural order of the elements. Let’s see the following example:

HashSet以随机顺序存储对象，而TreeSet应用元素的自然顺序。让我们看看下面的例子。

@Test
public void givenTreeSet_whenRetrievesObjects_thenNaturalOrder() {
    Set<String> set = new TreeSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add("Awesome");
 
    assertEquals(3, set.size());
    assertTrue(set.iterator().next().equals("Awesome"));
}

After adding the String objects into TreeSet, we see that the first one is “Awesome”, even though it was added at the very end. A similar operation done with HashSet does not guarantee that the order of elements will remain constant over time.

在将String对象添加到TreeSet中后，我们看到第一个对象是 “真棒”，尽管它是在最末端添加的。用HashSet进行的类似操作并不能保证元素的顺序在一段时间内保持不变。

2.2. Null Objects

2.2.Null对象

Another difference is that HashSet can store null objects, while TreeSet does not allow them:

另一个区别是，HashSet可以存储null对象，而TreeSet不允许这样做。

@Test(expected = NullPointerException.class)
public void givenTreeSet_whenAddNullObject_thenNullPointer() {
    Set<String> set = new TreeSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add(null);
}

@Test
public void givenHashSet_whenAddNullObject_thenOK() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add(null);
 
    assertEquals(3, set.size());
}

If we try to store the null object in a TreeSet, the operation will result in a thrown NullPointerException. The only exception was in Java 7 when it was allowed to have exactly one null element in the TreeSet.

如果我们试图将null对象存储在TreeSet中，该操作将导致抛出NullPointerException。唯一的例外是在Java 7中，当时允许在TreeSet中正好有一个null元素。

2.3. Performance

2.3.性能

Simply put, HashSet is faster than the TreeSet.

简单地说，HashSet比TreeSet快。。

HashSet provides constant-time performance for most operations like add(), remove() and contains(), versus the log(n) time offered by the TreeSet.

HashSet为大多数操作（如add()、remove()和contains()）提供了恒定的时间性能，而TreeSet则提供了log（n）时间。

Usually, we can see that the execution time for adding elements into TreeSet is much more than for the HashSet.

通常，我们可以看到，向TreeSet添加元素的执行时间要比HashSet多。

Please remember that the JVM might be not warmed up, so the execution times can differ. A good discussion how to design and perform micro tests using various Set implementations is available here.

请记住，JVM可能没有预热，所以执行时间可能不同。关于如何使用各种Set实现来设计和执行微测试的良好讨论可在这里。

2.4. Implemented Methods

2.4.已实现的方法

TreeSet is rich in functionalities, implementing additional methods like:

TreeSet具有丰富的功能，实现了额外的方法，如。

  • pollFirst() – to return the first element, or null if Set is empty
  • pollLast() – to retrieve and remove the last element, or return null if Set is empty
  • first() – to return the first item
  • last() – to return the last item
  • ceiling() – to return the least element greater than or equal to the given element, or null if there is no such element
  • lower() – to return the largest element strictly less than the given element, or null if there is no such element

The methods mentioned above make TreeSet much easier to use and more powerful than HashSet.

上面提到的方法使TreeSet比HashSet更容易使用，更强大。

3. Similarities

3.相似之处

3.1. Unique Elements

<3.1.独特的元素

Both TreeSet and HashSet guarantee a duplicate-free collection of elements, as it is a part of the generic Set interface:

TreeSet和HashSet都保证无重复的元素集合，因为它是通用Set接口的一部分。

@Test
public void givenHashSetAndTreeSet_whenAddDuplicates_thenOnlyUnique() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    set.add("Baeldung");
 
    assertTrue(set.size() == 1);
        
    Set<String> set2 = new TreeSet<>();
    set2.add("Baeldung");
    set2.add("Baeldung");
 
    assertTrue(set2.size() == 1);
}

3.2. Not synchronized

3.2.没有同步

None of the described Set implementations are synchronized. This means that if multiple threads access a Set concurrently, and at least one of the threads modifies it, then it must be synchronized externally.

所描述的Set实现都不是同步的。这意味着，如果多个线程同时访问一个Set，并且至少有一个线程修改了它，那么它必须在外部进行同步。

3.3. Fail-fast Iterators

3.3.失败快速的迭代器

The Iterators returned by TreeSet and HashSet are fail-fast.

由TreeSet和HashSet返回的Iterator是失败快速的。

That means that any modification of the Set at any time after the Iterator is created will throw a ConcurrentModificationException:

这意味着在迭代器创建后的任何时候对集合的任何修改都将抛出ConcurrentModificationException：。

@Test(expected = ConcurrentModificationException.class)
public void givenHashSet_whenModifyWhenIterator_thenFailFast() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    Iterator<String> it = set.iterator();

    while (it.hasNext()) {
        set.add("Awesome");
        it.next();
    }
}

4. Which Implementation to Use?

4.使用哪种实施方式？

Both implementations fulfill the contract of the idea of a set so it’s up to the context which implementation we might use.

这两种实现都履行了集合的概念的契约，所以我们可能会使用哪种实现，这取决于环境。

Here are few quick points to remember:

这里有几个需要快速记住的要点。

  • If we want to keep our entries sorted, we need to go for the TreeSet
  • If we value performance more than memory consumption, we should go for the HashSet
  • If we are short on memory, we should go for the TreeSet
  • If we want to access elements that are relatively close to each other according to their natural ordering, we might want to consider TreeSet because it has greater locality
  • HashSet‘s performance can be tuned using the initialCapacity and loadFactor, which is not possible for the TreeSet
  • If we want to preserve insertion order and benefit from constant time access, we can use the LinkedHashSet

5. Conclusion

5.结论

In this article, we covered the differences and similarities between TreeSet and HashSet.

在这篇文章中，我们介绍了TreeSet和HashSet之间的异同。

As always, the code examples for this article are available over on GitHub.

像往常一样，本文的代码示例可在GitHub上获得。