Wie implementiert man TreeSet in Java? (ausführliche Erklärung)

Der Inhalt dieses Artikels befasst sich mit der Implementierung von TreeSet in Java. (Ausführliche Erklärung), es hat einen gewissen Referenzwert. Freunde in Not können sich darauf beziehen. Ich hoffe, es wird Ihnen hilfreich sein.

HashSet wird basierend auf HashMap implementiert. Wie wird TreeSet implementiert? Das stimmt! Wie jeder denkt, wird es basierend auf TreeMap implementiert. Daher ist der Quellcode von TreeSet auch sehr einfach. Die Hauptsache ist, TreeMap zu verstehen.

Vererbungsbeziehung von TreeSet

Wie üblich schauen wir uns zunächst die Vererbungsbeziehung der TreeSet-Klasse an:

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

1. Es überrascht nicht, dass es die abstrakte Klasse AbstractSet erbt, die die Erweiterung erleichtert.

2. implementiert eine NavigableSet-Schnittstelle, die der NavigableMap-Schnittstelle ähnelt bietet verschiedene Navigationsmethoden;

3. implementiert die klonbare Schnittstelle und kann geklont werden;

4. implementiert die serialisierbare Schnittstelle;

Hier betrachten wir hauptsächlich die Schnittstellenklasse NavigableSet:

public interface NavigableSet<E> extends SortedSet<E>

Vertrauter Geschmack, das SortedSet erben Schnittstelle. SortedSet stellt eine Methode bereit, die einen Komparator zurückgibt:

Comparator<? super E> comparator();

unterstützt wie SortedMap natürliche Sortierung und benutzerdefinierte Sortierung. Die natürliche Sortierung erfordert, dass die dem Set hinzugefügten Elemente die Comparable-Schnittstelle implementieren, und die benutzerdefinierte Sortierung erfordert die Implementierung eines Comparators.

Quellcode-Analyse

Wichtiger Punkt

Der entscheidende Punkt ist natürlich, wie TreeSet sicherstellt, dass die Elemente nicht wiederholt werden und die Elemente in der Reihenfolge angeordnet sind Wie bereits erwähnt, basiert es auf TreeMap und implementiert es. Werfen wir also einen Blick darauf.

private transient NavigableMap<E,Object> m; // 保证有序
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object(); // 固定Value

Beim Betrachten des TreeSet-Quellcodes haben wir festgestellt, dass es nur diese beiden Attribute gibt (es gibt auch eine UID, die hier nicht enthalten ist). Offensichtlich wird m zum Speichern von Elementen verwendet, aber m deklariert NavigableMap anstelle von TreeMap. Es kann vermutet werden, dass TreeMap in der Konstruktionsmethode instanziiert werden sollte, um TreeSet flexibler zu machen. PRESENT hat die gleiche Funktion wie PRESENT in HashSet, es dient als Platzhalter für einen festen Wert.
Sehen Sie sich die Methoden zum Hinzufügen und Entfernen an:

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

Wie bei der Implementierung von HashSet wird auch der Schlüsselunterschied des Schlüsselwerts verwendet -Wertepaar, das von der Karte gespeichert wird und wiederholt wird.

Konstruktor

Natürlich wird die TreeMap in TreeSet im Konstruktor initialisiert.

public TreeSet() {
        this(new TreeMap<>()); // 默认自然排序的TreeMap
    }
public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator)); // 自定义比较器的TreeMap
    }
public TreeSet(Collection<? extends E> c) {
        this(); // 还是用的默认
        addAll(c); // 将元素一个一个添加到TreeMap中
    }
 public TreeSet(SortedSet<E> s) {
        this(s.comparator()); // 使用传入的SortedSet的比较器
        addAll(s); // 一个一个添加元素
    }

Eine natürlich geordnete TreeMap wird standardmäßig instanziiert. Natürlich können wir den Komparator anpassen.

Verfolgen Sie die addAll-Methode hier:

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; // 强转成TreeMap
            Comparator<?> cc = set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) { // 要保证set和map的比较器一样
                map.addAllForTreeSet(set, PRESENT); // TreeMap专门为TreeSet准备的方法
                return true;
            }
        }
        return super.addAll(c);
    }

Die addAllForTreeSet-Methode von TreeMap heißt:

void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
        try {
            buildFromSorted(set.size(), set.iterator(), null, defaultVal);
        } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
        }
    }

Sie sollten mit buildFromSorted vertraut sein, da es im TreeMap-Artikel analysiert wurde. Diese Methode erstellt aus den übergebenen Mengenelementen einen rot-schwarzen Baum, in dem der unterste Knoten rot und die anderen Knoten schwarz sind.

Navigationsmethoden

Da NavigableSet implementiert ist, sind verschiedene Navigationsmethoden natürlich unverzichtbar. Ihre Implementierung ist ebenfalls sehr einfach. Rufen Sie einfach die Navigationsmethode auf, die m entspricht. Zum Beispiel:

public E first() {
        return m.firstKey(); // 返回第一个元素
    }
public E lower(E e) {
        return m.lowerKey(e); // 返回小于e的第一个元素
    }
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive)); // 取前几个元素构成子集
    }
public E pollFirst() { // 弹出第一个元素
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }
public NavigableSet<E> descendingSet() { // 倒排Set
        return new TreeSet<>(m.descendingMap());
    }
......

Was hier beachtet werden muss, ist die Methode, die eine Teilmenge zurückgibt, zum Beispiel: headSet. Die zurückgegebene Untersammlung kann Elemente hinzufügen und löschen, es gibt jedoch beispielsweise Grenzbeschränkungen.

        // 前面构造了一个存储Int的Set
        // 3、5、7、9
        SortedSet<Integer> subSet = intSet.headSet(8); // 最大值7，超过7越界
        for (Integer sub : subSet) {
            System.out.println(sub);
        }
        subSet.add(2);
//        subSet.add(8); // 越界了
        subSet.remove(3);
        for (Integer sub : subSet) {
            System.out.println(sub);
        }

TreeSet unterstützt auch die Ausgabe in umgekehrter Reihenfolge, da es eine Implementierung von descendingIterator gibt:

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

Zusammenfassung

1. TreeSet wird basierend auf TreeMap implementiert, unterstützt natürliche Sortierung und benutzerdefinierte Sortierung und kann in umgekehrter Reihenfolge ausgegeben werden;

2. TreeSet erlaubt keine Nullwerte;

3. TreeSet ist nicht threadsicher und kann in einer Multithread-Umgebung verwendet werden. neues TreeSet(...));

Das obige ist der detaillierte Inhalt vonWie implementiert man TreeSet in Java? (ausführliche Erklärung). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!