Поэлементно ли копируется массив при расширении основы в ArrayList

Поэлементное копирование при расширении ArrayList

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

Как происходит расширение

ArrayList использует динамический массив, который расширяется по мере добавления элементов. Когда текущая ёмкость исчерпывается, создаётся новый, больший массив, и все старые элементы копируются в него.

// Внутренняя реализация ArrayList (упрощённо)
private Object[] elementData;
private int size;

private void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length) {
        // Вычисляем новую ёмкость (обычно 1.5x от старой)
        int newCapacity = elementData.length + (elementData.length >> 1);
        
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }
        
        // Создаём новый массив
        Object[] oldData = elementData;
        elementData = new Object[newCapacity];
        
        // Копируем элементы поэлементно
        System.arraycopy(oldData, 0, elementData, 0, size);
    }
}

System.arraycopy — вот кто копирует

Важное уточнение: копирование происходит с помощью System.arraycopy(), а не цикла. Это нативный метод, написанный на C/C++ и оптимизированный под конкретную платформу. Но суть остаётся той же — каждый элемент копируется из старого массива в новый.

// Сигнатура System.arraycopy
public static native void arraycopy(
    Object src,      // Исходный массив
    int srcPos,      // Начальная позиция в исходном
    Object dest,     // Целевой массив
    int destPos,     // Начальная позиция в целевом
    int length       // Количество элементов для копирования
);

Стратегия расширения

Это важно для производительности. ArrayList не просто добавляет один элемент — это была бы катастрофой. Вместо этого используется экспоненциальная стратегия:

// Обычная стратегия: увеличение на 50%
int newCapacity = oldCapacity + (oldCapacity >> 1);

// Пример:
// Начальная ёмкость: 10
// После 1-го расширения: 10 + 5 = 15
// После 2-го: 15 + 7 = 22
// После 3-го: 22 + 11 = 33

Это гарантирует амортизированную O(1) сложность для add() операции, несмотря на копирование.

Практические последствия

1. Производительность

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);  // Несколько раз произойдёт дорогостоящее расширение
}

// Лучше указать начальную ёмкость
ArrayList<Integer> list2 = new ArrayList<>(1_100_000);
for (int i = 0; i < 1_000_000; i++) {
    list2.add(i);  // Расширение может вообще не произойти
}

2. Памяти тратится больше После расширения старый массив может на время оставаться в памяти до сборки мусора. Если в системе критична память, это может быть проблемой.

3. Копирование сохраняет ссылки

ArrayList<String> list = new ArrayList<>();
String reference = "Hello";
list.add(reference);
// При расширении скопируется сама ссылка, а не новая строка
// Поэтому list.get(0) == reference будет true

Что копируется на самом деле

Здесь очень важно понять: копируются ссылки на объекты, не сами объекты.

ArrayList<StringBuilder> list = new ArrayList<>();
StringBuilder sb = new StringBuilder("test");
list.add(sb);

// При расширении копируется ссылка на sb, не новый объект
StringBuilder same = list.get(0);
same.append(" modified");
sb.toString(); // "test modified" — это один и тот же объект!

Альтернативы для избежания копирования

// 1. LinkedList — нет расширения, но медленнее доступ
List<Integer> linked = new LinkedList<>();

// 2. CopyOnWriteArrayList — копирует только при модификации
List<Integer> cow = new CopyOnWriteArrayList<>();

// 3. Правильная инициализация ёмкости
List<Integer> optimized = new ArrayList<>(expectedSize);

Итог

Да, элементы копируются поэлементно (точнее, их ссылки), и это происходит с помощью быстрого нативного метода System.arraycopy(). Это нормальная и ожидаемая часть работы ArrayList, благодаря которой достигается амортизированная линейная сложность для вставок.