ArrayList容量增长中Java 6和Java 7之间的差异

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

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

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

新代码小心避免不必要的整数溢出.即使oldCapacity * 3/2没有,oldCapacity * 3也会溢出.新行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.

06001

…

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.