java - JavaでHashSetを反復するよりもTreeSetを反復する方が遅いですか?

Question

いくつかのベンチマークを実行しています。私のテストの 1 つは順序に依存するため、そのために TreeSet を使用しています。私の 2 番目のテストはそうではないので、HashSet を使用しています。

TreeSet の挿入が遅いことはわかっています。しかし、すべての要素を反復処理する場合はどうでしょうか?

score 1 · Accepted Answer

TreeSets内部ではTreeMapswhich はRed Black Trees(特殊なタイプのBST) を使用します。

BSTインオーダートラバーサルはO(n)

HashSetsEntry オブジェクトを保持HashMapsするためのを内部的に使用します。array

ここでもトラバーサルはO(n).

ベンチマークを作成しない限り、どちらが速いかを証明するのは困難です。

score 1 · Accepted Answer

同様の投稿から（Hashset vs Treeset）：

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

ハッシュセット:

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

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

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

score 0 · Accepted Answer

(ほぼ) a のパフォーマンスで安定した順序付けが必要な場合は、 aHashSetを使用しLinkedHashSetます。それでも一定時間の操作TreeSetが得られますが、対数時間が得られると思います。