Які основні інтерфейси Collection Framework?

🟢 Junior Level

Collection Framework — це набір інтерфейсів та класів у Java для роботи з групами об’єктів.

Основні інтерфейси:

Інтерфейс	Що робить	Приклади
List	Упорядкований список, можна дублікати	ArrayList, LinkedList
Set	Тільки унікальні елементи	HashSet, TreeSet
Queue	Черга (FIFO)	PriorityQueue, ArrayDeque
Map	Пари ключ-значення	HashMap, TreeMap

Map технічно НЕ наслідується від Collection (це паралельний інтерфейс), але включений у Collection Framework для повноти.

Проста аналогія:

List = список покупок (порядок важливий, можна повторення)
Set = набір унікальних ключів (порядок не важливий, без повторень)
Queue = черга в магазині (хто перший прийшов, той перший пішов)
Map = словник (слово → визначення)

Приклад:

List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Apple");  // Можна дублікати

Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple");  // НЕ добавится (уже есть)

**Як Set дізнається про дублікат:** `HashSet` викликає `hashCode()` для знаходження «корзини» та `equals()` для перевірки збігу всередині неї. Тому елементи повинні коректно реалізовувати `hashCode()` та `equals()`.

Map<String, Integer> map = new HashMap<>();
map.put("Apple", 1);
map.put("Banana", 2);

🟡 Middle Level

Ієрархія інтерфейсів

Iterable<E>
  └── Collection<E>
       ├── List<E>         ← Упорядкований, дублікати OK
       │    ├── ArrayList
       │    └── LinkedList
       ├── Set<E>          ← Унікальні елементи
       │    ├── HashSet
       │    ├── LinkedHashSet
       │    └── TreeSet (SortedSet)
       └── Queue<E>        ← Черга
            ├── PriorityQueue
            └── Deque
                 └── ArrayDeque

Map<K,V> (НЕ наслідується від Collection!)
  ├── HashMap
  ├── LinkedHashMap
  └── TreeMap (SortedMap)

Ключові особливості

List:

Доступ за індексом: list.get(0)
Зберігає порядок додавання
Можна дублікати

Set:

Унікальність через equals() та hashCode()
HashSet: порядок не гарантований
LinkedHashSet: порядок додавання
TreeSet: відсортований

Queue:

FIFO (First-In-First-Out)
Методи: offer(), poll(), peek()
PriorityQueue: вилучення за пріоритетом

Map:

Пари ключ-значення
Ключі унікальні
get(key), put(key, value)

Маркерні інтерфейси

RandomAccess — маркерний інтерфейс без жодного методу. Він лише повідомляє JDK: «цей список підтримує швидкий доступ за індексом», щоб обрати оптимальний алгоритм (наприклад, для сортування).

// RandomAccess — швидкий доступ за індексом
ArrayList implements RandomAccess   // get(i) = O(1)
LinkedList                          // get(i) = O(n), немає RandomAccess

// NavigableSet — навігація по елементах
TreeSet implements NavigableSet
  → lower(e), floor(e), ceiling(e), higher(e)

Fail-Fast vs Fail-Safe

Fail-Fast = колекція відстежує модифікації через modCount (лічильник змін) та кидає ConcurrentModificationException при виявленні змін під час ітерації. Це детектор багів для одного потоку, а не механізм синхронізації.

Fail-Safe = ітератор працює з копією даних (snapshot), тому зміни оригіналу не впливають на ітерацію. Ніколи не кидає ConcurrentModificationException.

// Fail-Fast (ArrayList, HashMap)
List<String> list = new ArrayList<>();
Iterator<String> it = list.iterator();
list.add("new");    // Модификация
it.next();          // → ConcurrentModificationException!

// Fail-Safe (CopyOnWriteArrayList, ConcurrentHashMap)
List<String> safe = new CopyOnWriteArrayList<>();
Iterator<String> safeIt = safe.iterator();
safe.add("new");    // Модификация
safeIt.next();      // → Работает (итератор по копии)

🔴 Senior Level

Java 21: Sequenced Collections (JEP 431)

Більшість production-систем працюють на Java 11/17, де SequencedCollection недоступний. Використовуйте конкретні типи (ArrayList, LinkedList) з методами get(0)/get(size-1).

// Новий інтерфейс для колекцій з передбачуваним порядком
SequencedCollection<E>
  → addFirst(e), addLast(e)
  → getFirst(), getLast()
  → reversed()      // Відображення у зворотному порядку

// Спадкоємці: List, Deque

SequencedSet<E>
  → Реалізації: LinkedHashSet, SortedSet

SequencedMap<K, V>
  → firstEntry(), lastEntry()
  → reversed()
  → Реалізації: LinkedHashMap, SortedMap

До Java 21: Не було загального інтерфейсу для “перший/останній елемент” Після Java 21: Єдиний контракт для всіх упорядкованих колекцій

Spliterator (Java 8+)

// Заміна Iterator для Stream API
Spliterator<E> spliterator = list.spliterator();

// Характеристики:
// IMMUTABLE    → колекція не змінюється
// CONCURRENT   → можна змінювати паралельно
// DISTINCT     → всі елементи унікальні
// SORTED       → елементи відсортовані
// ORDERED      → порядок важливий

// Ці характеристики використовує Stream API для оптимізації паралельної обробки
// (наприклад, DISTINCT дозволяє уникнути зайвих перевірок, а SORTED — пропустити повторне сортування)
spliterator.trySplit()  // Розділення для паралельної обробки

Under the Hood: RandomAccess оптимізація

// JDK перевіряє RandomAccess для вибору алгоритму
Collections.binarySearch(list, key);

// Всередині JDK:
if (list instanceof RandomAccess) {
    // Бінарний пошук за індексами → O(log n)
    for (int i = 0; i < size; i++) { ... }
} else {
    // Ітерація → O(n log n) для LinkedList!
    ListIterator<E> it = list.listIterator();
}

Map: чому НЕ Collection?

Map працює з ПАРАМИ (Key-Value)
Collection працює з ОДИНОЧНИМИ елементами

Map.Entry<K,V> — внутрішній інтерфейс для пари
  → getKey(), getValue(), setValue()

Тому Map — паралельна гілка, не Collection!

Optional Operations

// Багато методів Collection = "optional operation"
// Unmodifiable колекції кидають UnsupportedOperationException

list.add(e)      // Може кинути!
list.remove(e)   // Може кинути!
list.clear()     // Може кинути!

// Чому? Щоб підтримувати незмінювані колекції:
List<String> unmodifiable = Collections.unmodifiableList(list);
unmodifiable.add("x");  // → UnsupportedOperationException!

Production Experience

Реальний сценарій: LinkedList убив продуктивність

Додаток: 1 млн елементів у LinkedList
Проблема: 10 секунд на ітерацію, 500 МБ пам’яті
Рішення: заміна на ArrayList
Результат: 50 мс, 50 МБ (прискорення у 200 разів!)

Best Practices

Інтерфейс у сигнатурі: List<String>, не ArrayList<String>
Collection якщо потрібна тільки ітерація
SequencedCollection (Java 21) для доступу до першого/останнього
RandomAccess перевірка для циклів for-i
Fail-Safe колекції для багатопотоковості
Уникайте Vector, Stack, Hashtable (legacy)
Spliterator для кастомних паралельних стримів

Резюме для Senior

JCF = єдина архітектура для колекцій
SequencedCollection (Java 21) = новий стандарт для упорядкованих
RandomAccess = маркер для оптимізації алгоритмів
Spliterator = основа паралельних Stream API
Optional operations = підтримка unmodifiable колекцій
Map ≠ Collection (пари vs одиночні елементи)
Fail-Fast = модифікація → exception
Legacy (Vector/Stack) = уникайте

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

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

Collection Framework = Iterable → Collection (List, Set, Queue) + Map (паралельна гілка)
Map НЕ наслідується від Collection — працює з парами Key-Value, а не одиночними елементами
List = упорядкований, дублікати OK; Set = унікальні елементи; Queue = FIFO
Fail-Fast = модифікація під час ітерації → ConcurrentModificationException (через modCount)
Fail-Safe = ітератор по копії (snapshot), ніколи не кидає exception
RandomAccess — маркерний інтерфейс без методів, сигналізує про швидкий доступ за індексом
Java 21: SequencedCollection уніфікує доступ до first/last/reversed для List та Deque
Spliterator — заміна Iterator для Stream API, містить характеристики для паралельної оптимізації

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

Чому Map не частина Collection? — Map працює з парами (K,V), Collection — з одиночними елементами
Чим Fail-Fast відрізняється від Fail-Safe? — Fail-Fast кидає exception при модифікації, Fail-Safe працює з копією
Навіщо потрібен RandomAccess? — JDK використовує його для вибору алгоритму (бінарний пошук за індексами vs ітерація)
Що таке optional operations? — Методи на кшталт add()/remove() можуть кидати UnsupportedOperationException для unmodifiable колекцій

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

❌ “Map наслідується від Collection” — це паралельна гілка
❌ “Vector — хороший вибір для багатопотоковості” — це legacy, використовуйте CopyOnWriteArrayList або ConcurrentHashMap
❌ “Fail-Fast гарантує thread-safety” — це детектор багів для одного потоку, а не синхронізація
❌ “Spliterator — це те саме що Iterator” — Spliterator підтримує паралельну обробку через trySplit()

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

[[В чому різниця між List, Set та Queue]]
[[Що таке Vector і чим він відрізняється від ArrayList]]
[[Що таке Queue і які реалізації існують]]
[[Яка часова складність операцій в ArrayList]]