Java Interview Questions

Главная / Все ответы / Коллекции

Вопрос 5 · Раздел 4

Какова временная сложность операций в ArrayList?

Branch prediction — CPU предсказывает результат условия (if) и заранее загружает следующие инструкции. Если предсказание верно — код выполняется без задержек. Pipeline — CPU обр...

Russian Коллекции Исходный Markdown
Версии по языкам: English Russian Ukrainian

🟢 Junior Level

Временная сложность — сколько времени занимает операция в зависимости от размера списка.

Операция Сложность Пояснение
get(index) O(1) Мгновенно, доступ по индексу
add(e) O(1)* Постоянное время в среднем. При заполнении массива происходит ресайз (копирование всех элементов), но это случается редко.
add(index, e) O(n) Нужно сдвинуть элементы
remove(index) O(n) Нужно сдвинуть элементы
contains(e) O(n) Линейный поиск
size() O(1) Хранится размер

Пример:

ArrayList<String> list = new ArrayList<>();

list.add("A");        // O(1) — быстро
list.get(0);          // O(1) — мгновенно!
list.add(0, "B");     // O(n) — сдвиг всех элементов
list.remove(0);       // O(n) — сдвиг всех элементов
list.contains("A");   // O(n) — перебор

🟡 Middle Level

Amortized O(1) для add(e)

Амортизированная сложность = если выполнить N операций, суммарное время = O(N), значит одна операция в среднем = O(1). Отдельная операция может занять O(n) при ресайзе, но это случается редко (каждые ~1.5x заполнений).

// add(e) = O(1) в среднем, но иногда O(n)

// Почему?
// 1. Есть место в массиве → O(1)
// 2. Массив заполнен → ресайз (O(n))

// Резайз: новый массив × 1.5
// capacity: 10 → 15 → 22 → 33 → 49 → ...

// Амортизированная сложность:
// N добавлений = O(N) суммарно
// Одно добавление = O(1) в среднем

Детали операций

// get(index): O(1)
// → array[index] → мгновенно

// add(e): O(1)* амортизированное
// → Если место: array[size++] = e
// → Если нет: resize + arraycopy

// add(index, e): O(n)
// → System.arraycopy(index, index+1, size-index)
// → array[index] = e
// → Нативный код → быстро!

// remove(index): O(n)
// → System.arraycopy(index+1, index, size-index-1)
// → array[size-1] = null (для GC)

// contains(e): O(n)
// → for (int i = 0; i < size; i++)
//     if (element.equals(e)) return true;

Bulk операции (Java 8+)

// removeIf(predicate): O(n)
// → Один проход для поиска
// → Один сдвиг для удаления
// → Вместо O(n²) в цикле!

// replaceAll(operator): O(n)
// → Прямая работа с массивом
// → Без создания итератора

// removeAll(collection): O(n × m)
// → Для каждого элемента проверяет collection

Оптимизации

// 1. ensureCapacity(size)
// → Убрать ресайзы если известен размер
// → new ArrayList<>(1_000_000);

// 2. trimToSize()
// → Уменьшить массив до реального размера
// → После массового удаления

// 3. Отсортированный ArrayList
// → Collections.binarySearch() → O(log n)
// → Вместо O(n) contains!

🔴 Senior Level

System.arraycopy Deep Dive

ArrayList.remove(0):
  → System.arraycopy(src, 1, dest, 0, size-1)

Under the hood:
  → JVM intrinsic — метод, который JVM заменяет на оптимизированную машинную инструкцию
  → memmove — стандартная C-функция копирования памяти
  → SIMD — параллельная обработка на уровне CPU
  → Перемещает 64 байта за такт (cache line)
  
→ O(n) теоретически, но константа МАЛЕНЬКАЯ
→ Для 1000 элементов: ~1 мкс
→ Быстрее, чем O(1) LinkedList с аллокацией!

Резайз: почему 1.5x?

// Некоторые реализации C++ std::vector используют 2x (libstdc++ GCC), другие — 1.5x или 2x (libc++ Clang).
// Java ArrayList: 1.5x

// Почему?
// 1.5x позволяет переиспользовать память:
//   10 → 15 (освободили 0-9)
//   15 → 22 (освободили 0-14)
//   22 → 33 (0-21 все ещё заняты, но 0-9 свободны!)
//   → Можно переиспользовать блок 0-9

// 2x не позволяет:
//   10 → 20 (0-9 свободны)
//   20 → 40 (0-19 заняты)
//   → Блок 0-9 слишком мал для 40
//   → Фрагментация кучи!

Memory Bandwidth瓶颈

Для больших списков (> 1 млн):
  add(e) ограничена скоростью записи в RAM
  → ~25 ГБ/с для DDR4
  → 1 млн ссылок (8 МБ) → ~0.3 мс

Это физический предел!

CPU Pipeline и Branch Prediction

Branch prediction — CPU предсказывает результат условия (if) и заранее загружает следующие инструкции. Если предсказание верно — код выполняется без задержек. Pipeline — CPU обрабатывает несколько инструкций одновременно на разных стадиях.

// contains(e): линейный поиск
for (int i = 0; i < size; i++) {
    if (array[i].equals(e)) return true;
}

// CPU branch predictor:
// → Пока ищем, предсказывает "не найдено"
// → Pipeline не прерывается
// → Почти O(n) без штрафов

Production Experience

Реальный сценарий: ensureCapacity спас 30 ресайзов

// ❌ Без ensureCapacity
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add(data[i]);  // ~30 ресайзов!
}

// ✅ С ensureCapacity
ArrayList<String> list = new ArrayList<>(1_000_000);
for (int i = 0; i < 1_000_000; i++) {
    list.add(data[i]);  // 0 ресайзов!
}

// Результат: -15% времени

Best Practices

  1. get(index) = O(1) — используйте для частых чтений
  2. add(e) = O(1)* — ресайзы редки
  3. add(0, e) = O(n) — но быстро благодаря SIMD
  4. removeIf() = O(n) — вместо цикла удалений
  5. ensureCapacity() — если известен размер
  6. binarySearch() = O(log n) — для отсортированных
  7. trimToSize() — после массового удаления

Резюме для Senior

  • get(index) = O(1) — идеальная кэш-локальность
  • add(e) = O(1)* amortized — ресайз × 1.5
  • add/remove(index) = O(n) — но SIMD ускоряет
  • contains = O(n) → binarySearch = O(log n)
  • System.arraycopy = нативный memmove
  • 1.5x ресайз — меньше фрагментации, чем 2x
  • removeIf = O(n) вместо O(n²)
  • ensureCapacity = экономия 30+ копирований

🎯 Шпаргалка для интервью

Обязательно знать:

  • get(index) = O(1), add(e) = O(1)* amortized, add/remove(index) = O(n)
  • Амортизированное O(1): ресайз случается редко (каждые ~1.5x заполнений), N добавлений = O(N) суммарно
  • Резайз × 1.5 (не 2x) — позволяет переиспользовать освободившуюся память, меньше фрагментация кучи
  • System.arraycopy() = JVM intrinsic → memmove + SIMD — перемещает 64 байта за такт, константа ОЧЕНЬ маленькая
  • removeIf() = O(n) вместо O(n²) в цикле — один проход для поиска + один сдвиг для удаления
  • ensureCapacity() экономит 30+ ресайзов при загрузке 1 млн элементов (-15% времени)
  • Для отсортированного ArrayList: Collections.binarySearch() = O(log n) вместо O(n) contains
  • CPU branch prediction делает линейный поиск почти без штрафов — pipeline не прерывается

Частые уточняющие вопросы:

  • Что значит «amortized O(1)»? — Отдельная операция может быть O(n) при ресайзе, но в среднем O(1) за N операций
  • Почему ресайз 1.5x а не 2x? — 1.5x позволяет переиспользовать старые блоки памяти, 2x вызывает фрагментацию
  • Когда contains() может быть быстрее O(n)? — Если список отсортирован — binarySearch = O(log n)
  • Почему System.arraycopy() быстрый? — Нативный memmove + SIMD инструкции + CPU prefetching

Красные флаги (НЕ говорить):

  • ❌ “add(e) всегда O(1)” — при ресайзе O(n), правильно говорить «amortized O(1)»
  • ❌ “remove(index) = O(n) значит это медленно” — System.arraycopy() очень быстр благодаря SIMD
  • ❌ “ArrayList всегда O(n) для поиска” — если отсортирован, binarySearch = O(log n)
  • ❌ “Ресайз 2x лучше потому что реже” — 2x вызывает фрагментацию кучи и wasted memory

Связанные темы:

  • [[Какие основные интерфейсы Collection Framework]]
  • [[Какова временная сложность операций в LinkedList]]
  • [[В чём разница между ArrayList и LinkedList]]
  • [[Когда использовать ArrayList, а когда LinkedList]]