Differences between Java 6 and Java 7 in ArrayList capacity growth

I have a question about how to manage the capacity growth (not size, but capacity) of ArrayList in Java

At this time, when we add another element to the list, the Oracle document says, "when an element is added to the ArrayList, its capacity will increase automatically. In addition to the fact that the added element has a constant, the details of the growth strategy are not specified to amortize the time cost“

If we look inside Java, the capacity growth policy has changed its functionality Until Java 6, it is:

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

Starting with Java 7 (and > 7), it is:

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

But the two math series are slightly different Starting from the default value (10), we have:

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

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

I don't think this has any impact on the use of ArrayList, but why did they change this function? Any performance reasons? Did they find old flaws or bugs?

Solution

The source control history of openjdk shows that it is changed to Martin Buchholz from Google in changeset 2350 to fix the error jdk-6933217: Tiger arrays handled poor in core libraries

The new code is careful to avoid unnecessary integer overflow Even if oldcapacity * 3 / 2 does not exist, oldcapacity * 3 will overflow The new line oldcapacity (oldcapacity > > 1) will not If it does overflow and becomes negative, additional code is required to set the capacity to integer MAX_ Value (or close to it)

/**
 * 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;
}

Details of bug report: