为什么Java ArrayLists不会自动缩小

Question

很久以前,我观看了普林斯顿Coursera MOOC:算法简介的视频讲座,可以在这里找到.它解释了ArrayList在添加或删除元素时调整类似结构的成本.事实证明,如果我们想要为我们的数据结构提供调整大小,我们将从for O(n)到amortized O(n)for add和removeoperation.

我已经使用Java ArrayList几年了.我一直都很确定它们会自动增长和缩小.就在最近,令我惊讶的是,我在这篇文章中被证明是错误的.Java ArrayList不会自动缩小(当然,它们会增长).

这是我的问题:

1. 在我看来,提供ArrayLists 缩小不会造成任何伤害,因为性能已经存在amortized O(n).为什么Java创建者没有将此功能包含在设计中？

2. 我知道像HashMaps 这样的其他数据结构也不会自动收缩.Java中是否有其他数据结构构建在支持自动收缩的数组之上？

3. 其他语言的趋势是什么？如果列表,字典,映射,集合在Python/C#等中,自动收缩怎么样？如果它们与Java的作用方向相反,那么我的问题是:为什么？

Answer 1

评论已经涵盖了您所问的大部分内容。以下是对您的问题的一些想法：

\n\n

\n

1. 在创建类似 Java 的结构时ArrayList，开发人员会做出有关运行时/性能的某些决定。他们显然决定从 \xe2\x80\x9cnormal\xe2\x80\x9d 操作中排除收缩，以避免所需的额外运行时间。

\n

2. 问题是为什么你想要自动收缩。增长ArrayList幅度不大（newCapacity = oldCapacity + (oldCapacity >> 1)确切地说，该系数约为 1.5；）。也许您还可以在中间插入，而不仅仅是在末尾附加。那么 a LinkedList（不是基于数组 -> 不需要收缩）可能会更好。这实际上取决于您的用例。如果您认为您确实需要 anArrayList所做的一切，但在删除元素时它必须缩小（我怀疑您真的需要这个），只需扩展ArrayList并覆盖这些方法即可。不过要小心！如果你在每次移除时都收缩，那么你就会回到O(n)。

\n

3. 在删除元素时缩小列表方面， C#List和 C++ 的vector行为相同。但自动生长的因素各不相同。甚至某些 Java 实现也使用不同的因素。

\n

\n