[解決済み] コレクションに追加してからソートするのと、ソートされたコレクションに追加するのでは、どちらが速いのでしょうか？

質問

もし私が Map のように

HashMap<Integer, ComparableObject> map;

で、自然順序でソートされた値のコレクションを取得したいのですが、どの方法が一番早いですか？

(A)

のようなソート可能なコレクションのインスタンスを作成します。 ArrayList のようなソート可能なコレクションのインスタンスを作成し、値を追加し、ソートする。

List<ComparableObject> sortedCollection = new ArrayList<ComparableObject>(map.values());
Collections.sort(sortedCollection);

(B)

のような順序付きコレクションのインスタンスを作成します。 TreeSet のような順序付きコレクションのインスタンスを作成し、それから値を追加します。

Set<ComparableObject> sortedCollection = new TreeSet<ComparableObject>(map.values());

結果のコレクションは決して変更されないので、ソートは一度だけ行われる必要があることに注意してください。

どのように解決するのですか？

TreeSetには log(n) の時間複雑性を保証します。 add()/remove()/contains() のメソッドを使用します。 をソートする ArrayList は n*log(n) 演算を行うが add()/get() のみを取る。 1 の操作だけです。

つまり、検索がメインで、頻繁にソートしないのであれば ArrayList が良いでしょう。もし、ソートは頻繁に行うが、リトリーブはあまり行わないのであれば TreeSet が良い選択でしょう。