Java Interview Questions

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

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

В чому різниця між List, Set та Queue?

Кеш-локальність = елементи розташовані поруч у пам'яті. CPU завантажує 64-байтну лінію кешу за один раз, отримуючи одразу 8-16 посилань. Це прискорює ітерацію у 10-100 разів пор...

Ukrainian Колекції Вихідний Markdown
Мовні версії: English Russian Ukrainian

🟢 Junior Level

List, Set та Queue — три основні типи колекцій у Java.

Головна різниця:

Тип Порядок Дублікати Доступ Аналогія
List Зберігає порядок ✅ Можна За індексом list.get(0) Список покупок
Set Не гарантує (крім LinkedHashSet) ❌ Не можна Тільки перебор Набір ключів
Queue FIFO (First-In-First-Out — перший доданий елемент буде першим вилучений) ✅ Можна Тільки голову Черга в магазині

Приклад:

// List: порядок та дублікати
List<String> list = new ArrayList<>();
list.add("B");
list.add("A");
list.add("B");  // OK
// → [B, A, B]

// Set: тільки унікальні
Set<String> set = new HashSet<>();
set.add("B");
set.add("A");
set.add("B");  // НЕ додасться
// → [A, B] (порядок не гарантований)

// Queue: FIFO
Queue<String> queue = new ArrayDeque<>();
queue.offer("B");
queue.offer("A");
queue.poll();  // → "B" (перший прийшов, перший пішов)

🟡 Middle Level

List (Послідовність)

// Реалізації:
ArrayList    // Динамічний масив → O(1) читання
LinkedList   // Двозв'язний список → O(n) читання

// Операції:
list.get(0)       // O(1) для ArrayList, O(n) для LinkedList
list.add(e)       // O(1)* амортизоване
list.contains(e)  // O(n) лінійний пошук
list.remove(0)    // O(n) зсув масиву

Set (Множина)

// Реалізації:
HashSet         // На базі HashMap → O(1) пошук
LinkedHashSet   // + порядок додавання
TreeSet         // Червоно-чорне дерево → O(log n), відсортований

// Всередині HashSet:
// HashMap<E, Object> де value = static final Object PRESENT
// → Попри один спільний об'єкт PRESENT, HashSet витрачає більше пам'яті, ніж ArrayList, через обгортку в HashMap.Node (ключ + value + hash + next pointer).

// Операції:
set.add(e)       // O(1) для HashSet, O(log n) для TreeSet
set.contains(e)  // O(1) для HashSet, O(log n) для TreeSet
set.remove(e)    // O(1) для HashSet

Queue (Черга)

// Реалізації:
ArrayDeque        // Кільцевий масив → O(1) вставка/видалення
PriorityQueue     // Binary Heap → O(log n), вилучення за пріоритетом
LinkedList        // Можна як Queue, але повільніший за ArrayDeque

// Методи:
queue.offer(e)    // true/false (не кидає exception)
queue.add(e)      // кидає exception при помилці
queue.poll()      // null якщо пуста
queue.remove()    // кидає exception якщо пуста
queue.peek()      // null якщо пуста
queue.element()   // кидає exception якщо пуста

Порівняння продуктивності

Операція ArrayList HashSet TreeSet ArrayDeque
Додавання O(1)* O(1) O(log n) O(1)
Пошук O(n) O(1) O(log n) O(n)
Видалення O(n) O(1) O(log n) O(1)
Доступ за індексом O(1) Н/Д Н/Д Н/Д

Коли що використовувати

Сценарій Що обрати Чому
Зберігання з порядком List Зберігає порядок
Перевірка унікальності Set Швидкий contains
Обробка по порядку Queue FIFO
Сортування TreeSet Автоматичне сортування
Часті читання ArrayList Кеш-локальність

Кеш-локальність = елементи розташовані поруч у пам’яті. CPU завантажує 64-байтну лінію кешу за один раз, отримуючи одразу 8-16 посилань. Це прискорює ітерацію у 10-100 разів порівняно з розкиданими елементами LinkedList.

Коли НЕ використовувати

  • List (ArrayList): Не використовуйте для перевірки унікальності — contains() = O(n)
  • HashSet: Не використовуйте якщо важливий порядок вставки — візьміть LinkedHashSet
  • TreeSet: Не використовуйте якщо не потрібне сортування — O(log n) повільніше за O(1)
  • Queue: Не використовуйте для довільного доступу — візьміть List

🔴 Senior Level

Memory Footprint

ArrayList:
  → Object[] array (4-8 байт на посилання)
  → Мінімальний оверхед

HashSet:
  → HashMap всередині
  → Node<K,V> для кожного елемента
  → + static final Object PRESENT (один на всі)
  → ~2x більше пам'яті, ніж ArrayList!

TreeSet:
  → TreeMap (червоно-чорне дерево)
  → Entry<K,V> + left + right + parent + color
  → ~4x більше пам'яті, ніж ArrayList

Concurrency

// List
CopyOnWriteArrayList      // Багато читань, мало записів
Collections.synchronizedList  // Універсальний, але повільний

// Set
ConcurrentHashMap.newKeySet()  // Найкращий вибір!
Collections.synchronizedSet()

// Queue
ConcurrentLinkedQueue     // Lock-free, wait-free
LinkedBlockingQueue       // Producer-Consumer
ArrayBlockingQueue        // Bounded, один лок
SynchronousQueue          // Нульова ємність

Cache Locality

ArrayList: елементи поруч у пам'яті
  → CPU prefetching → L1/L2 cache hits
  → Ітерація: дуже швидко

HashSet: елементи розкидані
  → Cache misses при ітерації
  → Але O(1) contains компенсує

LinkedList: вузли в різних кінцях купи
  → Cache miss на КОЖНОМУ елементі
  → Антипатерн для сучасних CPU!

Java 21: SequencedCollection

// Тепер List та Deque наслідують SequencedCollection
SequencedCollection<String> seq = new ArrayList<>();
seq.addFirst("A");   // Новий метод!
seq.addLast("B");    // Новий метод!
seq.getFirst();      // Новий метод!
seq.reversed();      // Відображення у зворотному порядку

// Для Set:
SequencedSet<String> seqSet = new LinkedHashSet<>();
// TreeSet теж підтримує через NavigableSet

Bloom Filter для величезних Set

// Коли елементів мільярди, HashSet не вміщується в RAM
// Рішення: Bloom Filter (стороння структура даних, не входить у JCF)
// «False positive» = фільтр може сказати «елемент можливо є» коли його насправді немає.
// Але «false negative» неможливий: якщо фільтр каже «елемента немає» — він точно відсутній.

BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(),
    expectedInsertions,
    falsePositiveRate
);

// O(1) пошук, мінімальна пам'ять
// Але: можливі false positives (немає false negatives)

Production Experience

Реальний сценарій: HashSet vs ArrayList для contains

// ❌ O(n) пошук у списку з 1 млн елементів
List<String> blacklist = List.of("bad1", "bad2", ...);
if (blacklist.contains(input)) { ... }  // Повільно!

// ✅ O(1) пошук
Set<String> blacklist = Set.of("bad1", "bad2", ...);
if (blacklist.contains(input)) { ... }  // Швидко!

Best Practices

  1. List → ArrayList за замовчуванням
  2. Set → HashSet для унікальності, TreeSet для сортування
  3. Queue → ArrayDeque для стека/черги
  4. Concurrency → ConcurrentHashMap.newKeySet() для Set
  5. Пам’ять → ArrayList компактніший за Set
  6. Cache Locality → ArrayList > LinkedList
  7. Java 21 → SequencedCollection для загального інтерфейсу

Резюме для Senior

  • List = індексація, порядок, кеш-локальність
  • Set = унікальність, O(1) contains (HashSet)
  • Queue = FIFO/LIFO, backpressure (Bounded)
  • Пам’ять: ArrayList < HashSet < TreeSet
  • Cache Locality: ArrayList » LinkedList
  • Concurrency: CopyOnWriteArrayList, ConcurrentHashMap.newKeySet()
  • Bloom Filter для величезних множин
  • Java 21 → SequencedCollection уніфікує API

🎯 Шпаргалка для інтерв’ю

Обов’язково знати:

  • List = порядок + дублікати + доступ за індексом (ArrayList O(1) читання, LinkedList O(n))
  • Set = унікальність через equals()/hashCode(), HashSet = O(1) пошук, TreeSet = O(log n) сортування
  • Queue = FIFO, методи offer/poll/peek безпечніші за add/remove/element
  • HashSet всередині = HashMap<E, Object> зі спільним PRESENT, ~2x більше пам’яті ніж ArrayList
  • Кеш-локальність: ArrayList » LinkedList — елементи поруч у пам’яті, CPU prefetching
  • Для concurrency: CopyOnWriteArrayList (багато читань), ConcurrentHashMap.newKeySet() для Set
  • Bloom Filter — для величезних множин (мільярди елементів), O(1) пошук, можливі false positives

Часті уточнюючі запитання:

  • Чому HashSet споживає більше пам’яті ніж ArrayList? — Всередині HashMap.Node (ключ + value + hash + next pointer)
  • Коли використовувати TreeSet замість HashSet? — Коли потрібне сортування, але O(log n) повільніше за O(1)
  • Чим offer/poll відрізняються від add/remove? — offer/poll повертають false/null замість exception
  • Як забезпечити thread-safety для Set? — ConcurrentHashMap.newKeySet() — найкращий вибір

Червоні прапорці (НЕ говорити):

  • ❌ “LinkedList швидший за ArrayList для ітерації” — навпаки, кеш-локальність ArrayList дає перевагу у 10-100 разів
  • ❌ “HashSet гарантує порядок вставки” — це LinkedHashSet, звичайний HashSet не гарантує порядок
  • ❌ “Для thread-safe Set потрібен Collections.synchronizedSet” — ConcurrentHashMap.newKeySet() ефективніше
  • ❌ “Queue та List взаємозамінні” — Queue не підтримує довільний доступ за індексом

Пов’язані теми:

  • [[Які основні інтерфейси Collection Framework]]
  • [[В чому різниця між ArrayList та LinkedList]]
  • [[Яка часова складність операцій в ArrayList]]
  • [[Що таке Queue і які реалізації існують]]