509

私は昔から木が好きで、O(n*log(n))その美しさと整頓された状態が好きです。しかし、私がこれまでに知っているすべてのソフトウェア エンジニアは、なぜTreeSet. CS の背景から、私はあなたが何を使うかはそれほど重要ではないと思いますし、ハッシュ関数やバケット (の場合Java) をいじるのは気にしません。

どのような場合に aHashSetよりも aを使用する必要がありTreeSetますか?

4

14 に答える 14

872

HashSet は TreeSet よりもはるかに高速ですが (add、remove、contains などのほとんどの操作で一定時間対ログ時間)、TreeSet のような順序保証はありません。

ハッシュセット

  • このクラスは、基本的な操作 (追加、削除、包含、およびサイズ) に対して一定時間のパフォーマンスを提供します。
  • 要素の順序が時間の経過とともに一定に保たれることを保証するものではありません
  • 反復のパフォーマンスは、HashSet の初期容量と負荷係数に依存します。
    • デフォルトの負荷係数を受け入れることは非常に安全ですが、セットが拡張すると予想されるサイズの約 2 倍の初期容量を指定することをお勧めします。

ツリーセット

  • 基本操作 (追加、削除、および含む) の log(n) 時間コストを保証します
  • set の要素がソートされることを保証します (昇順、自然、またはコンストラクターを介して指定したもの) (implements SortedSet)
  • 反復パフォーマンスの調整パラメーターを提供しません
  • first()、last()、headSet()などの順序付きセットを処理するためのいくつかの便利なメソッドを提供しtailSet()ます

重要なポイント:

  • どちらも要素の重複のないコレクションを保証します
  • 一般に、要素を HashSet に追加してから、コレクションを TreeSet に変換して、重複のないソート済み走査を行う方が高速です。
  • これらの実装はいずれも同期されません。つまり、複数のスレッドがセットに同時にアクセスし、少なくとも 1 つのスレッドがセットを変更する場合、外部で同期する必要があります。
  • LinkedHashSetHashSetはある意味でとの中間TreeSetです。リンクされたリストが実行されるハッシュテーブルとして実装されますが、 TreeSet によって保証されるソートされたトラバーサルとは異なる挿入順序の反復を提供します。

したがって、使用方法の選択は完全にニーズに依存しますが、順序付けられたコレクションが必要な場合でも、HashSet を使用して Set を作成し、それを TreeSet に変換することをお勧めします。

  • 例えばSortedSet<String> s = new TreeSet<String>(hashSet);
于 2010-12-16T18:59:54.320 に答える
39

a のまだ言及されていない利点の 1 つTreeSetは、より大きな「局所性」を持っていることです。これは、(1) 2 つのエントリが順序で近くにある場合、aTreeSetはそれらをデータ構造内で、つまりメモリ内で互いに近くに配置します。(2) この配置は、類似のデータが類似の頻度でアプリケーションによってアクセスされることが多いという局所性の原則を利用しています。

HashSetこれは、キーが何であれ、エントリをメモリ全体に分散させる とは対照的です。

ハード ドライブからの読み取りのレイテンシ コストがキャッシュまたは RAM からの読み取りの数千倍であり、データが実際に局所的にアクセスされる場合は、 をTreeSet選択する方がはるかに適しています。

于 2011-09-30T18:28:27.067 に答える
27

HashSet要素にアクセスするには O(1) であるため、確かに重要です。しかし、セット内のオブジェクトの順序を維持することはできません。

TreeSet順序の維持 (挿入順序ではなく値の観点から) が重要な場合に役立ちます。しかし、あなたが指摘したように、要素にアクセスする時間が遅くなるために注文を交換しています.O(log n)は基本的な操作です。

のjavadocからTreeSet：

addこの実装では、基本操作 ( 、removeおよび)の保証された log(n) 時間コストが提供されますcontains。

于 2009-09-23T00:13:50.977 に答える
27

@shevchyk による Mapsの素敵な視覚的回答に基づいて、ここに私の見解があります:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   Property   ║       HashSet       ║      TreeSet      ║     LinkedHashSet   ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║  no guarantee order ║ sorted according  ║                     ║
║   Order      ║ will remain constant║ to the natural    ║    insertion-order  ║
║              ║      over time      ║    ordering       ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ Add/remove   ║        O(1)         ║     O(log(n))     ║        O(1)         ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║   NavigableSet    ║                     ║
║  Interfaces  ║         Set         ║       Set         ║         Set         ║
║              ║                     ║    SortedSet      ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║    not allowed    ║                     ║
║  Null values ║       allowed       ║ 1st element only  ║      allowed        ║
║              ║                     ║     in Java 7     ║                     ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║              ║   Fail-fast behavior of an iterator cannot be guaranteed      ║
║   Fail-fast  ║ impossible to make any hard guarantees in the presence of     ║
║   behavior   ║           unsynchronized concurrent modification              ║
╠══════════════╬═══════════════════════════════════════════════════════════════╣
║      Is      ║                                                               ║
║ synchronized ║              implementation is not synchronized               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝
于 2017-04-12T08:18:20.577 に答える
23

1.HashSet は null オブジェクトを許可します。

2.TreeSet は null オブジェクトを許可しません。null 値を追加しようとすると、NullPointerException がスローされます。

3. HashSet は TreeSet よりもはるかに高速です。

例えば

 TreeSet<String> ts = new TreeSet<String>();
 ts.add(null); // throws NullPointerException

 HashSet<String> hs = new HashSet<String>();
 hs.add(null); // runs fine
于 2012-11-16T05:26:14.860 に答える
13

ほとんどの使用理由HashSetは、操作が (平均して) O(log n) ではなく O(1) であるためです。セットに標準アイテムが含まれている場合、「ハッシュ関数をいじる」ことはありません。セットにカスタム クラスが含まれている場合は、使用するために実装するhashCode必要がありますHashSet(ただし、Effective Java はその方法を示しています) 。クラスに特定の順序がない場合、これは問題になる可能性があります。TreeSetComparableComparator

私は非常に小さなセット/マップ (< 10 アイテム) に時々TreeSet(または実際に) 使用しましたが、そうすることに実際の利益があるかどうかを確認していません. TreeMap大きなセットの場合、その差はかなり大きくなる可能性があります。

ソートが必要な場合TreeSetは適切ですが、それでも更新が頻繁でソート結果の必要性が低い場合は、内容をリストまたは配列にコピーしてソートする方が高速な場合があります。

于 2009-09-23T00:27:06.070 に答える
11

頻繁な再ハッシュ (または、HashSet のサイズを変更できない場合は衝突) が発生するほど十分な要素を挿入していない場合、HashSet を使用すると一定時間アクセスできるという利点があります。しかし、多くの成長または縮小があるセットでは、実装によっては Treesets を使用した方が実際にはパフォーマンスが向上する場合があります。

メモリが役立つ場合、償却された時間は機能的な赤黒ツリーで O(1) に近くなる可能性があります。岡崎の本は、私がやってのけるよりも良い説明を持っている. (または彼の出版物リストを参照してください)

于 2009-09-23T00:21:39.213 に答える
7

もちろん、HashSet の実装ははるかに高速です。順序がないため、オーバーヘッドが少なくなります。Java でのさまざまな Set 実装の優れた分析がhttp://java.sun.com/docs/books/tutorial/collections/implementations/set.htmlで提供されています。

そこでの議論では、ツリーとハッシュの問題に対する興味深い「中立的な」アプローチも指摘されています。Java は LinkedHashSet を提供します。これは、「挿入指向」のリンク リストが実行される HashSet です。つまり、リンク リストの最後の要素は、ハッシュに最後に挿入されたものでもあります。これにより、TreeSet のコストを増加させることなく、順序付けられていないハッシュの無秩序を回避できます。

于 2009-09-23T00:25:26.847 に答える
4

TreeSetは、2 つのソートされたコレクションの 1 つです (もう 1 つは TreeMap です) 。これは赤黒ツリー構造を使用し (ご存知のとおり)、要素が自然順序に従って昇順になることを保証します。必要に応じて、Comparable または Comparator を使用して、(要素のクラスによって定義された順序に依存するのではなく) 順序がどうあるべきかについてコレクションに独自のルールを与えることができるコンストラクターで TreeSet を構築できます。

LinkedHashSetは、すべての要素にわたって二重にリンクされた List を維持する HashSet の順序付きバージョンです。反復順序が重要な場合は、HashSet の代わりにこのクラスを使用してください。HashSet を反復処理する場合、順序は予測できませんが、LinkedHashSet を使用すると、挿入された順序で要素を反復処理できます。

于 2010-12-10T08:01:09.510 に答える
1

メッセージ編集（完全書き直し） 順番が気にならない時はその時 両方とも Log(n) を返す必要があります。どちらかが他方よりも 5 パーセント以上高速かどうかを確認すると便利です。HashSet は O(1) を与えることができ、ループでテストすると、それがそうであるかどうかが明らかになるはずです。

于 2009-09-23T00:28:50.580 に答える
1

技術的な考慮事項、特にパフォーマンスに関する考慮事項に基づいて、多くの回答が提供されています。私によると、 と の間の選択がTreeSet重要HashSetです。しかし、私はどちらかと言えば、最初に概念的な考慮事項

によって決定されるべきだと言いたいです。 操作する必要があるオブジェクトに対して、自然な順序付けが意味をなさない場合は、 を使用しないでください。 を実装しているため、ソートされたセットです。したがって、 function をオーバーライドする必要があることを意味します。これは、 function を返すものと一致する必要があります。たとえば、Student というクラスのオブジェクトのセットがある場合、

TreeSet
SortedSetcompareToequalsTreeSet生徒間に自然な順序はないため、これは理にかなっています。平均的な等級で並べることはできますが、これは「自然な順序」ではありません。関数compareToは、2 つのオブジェクトが同じ学生を表す場合だけでなく、2 人の異なる学生が同じ成績を持っている場合にも 0 を返します。2 番目のケースでは、 equalsfalse を返します (2 人の異なる学生が同じ成績を持っている場合に後者を true に戻すように決定した場合を除きます。これにより 、equals間違った意味ではなく、誤解を招くような意味の関数が作成されます)。オプションですが、強くお勧めします。そうしないと、インターフェイスの契約が壊れ、コードが他の人に誤解を与え、予期しない動作につながる可能性があります。
equalscompareToSet

このリンクは、この質問に関する良い情報源かもしれません。

于 2013-02-11T03:24:09.733 に答える
-3 
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class HashTreeSetCompare {

    //It is generally faster to add elements to the HashSet and then
    //convert the collection to a TreeSet for a duplicate-free sorted
    //Traversal.

    //really? 
    O(Hash + tree set) > O(tree set) ??
    Really???? Why?



    public static void main(String args[]) {

        int size = 80000;
        useHashThenTreeSet(size);
        useTreeSetOnly(size);

    }

    private static void useTreeSetOnly(int size) {

        System.out.println("useTreeSetOnly: ");
        long start = System.currentTimeMillis();
        Set<String> sortedSet = new TreeSet<String>();

        for (int i = 0; i < size; i++) {
            sortedSet.add(i + "");
        }

        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useTreeSetOnly: " + (end - start));
    }

    private static void useHashThenTreeSet(int size) {

        System.out.println("useHashThenTreeSet: ");
        long start = System.currentTimeMillis();
        Set<String> set = new HashSet<String>();

        for (int i = 0; i < size; i++) {
            set.add(i + "");
        }

        Set<String> sortedSet = new TreeSet<String>(set);
        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useHashThenTreeSet: " + (end - start));
    }
}
于 2012-09-25T23:00:46.110 に答える