java - java Collection.sort() 的内存消耗

Question

我有一个 ArrayList，其中包含 150 万个某个类的对象。当我使用 Collection.sort 方法对这个列表进行排序时，分配给 JVM 的内存急剧增加。

所以我的问题是:

这正常吗？这可能是什么原因？这是垃圾收集器工作太慢或启动不够频繁的问题吗？列表中的对象是否必须满足某些规范才能在排序期间消耗更少的内存(除了不包含那么多数据之外)？

谢谢!

Answer 1

为了对 List 进行排序，default sorting implementation首先创建要排序的所有元素的数组副本。这会导致您在排序时观察到额外的堆消耗。这种复制是必要的，因为通用排序算法不知道列表的结构，例如它是否是随机访问。

对于 Java 8，sorting implementation was however changed委托(delegate)给 List 的每个实现。这通过使用默认方法成为可能。对于 ArrayList，这个额外的开销 could be removed通过实现更有效的排序算法。因此，升级到 Java 8 很可能会解决您的问题。

针对您的问题，垃圾回收没有任何问题。不幸的是，大型数组很难处理，因为它们可能不适合年轻一代，最终可能会触发完整的收集。

另外，如评论中所说，实际排序是performed via Tim Sort since Java 7通过 Arrays::sort 实现。 Tim 排序 需要额外的堆空间。来自 javadoc:

Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

如果这不适用于您的用例，您可以通过将系统属性 java.util.Arrays.useLegacyMergeSort 设置为 来切换回以前的合并排序实现真。

毕竟，Tim 排序仍然比合并排序更有效，因为合并排序需要另一个完整的数组副本。