私はいつもツリーが好きでした。そのすばらしいO(n*log(n))とその整然とした構造です。しかし、私が知るソフトウェア エンジニアは皆、なぜ を使うのかと私にはっきり尋ねてきましたTreeSet
。コンピューター サイエンスのバックグラウンドからすると、どちらを使うかはそれほど重要ではないと思いますし、ハッシュ関数やバケット (Java の場合) をいじり回す気もありません。
どのような場合に ではHashSet
なくを使用すべきでしょうかTreeSet
?
ベストアンサー1
HashSet は TreeSet よりもはるかに高速です (追加、削除、包含などのほとんどの操作で一定時間対ログ時間) が、TreeSet のような順序の保証はありません。
ハッシュセット
- このクラスは、基本的な操作 (追加、削除、包含、サイズ) に対して一定時間のパフォーマンスを提供します。
- 要素の順序が時間の経過とともに一定に保たれることを保証するものではない
- 反復パフォーマンスは、HashSet の 初期容量と負荷係数に依存します。
- デフォルトの負荷係数を受け入れることはまったく安全ですが、セットが拡大すると予想されるサイズの約 2 倍の初期容量を指定することをお勧めします。
ツリーセット
- 基本操作(追加、削除、包含)のlog(n)時間コストを保証する
- セットの要素がソートされることを保証します(昇順、自然順、またはコンストラクタで指定したもの)(実装
SortedSet
) - 反復パフォーマンスのチューニングパラメータは提供されていない
- 順序付き集合を扱うための便利なメソッドをいくつか提供している。
first()
、、last()
headSet()
、 そしてtailSet()
等
重要なポイント:
- どちらも要素の重複のないコレクションを保証します
- 一般的に、HashSet に要素を追加してから、重複のないソートされたトラバーサルのためにコレクションを TreeSet に変換する方が高速です。
- これらの実装はいずれも同期されていません。つまり、複数のスレッドが同時にセットにアクセスし、そのうちの少なくとも 1 つのスレッドがセットを変更する場合は、外部で同期する必要があります。
- LinkedHashSetは、ある意味では と の中間です
HashSet
。TreeSet
リンク リストが実行されるハッシュ テーブルとして実装されていますが、TreeSet によって保証されるソートされたトラバーサルとは異なる挿入順序の反復を提供します。
したがって、使用方法の選択は完全にニーズに依存しますが、順序付けられたコレクションが必要な場合でも、HashSet を使用して Set を作成し、それを TreeSet に変換することを優先すべきだと思います。
- 例えば
SortedSet<String> s = new TreeSet<String>(hashSet);