Java TreeSet指南

1.概述

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

2. TreeSet簡介

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

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

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

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

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

因此,讓我們創建一個TreeSet的實例:

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

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

(可選)我們可以使用構造函數構造TreeSet ,該構造函數使我們可以使用ComparableComparator定義元素排序的順序

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

此方法將返回從fromElementtoElement的元素請注意, 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上找到代碼段。

0 條評論,你可以發表評論,我們會進行改進
Comment author placeholder