java - 添加到集合然后对其进行排序或添加到已排序的集合中是否更快？

Question

如果我有这样的 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());

请注意，生成的集合永远不会被修改，因此排序只需要进行一次。

Answer 1

TreeSet 为 add()/remove()/contains() 方法提供 log(n) 时间复杂度保证。 对 ArrayList 进行排序需要 n*log(n) 操作，但 add()/get() 只需要 1 操作。

所以如果你主要是检索，并且不经常排序，ArrayList 是更好的选择。如果您经常排序但不检索那么多 TreeSet 将是一个更好的选择。