TreeSetの長所と短所

Question

TreeSetの賛否両論が何であるか疑問に思っています。ありがとう！

Answer 1

Collectionクラスの1つです。それは、あなたのコレクション内の要素にキーで、または順次キーにアクセスすることができます。 ArrayListやHashMapよりもかなりオーバーヘッドがあります。シーケンシャルアクセスを必要としない場合は、キーでルックアップするだけでHashSetを使用してください。 ArrayListを使用し、配列を使用します。要素を整列させたい場合はソートしてください。 TreeSetは、要素を常に順番に保持します。 ArrayListを使用すると、必要なときに並べ替えることができます。 TreeSetsでは、キーはコレクションに格納されているオブジェクトに埋め込まれている必要があります。多くの場合、TreeSet of Stringsがあります。指定したStringがSetに含まれているかどうかを確認するだけです。それは、あなたにTreemapのやり方とは関係のないオブジェクトを見つけることはありません。 TreeMapを使用すると、関連付けられているキーとオブジェクトは別々のものになります。

TreeSetとその兄弟TreeMapは、奇妙なことに木を表現することとは関係がありません。内部的には、ツリー構造を使用してアルファベット順にソートされたセット/マップを提供しますが、親と子の間のリンクを制御することはできません。

内部的にTreeSetは赤黒のツリーを使用します。バランスの取れたツリーを得るためにデータを事前に並べる必要はありません。一方、データがソート（昇順または降順）されている場合、他のタイプのツリーと同様に傷つくことはありません。

あなたが望む順序を定義するためにコンパレータを指定しない場合、TreeSetは自然順序を定義するためにアイテムクラスにComparable実装を必要とします。

Answer 2

TreeSet：
長所：赤/黒のツリーアルゴリズムに基づいてソートされ、操作にO（log（N））の複雑さを提供します。
短所：値はのいずれかである必要があります。またはコンパレータをコンストラクタに指定する必要があります。さらに、HashSet実装は〜O（1）の複雑さを提供するため、より良いパフォーマンスを提供します。

Answer 3

このデータ構造は、昇順検索が可能なようにデータを維持するためにバイナリツリーを使用すると思われます。その場合、ツリーをバランスさせて維持しようとすると、削除操作が多少コストがかかることになります。

Answer 4

短所：TreeSetの落とし穴の1つは、予期しない方法でSetインターフェイスを実装していることです。 TreeSetにオブジェクトaが含まれている場合、a.equals（b）がfalseであっても、a.compareTo（b）が0を返した場合、オブジェクトbはセットの一部とみなされるため、compareToとequalsが一貫性あなたは悪い乗り方のためにいる。

これは、メソッドがSetを返し、実装がTreeSetか、たとえばHashSetかどうかわからないときに特に問題になります。

ここで学ぶべきことは、常にcompareToとequalsが一貫して実装されないようにすることです。 equalsと矛盾する方法でオブジェクトを注文する必要がある場合は、Comparatorを使用します。

Answer 5

TreeSetはメモリを断片化し、追加のメモリオーバーヘッドを持ちます。ソースを見て、追加のメモリの量とそれが作成する追加オブジェクトの量を計算することができます。もちろん、それは格納されたオブジェクトの性質に依存し、また私はメモリについての妄想であると疑うことができます:)しかし、それはこことそこに費やさない方が良いです - あなたはGCを持っています、あなたはキャッシュミスを持っていて、

多くの場合、TreeSetではなくPriorityQueueを使用できます。そして、典型的なユースケースでは、文字列の配列をソートする方が良いでしょう。