1. Overview
1.概述
In this article, we’ll have a look at an integral part of the Java Collections Framework and one of the most popular Set implementations – the TreeSet.
在这篇文章中，我们将看看Java集合框架的一个组成部分和最受欢迎的Set实现之一–TreeSet。
2. Intro to TreeSet
2、TreeSet的介绍
Simply put, the TreeSet is a sorted collection that extends the AbstractSet class and implements the NavigableSet interface.
简单地说，TreeSet是一个分类集合，它扩展了AbstractSet类并实现了NavigableSet接口。
Here’s a quick summary of the most important aspects of this implementation:
下面是对这一实施的最重要方面的快速总结。
- It stores unique elements
- It doesn’t preserve the insertion order of the elements
- It sorts the elements in ascending order
- It’s not thread-safe
In this implementation, objects are sorted and stored in ascending order according to their natural order. The TreeSet uses a self-balancing binary search tree, more specifically a Red-Black tree.
在这个实现中，对象是按照其自然顺序升序排序和存储的。TreeSet使用了一个自我平衡的二进制搜索树，更确切地说，是一个Red-Black树。
Simply put, being a self-balancing binary search tree, each node of the binary tree comprises of an extra bit, which is used to identify the color of the node which is either red or black. During subsequent insertions and deletions, these “color” bits helps in ensuring that the tree remains more or less balanced.
简单地说，作为一个自我平衡的二进制搜索树，二进制树的每个节点都包括一个额外的位，用来识别节点的颜色，即红色或黑色。在随后的插入和删除过程中，这些 “颜色 “位有助于确保树保持或多或少的平衡。
So, let’s create an instance of a TreeSet:
所以，让我们创建一个TreeSet的实例。
Set<String> treeSet = new TreeSet<>();2.1. TreeSet With a Constructor Comparator Param
2.1.带有构造函数比较器参数的TreeSet
Optionally, we can construct a TreeSet with a constructor that lets us define the order in which the elements get sorted by using a Comparable or Comparator:
另外，我们可以用一个构造函数来构造一个TreeSet，让我们通过使用Comparable或Comparator来定义元素的排序顺序：。
Set<String> treeSet = new TreeSet<>(Comparator.comparing(String::length));Although TreeSet isn’t thread-safe, it can be synchronized externally using the Collections.synchronizedSet() wrapper:
尽管TreeSet不是线程安全的，但它可以使用Collections.synchronizedSet()包装器进行外部同步：
Set<String> syncTreeSet = Collections.synchronizedSet(treeSet);Alright, now that we have a clear idea of how to create a TreeSet instance, let’s have a look at the common operations we have available.
好了，现在我们对如何创建一个TreeSet实例有了清晰的概念，让我们看看我们可用的常见操作。
3. TreeSet add()
3.TreeSet add()
The add() method, as expected, can be used for adding elements to a TreeSet. If an element was added, the method returns true, otherwise – false.
add()方法，正如预期的那样，可用于向TreeSet添加元素。如果一个元素被添加，该方法返回true，否则–false。
The contract of the method states that an element will be added only when the same isn’t already present in the Set.
该方法的契约规定，只有在Set中不存在相同的元素时，才会被添加。。
Let’s add an element to a TreeSet:
让我们向TreeSet添加一个元素。
@Test
public void whenAddingElement_shouldAddElement() {
Set<String> treeSet = new TreeSet<>();
assertTrue(treeSet.add("String Added"));
}The add method is extremely important as the implementation details of the method illustrate how the TreeSet works internally, how it leverages the TreeMap’s put method to store the elements:
add方法极其重要，因为该方法的实现细节说明了TreeSet是如何在内部工作的，它如何利用TreeMap的put方法来存储元素。
public boolean add(E e) {
return m.put(e, PRESENT) == null;
}The variable m refers to an internal backing TreeMap (note that TreeMap implements NavigateableMap):
变量m指的是一个内部支持TreeMap（注意，TreeMap实现了NavigateableMap）。
private transient NavigableMap<E, Object> m;Therefore, the TreeSet internally depends on a backing NavigableMap which gets initialized with an instance of TreeMap when an instance of the TreeSet is created:
因此，TreeSet在内部依赖于一个支持NavigableMap，当TreeSet的实例被创建时，该实例会被初始化为TreeMap的实例。
public TreeSet() {
this(new TreeMap<E,Object>());
}More about this can be found in this article.
关于这一点的更多信息可以在这篇文章中找到。
4. TreeSet contains()
4.TreeSet contains()
The contains() method is used to check if a given element is present in a given TreeSet. If the element is found, it returns true, otherwise false.
contains()方法用于检查一个给定的元素是否存在于一个给定的TreeSet中。如果找到该元素，则返回true，否则false.。
Let’s see the contains() in action:
让我们看看contains()的操作。
@Test
public void whenCheckingForElement_shouldSearchForElement() {
Set<String> treeSetContains = new TreeSet<>();
treeSetContains.add("String Added");
assertTrue(treeSetContains.contains("String Added"));
}5. TreeSet remove()
5. TreeSet remove()
The remove() method is used to remove the specified element from the set if it’s present.
remove()方法用于从集合中移除指定的元素（如果它存在）。
If a set contained the specified element, this method returns true.
如果一个集合包含指定的元素，该方法将返回true.。
Let’s see it in action:
让我们看看它的行动。
@Test
public void whenRemovingElement_shouldRemoveElement() {
Set<String> removeFromTreeSet = new TreeSet<>();
removeFromTreeSet.add("String Added");
assertTrue(removeFromTreeSet.remove("String Added"));
}6. TreeSet clear()
6.TreeSet clear()
If we want to remove all the items from a set, we can use the clear() method:
如果我们想从一个集合中删除所有项目，我们可以使用clear()方法。
@Test
public void whenClearingTreeSet_shouldClearTreeSet() {
Set<String> clearTreeSet = new TreeSet<>();
clearTreeSet.add("String Added");
clearTreeSet.clear();
assertTrue(clearTreeSet.isEmpty());
}7. TreeSet size()
7.TreeSet size()
The size() method is used to identify the number of elements present in the TreeSet. It’s one of the fundamental methods in the API:
size()方法用于识别TreeSet中存在的元素数量。它是API中的基本方法之一。
@Test
public void whenCheckingTheSizeOfTreeSet_shouldReturnThesize() {
Set<String> treeSetSize = new TreeSet<>();
treeSetSize.add("String Added");
assertEquals(1, treeSetSize.size());
}8. TreeSet isEmpty()
8.TreeSet isEmpty()
The isEmpty() method can be used to figure out if a given TreeSet instance is empty or not:
isEmpty()方法可以用来计算一个给定的TreeSet实例是否为空。
@Test
public void whenCheckingForEmptyTreeSet_shouldCheckForEmpty() {
Set<String> emptyTreeSet = new TreeSet<>();
assertTrue(emptyTreeSet.isEmpty());
}9. TreeSet iterator()
9.TreeSet iterator()
The iterator() method returns an iterator iterating in the ascending order over the elements in the Set. Those iterators are fail-fast.
iterator()方法返回一个迭代器，该迭代器以升序方式对Set中的元素进行迭代。这些迭代器是快速失败的。
We can observe the ascending iteration order here:
我们可以观察到这里的升序迭代顺序。
@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInAscendingOrder() {
Set<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add("Second");
treeSet.add("Third");
Iterator<String> itr = treeSet.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
}Additionally, TreeSet enables us to iterate through the Set in descending order.
此外，TreeSet使我们能够以降序的方式迭代Set。
Let’s see that in action:
让我们看看这一点的行动。
@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInDescendingOrder() {
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add("Second");
treeSet.add("Third");
Iterator<String> itr = treeSet.descendingIterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
}The Iterator throws a ConcurrentModificationException if the set is modified at any time after the iterator is created in any way except through the iterator’s remove() method.
迭代器抛出ConcurrentModificationException i如果在迭代器创建后的任何时候，除了通过迭代器的remove()方法外，集合被修改。
Let’s create a test for this:
让我们为此创建一个测试。
@Test(expected = ConcurrentModificationException.class)
public void whenModifyingTreeSetWhileIterating_shouldThrowException() {
Set<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add("Second");
treeSet.add("Third");
Iterator<String> itr = treeSet.iterator();
while (itr.hasNext()) {
itr.next();
treeSet.remove("Second");
}
}
Alternatively, if we had used the iterator’s remove method, then we wouldn’t have encountered the exception:
另外，如果我们使用了迭代器的移除方法，那么我们就不会遇到这个异常了。
@Test
public void whenRemovingElementUsingIterator_shouldRemoveElement() {
Set<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add("Second");
treeSet.add("Third");
Iterator<String> itr = treeSet.iterator();
while (itr.hasNext()) {
String element = itr.next();
if (element.equals("Second"))
itr.remove();
}
assertEquals(2, treeSet.size());
}There’s no guarantee on the fail-fast behavior of an iterator as it’s impossible to make any hard guarantees in the presence of unsynchronized concurrent modification.
对于迭代器的故障快速行为没有任何保证，因为在存在非同步并发修改的情况下，不可能做出任何硬性保证。
More about this can be found here.
关于这一点的更多信息可以在这里找到。
10. TreeSet first()
10.TreeSet first()
This method returns the first element from a TreeSet if it’s not empty. Otherwise, it throws a NoSuchElementException.
如果一个TreeSet不是空的，这个方法将返回它的第一个元素。否则，它会抛出一个NoSuchElementException。
Let’s see an example:
让我们看一个例子。
@Test
public void whenCheckingFirstElement_shouldReturnFirstElement() {
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("First");
assertEquals("First", treeSet.first());
}11. TreeSet last()
11.TreeSet last()
Analogously to the above example, this method will return the last element if the set is not empty:
与上面的例子类似，如果这个集合不是空的，这个方法将返回最后一个元素。
@Test
public void whenCheckingLastElement_shouldReturnLastElement() {
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add("Last");
assertEquals("Last", treeSet.last());
}12. TreeSet subSet()
12.TreeSet subSet()
This method will return the elements ranging from fromElement to toElement. Note that fromElement is inclusive and toElement is exclusive:
这个方法将返回从fromElement到toElement的元素。注意，fromElement是包容的，toElement是排他的。
@Test
public void whenUsingSubSet_shouldReturnSubSetElements() {
SortedSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);
treeSet.add(4);
treeSet.add(5);
treeSet.add(6);
Set<Integer> expectedSet = new TreeSet<>();
expectedSet.add(2);
expectedSet.add(3);
expectedSet.add(4);
expectedSet.add(5);
Set<Integer> subSet = treeSet.subSet(2, 6);
assertEquals(expectedSet, subSet);
}13. TreeSet headSet()
13.TreeSet headSet()
This method will return elements of TreeSet which are smaller than the specified element:
此方法将返回TreeSet中比指定元素小的元素。
@Test
public void whenUsingHeadSet_shouldReturnHeadSetElements() {
SortedSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);
treeSet.add(4);
treeSet.add(5);
treeSet.add(6);
Set<Integer> subSet = treeSet.headSet(6);
assertEquals(subSet, treeSet.subSet(1, 6));
}14. TreeSet tailSet()
14.TreeSet tailSet()
This method will return the elements of a TreeSet which are greater than or equal to the specified element:
这个方法将返回TreeSet中大于或等于指定元素的元素。
@Test
public void whenUsingTailSet_shouldReturnTailSetElements() {
NavigableSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);
treeSet.add(4);
treeSet.add(5);
treeSet.add(6);
Set<Integer> subSet = treeSet.tailSet(3);
assertEquals(subSet, treeSet.subSet(3, true, 6, true));
}15. Storing Null Elements
15.存储Null元素
Before Java 7, it was possible to add null elements to an empty TreeSet.
在Java 7之前，可以在一个空的TreeSet中添加null elements。
However, that was considered a bug. Therefore, TreeSet no longer supports the addition of null.
然而，这被认为是一个错误。因此，TreeSet不再支持添加null.。
When we add elements to the TreeSet, the elements get sorted according to their natural order or as specified by the comparator. Hence adding a null, when compared to existing elements, results in a NullPointerException since null cannot be compared to any value:
当我们向TreeSet添加元素时，元素会根据它们的自然顺序或比较器指定的顺序进行排序。因此，添加null，与现有元素进行比较时，会导致NullPointerException，因为null无法与任何值进行比较。
@Test(expected = NullPointerException.class)
public void whenAddingNullToNonEmptyTreeSet_shouldThrowException() {
Set<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add(null);
}Elements inserted into the TreeSet must either implement the Comparable interface or at least be accepted by the specified comparator. All such elements must be mutually comparable, i.e. e1.compareTo(e2) or comparator.compare(e1, e2) mustn’t throw a ClassCastException.
插入TreeSet的元素必须实现Comparable接口或者至少被指定的比较器接受。所有这些元素必须是相互可比的， i.e. e1.compareTo(e2)或者comparator.compare(e1, e2) 不能抛出ClassCastException。
Let’s see an example:
让我们看一个例子。
class Element {
private Integer id;
// Other methods...
}
Comparator<Element> comparator = (ele1, ele2) -> {
return ele1.getId().compareTo(ele2.getId());
};
@Test
public void whenUsingComparator_shouldSortAndInsertElements() {
Set<Element> treeSet = new TreeSet<>(comparator);
Element ele1 = new Element();
ele1.setId(100);
Element ele2 = new Element();
ele2.setId(200);
treeSet.add(ele1);
treeSet.add(ele2);
System.out.println(treeSet);
}16. Performance of TreeSet
16.TreeSet的性能
When compared to a HashSet the performance of a TreeSet is on the lower side. Operations like add, remove and search take O(log n) time while operations like printing n elements in sorted order require O(n) time.
与HashSet相比，TreeSet的性能偏低。像添加、删除和搜索这样的操作需要O(log n)时间，而像按照排序顺序打印n元素这样的操作需要O(n)时间。
A TreeSet should be our primary choice if we want to keep our entries sorted as a TreeSet may be accessed and traversed in either ascending or descending order, and the performance of ascending operations and views is likely to be faster than that of descending ones.
如果我们想保持条目排序，TreeSet应该是我们的主要选择，因为TreeSet可以按升序或降序进行访问和遍历，而且升序操作和视图的性能可能比降序操作和视图的性能更快。
The Principle of Locality – is a term for the phenomenon in which the same values, or related storage locations, are frequently accessed, depending on the memory access pattern.
定位原则–是一个术语，指的是根据内存访问模式，经常访问相同的值或相关的存储位置的现象。
When we say locality:
当我们说地方性的时候。
- Similar data is often accessed by an application with similar frequency
- If two entries are nearby given an ordering, a TreeSet places them near each other in the data structure, and hence in memory
A TreeSet being a data-structure with greater locality we can, therefore, conclude in accordance to the Principle of Locality, that we should give preference to a TreeSet if we’re short on memory and if we want to access elements that are relatively close to each other according to their natural ordering.
树集是一个具有更大的位置性的数据结构，因此，根据位置性原则，我们可以得出结论，如果我们的内存不足，如果我们想要访问那些按照自然排序相对接近的元素，我们应该优先选择树集。
In case data needs to be read from the hard drive (which has greater latency than data read from the cache or memory) then prefer TreeSet as it has greater locality
如果数据需要从硬盘中读取（比从缓存或内存中读取的数据有更大的延迟），那么最好选择TreeSet，因为它有更大的定位性。
17. Conclusion
17.结论
In this article, we focus on understanding how to use the standard TreeSet implementation in Java. We saw its purpose and how efficient it is regarding usability given its ability to avoid duplicates and sort elements.
在这篇文章中，我们重点了解如何使用Java中的标准TreeSet实现。我们看到了它的目的，以及鉴于其避免重复和对元素进行排序的能力，它在可用性方面的效率如何。
As always, code snippets can be found over on GitHub.
像往常一样，代码片段可以在GitHub上找到over。