Что будет происходить с массивом в ArrayList при расширении?

# Как работает расширение массива в ArrayList

ArrayList — это динамический массив, который автоматически растёт при нехватке места. Разберу внутренний механизм этого процесса.

Основная идея

ArrayList обёртывает обычный Java массив (Object[]) и управляет его расширением.

public class ArrayList<E> extends AbstractList<E> {
    // Внутренний массив
    private transient Object[] elementData;
    
    // Количество элементов (не размер массива!)
    private int size;
    
    // Начальная ёмкость
    private static final int DEFAULT_CAPACITY = 10;
}

Процесс расширения

Этап 1: Инициализация

ArrayList<Integer> list = new ArrayList<>();
// elementData = {} (пусто)
// size = 0
// capacity = 0 (пока не добавили элементы)

Этап 2: Добавление первого элемента

list.add(1);

// Внутри ArrayList:
// 1. Проверяет, есть ли место: size (0) < capacity (0)
// 2. Нет места! Нужно расширить
// 3. Создаёт новый массив размером 10 (DEFAULT_CAPACITY)
// 4. elementData = new Object[10]
// 5. Копирует старые элементы (их нет)
// 6. Добавляет новый элемент в позицию 0
// 7. size = 1

Этап 3: Добавление элементов 2-10

for (int i = 2; i <= 10; i++) {
    list.add(i);
    // Всё помещается в существующий массив
    // size увеличивается на 1
}

// После цикла:
// elementData = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
// size = 10
// capacity = 10 (массив полный!)

Этап 4: Добавление 11-го элемента — РАСШИРЕНИЕ

list.add(11);

// Внутри ArrayList.add():
private void ensureCapacity(int minCapacity) {
    if (elementData.length < minCapacity) {
        grow(minCapacity);
    }
}

private void grow(int minCapacity) {
    // Старая ёмкость
    int oldCapacity = elementData.length; // 10
    
    // Новая ёмкость = 10 + (10/2) = 15
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // >> 1 это деление на 2 (битовый сдвиг)
    
    // Создаём новый массив большего размера
    Object[] newArray = new Object[newCapacity];
    
    // КОПИРУЕМ все элементы из старого массива в новый
    System.arraycopy(elementData, 0, newArray, 0, size);
    
    // Заменяем старый массив новым
    elementData = newArray;
}

Визуализация процесса

Шаг 1: Добавляем 1-10 элементов
elementData: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
size = 10, capacity = 10 (ПОЛНЫЙ!)

Шаг 2: Добавляем 11-й элемент
1. Проверка: size (10) == capacity (10) → расширяем!
2. newCapacity = 10 + 10/2 = 15
3. Создаём новый массив[15]
4. Копируем 10 элементов из старого массива
5. Добавляем новый элемент
6. Готово!

elementData: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, null, null, null, null]
size = 11, capacity = 15

Шаг 3: Добавляем 12-15 элементы
elementData: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
size = 15, capacity = 15 (снова полный!)

Шаг 4: Добавляем 16-й элемент
1. Проверка: size (15) == capacity (15) → расширяем!
2. newCapacity = 15 + 15/2 = 22
3. Копируем 15 элементов в новый массив[22]
4. Добавляем 16-й элемент

elementData: [1, 2, ..., 15, 16, null, null, null, null, null, null]
size = 16, capacity = 22

Алгоритм расширения

// Формула: newCapacity = oldCapacity * 1.5 (увеличение на 50%)

// Пример progression:
Добавление элементов:  1-10   11    12-15  16    17-22  23
ёмкость:             10    15    15     22    22     33
расширение при:      1     11    16     23    ...

// Это амортизированное расширение
// Не расширяем на +1, а расширяем на +50% за раз
// Это снижает количество расширений

Код из реального ArrayList

// Из JDK 17+
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

Производительность расширения

public class ArrayListPerformance {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        
        long startTime = System.nanoTime();
        
        // Добавляем 1 млн элементов
        for (int i = 0; i < 1_000_000; i++) {
            list.add(i); // Время: ~100ms
        }
        
        long endTime = System.nanoTime();
        long duration = (endTime - startTime) / 1_000_000; // ms
        
        System.out.println("Время: " + duration + "ms");
        System.out.println("Количество расширений: ~20");
        // Почему ~20 расширений?
        // 10 → 15 → 22 → 33 → 49 → 73 → 109 → 163 → 244 → ...
        // Логарифмическое количество операций!
    }
}

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

1. add(E element)

ArrayList<String> list = new ArrayList<>(2);
list.add("A"); // size=1, capacity=2
list.add("B"); // size=2, capacity=2 (полный!)
list.add("C"); // РАСШИРЕНИЕ! capacity=3

2. addAll(Collection c)

ArrayList<Integer> list = new ArrayList<>(5);
list.addAll(Arrays.asList(1,2,3,4,5)); // size=5, capacity=5
list.addAll(Arrays.asList(6,7)); // РАСШИРЕНИЕ! capacity=8

3. ensureCapacity(int minCapacity)

ArrayList<Integer> list = new ArrayList<>();
list.ensureCapacity(100); // Сразу выделяет capacity=100

Важные детали

1. Старый массив становится garbage

ArrayList<Integer> list = new ArrayList<>(2);
list.add(1);
list.add(2);
// elementData[1] указывает на массив размером 2

list.add(3);
// РАСШИРЕНИЕ!
// Создаётся новый массив размером 3
// Старый массив размером 2 становится недостижим
// GC освобождает его память

2. System.arraycopy() — быстрый нативный метод

// Копирование выполняется на уровне C/C++
// Это быстро! (~nanoseconds per element)

System.arraycopy(
    elementData,    // источник
    0,              // позиция в источнике
    newArray,       // назначение
    0,              // позиция в назначении
    size            // количество элементов
);

3. Потеря производительности из-за расширений

// ПЛОХО: не знаем размер заранее
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);
    // ~20 расширений с копированием
}

// ХОРОШО: знаем размер заранее
ArrayList<Integer> list = new ArrayList<>(1_000_000);
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);
    // Ноль расширений!
}

// РЕЗУЛЬТАТ: второй вариант НАМНОГО быстрее

Амортизированная сложность

М операция add() в середине развития ArrayList:
  - Обычно O(1) — просто добавляем элемент
  - Иногда O(n) — когда расширяем и копируем все элементы

Амортизированно: O(1) на среднюю операцию

Почему? Расширения редкие:
- За n добавлений бывает O(log n) расширений
- Каждое расширение копирует O(n) элементов
- Итого: O(n) работы на n операций = O(1) в среднем

Практические выводы

1. Знаешь размер? → Используй new ArrayList<>(size)
2. Не знаешь? → Используй ensureCapacity() если добавляешь много
3. Производительность критична? → Профилируй!
4. Удаление элементов? → Тоже O(n) из-за сдвига элементов

Код расширения (упрощённо)

public class SimpleArrayList<E> {
    private Object[] elementData = new Object[10];
    private int size = 0;
    
    public void add(E element) {
        // Проверяем место
        if (size == elementData.length) {
            // РАСШИРЕНИЕ!
            Object[] newArray = new Object[elementData.length + (elementData.length >> 1)];
            System.arraycopy(elementData, 0, newArray, 0, size);
            elementData = newArray;
        }
        
        // Добавляем элемент
        elementData[size++] = element;
    }
}

Вывод

При расширении ArrayList:

1. Проверяет, полный ли массив
2. Если полный → создаёт новый массив размером oldSize * 1.5
3. Копирует ВСЕ элементы из старого массива в новый
4. Заменяет ссылку на новый массив
5. Старый массив становится garbage

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