ArrayList：大小如何增加？

Question

我有一个关于 Java 的基本问题 ArrayList 。

当使用默认构造函数声明和初始化 ArrayList 时，将创建 10 个元素的内存空间。现在，当我添加第 11 个元素时，会发生什么？是否会创建具有 20 个（或更多）元素容量的新内存空间（这需要将元素从第一个内存位置复制到新位置）或其他内容？

我检查了 ArrayList Java 1.4.2 的 API 文档。但我没有找到答案。

请分享知识。谢谢。

编辑：新链接：

• ArrayList 在 Java 11 API 文档中
• Java™ 2 SDK，标准版文档 1.4.2

原文由 crazyTechie 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

创建一个新数组并复制旧数组的内容。这就是您在 API 级别所知道的全部内容。引用 文档（我的重点）：

每个 ArrayList 实例都有一个容量。容量是用于存储列表中元素的数组的大小。它始终至少与列表大小一样大。当元素被添加到 ArrayList 时，它的容量会自动增长。 除了添加一个元素具有恒定的摊销时间成本这一事实之外，没有具体说明增长政策的细节。

就 ArrayList （例如 Sun 的）的特定实现而言，它实际上是如何发生的，在他们的情况下，您可以在源代码中看到血淋淋的细节。但是，当然，依赖于特定实现的细节通常不是一个好主意……

原文由 T.J. Crowder 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

Sun的JDK6：

我相信它会增长到 15 个元素。不是编码出来，而是看jdk中的grow()代码。

int newCapacity 然后 = 10 + (10 >> 1) = 15。

 /**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

在 Javadoc 中，它说这是从 Java 2 开始的，所以它在 Sun JDK 中是一个安全的赌注。

编辑：对于那些不明白乘数 1.5 和 int newCapacity = oldCapacity + (oldCapacity >> 1); 之间有什么联系的人

>> 是右移运算符，它将数字减半。因此，

int newCapacity = oldCapacity + (oldCapacity >> 1);

=> int newCapacity = oldCapacity + 0.5*oldCapacity;

=> int newCapacity = 1.5*oldCapacity ;

原文由 mgmiller 发布，翻译遵循 CC BY-SA 3.0 许可协议