已排序的集合或已排序的集合类型

Question

假设一个应用程序生成多个包含数十到数百个类型为的对象的HashMap<String, MyClass>数据结构，这些对象需要被放入单个、排序的中。

实现该功能的两种可能的实现方式分别返回SortedSet或已排序List，如下所示：

public static Set<MyClass> getSortedSet(HashMap<String, MyClass>... allMaps)
{
    SortedSet<MyClass> set = new TreeSet<MyClass>();

    Collection<MyClass> c;

    for (HashMap<String, MyClass> map:allMaps)
    {
        c = map.values();
        set.addAll(c);
    }

    return set;
}

public static List<MyClass> getSortedList(HashMap<String, MyClass>... allMaps)
{
    List<MyClass> list = new ArrayList<MyClass>();

    Collection<MyClass> c;

    for (HashMap<String, MyClass> map:allMaps)
    {
        c = map.values();
        list.addAll(c);
    }

    Collections.sort(list);

    return list;
}

以上两种方法中是否有明显的性能优势？

是否有更快速实现相同功能的方法？

- PNS

---

如果你想知道哪个更快，为什么不用你实际的数据来测试呢？ - NPE

因为其他人将使用该代码！我只是想知道一个实现方式比另一个更快的深刻原因是否存在！ - PNS

你仍然可以进行负载测试以了解更好的性能表现... - Sridhar G

Answer 1

您的排序列表方法存在一些问题：

ArrayList是由数组支持的。每当您添加一个新元素时，它可能需要在幕后增加数组大小。如果要使用此方法，请提前创建正确大小的ArrayList。

在添加所有元素后进行排序似乎不太优化。为什么不将元素添加到其正确位置的列表中？（使用排序集合，然后转换为列表）Java的好排序列表 实际上回答您的问题，我会选择使用TreeSet在幕后。因为，如果用户希望，他们可以随时执行Set.toArray()，然后拥有一个列表。

- Colin D

---

这似乎与https://dev59.com/YFrUa4cB1Zd3GeqPfwJP一致。可以在https://dev59.com/h3RB5IYBdhLWcg3wCjjO找到从Set转换为List的通用解决方案。谢谢！ - PNS

Answer 2

在本质上，集合和列表的区别在于集合不会保留重复项。您只能拥有一个对象实例。而列表允许您保留重复项。

因此，集合需要更多的工作，所以它们速度较慢。

- srini.venigalla

---

当然可以，但假设没有重复项，有理由认为一种实现方式总是比另一种更快吗？ - PNS

也许问题不在于是否存在重复项，而在于检查元素是否已经存在于集合中的指令。因此，答案仍然适用。 - Carlo

@PNS 请参考下面 Colin D 的答案。使用 TreeSet 并让用户在需要时派生一个数组是一个不错的方法。 - srini.venigalla

他的答案被放在上面，但我明白了。谢谢！ - PNS

Answer 3

有没有理由认为一种实现总是比另一种实现更快？

没有，没有这样的理由。

哪种更快可能取决于数据的数量、属性、比较器的性能特征、您的JDK、JIT编译器等等。

唯一确定的方法是在真实数据上对代码进行基准测试。

- NPE

---

有人指向了https://dev59.com/YFrUa4cB1Zd3GeqPfwJP，但后来又删除了评论。不过看起来TreeSet确实更快。 - PNS

@PNS：这是一个不同的问题（他们在每次插入之后都对列表进行排序，而您仅在最后进行排序）。 - NPE