1概要

この記事では、Java Collections Frameworkの不可欠な部分と、最も普及している

Set

実装の1つである

TreeSet

** について説明します。


2

TreeSet


の紹介

簡単に言うと、

TreeSet

は

AbstractSet

クラスを拡張し、

NavigableSet

インターフェースを実装するソートされたコレクションです。

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

  • それはユニークな要素を格納します

  • 要素の挿入順序は保持されません

  • 要素を昇順に並べ替えます

  • スレッドセーフではありません

  • この実装では、オブジェクトは自然な順序に従って昇順にソートされて格納されます。

    TreeSet

    は自己均衡二分探索木、より具体的にはhttps://en.wikipedia.org/wiki/Red%E2%80%93black

    tree[

    Red-Black__ tree]を使用します。

簡単に言うと、自己均衡二分探索木である二分木の各ノードは、赤または黒のいずれかであるノードの色を識別するために使用される追加のビットを含む。その後の挿入と削除の間、これらの「カラー」ビットはツリーが多かれ少なかれバランスを保ったままでいることを確実にするのを助けます。

それでは、

TreeSet

のインスタンスを作成しましょう。 

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

** 2.1. コンストラクタ比較パラメータを持つTreeSet

必要に応じて、

Comparable

または

Comparatorを使用して要素のソート順を定義できるコンストラクタを使用して

TreeSet__を構築できます。 

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


  • TreeSet

    はスレッドセーフではありませんが、

    Collections.synchronizedSet（）

    ラッパーを使用して外部的に同期することができます。** 

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

さて、

TreeSet

インスタンスを作成する方法について明確なアイデアが得られたので、今度は使用可能な一般的な操作を見てみましょう。


3.



TreeSet


add（）



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（）

    メソッドは、与えられた要素が与えられた

    TreeSet

    内に存在するかどうかをチェックするために使用されます。


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（）

メソッドは、

Set.


の要素を昇順に繰り返し処理する反復子を返します。

これらの反復子はフェイルファスト** です。

昇順の反復順序は、次のとおりです。 

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

非同期の同時変更がある場合には何の保証もできないため、イテレータのフェイルファースト動作については保証しません。

これについての詳細はリンクを見つけることができます:/java-fail-safe-vs-fail-fast-iterator[ここ]。


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までの範囲の要素を返します。 

@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に要素を追加すると、

は自然な順序で並べ替えられるか、__comparatorで指定されたとおりに並べ替えられます。 : 

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


TreeSet

に挿入された要素は、

Comparable

インタフェースを実装するか、少なくとも指定されたコンパレータによって受け入れられる必要があります。

そのような要素はすべて相互に比較可能でなければなりません。





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

実装を使用する方法を理解することに焦点を当てます。重複を避け、要素をソートすることができることを考えると、その目的と、それがユーザビリティに関してどれほど効率的であるかを見ました。

いつものように、コードスニペットはhttps://github.com/eugenp/tutorials/tree/master/core-java-collections[over on GitHub]にあります。