Какие основные интерфейсы 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) {
    // Binary search по индексам → 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]]