#この記事の内容は、Java で TreeSet を実装する方法についてです。 （詳細な説明）は、必要な友人が参考にできることを願っています。
HashSet は HashMap に基づいて実装されていますが、TreeSet はどのように実装されるのでしょうか?それは正しい！誰もが思う通り、TreeMapをベースに実装されています。したがって、TreeSet のソース コードも非常にシンプルです。重要なのは、TreeMap を理解することです。
TreeSet の継承関係
いつものように、最初に TreeSet クラスの継承関係を見てみましょう:
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable
当然のことながら、拡張を容易にする抽象クラス AbstractSet を継承します。
は NavigableMap インターフェイスに似た NavigableSet インターフェイスを実装します。さまざまなナビゲーション メソッドを提供します。
は Cloneable インターフェイスを実装し、複製できます。
は Serializable インターフェイスを実装し、シリアル化できます。
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(); // 固定ValueTreeSet のソース コードを見ると、これら 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 はマルチスレッド環境で使用できません。 .synchronizedSortedSet(new TreeSet(.. .));
以上がJava で TreeSet を実装するにはどうすればよいですか? (詳しい説明)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。