Java で TreeSet を実装するにはどうすればよいですか? (詳しい説明)

#この記事の内容は、Java で TreeSet を実装する方法についてです。 （詳細な説明）は、必要な友人が参考にできることを願っています。

HashSet は HashMap に基づいて実装されていますが、TreeSet はどのように実装されるのでしょうか?それは正しい！誰もが思う通り、TreeMapをベースに実装されています。したがって、TreeSet のソース コードも非常にシンプルです。重要なのは、TreeMap を理解することです。

TreeSet の継承関係

いつものように、最初に TreeSet クラスの継承関係を見てみましょう:

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

1. 当然のことながら、拡張を容易にする抽象クラス AbstractSet を継承します。

2. は NavigableMap インターフェイスに似た NavigableSet インターフェイスを実装します。さまざまなナビゲーション メソッドを提供します。

3. は Cloneable インターフェイスを実装し、複製できます。

4. は Serializable インターフェイスを実装し、シリアル化できます。

#ここでは主に NavigableSet インターフェイス クラスについて説明します。

public interface NavigableSet<E> extends SortedSet<E>

使い慣れたテイストを継承し、ソートセットインターフェイス。 SortedSet はコンパレータを返すメソッドを提供します:

Comparator<? super E> comparator();

は、SortedMap と同様に、

自然な並べ替え と カスタム 並べ替え をサポートします。自然な並べ替えでは、Comparable インターフェイスを実装するために要素を Set に追加する必要があり、カスタム 並べ替えでは Comparator を実装する必要があります。

ソース コード分析

重要なポイント

重要なポイントは、当然のことながら、TreeSet が要素が繰り返されず、要素が次のように順序付けされることを保証する方法です。前述したように、これは TreeMap の実装に基づいているので、見てみましょう。

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

TreeSet のソース コードを見ると、これら 2 つの属性しかないことがわかりました (ここには含まれていない uid もあります)。明らかに、m は要素を保存するために使用されますが、m は TreeMap の代わりに NavigableMap を宣言します。ここで NavigableMap を使用すると、TreeSet をより柔軟にできると考えられます。 PRESENT は HashSet の PRESENT と同じ機能を持ち、固定の Value 値のプレースホルダーとして機能します。

追加メソッドと削除メソッドをもう一度見てください:

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

は HashSet の実装と同じであり、Key-Value キー値ペアも使用します。マップによって保存され、繰り返される特性。

コンストラクター

案の定、TreeSet の TreeMap はコンストラクターで初期化されます。

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); // 一个一个添加元素
    }

自然に順序付けされた TreeMap はデフォルトでインスタンス化されます。もちろん、コンパレーターをカスタマイズできます。

ここで addAll メソッドを追跡します:

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

TreeMap の

addAllForTreeSet メソッドが呼び出されます:

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

buildFromSorted については、TreeMap の記事で分析されているので、よく知っているはずです。このメソッドは、渡されたセット要素を、一番下のノードが赤で他のノードが黒である赤黒ツリーに構築します。

ナビゲーションメソッド

NavigableSetが実装されているので、当然ながら様々なナビゲーションメソッドが必須となります。実装も非常に簡単で、m に対応するナビゲーション メソッドを直接呼び出すだけです。例:

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

ここで注意する必要があるのは、サブセットを返すメソッドです (例: headSet)。返されたサブコレクションでは要素を追加および削除できますが、境界制限などがあります。

        // 前面构造了一个存储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 は、

descendingIterator:

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

の実装があるため、逆順の出力もサポートしています。

概要

##TreeSet は TreeMap に基づいて実装され、自然な並べ替えとカスタム 並べ替えをサポートし、逆順に出力できます。

1. ##TreeSet は null 値を許可しません。

2. #TreeSet はマルチスレッド環境で使用できません。 .synchronizedSortedSet(new TreeSet(.. .));

以上がJava で TreeSet を実装するにはどうすればよいですか? (詳しい説明)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。