Java中的TreeSet集合詳解

更新時(shí)間：2023年09月13日 09:53:00 作者：Yake1965

這篇文章主要介紹了Java中的TreeSet集合詳解,TreeSet 是一個(gè) 有序集合,它擴(kuò)展了 AbstractSet 類并實(shí)現(xiàn)了 NavigableSet 接口,作為自平衡二叉搜索樹,二叉樹的每個(gè)節(jié)點(diǎn)包括一個(gè)額外的位,用于識(shí)別紅色或黑色的節(jié)點(diǎn)的顏色,需要的朋友可以參考下

TreeSet

TreeSet 是一個(gè) 有序集合，它擴(kuò)展了 AbstractSet 類并實(shí)現(xiàn)了 NavigableSet 接口。

它存儲(chǔ)唯一的元素它不保留元素的插入順序它按升序?qū)υ剡M(jìn)行排序它不是線程安全的

在該實(shí)現(xiàn)中，對(duì)象根據(jù)其自然順序以升序排序和存儲(chǔ)。該 TreeSet 中使用 平衡樹，更具體的一個(gè) 紅黑樹。

簡單地說，作為 自平衡二叉搜索樹，二叉樹的每個(gè)節(jié)點(diǎn)包括一個(gè)額外的位，用于識(shí)別紅色或黑色的節(jié)點(diǎn)的顏色。在隨后的插入和刪除期間，這些“顏色”位有助于確保樹保持或多或少的平衡。

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

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

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

TreeSet add

可用于將元素添加到一個(gè) TreeSet 中。如果成功添加了元素，則該方法返回 true，否則返回 false。該方法的聲明只有當(dāng) Set 中不存在該元素時(shí)才會(huì)添加該元素。

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

該方法的實(shí)現(xiàn)細(xì)節(jié)說明了如何 TreeSet 的內(nèi)部工作，它如何利用 TreeMap 中的放方法來存儲(chǔ)元素：

public boolean add(E e) {
    return m.put(e, PRESENT) == null;
}

變量 m 指的是內(nèi)部支持 TreeMap（注意TreeMap實(shí)現(xiàn)了NavigateableMap）：

private transient NavigableMap<E, Object> m;

因此，TreeSet 在內(nèi)部依賴于后備 NavigableMap，當(dāng)創(chuàng)建 TreeSet 的實(shí)例時(shí)，它會(huì)使用 TreeMap 實(shí)例進(jìn)行初始化：

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

TreeSet contains

檢查一個(gè)給定的元素是否存在于一個(gè)給定的 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

從集合中刪除所有項(xiàng)

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

TreeSet size

size() 方法被用于識(shí)別存在于該TreeSet中元素的數(shù)量。它是API中的基本方法之一：

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

TreeSet isEmpty（）

所述的isEmpty（）方法可用于找出如果一個(gè)給定的TreeSet的實(shí)例是空的或不是：

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 被創(chuàng)建之后，只能通過迭代器 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 方法，那么就不會(huì)遇到異常：

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 事件行為，因?yàn)樵诖嬖诓煌降牟l(fā)修改時(shí)不可能做出任何硬性保證。

fail-fast 機(jī)制是 java 集合(Collection)中的一種錯(cuò)誤機(jī)制。當(dāng)多個(gè)線程對(duì)同一個(gè)集合的內(nèi)容進(jìn)行操作時(shí)，就可能會(huì)產(chǎn)生 fail-fast 事件。例如：當(dāng)某一個(gè)線程 A 通過 iterator 去遍歷某集合的過程中，若該集合的內(nèi)容被其他線程所改變了；那么線程 A 訪問集合時(shí)，就會(huì)拋出 ConcurrentModificationException 異常，產(chǎn)生 fail-fast 事件。

TreeSet first

如果 TreeSet 不為空，則此方法返回 TreeSet 中的第一個(gè)元素。否則，它會(huì)拋出 NoSuchElementException。

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

TreeSet last

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

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

TreeSet subSet

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

請(qǐng)注意：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));

存儲(chǔ)空元素

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

但是，這被認(rèn)為是一個(gè)錯(cuò)誤。因此，TreeSet 不再支持添加 null。

當(dāng)我們向 TreeSet 添加元素時(shí)，元素將根據(jù)其自然順序或比較器指定的方式進(jìn)行排序。因此，與現(xiàn)有元素相比，添加 null 會(huì)導(dǎo)致 NullPointerException，因?yàn)?null 無法與任何值進(jìn)行比較：

@Test(expected = NullPointerException.class)
public void whenAddingNullToNonEmptyTreeSet_shouldThrowException() {
    Set<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add(null);
}

插入 TreeSet 的元素必須實(shí)現(xiàn) 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）的時(shí)間，而像打印操作 ñ 在有序元素需要 O（n）的時(shí)間。

局部性原則 - 是根據(jù)存儲(chǔ)器訪問模式，經(jīng)常訪問相同值或相關(guān)存儲(chǔ)位置的現(xiàn)象的術(shù)語。

類似數(shù)據(jù)通常由具有相似頻率的應(yīng)用程序訪問如果給定排序附近有兩個(gè)條目，則 TreeSet 將它們放置在數(shù)據(jù)結(jié)構(gòu)中彼此靠近，因此在內(nèi)存中我們可以說一個(gè)TreeSet 的數(shù)據(jù)結(jié)構(gòu)有更大的地方，因此，得出結(jié)論：按照局部性原理，我們應(yīng)該優(yōu)先考慮一個(gè) TreeSet 的，如果我們短期使用，我們想訪問相對(duì)靠近元素根據(jù)他們的自然順序相互依賴。

如果需要從硬盤驅(qū)動(dòng)器讀取數(shù)據(jù)（其延遲大于從緩存或內(nèi)存中讀取的數(shù)據(jù)），則更喜歡 TreeSet，因?yàn)樗哂懈蟮木植啃?/p>

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

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

參數(shù)類型

E - 此集維護(hù)的元素類型實(shí)現(xiàn)的所有接口

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

public class TreeSet extends AbstractSet implements NavigableSet, Cloneable, Serializable

一個(gè)NavigableSet實(shí)現(xiàn)基于一個(gè)TreeMap 。的元件使用其有序natural ordering ，或由Comparator集合創(chuàng)建時(shí)提供，這取決于所使用的構(gòu)造方法。此實(shí)現(xiàn)提供了基本的操作（保證的log（n）時(shí)間成本add ， remove和contains ）。

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

請(qǐng)注意，此實(shí)現(xiàn)不同步。如果多個(gè)線程同時(shí)訪問樹集，并且至少有一個(gè)線程修改了該集，則必須在外部進(jìn)行同步。這通常通過在自然封裝集合的某個(gè)對(duì)象上進(jìn)行同步來實(shí)現(xiàn)。如果不存在此類對(duì)象，則應(yīng)使用Collections.synchronizedSortedSet方法“包裝”該集合。這最好在創(chuàng)建時(shí)完成，以防止對(duì)集合的意外不同步訪問：

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(…)); 此類的iterator方法返回的迭代器是快速失敗的：如果在創(chuàng)建迭代器之后的任何時(shí)間修改集合，除了通過迭代器自己的remove方法之外，迭代器將拋出ConcurrentModificationException 。因此，在并發(fā)修改的情況下，迭代器快速而干凈地失敗，而不是在未來的未確定時(shí)間冒任意，非確定性行為的風(fēng)險(xiǎn)。

請(qǐng)注意，迭代器的快速失敗行為無法得到保證，因?yàn)橐话銇碚f，在存在不同步的并發(fā)修改時(shí)，不可能做出任何硬性保證。失敗快速迭代器在盡力而為的基礎(chǔ)上拋出ConcurrentModificationException 。因此，編寫依賴于此異常的程序以確保其正確性是錯(cuò)誤的：迭代器的快速失敗行為應(yīng)該僅用于檢測錯(cuò)誤。

Java Collections Framework 的成員

TreeSet()	//構(gòu)造一個(gè)新的空樹集，根據(jù)其元素的自然順序進(jìn)行排序。
TreeSet?(Collection<? extends E> c)	//構(gòu)造一個(gè)新的樹集，其中包含指定集合中的元素，并根據(jù)其元素的 自然順序進(jìn)行排序 。
TreeSet?(Comparator<? super E> comparator)	//構(gòu)造一個(gè)新的空樹集，根據(jù)指定的比較器進(jìn)行排序。
TreeSet?(SortedSet<E> s)	 //構(gòu)造一個(gè)包含相同元素并使用與指定有序集相同排序的新樹集。
boolean	add?(E e)	//如果指定的元素尚不存在，則將其添加到此集合中。
boolean	addAll?(Collection<? extends E> c)	//將指定集合中的所有元素添加到此集合中。
E	pollFirst()	//檢索并刪除第一個(gè)（最低）元素，如果此組為空，則返回 null 。
E	pollLast()	//檢索并刪除最后一個(gè)（最高）元素，如果此集合為空，則返回 null 。
boolean remove?(Object o)	//如果存在，則從該集合中移除指定的元素。
void	clear()	//從該集中刪除所有元素。
E	first()	//返回此集合中當(dāng)前的第一個(gè)（最低）元素。
E	last()	//返回此集合中當(dāng)前的最后一個(gè)（最高）元素。
E	lower?(E e)	//返回此集合中的最大元素嚴(yán)格小于給定元素，如果沒有這樣的元素，則 null 。	
E	higher?(E e)	//返回此集合中的最小元素嚴(yán)格大于給定元素，如果沒有這樣的元素，則 null 。
E	floor?(E e) //返回此 set 中小于或等于給定元素的最大元素，如果沒有這樣的元素，則 null 。
E	ceiling?(E e)	//返回此 set 中大于或等于給定元素的最小元素，如果沒有這樣的元素，則 null 。
int size()	//返回此集合中的元素?cái)?shù)（基數(shù)）。
boolean contains?(Object o)	//如果此set包含指定的元素，則返回 true 。
boolean isEmpty()	//如果此集合不包含任何元素，則返回 true 。
Object	clone() //返回此 TreeSet實(shí)例的淺表副本。
Iterator<E>	iterator()	//以升序返回此集合中元素的迭代器。
Iterator<E>	descendingIterator()	//以降序返回此集合中元素的迭代器。
NavigableSet<E> descendingSet()	//返回此set中包含的元素的逆序視圖。
SortedSet<E>	headSet?(E toElement)	 //返回此 set 的部分視圖，其元素嚴(yán)格小于 toElement 。
NavigableSet<E> headSet?(E toElement, boolean inclusive)	//返回此 set 的部分視圖，其元素小于（或等于，如果 inclusive為true） toElement 。
Spliterator<E>	spliterator()	//在此集合中的元素上創(chuàng)建late-binding和故障快速 Spliterator 。
NavigableSet<E> subSet?(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)	//返回此set的部分視圖，其元素范圍為 fromElement到 toElement 。
SortedSet<E>	subSet?(E fromElement, E toElement)	//返回此set的部分視圖，其元素范圍從 fromElement （含）到 toElement （獨(dú)占）。
SortedSet<E>	tailSet?(E fromElement) //返回此 set 的部分視圖，其元素大于或等于 fromElement 。
NavigableSet<E> 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

到此這篇關(guān)于Java中的TreeSet集合詳解的文章就介紹到這了,更多相關(guān)TreeSet集合內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: