JavaでのTreeSetのガイド

投稿日: 2019-10-19 2022-11-03
タグ: Java, Java Collections, Java Set

1. 概要

この記事では、Javaコレクションフレームワークの不可欠な部分と、最も人気のあるSet実装の1つであるTreeSetについて説明します。

**2. TreeSetの紹介**

簡単に言うと、 TreeSet は、 AbstractSet クラスを拡張し、NavigableSetインターフェイスを実装するソートされたコレクションです。

この実装の最も重要な側面の概要は次のとおりです。

ユニークな要素を保存します
要素の挿入順序は保持されません
要素を昇順で並べ替えます
スレッドセーフではありません

この実装では、オブジェクトは自然な順序に従って昇順でソートおよび保存されます。 TreeSet は、自己平衡二分探索木、より具体的には赤黒木を使用します。

簡単に言えば、自己平衡二分探索木であるため、二分木の各ノードは、赤または黒のノードの色を識別するために使用される追加のビットで構成されます。その後の挿入および削除中に、これらの「色」ビットは、ツリーのバランスをほぼ維持するのに役立ちます。

それでは、TreeSetのインスタンスを作成しましょう。

Set<String> treeSet = new TreeSet<>();

2.1. コンストラクタコンパレータパラメータを使用したTreeSet

オプションで、 Compareable またはComparator：を使用して要素がソートされる順序を定義できるコンストラクターを使用して、TreeSetを作成できます。

Set<String> treeSet = new TreeSet<>(Comparator.comparing(String::length));

TreeSet はスレッドセーフではありませんが、 Collections.synchronizedSet（）ラッパーを使用して外部で同期できます。

Set<String> syncTreeSet = Collections.synchronizedSet(treeSet);

さて、 TreeSet インスタンスを作成する方法が明確になったので、使用可能な一般的な操作を見てみましょう。

3. TreeSet 追加（）

add（）メソッドは、予想どおり、TreeSetに要素を追加するために使用できます。要素が追加された場合、メソッドは trueを返し、それ以外の場合はを返します–false。

メソッドのコントラクトは、要素がSetにまだ存在しない場合にのみ要素が追加されることを示しています。

TreeSetに要素を追加しましょう。

@Test
public void whenAddingElement_shouldAddElement() {
    Set<String> treeSet = new TreeSet<>();

    assertTrue(treeSet.add("String Added"));
 }

addメソッドは、TreeSetが内部でどのように機能するか、TreeMapの put メソッドを利用して要素を格納する方法を示すため、非常に重要です。

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

変数mは、内部バッキング TreeMap を参照します（TreeMapはNavigateableMapを実装することに注意してください）。

private transient NavigableMap<E, Object> m;

したがって、 TreeSet は、 TreeSet のインスタンスが作成されるときに、TreeMapのインスタンスで初期化されるバッキングNavigableMapに内部的に依存します。：

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

これについての詳細はこの記事で見つけることができます。

4. TreeSet contains（）

contains（）メソッドは、特定の要素が特定のTreeSetに存在するかどうかを確認するために使用されます。要素が見つかった場合はtrueを返し、それ以外の場合はtrueを返します。 間違い。

contains（）の動作を見てみましょう。

@Test
public void whenCheckingForElement_shouldSearchForElement() {
    Set<String> treeSetContains = new TreeSet<>();
    treeSetContains.add("String Added");

    assertTrue(treeSetContains.contains("String Added"));
}

5. TreeSet remove（）

remove（）メソッドは、指定された要素が存在する場合、それをセットから削除するために使用されます。

セットに指定された要素が含まれている場合、このメソッドはtrueを返します。

実際の動作を見てみましょう。

@Test
public void whenRemovingElement_shouldRemoveElement() {
    Set<String> removeFromTreeSet = new TreeSet<>();
    removeFromTreeSet.add("String Added");

    assertTrue(removeFromTreeSet.remove("String Added"));
}

6. TreeSet clear（）

セットからすべてのアイテムを削除する場合は、 clear（）メソッドを使用できます。

@Test
public void whenClearingTreeSet_shouldClearTreeSet() {
    Set<String> clearTreeSet = new TreeSet<>();
    clearTreeSet.add("String Added");
    clearTreeSet.clear();
 
    assertTrue(clearTreeSet.isEmpty());
}

7. TreeSet size（）

size（）メソッドは、TreeSetに存在する要素の数を識別するために使用されます。これは、APIの基本的なメソッドの1つです。

@Test
public void whenCheckingTheSizeOfTreeSet_shouldReturnThesize() {
    Set<String> treeSetSize = new TreeSet<>();
    treeSetSize.add("String Added");
 
    assertEquals(1, treeSetSize.size());
}

8. TreeSet isEmpty（）

isEmpty（）メソッドを使用して、特定のTreeSetインスタンスが空であるかどうかを判断できます。

@Test
public void whenCheckingForEmptyTreeSet_shouldCheckForEmpty() {
    Set<String> emptyTreeSet = new TreeSet<>();
    
    assertTrue(emptyTreeSet.isEmpty());
}

9. TreeSet iterator（）

The iterator（）メソッドは、の要素に対して昇順で反復するイテレータを返します。設定。 これらのイテレータはフェイルファストです 。

ここで、反復の昇順を確認できます。

@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInAscendingOrder() {
    Set<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator<String> itr = treeSet.iterator();
    while (itr.hasNext()) {
        System.out.println(itr.next());
    }
}

さらに、 TreeSet を使用すると、Setを降順で繰り返すことができます。

それを実際に見てみましょう：

@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInDescendingOrder() {
    TreeSet<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator<String> itr = treeSet.descendingIterator();
    while (itr.hasNext()) {
        System.out.println(itr.next());
    }
}

Iterator は、イテレータの remove（）メソッド以外の方法でイテレータが作成された後、いつでもセットが変更された場合にConcurrentModificationExceptionをスローします。

このためのテストを作成しましょう：

@Test(expected = ConcurrentModificationException.class)
public void whenModifyingTreeSetWhileIterating_shouldThrowException() {
    Set<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator<String> itr = treeSet.iterator();
    while (itr.hasNext()) {
        itr.next();
        treeSet.remove("Second");
    }
}

または、イテレータのremoveメソッドを使用した場合、例外は発生しませんでした。

@Test
public void whenRemovingElementUsingIterator_shouldRemoveElement() {
 
    Set<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator<String> itr = treeSet.iterator();
    while (itr.hasNext()) {
        String element = itr.next();
        if (element.equals("Second"))
           itr.remove();
    }
 
    assertEquals(2, treeSet.size());
}

同期されていない同時変更が存在する場合、ハード保証を行うことは不可能であるため、イテレーターのフェイルファスト動作は保証されません。

これについての詳細はここで見つけることができます。

10. TreeSet first（）

このメソッドは、 TreeSet が空でない場合、最初の要素を返します。それ以外の場合は、NoSuchElementExceptionをスローします。

例を見てみましょう：

@Test
public void whenCheckingFirstElement_shouldReturnFirstElement() {
    TreeSet<String> treeSet = new TreeSet<>();
    treeSet.add("First");
   
    assertEquals("First", treeSet.first());
}

11. TreeSet last（）

上記の例と同様に、このメソッドは、セットが空でない場合に最後の要素を返します。

@Test
public void whenCheckingLastElement_shouldReturnLastElement() {
    TreeSet<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Last");
    
    assertEquals("Last", treeSet.last());
}

12. TreeSet subSet（）

このメソッドは、次の範囲の要素を返します。 fromElement に toElement。ご了承ください fromElement 包括的であり、 toElement 排他的です：

@Test
public void whenUsingSubSet_shouldReturnSubSetElements() {
    SortedSet<Integer> treeSet = new TreeSet<>();
    treeSet.add(1);
    treeSet.add(2);
    treeSet.add(3);
    treeSet.add(4);
    treeSet.add(5);
    treeSet.add(6);
    
    Set<Integer> expectedSet = new TreeSet<>();
    expectedSet.add(2);
    expectedSet.add(3);
    expectedSet.add(4);
    expectedSet.add(5);

    Set<Integer> subSet = treeSet.subSet(2, 6);
 
    assertEquals(expectedSet, subSet);
}

13. TreeSet headSet（）

このメソッドは、指定された要素よりも小さいTreeSetの要素を返します。

@Test
public void whenUsingHeadSet_shouldReturnHeadSetElements() {
    SortedSet<Integer> treeSet = new TreeSet<>();
    treeSet.add(1);
    treeSet.add(2);
    treeSet.add(3);
    treeSet.add(4);
    treeSet.add(5);
    treeSet.add(6);

    Set<Integer> subSet = treeSet.headSet(6);
 
    assertEquals(subSet, treeSet.subSet(1, 6));
}

14. TreeSet tailSet（）

このメソッドは、指定された要素以上のTreeSetの要素を返します。

@Test
public void whenUsingTailSet_shouldReturnTailSetElements() {
    NavigableSet<Integer> treeSet = new TreeSet<>();
    treeSet.add(1);
    treeSet.add(2);
    treeSet.add(3);
    treeSet.add(4);
    treeSet.add(5);
    treeSet.add(6);

    Set<Integer> subSet = treeSet.tailSet(3);
 
    assertEquals(subSet, treeSet.subSet(3, true, 6, true));
}

**15. Null要素の保存**

Java 7より前では、null要素を空の要素に追加することが可能でした。 TreeSet。

ただし、これはバグと見なされました。したがって、TreeSetはnullの追加をサポートしなくなりました。

TreeSetに要素を追加すると、要素は自然な順序に従って、またはコンパレータで指定されたとおりに並べ替えられます。したがって、 null、を追加すると既存の要素の場合、 null はどの値とも比較できないため、NullPointerExceptionが発生します。

@Test(expected = NullPointerException.class)
public void whenAddingNullToNonEmptyTreeSet_shouldThrowException() {
    Set<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add(null);
}

TreeSet に挿入される要素は、 Compareable インターフェースを実装するか、少なくとも指定されたコンパレーターによって受け入れられる必要があります。 このような要素はすべて相互に比較可能である必要があります。ie e1.compareTo（e2）またはcomparator.compare（e1、e2） ClassCastException。

例を見てみましょう：

class Element {
    private Integer id;

    // Other methods...
}

Comparator<Element> comparator = (ele1, ele2) -> {
    return ele1.getId().compareTo(ele2.getId());
};

@Test
public void whenUsingComparator_shouldSortAndInsertElements() {
    Set<Element> treeSet = new TreeSet<>(comparator);
    Element ele1 = new Element();
    ele1.setId(100);
    Element ele2 = new Element();
    ele2.setId(200);
    
    treeSet.add(ele1);
    treeSet.add(ele2);
    
    System.out.println(treeSet);
}

**16. TreeSetのパフォーマンス**

HashSet と比較すると、TreeSetのパフォーマンスは低くなっています。 add 、 remove 、 search などの操作には、 O（log n）時間がかかりますが、n要素の印刷などの操作には時間がかかります。ソートされた順序では、 O（n）の時間が必要です。

TreeSet は、エントリを TreeSet にアクセスして昇順または降順でトラバースできるようにし、昇順の操作とビューのパフォーマンスを維持する場合の主な選択肢です。降順のものよりも速い可能性があります。

局所性の原則–メモリアクセスパターンに応じて、同じ値または関連する保存場所が頻繁にアクセスされる現象の用語です。

地域性と言うとき：

同様のデータは、多くの場合、同様の頻度のアプリケーションによってアクセスされます
順序付けされた2つのエントリが近くにある場合、 TreeSet は、データ構造内、つまりメモリ内でそれらを互いに近くに配置します。

TreeSet は、より局所性の高いデータ構造であるため、局所性の原則に従って、不足している場合はTreeSetを優先する必要があると結論付けることができます。メモリと、自然な順序に従って互いに比較的近い要素にアクセスしたい場合。

データをハードドライブから読み取る必要がある場合（キャッシュまたはメモリから読み取るデータよりも遅延が大きい）、局所性が高いため、TreeSetを優先します。

17. 結論

この記事では、Javaで標準のTreeSet実装を使用する方法を理解することに焦点を当てます。その目的と、重複を避けて要素を並べ替える機能を考えると、ユーザビリティに関してどれほど効率的であるかを確認しました。

いつものように、コードスニペットはGitHubのにあります。

getdocs

13036