java - ArrayList 底层数组成本

Question

我最近正在阅读 Java 中的 ArrayList。据我了解，当 ArrayList 达到其容量时，它会调用其 resize 方法并创建一个新的底层数组，该数组的大小是原始数组的两倍。由于这种情况，这种方式插入可以被视为 O(n)，但平均而言它仍然是 O(1)。然而，我对它背后的原因感到困惑，特别是增加了两倍的大小。将其增加 3 倍于原始容量会更好吗？

Answer 1

重要的是容量增加了一个常数因子。该因子是什么并不重要：1.5 与 3 一样好。摊销成本将为 O(1) - 恒定时间。但是，不同的因素会导致不同的常数。

如果您在考虑该因素的情况下进行数学计算，则摊销时间成本为 O(f/(f-1))，其中 f 是因素。如果加倍的时间成本为 2，则三倍的时间成本为 1.5。

大幅增加容量会减少调整大小的操作，但会浪费更多的空间。您必须找到一个平衡点：减少 25% 的执行时间是否值得增加 50% 的存储开销？

Answer 2

请记住，该O符号仅将缩放行为考虑到一个常数。虽然增加 3 倍会减少运行时间，但缩放行为仍然是线性 O(1)。如果插入的成本为 1，它不会变得更好。因此，摊销成本永远不会优于插入的 O(1)。

如果你看一下证明，你会发现用 2x 缩放的每个元素的成本是 3，用 3x 缩放它是 2.5，两者都是常数，所以 O(1)。

缩放因子 s 的平均成本是：(2s - 1) / (s - 1)对于任何缩放因子 s > 1，成本都是 O(1)。即使是非常小的缩放因子，例如 1.1，虽然每个元素的成本为 12，但仍然有O(1) 的摊销插入成本。

Answer 3

有关调整大小因素对摊销成本和渐近复杂性影响的答案，请参阅此答案。

让我从一个不同的、更实际的角度来解决这个问题。

标准库的设计者必须找到适用于非常广泛的一般工作负载的良好默认行为。有时，经过大量考虑和基准测试后，他们会更改这些内容（请参阅 HashMap 或 String 的实现细节演变）。总是有一个权衡，你不能让每个用例都绝对正确。

如果您发现默认行为不适合您，您作为应用程序开发人员有能力和义务调整默认值。

在手头的情况下，如果您已经知道您的 ArrayList 将需要增长到超出默认初始容量，您可以告诉构造函数预先分配一个更大的容量。而且您以后也可以调用ensureCapacity并trimToSize对其进行调整。