ArrayList：大小是如何增加的？

arrays collections java arraylist

2022-08-31 11:01:43

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

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

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

请分享知识。谢谢。

编辑：新链接：

答案 1

将创建一个新数组，并将旧数组的内容复制过来。这就是您在 API 级别所知道的一切。引用文档（我的强调）：

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

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

答案 2

孙氏JDK6：

我相信它增长到15个元素。不是将其编码出来，而是查看jdk中的grow（）代码。

int newCapacity then = 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.5int newCapacity = oldCapacity + (oldCapacity >> 1);

>>是右移位运算符，它将数字减少到其一半。因此
int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=> int newCapacity = 1.5*oldCapacity ;