java - 为什么 ArrayList 通过特定公式扩展 elementData 数组？

Question

就在五分钟前，我发现了它的ArrayList工作原理。它具有elementData特定类型的数组字段，如果我们添加元素并且elementData数组已满，则集合在内部通过以下公式创建另一个数组：

(oldCapacity * 3) / 2 + 1

并将数据从旧数组复制到新数组。我只是想知道，这是为什么呢？为什么不把最后一码加倍？通过描述此公式，我在哪里可以获得有关 ArrayList 集合的内部表示的更多理论信息。PS对不起我的英语，它不是我的母语。

score 2 · Accepted Answer

实际上，增长策略是未指定的，只是它保证添加一个元素具有恒定的摊销成本。

您提出的方案和 JDK 使用的方案都提供了这样的保证。事实上，任何乘法增长方案都是合规的。其他语言/库将大小增加了两倍，因此这也是一种常见的方案。不同的 Java 实现可以选择遵循该方案，并且仍然符合规范。

请参阅Amortized analysis of std::vector 插入的讨论——它是关于 C++ 但同样适用于 Java。

score 0 · Accepted Answer

可能没有客观的衡量标准。我们可以通过浪费更多内存来避免复制，或者我们可以通过更频繁地复制来节省内存。这两个不能在一个目标函数中客观地衡量。

2 回答 2