一. ?? 前言

TreeSet是基于紅黑樹(shù)實(shí)現(xiàn)的Set集合，它具有以下特點(diǎn)：

1. 有序性：TreeSet是有序的，它按照元素的自然排序進(jìn)行排序，或者按照指定的Comparator進(jìn)行排序。

2. 不允許重復(fù)元素：與HashSet一樣，TreeSet也不允許重復(fù)元素，如果試圖將一個(gè)已經(jīng)存在的元素添加到TreeSet中，那么添加操作將會(huì)被忽略。

3. 支持高效的插入、刪除、查找操作：由于TreeSet是基于紅黑樹(shù)實(shí)現(xiàn)的，因此它的插入、刪除、查找等操作的時(shí)間復(fù)雜度為O(logn)，具有良好的時(shí)間性能。

4. 不支持隨機(jī)訪問(wèn)：由于TreeSet是基于紅黑樹(shù)實(shí)現(xiàn)的，因此它不支持隨機(jī)訪問(wèn)，不能通過(guò)下標(biāo)來(lái)訪問(wèn)集合中的元素。如果需要隨機(jī)訪問(wèn)集合中的元素，可以使用ArrayList或LinkedList等數(shù)據(jù)結(jié)構(gòu)。

5. 線程不安全：TreeSet是非線程安全的，如果多個(gè)線程同時(shí)操作同一個(gè)TreeSet對(duì)象，可能會(huì)導(dǎo)致集合數(shù)據(jù)結(jié)構(gòu)被破壞，因此在多線程環(huán)境下需要考慮對(duì)TreeSet進(jìn)行同步操作。

總之，TreeSet是一個(gè)有序、不允許重復(fù)元素、支持高效插入、刪除、查找操作的集合，適合需要按照一定順序訪問(wèn)元素的場(chǎng)景。

二. ?? 剝析流程

2.1 類(lèi)圖

TreeSet 實(shí)現(xiàn)的接口、繼承的類(lèi)，如下圖所示：類(lèi)圖

• 實(shí)現(xiàn) java.util.NavigableSet 接口，并繼承 java.util.AbstractSet 抽像類(lèi)。
• 實(shí)現(xiàn) java.io.Serializable 接口。
• 實(shí)現(xiàn) java.lang.Cloneable 接口。

2.2 屬性

TreeSet 只有一個(gè)屬性，那就是 m 。代碼如下：

private transient NavigableMap<E,Object> m;

• m 的 key ，存儲(chǔ) HashSet 的每個(gè) key 。

• map 的 value ，因?yàn)?TreeSet 沒(méi)有 value 的需要，所以使用一個(gè)統(tǒng)一的 PRESENT 即可。代碼如下：

  // Dummy value to associate with an Object in the backing Map
  private static final Object PRESENT = new Object();
  

2.3 構(gòu)造方法

TreeSet 一共有 5 個(gè)構(gòu)造方法，代碼如下：

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

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

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

public TreeSet(Collection<? extends E> c) {
    this();
    // 批量添加
    addAll(c);
}

public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    // 批量添加
    addAll(s);
}

• 在構(gòu)造方法中，會(huì)創(chuàng)建 TreeMap 對(duì)象，賦予到 m 屬性。

2.4 添加單個(gè)元素

add(E e) 方法，添加單個(gè)元素。代碼如下：

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

• m 的 value 值，就是我們看到的 PRESENT 。

addAll(Collection<? extends E> c) 方法，批量添加。代碼如下：

public  boolean addAll(Collection<? extends E> c) {
    // Use linear-time version if applicable
    // 情況一
    if (m.size()==0 && c.size() > 0 &&
        c instanceof SortedSet &&
        m instanceof TreeMap) {
        SortedSet<? extends E> set = (SortedSet<? extends E>) c;
        TreeMap<E,Object> map = (TreeMap<E, Object>) m;
        if (Objects.equals(set.comparator(), map.comparator())) {
            map.addAllForTreeSet(set, PRESENT);
            return true;
        }
    }
    // 情況二
    return super.addAll(c);
}

• 在實(shí)現(xiàn)上，和 TreeMap 的批量添加是一樣的，對(duì)于情況一，會(huì)進(jìn)行優(yōu)化。

2.5 移除單個(gè)元素

remove(Object o) 方法，移除 o 對(duì)應(yīng)的 value ，并返回是否成功。代碼如下：

public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

2.6 查找單個(gè)元素

#contains(Object key) 方法，判斷 key 是否存在。代碼如下：

public boolean contains(Object o) {
    return m.containsKey(o);
}

2.7 查找接近的元素

在 NavigableSet 中，定義了四個(gè)查找接近的元素：

• #lower(E e) 方法，小于 e 的 key
• #floor(E e) 方法，小于等于 e 的 key
• #higher(E e) 方法，大于 e 的 key
• #ceiling(E e) 方法，大于等于 e 的 key

我們一起來(lái)看看哈。

// TreeSet.java

public E lower(E e) {
    return m.lowerKey(e);
}

public E floor(E e) {
    return m.floorKey(e);
}

public E ceiling(E e) {
    return m.ceilingKey(e);
}

public E higher(E e) {
    return m.higherKey(e);
}

2.8 獲得首尾的元素

first() 方法，獲得首個(gè) key 。代碼如下：

public E first() {
    return m.firstKey();
}

• pollFirst() 方法，獲得并移除首個(gè) key 。代碼如下：

  public E pollFirst() {
      Map.Entry<E,?> e = m.pollFirstEntry();
      return (e == null) ? null : e.getKey();
  }
  

last() 方法，獲得尾部 key 。代碼如下：

public E last() {
    return m.lastKey();
}

• pollLast() 方法，獲得并移除尾部 key 。代碼如下：

  public E pollLast() {
      Map.Entry<E,?> e = m.pollLastEntry();
      return (e == null) ? null : e.getKey();
  }
  

2.9 清空

clear() 方法，清空。代碼如下：

public void clear() {
    m.clear();
}

2.10 克隆

clone() 方法，克隆 TreeSet 。代碼如下：

public Object clone() {
    // 克隆創(chuàng)建 TreeSet 對(duì)象
    TreeSet<E> clone;
    try {
        clone = (TreeSet<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }

    // 創(chuàng)建 TreeMap 對(duì)象，賦值給 clone 的 m 屬性
    clone.m = new TreeMap<>(m);
    return clone;
}

2.11 序列化

writeObject(ObjectOutputStream s) 方法，序列化 TreeSet 對(duì)象。代碼如下：

@java.io.Serial
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden stuff
    // 寫(xiě)入非靜態(tài)屬性、非 transient 屬性
    s.defaultWriteObject();

    // Write out Comparator
    // 寫(xiě)入比較器
    s.writeObject(m.comparator());

    // Write out size
    // 寫(xiě)入 key-value 鍵值對(duì)數(shù)量
    s.writeInt(m.size());

    // Write out all elements in the proper order.
    // 寫(xiě)入具體的 key-value 鍵值對(duì)
    for (E e : m.keySet())
        s.writeObject(e);
}

2.12 反序列化

#readObject(ObjectInputStream s) 方法，反序列化成 TreeSet 對(duì)象。代碼如下：

// TreeSet.java

@java.io.Serial
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden stuff
    // 讀取非靜態(tài)屬性、非 transient 屬性
    s.defaultReadObject();

    // Read in Comparator
    // 讀取比較器
    @SuppressWarnings("unchecked")
    Comparator<? super E> c = (Comparator<? super E>) s.readObject();

    // Create backing TreeMap
    // 創(chuàng)建 TreeMap 對(duì)象
    TreeMap<E,Object> tm = new TreeMap<>(c);
    m = tm;

    // Read in size
    // 讀取 key-value 鍵值對(duì)數(shù)量
    int size = s.readInt();

    // 讀取具體的 key-value 鍵值對(duì)
    tm.readTreeSet(size, s, PRESENT);
}

// TreeMap.java

void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
    throws java.io.IOException, ClassNotFoundException {
    buildFromSorted(size, null, s, defaultVal);
}

2.13 獲得迭代器

// TreeSet.java

public Iterator<E> iterator() { // 正序 Iterator 迭代器
    return m.navigableKeySet().iterator();
}

public Iterator<E> descendingIterator() { // 倒序 Iterator 迭代器
    return m.descendingKeySet().iterator();
}

2.14 轉(zhuǎn)換成 Set/Collection

public NavigableSet<E> descendingSet() {
    return new TreeSet<>(m.descendingMap());
}

2.15 查找范圍的元素

// subSet 組
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                              E toElement,   boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                   toElement,   toInclusive));
}
public SortedSet<E> subSet(E fromElement, E toElement) {
    return subSet(fromElement, true, toElement, false);
}

// headSet 組
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new TreeSet<>(m.headMap(toElement, inclusive));
}
public SortedSet<E> headSet(E toElement) {
    return headSet(toElement, false);
}

// tailSet 組
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
    return new TreeSet<>(m.tailMap(fromElement, inclusive));
}

public SortedSet<E> tailSet(E fromElement) {
    return tailSet(fromElement, true);
}

三. ?? 總結(jié)

TreeSet 是基于 TreeMap 的 Set 實(shí)現(xiàn)類(lèi)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-416150.html

到了這里，關(guān)于【TreeSet】| 深度剝析Java SE 源碼合集Ⅳ的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！