ArrayList:大小如何增加？

Question

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

当ArrayList被声明和初始化使用默认构造,对于10个元件的存储器空间被创建.现在,当我添加第11个元素时,会发生什么？是否会创建具有20(或更多)元素容量的新内存空间(这需要将元素从第一个内存位置复制到新位置)还是其他一些东西？

我查了这里.但我没有找到答案.

请分享知识.谢谢.

Answer 1

创建一个新数组,并复制旧数组的内容.这就是你在API级别所知道的.引用文档(我的重点):

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

就具体实现方式ArrayList(如Sun的实际情况)而言,在他们的情况下,您可以在源代码中看到血淋淋的细节.但是,当然,依靠特定实现的细节通常不是一个好主意......

Answer 2

Sun的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.5和.之间的联系的人int newCapacity = oldCapacity + (oldCapacity >> 1);

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

Answer 3

它取决于实现,但取决于Sun Java 6源代码:

int newCapacity = (oldCapacity * 3)/2 + 1;

这就是ensureCapacity方法.其他JDK实现可能会有所不同.

Answer 4

当我们尝试将对象添加到arraylist时,

Java检查以确保现有阵列中有足够的容量来容纳新对象.如果没有,则创建一个更大的新数组,使用Arrays.copyOf将旧数组复制到新数组,并将新数组分配给现有数组.

查看下面的代码(取自GrepCode.com上的Java ArrayList Code).

编辑:

public ArrayList()构造一个初始容量为10的空列表.

public ArrayList(int initialCapacity)我们可以指定初始容量.

public ArrayList(Collection c)按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表.

现在,当我们使用ArrayList()constructore时,我们得到一个SizeList 为10的ArrayList .在列表中添加第11个元素时,在EnsureCapacity()方法中创建了新的Arraylist.

使用以下公式:

  int newCapacity= (oldCapacity * 3)/2 +1;

Answer 5

让我们看看这个测试用例（jdk1.8）

@Test
    public void testArraySize() throws Exception {
        List<String> list = new ArrayList<>();
        list.add("ds");
        list.add("cx");
        list.add("cx");
        list.add("ww");
        list.add("ds");
        list.add("cx");
        list.add("cx");
        list.add("ww");
        list.add("ds");
        list.add("cx");
        list.add("last");
    }

1）插入“last”时在行上放置断点

2）转到添加方法ArrayList 你会看到

ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;

3. 转到ensureCapacityInternal方法，该方法调用 ensureExplicitCapacity

4. private void ensureExplicitCapacity(int minCapacity) { modCount++;

         // overflow-conscious code
         if (minCapacity - elementData.length > 0)
             grow(minCapacity);
     }
             return true;
   

在我们的示例中 minCapacity 等于 1111-10 > 0因此 grow将调用方法

5)

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);
    }

让我们描述每个步骤：

1. oldCapacity = 10 默认情况下，在 java 8 arraylist 的容量是 10 ，您可以通过在构造函数中传递另一个值来覆盖它

2. int newCapacity = oldCapacity + (oldCapacity >> 1); 这里 newCapacity 等于 oldCapacity 加上 oldCapacity 右移一（oldCapacity is 10这是二进制表示00001010向右移动一位将使其00000101十进制为 5 因此newCapacity是10 + 5 = 15）

3. if (newCapacity - minCapacity < 0) newCapacity = minCapacity; 例如您的初期容量为1（ new ArrayList<>(1)）中，当添加的第二个元素newCapacity将等于1(oldCapacity) + 0 (moved to right by one bit) = 1 在此情况下newCapacity小于minCapacity和elementData（对象阵列Object[]内的ArrayList，其存储数据）不能保持新的元件，因此newCapacity将等于最小容量

4. if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);

检查数组大小是否达到 MAX_ARRAY_SIZE（即 Integer.MAX - 8）为什么 ArrayList 的最大数组大小是 Integer.MAX_VALUE - 8？

5. 最后它将旧值复制到长度为 15 的 newArray

Answer 6

当使用默认构造函数声明和初始化ArrayList时,将创建10个元素的内存空间.现在,当我添加第11个元素时,会发生什么

ArrayList创建一个具有以下大小的新对象

即OldCapacity*3/2 + 1 = 10*3/2 + 1 = 16

Answer 7

直到JDK 6，容量随着公式的增长而增加newCapacity = (oldCapacity * 3/2) + 1。

在JDK 7及更高版本中，公式更改为newCapacity = oldCapacity + (oldCapacity >> 1)。

所以，如果初始容量为10当时的新能力将16 in JDK6和15 in above JDK6

Answer 8

通常，ArrayList 类型容器的内存通过加倍来增加。因此，如果您最初有 10 个项目的空间并且您添加了 10 个，那么第 11 个项目将被添加到一个包含 20 个项目的新（内部）数组中。这样做的原因是，如果数组以固定大小的增量递增，则添加项目的增量成本从 O(n^2) 减少到每次内部数组已满时将大小加倍时的不错的 O(n)。