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

问题描述

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

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 不会自动缩小(尽管它们当然会增长).

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 中提供收缩不会造成任何损害，因为性能已经分摊 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. 在 Java 中创建类似 ArrayList 的结构时，开发人员会就运行时/性能做出某些决定.他们显然决定从正常"操作中排除收缩，以避免额外的运行时间，这是必需的.

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++ vector 在删除元素时缩小列表的行为相同.但自动生长的因素各不相同.甚至一些 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屋！