Java Interview Questions

Головна / Усі відповіді / Колекції

Питання 5 · Розділ 4

Яка часова складність операцій в ArrayList?

Branch prediction — CPU передбачає результат умови (if) та заздалегідь завантажує наступні інструкції. Якщо передбачення вірне — код виконується без затримок. Pipeline — CPU обр...

Ukrainian Колекції Вихідний 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]]