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的使用没有任何影响，但他们为什么要更改这个函数呢？是否有性能原因？他们是否在旧函数中发现了缺陷或错误？

- IgrewupwithSlackware

Answer 1

OpenJDK的源代码控制历史记录显示，它被Google的Martin Buchholz在更改集2350中更改，以修复bug JDK-6933217：核心库中处理大数组的问题。

新代码小心避免不必要的整数溢出。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;
}

从错误报告中获取完整细节：

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.

- John Kugelman