Kapitel zur Java-Verbesserung (28) ------TreeSet-javaLernprogramm-php.cn

So wie HashSet auf Basis von HashMap implementiert wird, wird auch TreeSet auf Basis von TreeMap implementiert. In „Java Improvement Chapter 27 -----TreeMap“ erläuterte LZ den TreeMap-Implementierungsmechanismus ausführlich. Wenn Sie diesen Blog-Beitrag ausführlich gelesen haben oder ein detaillierteres Verständnis von TreeMap haben, wird die Implementierung von TreeSet hilfreich sein Sie. Es ist so einfach wie Wasser trinken.

1. TreeSet-Definition

Wir wissen, dass TreeMap ein geordneter Binärbaum ist, daher ist TreeSet ebenfalls geordnet und seine Funktion besteht darin, eine geordnete Set-Sammlung bereitzustellen. Durch den Quellcode wissen wir, dass TreeSet auf AbstractSet basiert, das die Schnittstellen NavigableSet, Cloneable und Serializable implementiert. Unter anderem stellt AbstractSet die Backbone-Implementierung der Set-Schnittstelle bereit und minimiert so den Arbeitsaufwand für die Implementierung dieser Schnittstelle. NavigableSet ist eine Erweiterung von SortedSet mit Navigationsmethoden, die die größte Übereinstimmung für ein bestimmtes Suchziel melden, was bedeutet, dass es eine Reihe von Navigationsmethoden unterstützt. Finden Sie beispielsweise die beste Übereinstimmung für ein bestimmtes Ziel. Cloneable unterstützt das Klonen und Serializable unterstützt die Serialisierung.

public class TreeSet<E> extends AbstractSet<E>    implements NavigableSet<E>, Cloneable, java.io.Serializable

Nach dem Login kopieren

Gleichzeitig werden in TreeSet die folgenden Variablen definiert.

private transient NavigableMap<E,Object> m;        
//PRESENT会被当做Map的value与key构建成键值对
 private static final Object PRESENT = new Object();

Nach dem Login kopieren

Seine Konstruktionsmethode:

//默认构造方法，根据其元素的自然顺序进行排序
    public TreeSet() {        this(new TreeMap<E,Object>());
    }    
    //构造一个包含指定 collection 元素的新 TreeSet，它按照其元素的自然顺序进行排序。
    public TreeSet(Comparator<? super E> comparator) {            this(new TreeMap<>(comparator));
    }    
    //构造一个新的空 TreeSet，它根据指定比较器进行排序。
    public TreeSet(Collection<? extends E> c) {        this();
        addAll(c);
    }    
    //构造一个与指定有序 set 具有相同映射关系和相同排序的新 TreeSet。
    public TreeSet(SortedSet<E> s) {        this(s.comparator());
        addAll(s);
    }
    
    TreeSet(NavigableMap<E,Object> m) {        this.m = m;
    }

Nach dem Login kopieren

2. TreeSet Main Methoden

1, add: Das angegebene Element zu dieser Menge hinzufügen (falls das Element noch nicht in der Menge vorhanden ist).

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

Nach dem Login kopieren

2 addAll: Alle Elemente in der angegebenen Sammlung zu diesem Satz hinzufügen.

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;
            Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
            Comparator<? super E> mc = map.comparator();            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);                return true;
            }
        }        return super.addAll(c);
    }

Nach dem Login kopieren

3 Ceiling: Gibt das kleinste Element in dieser Menge zurück, das größer oder gleich dem angegebenen Element ist Es gibt kein solches Element, es wird null zurückgegeben.

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

Nach dem Login kopieren

4. clear: Alle Elemente in diesem Set entfernen.

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

Nach dem Login kopieren

5. Klonen: Gibt eine flache Kopie der TreeSet-Instanz zurück. Es handelt sich um eine oberflächliche Kopie.

public Object clone() {
        TreeSet<E> clone = null;        try {
            clone = (TreeSet<E>) super.clone();
        } catch (CloneNotSupportedException e) {            throw new InternalError();
        }

        clone.m = new TreeMap<>(m);        return clone;
    }

Nach dem Login kopieren

6. Komparator: Gibt den Komparator zurück, der die Elemente in dieser Menge sortiert; wenn diese Menge die natürliche Reihenfolge ihrer Elemente verwendet, wird Null zurückgegeben.

public Comparator<? super E> comparator() {        return m.comparator();
    }

Nach dem Login kopieren

7 enthält: Wenn dieser Satz das angegebene Element enthält, wird true zurückgegeben.

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

Nach dem Login kopieren

8、descendingIterator：返回在此 set 元素上按降序进行迭代的迭代器。

public Iterator<E> descendingIterator() {        return m.descendingKeySet().iterator();
    }

Nach dem Login kopieren

9、descendingSet：返回此 set 中所包含元素的逆序视图。

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

Nach dem Login kopieren

10、first：返回此 set 中当前第一个（最低）元素。

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

Nach dem Login kopieren

11、floor：返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。

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

Nach dem Login kopieren

12、headSet：返回此 set 的部分视图，其元素严格小于 toElement。

public SortedSet<E> headSet(E toElement) {        return headSet(toElement, false);
    }

Nach dem Login kopieren

13、higher：返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。

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

Nach dem Login kopieren

14、isEmpty：如果此 set 不包含任何元素，则返回 true。

public boolean isEmpty() {        return m.isEmpty();
    }

Nach dem Login kopieren

15、iterator：返回在此 set 中的元素上按升序进行迭代的迭代器。

public Iterator<E> iterator() {        return m.navigableKeySet().iterator();
    }

Nach dem Login kopieren

16、last：返回此 set 中当前最后一个（最高）元素。

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

Nach dem Login kopieren

17、lower：返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。

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

Nach dem Login kopieren

18、pollFirst：获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。

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

Nach dem Login kopieren

19、pollLast：获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。

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

Nach dem Login kopieren

20、remove：将指定的元素从 set 中移除（如果该元素存在于此 set 中）。

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

Nach dem Login kopieren

21、size：返回 set 中的元素数（set 的容量）。

public int size() {        return m.size();
    }

Nach dem Login kopieren

22、subSet：返回此 set 的部分视图

/**
     * 返回此 set 的部分视图，其元素范围从 fromElement 到 toElement。     */
     public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
             E toElement,   boolean toInclusive) {             return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                  toElement,   toInclusive));
     }     
     /**
      * 返回此 set 的部分视图，其元素从 fromElement（包括）到 toElement（不包括）。      */
     public SortedSet<E> subSet(E fromElement, E toElement) {         return subSet(fromElement, true, toElement, false);
     }

Nach dem Login kopieren

23、tailSet：返回此 set 的部分视图

/**
     * 返回此 set 的部分视图，其元素大于（或等于，如果 inclusive 为 true）fromElement。     */
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {        return new TreeSet<>(m.tailMap(fromElement, inclusive));
    }    
    /**
     * 返回此 set 的部分视图，其元素大于等于 fromElement。     */
    public SortedSet<E> tailSet(E fromElement) {        return tailSet(fromElement, true);
    }

Nach dem Login kopieren