Java TreeSet指南

1.概述

在本文中，我們將研究Java Collections Framework的組成部分以及最流行的Set實現之一：TreeSet 。

2. TreeSet簡介

簡而言之， TreeSet是一個有序集合，它擴展了AbstractSet類並實現了NavigableSet接口。

這是此實現最重要方面的快速摘要：

• 它存儲了獨特的元素，不會有重複元素
• 它不保留元素的插入順序
• 它將元素按升序排序
• 它不是線程安全的

在此實現中，對象按照其自然順序升序排序並存儲。 TreeSet使用自平衡的二進制搜索樹，更具體地說是紅黑樹。

簡而言之，作為自平衡二進制搜索樹，二進制樹的每個節點都包含一個額外的位，用於標識該節點的顏色是紅色還是黑色。在隨後的插入和刪除過程中，這些“顏色”位有助於確保樹保持或多或少的平衡。

因此，讓我們創建一個TreeSet的實例：

Set<String> treeSet = new TreeSet<>();

2.1。具有構造函數比較器參數的TreeSet

（可選）我們可以使用構造函數構造TreeSet ，該構造函數使我們可以使用Comparable或Comparator定義元素排序的順序：

Set<String> treeSet = new TreeSet<>(Comparator.comparing(String::length));

儘管TreeSet不是線程安全的，但可以使用Collections.synchronizedSet()包裝器在外部對其進行同步：

Set<String> syncTreeSet = Collections.synchronizedSet(treeSet);

好了，既然我們對如何創建TreeSet實例有了清晰的了解，讓我們看一下可用的常見操作。

3. TreeSet add()

如預期的那樣， add（）方法可用於將元素添加到TreeSet中。如果添加了元素，則該方法返回true，否則返回false。

該方法的約定規定，僅當Set中尚未存在元素時才添加該元素。

讓我們向TreeSet添加一個元素：

@Test

 public void whenAddingElement_shouldAddElement() {

 Set<String> treeSet = new TreeSet<>();



 assertTrue(treeSet.add("String Added"));

 }

add方法非常重要，因為該方法的實現細節說明TreeSet在內部如何工作，如何利用TreeMap的**put方法存儲元素：

public boolean add(E e) {

 return m.put(e, PRESENT) == null;

 }

變量m表示內部支持TreeMap （請注意， TreeMap實現了NavigateableMap ）：

private transient NavigableMap<E, Object> m;

因此， TreeSet在內部依賴於支持的NavigableMap ，該NavigableMap在創建TreeSet的實例時使用TreeMap的實例進行初始化：

public TreeSet() {

 this(new TreeMap<E,Object>());

 }

4. TreeSet contains()

contains（）方法用於檢查給定TreeSet中是否存在給定元素。如果找到該元素，則返回true，否則返回false。

讓我們看一下contains（）的作用：

@Test

 public void whenCheckingForElement_shouldSearchForElement() {

 Set<String> treeSetContains = new TreeSet<>();

 treeSetContains.add("String Added");



 assertTrue(treeSetContains.contains("String Added"));

 }

5. TreeSet remove()

remove（）方法用於從集中刪除指定的元素（如果存在）。

如果集合包含指定的元素，則此方法返回true。

讓我們看看它的作用：

@Test

 public void whenRemovingElement_shouldRemoveElement() {

 Set<String> removeFromTreeSet = new TreeSet<>();

 removeFromTreeSet.add("String Added");



 assertTrue(removeFromTreeSet.remove("String Added"));

 }

6. TreeSet clear()

如果要刪除集合中的所有項目，可以使用clear（）方法：

@Test

 public void whenClearingTreeSet_shouldClearTreeSet() {

 Set<String> clearTreeSet = new TreeSet<>();

 clearTreeSet.add("String Added");

 clearTreeSet.clear();



 assertTrue(clearTreeSet.isEmpty());

 }

7. TreeSet size()

size（）方法用於標識TreeSet中存在的元素數。這是API中的基本方法之一：

@Test

 public void whenCheckingTheSizeOfTreeSet_shouldReturnThesize() {

 Set<String> treeSetSize = new TreeSet<>();

 treeSetSize.add("String Added");



 assertEquals(1, treeSetSize.size());

 }

8. TreeSet isEmpty()

isEmpty（）方法可用於確定給定的TreeSet實例是否為空：

@Test

 public void whenCheckingForEmptyTreeSet_shouldCheckForEmpty() {

 Set<String> emptyTreeSet = new TreeSet<>();



 assertTrue(emptyTreeSet.isEmpty());

 }

9. TreeSet的iterator()

iterator（）方法返回一個Set元素上升序迭代的迭代器。**這些迭代器是快速失敗的**。

我們可以在這裡觀察升序：

@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());

 }

 }

此外， TreeSet使我們能夠以降序遍歷Set 。

讓我們看看實際情況：

@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());

 }

 }

如果通過迭代器的remove（）方法以外的任何方式創建了迭代器，則在修改集合後，迭代器都會引發ConcurrentModificationException 。

讓我們為此做一個測試：

@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");

 }

 }

另外，如果我們使用了迭代器的remove方法，那麼我們就不會遇到異常：

@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());

 }

不能保證迭代器的快速失敗行為，因為在存在不同步的並發修改的情況下不可能做出任何嚴格的保證。

有關更多信息，請參見此處。

10. TreeSet first()

如果不為空，則此方法從TreeSet返回第一個元素。否則，將引發NoSuchElementException 。

讓我們來看一個例子：

@Test

 public void whenCheckingFirstElement_shouldReturnFirstElement() {

 TreeSet<String> treeSet = new TreeSet<>();

 treeSet.add("First");



 assertEquals("First", treeSet.first());

 }

11. TreeSet last()

與上面的示例類似，如果集合不為空，則此方法將返回最後一個元素：

@Test

 public void whenCheckingLastElement_shouldReturnLastElement() {

 TreeSet<String> treeSet = new TreeSet<>();

 treeSet.add("First");

 treeSet.add("Last");



 assertEquals("Last", treeSet.last());

 }

12. TreeSet subSet()

此方法將返回從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()

此方法將返回小於指定元素的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()

此方法將返回大於或等於指定元素的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.存儲空元素

在Java 7之前，可以將null元素添加到空的****TreeSet中。

但是，這被認為是一個錯誤。因此， TreeSet不再支持添加null。

當我們將元素添加到TreeSet時，元素將根據其自然順序或由比較器指定的順序進行排序。因此，與現有元素相比，添加null會導致NullPointerException，因為null無法與任何值進行比較：

@Test(expected = NullPointerException.class)

 public void whenAddingNullToNonEmptyTreeSet_shouldThrowException() {

 Set<String> treeSet = new TreeSet<>();

 treeSet.add("First");

 treeSet.add(null);

 }

插入TreeSet中的元素必須實現Comparable接口，或者至少被指定的比較器接受。所有這些元素都必須相互可比較，*即**e1.compareTo（e2）或比較器*.compare （e1，e2）**不得拋出ClassCastException 。**

讓我們來看一個例子：

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. TreeSet的性能

與HashSet相比， TreeSet的性能較低。諸如添加，刪除和搜索之類的操作需要O（log n）的時間，而按已排序順序打印n個元素的操作則需要O（n）的時間。

如果要使條目保持排序狀態，則TreeSet應該是我們的主要選擇，因為TreeSet可以按升序或降序訪問和遍歷，並且升序操作和視圖的性能可能比降序的操作和視圖更快。

局部性原理–是一種現象的術語，其中取決於存儲器訪問模式，經常訪問相同的值或相關的存儲位置。

當我們說地點：

• 應用程序經常以相似的頻率訪問相似的數據
• 如果有兩個條目在附近排序，則TreeSet會將它們在數據結構中並排放置在內存中

TreeSet是具有更大局部性的數據結構，因此，我們可以根據局部性原理得出結論，如果我們內存不足並且要訪問相對較近的元素，則應該優先考慮TreeSet彼此按照其自然順序排列。

如果需要從硬盤驅動器讀取數據（延遲時間比從緩存或內存讀取的數據長），則首選TreeSet，因為它具有更大的局部性

17.結論

在本文中，我們著重於了解如何在Java中使用標準TreeSet實現。考慮到它避免重複和排序元素的能力，我們看到了它的目的以及它在可用性方面的效率。

與往常一樣，可以在GitHub上找到代碼段。