В чем заключается увеличение в ArrayList

Увеличение емкости в ArrayList

ArrayList — это реализация динамического массива в Java, которая автоматически увеличивает свою емкость при добавлении элементов, когда внутренний массив заполняется. Это ключевое отличие от обычных массивов (например, int[]), которые имеют фиксированный размер.

Механизм увеличения емкости

Процесс увеличения емкости состоит из следующих шагов:

1. Проверка необходимости увеличения: При каждом вызове метода add() (или при добавлении коллекции) проверяется, достаточно ли свободных ячеек в внутреннем массиве elementData.

2. Создание нового массива: Если емкости недостаточно, создается новый массив большего размера. По умолчанию, начиная с Java 8, новый размер рассчитывается по формуле:

   newCapacity = oldCapacity + (oldCapacity >> 1)
   

   То есть, новая емкость = старая емкость + старая емкость / 2 (прирост составляет примерно 50%).

3. Копирование элементов: Все существующие элементы копируются из старого массива в новый с помощью Arrays.copyOf() или System.arraycopy().

4. Замена ссылки: Внутренняя ссылка elementData начинает указывать на новый массив, а старый массив становится доступным для сборщика мусора.

Пример кода и демонстрация

Рассмотрим наглядный пример:

import java.util.ArrayList;

public class ArrayListGrowthDemo {
    public static void main(String[] args) {
        // Создаем ArrayList с начальной емкостью 5
        ArrayList<Integer> list = new ArrayList<>(5);
        
        System.out.println("Начальная емкость (ориентировочно): 5");
        
        // Добавляем элементы, чтобы спровоцировать увеличение
        for (int i =ショ0; i < 10; i++) {
            list.add(i);
            // Выводим состояние после каждого добавления
            System.out.printf("Добавлен элемент %d. Размер: %d%n", 
                i, list.size());
            
            // Получаем примерную емкость через рефлексию (для демонстрации)
            try {
                java.lang.reflect.Field field = ArrayList.class
                    .getDeclaredField("elementData");
                field.setAccessible(true);
                Object[] elementData = (Object[]) field.get(list);
                System.out.println("  Примерная емкость массива: " 
                    + elementData.length);
            } catch (Exception e) {
                // В реальном коде рефлексию использовать не рекомендуется
            }
        }
    }
}

Ключевые параметры увеличения

• Начальная емкость: Можно задать при создании через конструктор ArrayList(int initialCapacity). По умолчанию — 10.
• Коэффициент увеличения: Фиксированный — 1.5x (увеличение на 50%). В отличие от Vector, где можно задать capacityIncrement.
• Минимальное увеличение: Если расчетная новая емкость недостаточна (например, при добавлении многих элементов сразу), используется требуемый размер.

Внутренняя реализация (на основе OpenJDK)

Вот как примерно выглядит метод ensureCapacity() внутри ArrayList:

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // Если требуемая емкость превышает текущую длину массива
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // Увеличение на 50%
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // Если расчетной емкости недостаточно, используем minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // Проверка на переполнение
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    // Копирование в новый массив
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Практические рекомендации

1. Задавайте начальную емкость, если знаете приблизительное количество элементов. Это уменьшит количество переаллокаций:

   // Если ожидается ~1000 элементов
   ArrayList<String> list = new ArrayList<>(1000);
   

2. Используйте ensureCapacity() для ручного увеличения перед добавлением большого количества элементов:

   list.ensureCapacity(5000);
   

3. Помните о производительности: Каждое увеличение емкости требует:

   • Создания нового массива
   • Копирования всех элементов (O(n))
   • Сборки мусора старого массива

4. Не путайте size() и емкость:

   • size() — текущее количество элементов
   • Емкость — размер внутреннего массива (вместимость)

Сравнение с другими коллекциями

• Vector: Увеличивается на capacityIncrement или удваивается.
• LinkedList: Не имеет понятия емкости — элементы добавляются через узлы.
• CopyOnWriteArrayList: Также увеличивает емкость, но с особыми правилами для потокобезопасности.

Увеличение емкости в ArrayList — это компромисс между:

• Эффективностью памяти (не слишком большой массив)
• Производительностью добавления (минимизация переаллокаций)

Понимание этого механизма помогает писать более эффективный код, особенно при работе с большими объемами данных.