Java ArrayList：大小如何增加？

ArrayList: how does the size increase?

提问by crazyTechie

I have a basic question on Java ArrayList.

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

When ArrayListis declared and initialized using the default constructor, memory space for 10 elements is created. Now, when I add an 11th element, what happens? Will new memory space be created with 20 (or more) element capacity (this requires copying elements from 1st memory location to new location) OR some thing else?

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

I checked here. But I didn't find an answer.

我在这里查过。但我没有找到答案。

Please share the knowledge. Thanks.

请分享知识。谢谢。

采纳答案by T.J. Crowder

A new array is created and the contents of the old one are copied over. That's all you know at the API level. Quoting from the docs(my emphasis):

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

Each ArrayListinstance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

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

In terms of how it actually happens with a specific implementation of ArrayList(such as Sun's), in their case you can see the gory details in the source. But of course, relying on the details of a specific implementation isn't usually a good idea...

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

回答by Jason

What happens is a new Array is created with n*2 spaces, then all items in the old array are copied over and the new item is inserted in the first free space. All in all, this results in O(N) add time for the ArrayList.

发生的情况是创建一个具有 n*2 个空格的新数组，然后将旧数组中的所有项复制过来，并将新项插入到第一个空闲空间中。总而言之，这导致为 ArrayList 增加 O(N) 时间。

If you're using Eclipse, install Jadand Jadclipseto decompile the JARs held in the library. I did this to read the original source code.

如果您使用 Eclipse，请安装Jad和Jadclipse来反编译库中保存的 JAR。我这样做是为了阅读原始源代码。

回答by John K?llén

Typically, the memory for ArrayList type containers is increased by doubling it. Thus, if you initially had space for 10 items and you added 10, the eleventh item will be added to a new (internal) array of 20 items. The reason for this is that the incremental cost of adding items is reduced from O(n^2) if the array had been incremented in fixed size increments to a nice O(n) when doubling the size each time the internal array is full.

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

回答by Cameron Skinner

It will depend on the implementation, but from the Sun Java 6 source code:

这将取决于实现，但来自 Sun Java 6 源代码：

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

That's in the ensureCapacitymethod. Other JDK implementations may vary.

那是在ensureCapacity方法中。其他 JDK 实现可能会有所不同。

回答by sumitkaushik

The default size of the arraylist is 10. When we add the 11th ....arraylist increases the size (n*2). The values stored in old arraylist are copied into the new arraylist whose size is 20.

arraylist 的默认大小是 10。当我们添加第 11 个 ....arraylist 时会增加大小 (n*2)。存储在旧数组列表中的值被复制到大小为 20 的新数组列表中。

回答by rajagopala reddy

when a ArrayList is declared and initialized using default constructor, memory space for 10 elements will be created. now, when i add 11 th element, what happens is

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

ArrayList create a new object with the following size

ArrayList 创建一个大小如下的新对象

i.e OldCapacity*3/2+1 = 10*3/2+1 =16

即旧容量*3/2+1 = 10*3/2+1 =16

回答by mgmiller

Sun's JDK6:

Sun的JDK6：

I believe that it grows to 15 elements. Not coding it out, but looking at the grow() code in the jdk.

我相信它会增长到 15 个元素。不是编写代码，而是查看 jdk 中的增长（）代码。

int newCapacity then = 10 + (10 >> 1) = 15.

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

From the Javadoc, it says this is from Java 2 and on, so its a safe bet in the Sun JDK.

从 Javadoc 中，它说这是来自 Java 2 及更高版本，因此它在 Sun JDK 中是一个安全的赌注。

EDIT: for those who didn't get what's the connection between multiplying factor 1.5and int newCapacity = oldCapacity + (oldCapacity >> 1);

编辑：对于那些没有得到乘法因子1.5和int newCapacity = oldCapacity + (oldCapacity >> 1);

>>is right shift operator which reduces a number to its half. Thus,
int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=> int newCapacity = 1.5*oldCapacity ;

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

回答by VdeX

When we try to add an object to the arraylist,

当我们尝试向数组列表中添加一个对象时，

Java checksto ensure that there is enough capacity in the existing array to hold the new object. If not, a new array of a greater size is created, the old array is copied to new arrayusing Arrays.copyOfand the new array is assigned to the existing array.

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

Look at the code below (taken from Java ArrayList Code at GrepCode.com).

看看下面的代码（取自 GrepCode.com 的 Java ArrayList 代码）。

Edit:

编辑：

public ArrayList()Constructs an empty list with an initial capacity of ten.

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

public ArrayList(int initialCapacity)we can specify initial capacity.

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

public ArrayList(Collection c)Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

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

Now when we use ArrayList() constructore we get a ArrayList with Size=10On adding 11th element in the list new Arraylist is created inside ensureCapacity() method.

现在，当我们使用 ArrayList() 构造函数时，我们会得到一个Size=10的 ArrayList 在列表中添加第 11 个元素时，在 ensureCapacity() 方法中创建了新的 Arraylist。

Using following formula:

使用以下公式：

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

回答by Premraj

ArrayList does increases the size on load factor on following cases:

ArrayList 在以下情况下会增加负载因子的大小：

• Initial Capacity:10
• Load Factor:1 (i.e. when the list is full)
• Growth Rate:current_size + current_size/2

• 初始容量：10
• 负载因子：1（即当列表已满时）
• 增长率：current_size + current_size/2

Context : JDK 7

上下文：JDK 7

While adding an element into the ArrayList, the following public ensureCapacityInternalcalls and the other private method calls happen internally to increase the size. This is what dynamically increase the size of ArrayList. while viewing the code you can understand the logic by naming conventions, because of this reason I am not adding explicit description

在向 中添加元素时ArrayList，以下public ensureCapacityInternal调用和其他私有方法调用在内部发生以增加大小。这就是动态增加ArrayList. 在查看代码时，您可以通过命名约定来理解逻辑，因此我没有添加明确的描述

public boolean add(E paramE) {
        ensureCapacityInternal(this.size + 1);
        this.elementData[(this.size++)] = paramE;
        return true;
    }

private void ensureCapacityInternal(int paramInt) {
        if (this.elementData == EMPTY_ELEMENTDATA)
            paramInt = Math.max(10, paramInt);
        ensureExplicitCapacity(paramInt);
    }
private void ensureExplicitCapacity(int paramInt) {
        this.modCount += 1;
        if (paramInt - this.elementData.length <= 0)
            return;
        grow(paramInt);
    }

private void grow(int paramInt) {
    int i = this.elementData.length;
    int j = i + (i >> 1);
    if (j - paramInt < 0)
        j = paramInt;
    if (j - 2147483639 > 0)
        j = hugeCapacity(paramInt);
    this.elementData = Arrays.copyOf(this.elementData, j);
}

回答by ZhaoGang

Context java 8

上下文 java 8

I give my answer here in the context of Oracle java 8 implementation, since after reading all the answers, I found that an answer in the context of java 6 has given by gmgmiller, and another answer has been given in the context of java 7. But how java 8 implementes the size increasement has not been given.

我在 Oracle java 8 实现的上下文中给出我的答案，因为在阅读所有答案后，我发现 gmgmiller 在 java 6 的上下文中给出了一个答案，而在 java 7 的上下文中给出了另一个答案。但是java 8是如何实现大小增加的还没有给出。

In java 8, the size increasement behavior is the same as java 6, see the growmethod of ArrayList:

在java 8中，大小增加行为与java 6相同，参见growArrayList的方法：

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

the key code is this line:

关键代码是这一行：

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

So clearly, the growth factor is also 1.5, the same as java 6.

所以很明显，增长因子也是1.5，和java 6一样。