为什么Java ArrayLists不会自动缩小 [英] Why Java ArrayLists do not shrink automatically

问题描述

很久以前我观看了普林斯顿Coursera MOOC的视频讲座：算法简介，可以找到此处。它解释了在添加或删除元素时调整 ArrayList 之类结构的成本。事实证明，如果我们想要为我们的数据结构提供调整大小，我们将从 O（n）转到摊销的O（n）用于添加和删除操作。

Long time ago I watched a video lecture from the Princeton Coursera MOOC: Introduction to algorithms, which can be found here. It explains the cost of resizing an ArrayList like structure while adding or removing the elements from it. It turns out that if we want to supply resizing to our data structure we will go from O(n) to amortized O(n) for add and remove operations.

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

I have been using Java ArrayList for a couple of years. I've been always sure that they grow and shrink automatically. Only recently, to my great surprise, I was proven wrong in this post. Java ArrayLists do not shrink (even though, of course they do grow) automatically.

这是我的问题：

1. 在我看来，提供收缩在 ArrayList s不会任何损害，因为性能已经摊销O（n）。为什么Java创建者没有将此功能包含在设计中？

1. In my opinion providing shrinking in ArrayLists does not make any harm as the performance is already amortized O(n). Why did Java creators did not include this feature into the design?

我知道其他数据结构如 HashMap 也不会自动收缩。 Java中是否有其他数据结构构建在支持自动收缩的数组之上？

I know that other data structures like HashMaps also do not shrink automatically. Is there any other data structure in Java which is build on top of arrays that supports automatic shrinking?

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

What are the tendencies in other languages? How does automatic shrinking look like in case of lists, dictionaries, maps, sets in Python/C# etc. If they go in the opposite direction to what Java does, then my question is: why?

推荐答案

评论已经涵盖了你所要求的大部分内容。这里有一些关于你的问题的想法：

The comments already cover most of what you are asking. Here some thoughts on your questions:

1. 创建像 ArrayList 在Java中，开发人员就运行时/性能做出某些决定。他们显然决定将正常操作中的缩小排除在外，以避免需要额外的运行时间。

1. When creating a structure like the ArrayList in Java, the developers make certain decisions regarding runtime / performance. They obviously decided to exclude shrinking from the "normal" operations to avoid the additional runtime, which is needed.

问题是你想要自动收缩的原因。 ArrayList 增长不多（系数约为1.5; newCapacity = oldCapacity +（oldCapacity>> 1），确切地说）。也许你也插入中间而不只是追加到最后。然后 LinkedList （不基于数组 - >不需要收缩）可能会更好。这真的取决于你的用例。如果你认为你真的需要 ArrayList 所做的一切，但是在删除元素时它必须缩小（我怀疑你真的需要这个），只需扩展 ArrayList 并覆盖方法。不过要小心！如果你在每次删除时收缩，你都会回到 O（n）。

The question is why you would want to shrink automatically. The ArrayList does not grow that much (the factor is about 1.5; newCapacity = oldCapacity + (oldCapacity >> 1), to be exact). Maybe you also insert in the middle and not just append at the end. Then a LinkedList (which is not based on an array -> no shrinking needed) might be better. It really depends on your use case. If you think you really need everything an ArrayList does, but it has to shrink when removing elements (I doubt you really need this), just extend ArrayList and override the methods. But be careful! If you shrink at every removal, you are back at O(n).

C＃ List 和C ++ 向量在删除元素时缩小列表的行为相同。但自动增长的因素各不相同。甚至一些Java实现也使用不同的因素。

The C# List and the C++ vector behave the same concerning shrinking a list at removal of elements. But the factors of automatic growing vary. Even some Java-implementations use different factors.

这篇关于为什么Java ArrayLists不会自动缩小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！