java - Java 6 和 Java 7 ArrayList 容量增长的区别

Question

我有一个关于如何在 Java 中管理ArrayList 的容量增长(不是大小，而是容量)的问题。 当我们使用默认构造函数初始化 ArrayList 而未设置容量时，容量默认设置为 10。

此时，当我们将另一个元素添加到列表中时，Oracle 文档说“随着元素添加到 ArrayList，其容量会自动增长。除了添加一个元素之外，没有指定增长策略的细节元素具有恒定的摊销时间成本。”

如果我们看一下 Java 内部结构，容量增长策略已经改变了它的功能。在 Java 6 之前，它是:

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

从 Java 7(和 > 7)开始，它是:

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

但这两个数学级数略有不同。从默认值 (10) 开始，我们有:

(1) 10,16,25,38,58,88,133,200,301,452...

(2) 10,15,22,33,49,73,109,163,244,366...

我认为这对 ArrayList 的使用没有任何影响，但他们为什么要更改此功能？有什么性能原因吗？他们是否在旧版本中发现了缺陷或错误？

Answer 1

OpenJDK 的 source control history显示它被 Martin Buchholz from Google 改变了在 changeset 2350修复错误 JDK-6933217: Huge arrays handled poorly in core libraries .

新代码小心避免了不必要的整数溢出。 oldCapacity * 3 可以溢出，即使 oldCapacity * 3/2 没有。新行 oldCapacity + (oldCapacity >> 1) 不会。如果它确实溢出并变为负数，则有额外的代码将容量设置为 Integer.MAX_VALUE(或接近它)。

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

来自 bug report 的完整详细信息:

I've noticed bugs in java.util.ArrayList, java.util.Hashtable and java.io.ByteArrayOutputStream which arise when the capacities of the data structures reach a particular threshold. More below.

When the capacity of an ArrayList reaches (2/3)*Integer.MAX_VALUE its size reaches its capacity and an add or an insert operation is invoked, the capacity is increased by only one element. Notice that in the following excerpt from ArrayList.ensureCapacity the new capacity is set to (3/2) * oldCapacity + 1 unless this value would not suffice to accommodate the required capacity in which case it is set to the required capacity. If the current capacity is at least (2/3)*Integer.MAX_VALUE, then (oldCapacity * 3)/2 + 1 overflows and resolves to a negative number resulting in the new capacity being set to the required capacity. The major consequence of this is that each subsequent add/insert operation results in a full resize of the ArrayList causing performance to degrade significantly.

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

...

It is interesting to note that any statements about the amortized time complexity of add/insert operations, such as the one in the ArrayList javadoc, are invalidated by the performance related bugs. One solution to the above situations is to set the new capacity of the backing array to Integer.MAX_VALUE when the initial size calculation results in a negative number during a resize.