Какие основные интерфейсы 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).