[解決済み】ハッシュセットとツリーセットの比較

質問

昔から木が好きなんです。 O(n*log(n)) と整頓されているのが特徴です。しかし、私がこれまで知っているすべてのソフトウェアエンジニアは、なぜ私が TreeSet . CS出身者としては、どちらを使うかはそれほど重要ではないと思うし、ハッシュ関数やバケット（の場合）をいじくり回すのも気にならない。 Java ).

どのような場合に HashSet の上に TreeSet ?

解決方法は？

HashSet は TreeSet よりもはるかに高速ですが（add, remove, contains などのほとんどの操作でログタイムに対して定数時間）、TreeSet のように順序を保証するものではありません。

ハッシュセット

• は、基本的な操作（add、remove、contains、size）に対して一定時間のパフォーマンスを提供します。
• 要素の順序が時間経過とともに一定になることを保証するものではありません。
• 反復処理の性能は 初期容量 と 負荷率 をHashSetの
  • デフォルトの負荷率を受け入れても問題ありませんが、セットが大きくなると予想されるサイズの約2倍の初期容量を指定するとよいでしょう。

ツリーセット

• 基本操作（add, remove, contains）に対してlog(n)の時間コストを保証します。
• は、セットの要素が（昇順、自然、またはコンストラクタで指定したもの）ソートされることを保証します（implements SortedSet )
• は、反復処理のパフォーマンスに関するチューニング・パラメータを提供していません。
• のような順序付きセットを処理するためのいくつかの便利なメソッドを提供しています。 first() , last() , headSet() および tailSet() その他

重要なポイント

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

このように、使い方の選択はニーズによって異なりますが、順序付きコレクションが必要な場合でも、HashSetでSetを作成し、それをTreeSetに変換した方が良いと思います。

• 例 SortedSet<String> s = new TreeSet<String>(hashSet);