HashSetとTreeSetの比較

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

1. 序章

この記事では、 java .util.Set インターフェースの最も一般的なJava実装の2つ、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に追加すると、最後に追加されたにもかかわらず、最初のオブジェクトが「Awesome」であることがわかります。 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 次のようなほとんどの操作に一定時間のパフォーマンスを提供します追加（） 、 削除する（） と contains（） 、対ログ（（ n ）によって提供される時間 TreeSet。

通常、TreeSetに要素を追加するための実行時間は、HashSetよりもはるかに優れていることがわかります。

JVMがウォームアップされていない可能性があるため、実行時間が異なる可能性があることに注意してください。さまざまなSet実装を使用してマイクロテストを設計および実行する方法についての優れた説明は、こちらで入手できます。

2.4. 実装されたメソッド

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

pollFirst（） –最初の要素を返すか、Setが空の場合はnullを返します
pollLast（） –最後の要素を取得して削除するか、Setが空の場合はnullを返します
first（） –最初のアイテムを返します
last（）–最後のアイテムを返します
ceiling（） –指定された要素以上の最小要素を返すか、そのような要素がない場合はnullを返します
lower（） –指定された要素よりも厳密に小さい最大の要素を返すか、そのような要素がない場合はnullを返します

上記の方法により、 TreeSet は、HashSetよりもはるかに使いやすく強力になります。

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実装のいずれも同期されていません。これは、複数のスレッドが Set に同時にアクセスし、少なくとも1つのスレッドがそれを変更する場合、外部で同期する必要があることを意味します。

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

TreeSetおよびHashSetによって返されるIteratorはフェイルファストです。

つまり、 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の相違点と類似点について説明しました。

いつものように、この記事のコード例はGitHubでから入手できます。

getdocs

13036