Java TreeSet

Yake1965 2022-01-07 20:26:31 阅读数:261

java treeset

Java TreeSet

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

  • 它存儲唯一的元素
  • 它不保留元素的插入順序
  • 它按昇序對元素進行排序
  • 它不是線程安全的

在該實現中,對象根據其自然順序以昇序排序和存儲。該 TreeSet 中使用平衡樹,更具體的一個紅黑樹。

簡單地說,作為自平衡二叉搜索樹,二叉樹的每個節點包括一個額外的比特,用於識別紅色或黑色的節點的顏色。在隨後的插入和删除期間,這些“顏色”比特有助於確保樹保持或多或少的平衡。

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

雖然 TreeSet 不是線程安全的,但可以使用 Collections.synchronizedSet() 包裝器在外部進行同步:

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

TreeSet add

可用於將元素添加到一個 TreeSet 中。如果成功添加了元素,則該方法返回 true,否則返回 false。
該方法的聲明只有當 Set 中不存在該元素時才會添加該元素。

Set<String> treeSet = new TreeSet<>();
assertTrue(treeSet.add("String Added"));

該方法的實現細節說明了如何 TreeSet 的內部工作,它如何利用 TreeMap 中的 放方法來存儲元素:

public boolean add(E e) {

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

變量 m 指的是內部支持 TreeMap(注意TreeMap實現了NavigateableMap):

private transient NavigableMap<E, Object> m;

因此,TreeSet 在內部依賴於後備 NavigableMap,當創建 TreeSet 的實例時,它會使用 TreeMap 實例進行初始化:

public TreeSet() {

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

TreeSet contains

檢查一個給定的元素是否存在於一個給定的 TreeSet 中。如果找到該元素,則返回 true,否則返回 false。

Set<String> treeSetContains = new TreeSet<>();
treeSetContains.add("String Added");
assertTrue(treeSetContains.contains("String Added"));

TreeSet remove

從該組中删除指定的元素,如果它是存在。
如果集合包含指定的元素,則此方法返回 true。

Set<String> removeFromTreeSet = new TreeSet<>();
removeFromTreeSet.add("String Added");
assertTrue(removeFromTreeSet.remove("String Added"));

TreeSet clear

從集合中删除所有項

 Set<String> clearTreeSet = new TreeSet<>();
clearTreeSet.add("String Added");
clearTreeSet.clear();
assertTrue(clearTreeSet.isEmpty());

TreeSet size

size() 方法被用於識別存在於該TreeSet中元素的數量。它是API中的基本方法之一:

Set<String> treeSetSize = new TreeSet<>();
treeSetSize.add("String Added");
assertEquals(1, treeSetSize.size());

TreeSet isEmpty()

所述的isEmpty()方法可用於找出如果一個給定的TreeSet的實例是空的或不是:

Set<String> emptyTreeSet = new TreeSet<>();
assertTrue(emptyTreeSet.isEmpty());

TreeSet iterator

所述iterator() 方法返回迭代以昇序過在元件迭代集。

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。

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

如果 Iterator 被創建之後,只能通過迭代器 remove() 方法。其它任何方式在集合上删除元素都將拋出ConcurrentModificationException 异常。

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 方法,那麼我們就不會遇到异常:

Set&lt;String&gt; treeSet = new TreeSet&lt;&gt;();
treeSet.add("First");
treeSet.add("Second");
treeSet.add("Third");
Iterator&lt;String&gt; itr = treeSet.iterator();
while (itr.hasNext()) {

String element = itr.next();
if (element.equals("Second"))
itr.remove();
}
assertEquals(2, treeSet.size());

不能保證迭代器的 fail-fast 事件行為,因為在存在不同步的並發修改時不可能做出任何硬性保證。

fail-fast 機制是 java 集合(Collection)中的一種錯誤機制。當多個線程對同一個集合的內容進行操作時,就可能會產生 fail-fast 事件。例如:當某一個線程 A 通過 iterator 去遍曆某集合的過程中,若該集合的內容被其他線程所改變了;那麼線程 A 訪問集合時,就會拋出 ConcurrentModificationException 异常,產生 fail-fast 事件。

TreeSet first

如果 TreeSet 不為空,則此方法返回 TreeSet 中的第一個元素。否則,它會拋出 NoSuchElementException。

TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("First");
assertEquals("First", treeSet.first());

TreeSet last

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

TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add("Last");
assertEquals("Last", treeSet.last());

TreeSet subSet

此方法將返回從 fromElement 到 toElemen t的元素。

請注意:fromElement是包含的,toElement 是不包含的:

SortedSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);
treeSet.add(4);
treeSet.add(5);
treeSet.add(6);
Set&lt;Integer&gt; expectedSet = new TreeSet&lt;&gt;();
expectedSet.add(2);
expectedSet.add(3);
expectedSet.add(4);
expectedSet.add(5);
Set&lt;Integer&gt; subSet = treeSet.subSet(2, 6);
assertEquals(expectedSet, subSet);

TreeSet headSet()

此方法將返回 TreeSet 的元素,這些元素小於指定的元素:

SortedSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);
treeSet.add(4);
treeSet.add(5);
treeSet.add(6);
Set&lt;Integer&gt; subSet = treeSet.headSet(6);
assertEquals(subSet, treeSet.subSet(1, 6));

TreeSet tailSet()

此方法將返回 TreeSet 的元素,這些元素大於或等於指定的元素:

NavigableSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);
treeSet.add(4);
treeSet.add(5);
treeSet.add(6);
Set&lt;Integer&gt; subSet = treeSet.tailSet(3);
assertEquals(subSet, treeSet.subSet(3, true, 6, true));

存儲空元素

在Java 7之前,可以將空元素添加到空 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)或 comparator.compare(e1,e2) 不得拋出 ClassCastException。

class Element {

private Integer id;
// Other methods...
}
Comparator<Element> comparator = (ele1, ele2) -> {
undefined
return ele1.getId().compareTo(ele2.getId());
};
@Test
public void whenUsingComparator_shouldSortAndInsertElements() {
undefined
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);
}

TreeSet 的性能

與 HashSet 相比,TreeSet 的性能更低。操作,比如添加、删除和搜索需要 O(log n)的時間,而像打印操作 ñ 在有序元素需要 O(n)的時間。

局部性原則 - 是根據存儲器訪問模式,經常訪問相同值或相關存儲比特置的現象的術語。

類似數據通常由具有相似頻率的應用程序訪問
如果給定排序附近有兩個條目,則 TreeSet 將它們放置在數據結構中彼此靠近,因此在內存中
我們可以說一個TreeSet 的數據結構有更大的地方,因此,得出結論:按照局部性原理,我們應該優先考慮一個 TreeSet 的,如果我們短期使用,我們想訪問相對靠近元素根據他們的自然順序相互依賴。

如果需要從硬盤驅動器讀取數據(其延遲大於從緩存或內存中讀取的數據),則更喜歡 TreeSet,因為它具有更大的局部性

模塊 java.base 軟件包 java.util
Class TreeSet

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<E>
java.util.TreeSet<E>

參數類型

E - 此集維護的元素類型
實現的所有接口

Serializable , Cloneable , Iterable<E> , Collection<E> , NavigableSet<E> , Set<E> , SortedSet<E>

public class TreeSet
extends AbstractSet
implements NavigableSet, Cloneable, Serializable
一個NavigableSet實現基於一個TreeMap 。 的元件使用其有序natural ordering ,或由Comparator集合創建時提供,這取决於所使用的構造方法。
此實現提供了基本的操作(保證的log(n)時間成本add , remove和contains )。

請注意,如果要正確實現Set接口,則由集合維護的排序(無論是否提供顯式比較器)必須與equals一致 。 (有關與equals一致的精確定義,請參閱Comparable或Comparator )這是因為Set接口是根據equals操作定義的,但是TreeSet實例使用其compareTo (或compare )方法執行所有元素比較,因此從該集合的角度來看,通過這種方法被認為相等的元素是相等的。 一套的行為是明確的,即使它的排序和equals不一致; 它只是沒有遵守Set接口的一般合同。

請注意,此實現不同步。 如果多個線程同時訪問樹集,並且至少有一個線程修改了該集,則必須在外部進行同步。 這通常通過在自然封裝集合的某個對象上進行同步來實現。 如果不存在此類對象,則應使用Collections.synchronizedSortedSet方法“包裝”該集合 。 這最好在創建時完成,以防止對集合的意外不同步訪問:

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(…));
此類的iterator方法返回的迭代器是快速失敗的 :如果在創建迭代器之後的任何時間修改集合,除了通過迭代器自己的remove方法之外,迭代器將拋出ConcurrentModificationException 。 因此,在並發修改的情况下,迭代器快速而幹淨地失敗,而不是在未來的未確定時間冒任意,非確定性行為的風險。

請注意,迭代器的快速失敗行為無法得到保證,因為一般來說,在存在不同步的並發修改時,不可能做出任何硬性保證。 失敗快速迭代器在盡力而為的基礎上拋出ConcurrentModificationException 。 因此,編寫依賴於此异常的程序以確保其正確性是錯誤的: 迭代器的快速失敗行為應該僅用於檢測錯誤。

此類是 Java Collections Framework 的成員。

TreeSet() 構造一個新的空樹集,根據其元素的自然順序進行排序。
TreeSet​(Collection<? extends E> c) 構造一個新的樹集,其中包含指定集合中的元素,並根據其元素的 自然順序進行排序 。
TreeSet​(Comparator<? super E> comparator) 構造一個新的空樹集,根據指定的比較器進行排序。
TreeSet​(SortedSet s) 構造一個包含相同元素並使用與指定有序集相同排序的新樹集。

boolean add​(E e) 如果指定的元素尚不存在,則將其添加到此集合中。
boolean addAll​(Collection<? extends E> c) 將指定集合中的所有元素添加到此集合中。
E ceiling​(E e) 返回此 set 中大於或等於給定元素的 null 元素,如果沒有這樣的元素,則 null 。
void clear() 從該集中删除所有元素。
Object clone() 返回此 TreeSet實例的淺錶副本。
boolean contains​(Object o) 如果此set包含指定的元素,則返回 true 。
Iterator descendingIterator() 以降序返回此集合中元素的迭代器。
NavigableSet descendingSet() 返回此set中包含的元素的逆序視圖。
E first() 返回此集合中當前的第一個(最低)元素。
E floor​(E e) 返回此set中小於或等於給定元素的最大元素,如果沒有這樣的元素,則 null 。
SortedSet headSet​(E toElement) 返回此 set 的部分視圖,其元素嚴格小於 toElement 。
NavigableSet headSet​(E toElement, boolean inclusive) 返回此 set 的部分視圖,其元素小於(或等於,如果 inclusive為true) toElement 。
E higher​(E e) 返回此集合中的最小元素嚴格大於給定元素,如果沒有這樣的元素,則 null 。
boolean isEmpty() 如果此集合不包含任何元素,則返回 true 。
Iterator iterator() 以昇序返回此集合中元素的迭代器。
E last() 返回此集合中當前的最後一個(最高)元素。
E lower​(E e) 返回此集合中的最大元素嚴格小於給定元素,如果沒有這樣的元素,則 null 。
E pollFirst() 檢索並删除第一個(最低)元素,如果此組為空,則返回 null 。
E pollLast() 檢索並删除最後一個(最高)元素,如果此集合為空,則返回 null 。
boolean remove​(Object o) 如果存在,則從該集合中移除指定的元素。
int size() 返回此集合中的元素數(基數)。
Spliterator spliterator() 在此集合中的元素上創建late-binding和故障快速 Spliterator 。
NavigableSet subSet​(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) 返回此set的部分視圖,其元素範圍為 fromElement到 toElement 。
SortedSet subSet​(E fromElement, E toElement) 返回此set的部分視圖,其元素範圍從 fromElement (含)到 toElement (獨占)。
SortedSet tailSet​(E fromElement) 返回此set的部分視圖,其元素大於或等於 fromElement 。
NavigableSet tailSet​(E fromElement, boolean inclusive) 返回此set的部分視圖,其元素大於(或等於,如果 inclusive為true) fromElement 。

聲明方法的類 java.util.AbstractSet
equals, hashCode, removeAll
聲明方法的類 java.util.AbstractCollection
containsAll, retainAll, toArray, toArray, toString
聲明方法的類 java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
聲明方法的接口 java.util.Collection
parallelStream, removeIf, stream, toArray
聲明方法的接口 java.lang.Iterable
forEach
聲明方法的接口 java.util.Set
containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray
聲明方法的接口 java.util.SortedSet
comparator

版权声明:本文为[Yake1965]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201072026305004.html