Почему коллекция ArrayList будет менее производительна при вставке большого количества элементов в конец?

# ArrayList при вставке в конец — производительность

Актуально, ArrayList очень эффективен при добавлении элементов в конец, благодаря амортизированной O(1) сложности. Однако при добавлении большого количества элементов может возникнуть проблема с переаллокацией памяти. Разберём это детально.

Как работает ArrayList

ArrayList использует внутренний массив для хранения элементов:

public class ArrayList<E> implements List<E> {
    private Object[] elementData;  // Внутренний массив
    private int size;             // Количество элементов
    private static final int DEFAULT_CAPACITY = 10;
}

Механизм добавления элементов

Фаза 1: Есть свободное место

ArrayList<Integer> list = new ArrayList<>();
list.add(1);  // elementData.length = 10, size = 1 — быстро!
list.add(2);  // elementData.length = 10, size = 2 — быстро!
list.add(3);  // elementData.length = 10, size = 3 — быстро!
// ...
list.add(10); // elementData.length = 10, size = 10 — всё еще быстро

Фаза 2: Нехватка места — переаллокация

list.add(11);  // elementData.length = 10, но size будет 11 — НЕДОСТАТОЧНО МЕСТА!

// Происходит:
// 1. Создаётся новый массив большего размера
Object[] newElementData = new Object[capacity * 3 / 2];  // Увеличение на 50%

// 2. Копируются все старые элементы
system.arraycopy(elementData, 0, newElementData, 0, size);

// 3. Старый массив отбрасывается (для сборки мусора)
elementData = newElementData;

// 4. Добавляется новый элемент
elementData[size++] = 11;

Производительность при большом количестве добавлений

Проблема: множественные переаллокации

ArrayList<Integer> list = new ArrayList<>(1);  // Начальная ёмкость 1

for (int i = 0; i < 1_000_000; i++) {
    list.add(i);  // Каждое добавление может вызвать переаллокацию
}

// Что происходит:
// 1. add(0)     → capacity = 1, size = 1 (нет переаллокации)
// 2. add(1)     → capacity = 1, size = 1... ПЕРЕАЛЛОКАЦИЯ! → capacity = 1
// 3. add(2)     → capacity = 2, size = 2 (нет переаллокации)
// 4. add(3)     → capacity = 2, size = 2... ПЕРЕАЛЛОКАЦИЯ! → capacity = 3
// 5. add(4)     → capacity = 3, size = 3... ПЕРЕАЛЛОКАЦИЯ! → capacity = 4 (округление)
// И так далее...

// Каждая переаллокация:
// - Создаёт новый массив (O(1))
// - Копирует все элементы (O(n))
// - Требует работы сборщика мусора (может быть дорого)

Пример с измерением

public class ArrayListPerformance {
    public static void main(String[] args) {
        // ❌ Плохой вариант: начинаем с маленькой ёмкости
        long start = System.nanoTime();
        ArrayList<Integer> list1 = new ArrayList<>(1);
        for (int i = 0; i < 1_000_000; i++) {
            list1.add(i);
        }
        long duration1 = System.nanoTime() - start;
        System.out.println("ArrayList(1): " + duration1 + " ns");  // Долго!
        
        // ✅ Хороший вариант 1: указываем начальную ёмкость
        start = System.nanoTime();
        ArrayList<Integer> list2 = new ArrayList<>(1_000_000);
        for (int i = 0; i < 1_000_000; i++) {
            list2.add(i);
        }
        long duration2 = System.nanoTime() - start;
        System.out.println("ArrayList(1_000_000): " + duration2 + " ns");  // Быстро!
        
        // ✅ Хороший вариант 2: используем default capacity (10)
        start = System.nanoTime();
        ArrayList<Integer> list3 = new ArrayList<>();
        for (int i = 0; i < 1_000_000; i++) {
            list3.add(i);
        }
        long duration3 = System.nanoTime() - start;
        System.out.println("ArrayList(): " + duration3 + " ns");  // Быстро!
        
        System.out.println();
        System.out.println("Разница (плохой/хороший): " + (duration1 / duration2) + "x медленнее");
    }
}

// Примерный вывод:
// ArrayList(1): 250_000_000 ns
// ArrayList(1_000_000): 50_000_000 ns
// ArrayList(): 60_000_000 ns
// Разница: ~4x медленнее при начальной ёмкости 1

Амортизированная сложность O(1)

Теория объясняет, почему это работает:

Добавления:  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Емкость:     1 1 1 2 2 2 3 3 3 4  4  4  6  6  6  8  8  8  12 12
Пеаллокация: -                 ✓           ✓           ✓

Количество переаллокаций для N элементов: O(log N)
Средняя стоимость на элемент: O(N) / N = O(1) ← амортизированная!

Так что в среднем каждое добавление стоит O(1), но иногда может быть O(n).

Сравнение с LinkedList

// Сценарий: добавить 1 млн элементов в конец

// ❌ ArrayList с маленькой ёмкостью
ArrayList<Integer> arrayList = new ArrayList<>(1);
for (int i = 0; i < 1_000_000; i++) {
    arrayList.add(i);  // О(1) в среднем, но может быть O(n) при переаллокации
}
// Результат: ~60-250 мс (в зависимости от переаллокаций)

// ✅ ArrayList с правильной ёмкостью
ArrayList<Integer> arrayList = new ArrayList<>(1_000_000);
for (int i = 0; i < 1_000_000; i++) {
    arrayList.add(i);  // O(1) — нет переаллокаций
}
// Результат: ~50 мс

// ✓ LinkedList
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 1_000_000; i++) {
    linkedList.add(i);  // O(1) — просто добавляем узел
}
// Результат: ~100-150 мс
// Медленнее из-за создания объектов Node и расходов памяти

Стратегии оптимизации

1. Укажи начальную ёмкость

// ❌ Неэффективно
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 100_000; i++) {
    list.add("item" + i);
}

// ✅ Оптимально
ArrayList<String> list = new ArrayList<>(100_000);
for (int i = 0; i < 100_000; i++) {
    list.add("item" + i);
}

2. Используй ensureCapacity()

ArrayList<Integer> list = new ArrayList<>();
list.ensureCapacity(1_000_000);  // Заранее выделяем место
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);  // Без переаллокаций
}

3. Stream API с collect()

// Немного медленнее, но удобнее
List<Integer> list = IntStream.range(0, 1_000_000)
    .boxed()
    .collect(Collectors.toCollection(() -> new ArrayList<>(1_000_000)));

Реальный пример: работа с БД

public List<User> getAllUsers(int expectedCount) {
    // ❌ Неправильно
    List<User> users = new ArrayList<>();
    try (ResultSet rs = statement.executeQuery("SELECT * FROM users")) {
        while (rs.next()) {
            users.add(new User(rs));
        }
    }
    // Множественные переаллокации если expectedCount > 10
    
    // ✅ Правильно
    List<User> users = new ArrayList<>(expectedCount);
    try (ResultSet rs = statement.executeQuery("SELECT COUNT(*) FROM users")) {
        if (rs.next()) {
            int count = rs.getInt(1);
            users.ensureCapacity(count);
        }
    }
    // Или прямо с известным размером:
    // List<User> users = new ArrayList<>(10000);
    
    try (ResultSet rs = statement.executeQuery("SELECT * FROM users")) {
        while (rs.next()) {
            users.add(new User(rs));
        }
    }
}

Когда ArrayList медленнее по-настоящему

1. Вставка в начало/середину

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 10_000; i++) {
    list.add(0, i);  // ❌ O(n) — сдвигает все элементы
}
// Результат: O(n²) — очень медленно!

// Лучше используй LinkedList для этого
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10_000; i++) {
    list.addFirst(i);  // O(1)
}

2. Частое удаление

// ❌ Медленно
for (int i = 0; i < list.size(); i++) {
    if (list.get(i).isInvalid()) {
        list.remove(i);  // O(n) за каждое удаление
    }
}

// ✅ Лучше
list.removeIf(item -> item.isInvalid());  // O(n) один раз

Выводы

✓ ArrayList добавляет в конец с амортизированной O(1) ✓ Указывай начальную ёмкость, если знаешь размер ✓ Переаллокации происходят редко и увеличиваются в размере (1.5x) ✓ При добавлении в начало/середину используй LinkedList ✓ Удаления дорогие — используй removeIf() ✓ Для работы с потоками есть CopyOnWriteArrayList