java - TreeSet の長所と短所は何ですか

Question

TreeSet の長所と短所を知りたいのですが、誰か教えてください。ありがとう！

Answer 1

コレクション クラスの 1 つ。コレクション内の要素にキーで、またはキーで順番にアクセスできます。ArrayList や HashMap よりもオーバーヘッドがかなり大きくなります。シーケンシャル アクセスが不要な場合は HashSet を使用し、キーで検索するだけです。ArrayList を使用し、配列を使用します。要素を順番に並べたい場合は、並べ替えます。TreeSet は常に要素を順番に保持します。ArrayList を使用すると、必要なときに並べ替えるだけです。TreeSets では、コレクションに格納するオブジェクトにキーを埋め込む必要があります。多くの場合、文字列の TreeSet がある場合があります。次にできることは、指定された文字列がセットにあるかどうかを確認することだけです。ツリーマップのように、関連付けられたオブジェクトを見つけることはできません。TreeMap では、関連付けられているキーとオブジェクトが分離されています。

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

内部的に TreeSet は赤黒木を使用します。バランスの取れたツリーを取得するために、データを事前に並べ替える必要はありません。一方、データが (昇順または降順で) 並べ替えられている場合は、他の種類のツリーの場合のように問題はありません。

必要な順序を定義するための Comparator を指定しない場合、TreeSet は項目クラスで Comparable 実装を使用して自然な順序を定義する必要があります。

Answer 2

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

これは、メソッドがSetを返す場合に特に問題になり、実装がTreeSetなのか、たとえばHashSetなのかがわかりません。

ここで学ぶべき教訓は、常にcompareToとequalsを一貫性のない形で実装することを避けることです。equalsと矛盾する方法でオブジェクトを並べ替える必要がある場合は、コンパレータを使用してください。

Answer 3

TreeSet:
長所: 赤/黒ツリー アルゴリズムに基づいて並べ替えられ、O(log(N)) の操作の複雑さを提供します。
短所: 値はComparableにするか、コンストラクターでComparatorを提供する必要があります。さらに、HashSet 実装は ~O(1) の複雑さを提供するため、パフォーマンスが向上します。

Answer 4

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