java - ArrayList 底层数组成本

Question

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

Answer 1

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

如果您在计算时考虑到该因子，则摊余时间成本为 O(f/(f-1))，其中 f 是因子。如果加倍的时间成本为 2，则三倍的时间成本为 1.5。

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