java - 为什么 Java ArrayLists 不会自动收缩

Question

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

我已经使用 Java ArrayList 几年了。我一直确信它们会自动增长和收缩。直到最近，令我非常惊讶的是，我在 this post 中被证明是错误的. Java ArrayList 不会自动收缩(尽管它们当然会增长)。

这是我的问题:

1. 在我看来，在 ArrayList 中提供收缩不会造成任何损害，因为性能已经摊销 O(n)。为什么 Java 的创建者没有在设计中包含这个特性？

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

3. 其他语言的趋势是什么？在 Python/C# 中的列表、字典、映射、集合等情况下，自动收缩看起来如何。如果它们与 Java 的方向相反，那么我的问题是:为什么？

Answer 1

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

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

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

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