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

Вона складається з інтерфейсів, їхніх конкретних реалізацій (структур даних) та алгоритмів утилітарного класу Collections.

🟢 Junior Level

Java Collections Framework (JCF) — це уніфікована архітектура для зберігання, обробки та маніпулювання групами об’єктів у Java.

Вона складається з інтерфейсів, їхніх конкретних реалізацій (структур даних) та алгоритмів утилітарного класу Collections.

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

Інтерфейс	Опис	Основні реалізації
`List`	Впорядкована послідовність із доступом за цілочисловим індексом. Допускає дублікати елементів.	`ArrayList`, `LinkedList`
`Set`	Множина унікальних елементів. Дублікати заборонені (за контрактом `equals()` та `hashCode()`).	`HashSet`, `LinkedHashSet`, `TreeSet`
`Queue`	Черга для обробки елементів у визначеному порядку (зазвичай FIFO — First-In-First-Out).	`PriorityQueue`, `ArrayDeque`
`Deque`	Двобічна черга (Double-Ended Queue). Дозволяє вставляти та вилучати елементи з обох кінців. Може працювати як стек (LIFO) і як черга (FIFO).	`ArrayDeque`, `LinkedList`
`Map`	Асоціативний масив пар «ключ — значення». Ключі унікальні, кожне значення прив’язане до свого ключа.	`HashMap`, `LinkedHashMap`, `TreeMap`

[!NOTE] Найважливіша деталь: Інтерфейс Map НЕ успадковується від Collection! Він є самостійною гілкою ієрархії, але входить до Java Collections Framework, надаючи колекції своїх ключів, значень та записів (views).

// Приклад роботи з базовими інтерфейсами
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"); // Дублікат буде проігноровано (поверне false)

Map<String, Integer> map = new HashMap<>();
map.put("Apple", 10);
map.put("Banana", 20);
map.put("Apple", 30); // Значення перезапишеться за наявним ключем

🟡 Middle Level

1. Повна ієрархія інтерфейсів

Уся система колекцій бере початок від інтерфейсу java.lang.Iterable:

                    java.lang.Iterable<E>
                              │
                              ▼
                   java.util.Collection<E>
                              │
      ┌───────────────────────┼───────────────────────┐
      ▼                       ▼                       ▼
   List<E>                 Set<E>                  Queue<E>
      │                       │                       │
      │                  SortedSet<E>                 ▼
      │                       │                    Deque<E>
      │                       ▼                       │
      │                 NavigableSet<E>               │
      │                       │                       │
      └───────────────────────┼───────────────────────┘
                              ▼ (Java 21+)
                  SequencedCollection<E>

Паралельна гілка відображень (Key-Value):

                       java.util.Map<K, V>
                              │
                              ▼
                       SortedMap<K, V>
                              │
                              ▼
                      NavigableMap<K, V>
                              │
                              ▼ (Java 21+)
                      SequencedMap<K, V>

2. Маркерні інтерфейси (Marker Interfaces)

Низка ключових можливостей колекцій визначається інтерфейсами-маркерами, які не містять власних методів:

RandomAccess: маркерний інтерфейс, що реалізується колекціями з константним часом довільного доступу до елементів $O(1)$ за індексом (наприклад, ArrayList).
- JDK використовує перевірку instanceof RandomAccess для вибору найбільш продуктивного алгоритму:
```
// Всередині Collections.binarySearch:
if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)
  return Collections.indexedBinarySearch(list, key); // Швидкий доступ через for(int i=0...)
else
  return Collections.iteratorBinarySearch(list, key); // Ітератор ListIterator O(n)
```
Cloneable та Serializable: декларують можливість поверхневого клонування об’єкта та серіалізації в байтовий потік.

3. Поняття опціональних операцій (Optional Operations)

Інтерфейс Collection проєктувався з розрахунком як на змінювані, так і на незмінювані структури даних. Методи модифікації (add(), remove(), clear()) у специфікації позначені як опціональні.

Якщо реалізація колекції є незмінюваною (Collections.unmodifiableList(), List.of()), виклик методу модифікації призводить до викидання UnsupportedOperationException.

🔴 Senior Level

1. Чому `Map` не успадковує `Collection`?

Це класичне архітектурне питання проєктування API:

Порушення принципу підстановки Лісков (LSP): Інтерфейс Collection<E> розрахований на роботу з одиничними елементами $E$. Базові методи add(E e) або contains(Object o) втрачають сенс для відображення, що оперує парами (K key, V value). Додавання методу add(Entry<K, V>) в інтерфейс Map ускладнило б і забруднило контракт.
Семантика колекцій: У Map немає однозначного поняття «елемент». Що є елементом мапи: ключ, значення чи пара? Тому розробники Java виділили Map у незалежний інтерфейс, надавши три колекційні представлення (Collection Views):
- map.keySet() $\to$ Set<K> (множина ключів);
- map.values() $\to$ Collection<V> (колекція значень, не обов’язково унікальних);
- map.entrySet() $\to$ Set<Map.Entry<K, V>> (множина зв’язаних пар).

2. Революція Java 21: `SequencedCollection` (JEP 431)

Протягом 25 років у Java не існувало спільного інтерфейсу для колекцій, що мають фіксований порядок елементів. Дізнатися перший чи останній елемент у різних колекціях доводилося неузгодженими способами:

List: list.get(0) та list.get(list.size() - 1);
Deque: deque.getFirst() та deque.getLast();
SortedSet: set.first() та set.last();
LinkedHashSet: тільки через set.iterator().next() (для першого) або повний перебір.

У Java 21 представлено інтерфейс SequencedCollection<E>, який став предком List та Deque, а також впроваджено SequencedSet та SequencedMap:

// Єдиний контракт у Java 21+:
SequencedCollection<String> seq = new ArrayList<>();
seq.addFirst("Start");
seq.addLast("End");

String first = seq.getFirst(); // "Start"
String last = seq.getLast();   // "End"

// Отримання дзеркального представлення у зворотному порядку за O(1) без копіювання пам'яті:
SequencedCollection<String> reversed = seq.reversed();

3. Механізм Spliterator у Stream API

Інтерфейс Spliterator<E> (введений у Java 8) прийшов на заміну класичному Iterator для підтримки ефективної паралельної обробки у Stream API:

Метод trySplit(): рекурсивно розділяє колекцію на два незалежні сплітератори для паралельного обходу в пулі ForkJoinPool;
Метод characteristics(): бітова маска характеристик даних (ORDERED, DISTINCT, SORTED, SIZED, NONNULL, IMMUTABLE, CONCURRENT, SUBSIZED). Stream API аналізує ці прапорці для виключення зайвих обчислень (наприклад, пропускаючи операцію distinct(), якщо сплітератор повідомляє прапорець DISTINCT).

4. Вплив кешу процесора: `ArrayList` проти `LinkedList`

У сучасному серверному обладнанні критичним фактором продуктивності є Cache Locality (локалізація даних у кеші процесора L1/L2/L3):

ArrayList: елементи зберігаються в неперервному блоці оперативної пам’яті (Object[]). При читанні одного елемента процесор автоматично завантажує сусідні 64 байти в рядок кешу (Hardware Prefetching). Ітерація по ArrayList відбувається практично миттєво на рівні регістрів та кешу процесора.
LinkedList: кожен вузол Node алокується окремо в купі й розпорошений за різними адресами RAM. Ітерація по зв’язному списку породжує постійні промахи кешу процесора (CPU Cache Misses), перетворюючи обхід пам’яті на багаторазові затримки читання з повільної RAM.
Додатково: LinkedList витрачає 24 байти на кожен вузол (заголовок + 2 покажчики) понад сам збережений об’єкт, створюючи величезний оверхед за пам’яттю.

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

30-секундна відповідь для співбесіди

«Java Collections Framework об’єднує інтерфейси для роботи зі структурами даних. Коренем ієрархії є Collection (що наслідує Iterable), який розгалужується на три основні напрямки: List (впорядкований список із доступом за індексом), Set (множина унікальних елементів) та Queue/Deque (черги обробки). Інтерфейс Map (пари ключ-значення) не наслідує Collection, оскільки має принципово інший контракт оперування парами, але інтегрований через представлення keySet(), values() та entrySet(). Починаючи з Java 21, усі колекції з детермінованим порядком об’єднані інтерфейсом SequencedCollection».

Питання підвищеної складності з відповідями

Чому інтерфейс Map не розширює інтерфейс Collection?
- Відповідь: Інтерфейс Collection<E> орієнтований на маніпулювання поодинокими елементами через методи add(E), contains(Object), iterator(). Інтерфейс Map<K, V> оперує парами зв’язаних об’єктів. Спроба успадкувати Map від Collection призвела б до порушення принципу підстановки Барбари Лісков (LSP), оскільки методи на кшталт add(E) або не мали б сенсу, або вимагали б штучного загортання в Map.Entry. Натомість Map надає три спеціалізовані колекційні представлення: ключі (keySet), значення (values) та пари (entrySet).
Що таке маркерний інтерфейс RandomAccess і як він впливає на продуктивність?
- Відповідь: RandomAccess — це порожній інтерфейс-маркер, що сигналізує про те, що структура даних підтримує швидкий доступ до будь-якого елемента за індексом за час $O(1)$ (як масив в ArrayList). Стандартні алгоритми JDK (наприклад, Collections.binarySearch або методи сортування) перевіряють колекцію через instanceof RandomAccess. Якщо маркер є, алгоритм виконує швидкий цикл з індексацією list.get(i); якщо маркера немає (як у LinkedList), алгоритм перемикається на обхід через ListIterator, щоб уникнути деградації складності до $O(N^2)$.
Яку фундаментальну проблему архітектури колекцій розв’язав JEP 431 у Java 21?
- Відповідь: До Java 21 у стандартній бібліотеці не було єдиного супер-інтерфейсу для колекцій, що володіють суворо визначеним порядком обходу (sequence). Щоб отримати перший чи останній елемент у List, Deque, SortedSet або LinkedHashSet, доводилося використовувати різні, часто незручні методи (або робити повний обхід через ітератор). Java 21 ввела SequencedCollection, SequencedSet та SequencedMap, стандартизувавши методи addFirst(), addLast(), getFirst(), getLast() та отримання зворотного представлення reversed() за константний час $O(1)$.
Що таке Fail-Fast поведінка ітераторів і чи гарантує вона захист у багатопотоковому середовищі?
- Відповідь: Ітератори колекцій (таких як ArrayList або HashMap) відстежують структурні зміни колекції через внутрішній лічильник modCount. Якщо під час обходу ітератором колекція була змінена не через методи самого ітератора, при наступному зверненні викидається ConcurrentModificationException. Ця поведінка називається Fail-Fast. Вона не гарантує потокобезпечність і слугує лише для раннього виявлення багів у коді; покладатися на неї для синхронізації потоків категорично не можна.

Типові помилки та Red Flags

🚩 Стверджувати, що Map успадковується від Collection. (Red Flag: нерозуміння базової ієрархії Java Collections Framework).
🚩 Вважати, що LinkedList швидший за ArrayList при випадковій вставці в середину. (У реальних умовах пошук позиції вставки в LinkedList вимагає $O(N)$ переходів за посиланнями з кеш-місами, через що ArrayList зі зсувом системної пам’яті System.arraycopy на практиці майже завжди виграє).
🚩 Вважати Fail-Fast механізмом паралельної синхронізації. (ConcurrentModificationException кидається навіть у суворо однопотоковому коді при некоректній модифікації в циклі foreach).