Различия между Java 6 и Java 7 в наращивании емкости ArrayList

Question

У меня есть вопрос о том, как Увеличение емкости ArrayList (не размер, а емкость) управляется в Java.Когда мы инициализируем 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 показывает, что она была изменена Мартином Бухгольцем из Google в наборе изменений 2350 для исправления ошибки 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;
}

Полная информация из отчета об ошибке :

Я заметил ошибки в java.util.ArrayList, java.util.Hashtable и java.io.ByteArrayOutputStream, которые возникают, когда возможности структур данных достигают определенного порога.Подробнее ниже.

Когда емкость ArrayList достигает (2/3)*Integer.MAX_VALUE, его размер достигает емкости и вызывается операция добавления или вставки, емкость увеличивается только на один элемент.Обратите внимание, что в следующем отрывке из ArrayList.ensureCapacity новая емкость установлена ​​на (3/2) * oldCapacity + 1, если только это значение не будет достаточным для размещения требуемой емкости, и в этом случае она будет установлена ​​на требуемую емкость.Если текущая емкость по крайней мере (2/3)*Integer.MAX_VALUE, то (oldCapacity * 3)/2 + 1 переполняется и преобразуется в отрицательное число, в результате чего новая емкость устанавливается на требуемую емкость.Основным следствием этого является то, что каждая последующая операция добавления / вставки приводит к полному изменению размера ArrayList, что приводит к значительному снижению производительности.

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

...

Это интересноотметить, что любые утверждения об амортизированной временной сложности операций добавления / вставки, например, в javadoc ArrayList, недействительны из-за ошибок, связанных с производительностью.Одним из решений вышеупомянутых ситуаций является установка новой емкости резервного массива равной Integer.MAX_VALUE, когда вычисление первоначального размера приводит к отрицательному числу во время изменения размера.