1前書き

この記事では、

java.util.Set

インターフェースの最も一般的な2つのJava実装(

HashSet



TreeSet

)を比較します。


2違い


HashSet



TreeSet

は同じブランチの葉ですが、重要な点がいくつか異なります。


2.1. ご注文


  • HashSet

    はオブジェクトをランダムな順序で格納しますが、

    TreeSet

    は要素の自然な順序を適用します。** 次の例を見てみましょう。

@Test
public void givenTreeSet__whenRetrievesObjects__thenNaturalOrder() {
    Set<String> set = new TreeSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add("Awesome");

    assertEquals(3, set.size());
    assertTrue(set.iterator().next().equals("Awesome"));
}


String

オブジェクトを

TreeSet

に追加した後、最初のオブジェクトは最後に追加されていても「素晴らしい」です。

HashSet

を使った同様の操作は、要素の順序が時間の経過とともに一定に保たれることを保証するものではありません。


2.2.

Null

オブジェクト

もう1つの違いは、


HashSet



null

個のオブジェクトを格納できるのに対し、

TreeSet

はそれらを許可しない

ことです。

@Test(expected = NullPointerException.class)
public void givenTreeSet__whenAddNullObject__thenNullPointer() {
    Set<String> set = new TreeSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add(null);
}

@Test
public void givenHashSet__whenAddNullObject__thenOK() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add(null);

    assertEquals(3, set.size());
}


null

オブジェクトを

TreeSet

に格納しようとすると、操作は

NullPointerException

がスローされます。唯一の例外は、Java 7では、TreeSet内に

null

要素を1つだけ持つことが許可されていたときでした。


2.3. パフォーマンス

簡単に言うと、

HashSet



TreeSet

より速いです。


HashSet

は、

add()



remove()

、および

contains()

のようなほとんどの操作に対して、

TreeSetによって提供される

log



n__)時間に対して、一定時間のパフォーマンスを提供します。

通常、

TreeSet

に要素を追加するための実行時間は、

HashSet

** よりもはるかに良いことがわかります。

JVMはウォームアップされていない可能性があるため、実行時間が異なる可能性があることを忘れないでください。さまざまな

Set

実装を使用してマイクロテストを設計および実行する方法については、http://stackoverflow.com/questions/23168490/hashset-and-treeset-performance-test[ここ]を参照してください。


2.4. 実装されているメソッド


  • TreeSet

    は機能性** が豊富で、以下のような追加のメソッドを実装しています。



  • pollFirst()


    – 最初の要素を返すか、

    Set



    の場合は

    null__

空の



pollLast()

** – 最後の要素を取得して削除する


Set

が空の場合は

null




first()

** – 最初の項目を返す



  • last()



    最後の項目を返す



  • ceiling()


    – 以上の最小の要素を返す

指定された要素。そのような要素がない場合は

null




lower()

** – 最大の要素を厳密により小さい

与えられた要素。そのような要素がない場合は

null

上記のメソッドは、

HashSet

よりも

TreeSet

をはるかに使いやすく強力にします。


3類似点


3.1. ユニークな要素


TreeSet



HashSet

はどちらも

重複しない要素の集まり

を保証します。** これは汎用の

Set

インタフェースの一部であるためです。

@Test
public void givenHashSetAndTreeSet__whenAddDuplicates__thenOnlyUnique() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    set.add("Baeldung");

    assertTrue(set.size() == 1);

    Set<String> set2 = new TreeSet<>();
    set2.add("Baeldung");
    set2.add("Baeldung");

    assertTrue(set2.size() == 1);
}


3.2. 同期されていない

これは、複数のスレッドが同時に

Set

にアクセスし、少なくとも1つのスレッドがそれを変更する場合、外部で同期させる必要があることを意味します。


3.3. フェイルファーストイテレータ


TreeSet



HashSet

によって返される

__Iterator

__sは、非常に高速です。

つまり、

Iterator

が作成された後はいつでも

Set

を変更すると、__ConcurrentModificationExceptionがスローされます。

@Test(expected = ConcurrentModificationException.class)
public void givenHashSet__whenModifyWhenIterator__thenFailFast() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    Iterator<String> it = set.iterator();

    while (it.hasNext()) {
        set.add("Awesome");
        it.next();
    }
}


4どの実装を使用しますか?

どちらの実装もセットという概念の契約を満たすため、どちらの実装を使用するかはコンテキスト次第です。

ここに覚えておくべきいくつかの簡単なポイントがあります:

  • エントリをソートしておきたい場合は、

    TreeSet

    を実行する必要があります

  • メモリ消費量よりもパフォーマンスを重視するのであれば、


HashSet

** メモリが足りない場合は、

TreeSet

を選択してください。

  • 比較的近い要素にアクセスしたい場合

それらの自然な順序に従って、私たちは

TreeSet

を考慮したいかもしれません
ローカリティが大きいから
**

HashSet

のパフォーマンスは、

initialCapacity


loadFactor

、これは

TreeSet

では不可能です
** 広告掲載順序を守り、一定時間の恩恵を受けるには

アクセスするには、

LinkedHashSet

を使用できます。


5結論

この記事では、

TreeSet



HashSet

の違いと類似点について説明しました。

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