contains メソッドはオンになっていますかTreeSet(デフォルトで既にソートされているため)、言うよりも高速HashSetですか?
私が尋ねる理由はCollections.binarySearch、リストがソートされている場合は非常に高速であるため、おそらくTreeSetのcontainsメソッドが同じである可能性があると考えています.
1 に答える
5
TreeSetのjavadocから：
この実装は、基本操作（追加、削除、および含む）に保証されたlog（n）時間コストを提供します。
HashSetのjavadocから：
このクラスは、ハッシュ関数が要素をバケット間で適切に分散することを前提として、基本操作（追加、削除、包含、およびサイズ設定）に対して一定時間のパフォーマンスを提供します。
したがって、答えはノーです。
実装（JDK 1.7 oracle）を見ると、treeset.contains（またはhashtree）はtreemap.containsKey（またはhashmap）メソッドに依存しています。containsKeyは、ハッシュマップ内の1つのハッシュバケット（おそらく1つのアイテムのみを含む）をループしますが、compareToメソッドを使用して、ツリーマップ内のノードからノードに移動して、マップ全体をループします。アイテムが最大または最小の場合、これにはかなり長い時間がかかる可能性があります。
最後に、1mの整数を含むツリーで簡単なテストを実行し（そうです、信頼性はあまり高くありません）、2つの最大のツリーの1つを探しました。これにより、ツリーセットはセット全体を参照します。HashSetは50倍高速です。
于 2012-05-03T11:00:43.447 に答える