Тема 7. Collections Framework (List, Set, Map, Queue)

Collections Framework в Java — это не «набор контейнеров», а язык проектирования in-memory модели данных. В реальном backend-коде почти каждая операция проходит через коллекции: мы читаем строки из БД в List, строим индекс по ключу в Map, убираем дубликаты через Set, планируем обработку задач в Queue. Поэтому выбор структуры влияет не только на скорость, но и на корректность логики. Если выбрать структуру по привычке, можно получить скрытые ошибки: потерю порядка, дубли, неустойчивую производительность и сложные race-condition при масштабировании.

В этой теме мы разберем фундаментальные интерфейсы и внутренние модели хранения по слоям абстракции: сначала Iterable, затем Collection, дальше специализации List, Set, Queue, и отдельно Map, который не наследует Collection, но является центральной частью framework. Цель — чтобы ты мог смотреть на бизнес-задачу и сразу понимать, какая структура данных выражает ее семантику наиболее точно.

Iterable: контракт обхода, на котором держится for-each

Iterable<T> — минимальный интерфейс, который говорит: «эту структуру можно последовательно обходить». Он содержит ключевой метод iterator(), возвращающий объект Iterator<T>. Когда ты пишешь for-each, компилятор под капотом использует именно этот контракт и вызывает hasNext()/next().

Важно понимать, что Iterable не обещает ни уникальности, ни сортировки, ни доступа по индексу. Он обещает только валидный traversal. Это делает интерфейс универсальным: один и тот же цикл for-each работает и для списка, и для множества, и для очереди, пока они предоставляют Iterator.

Iterable<String> names = List.of("Alice", "Bob", "Carol");

for (String item : names) {
    System.out.println(item);
}

Этот фрагмент выглядит простым, но за ним есть важная идея архитектуры Java: алгоритмы можно писать к самому слабому контракту, который достаточен для задачи. Если тебе нужен только последовательный обход, используй абстракцию Iterable, а не более «тяжелые» типы. Это упрощает API методов и делает код менее связанным с конкретной реализацией.

public static void printAll(Iterable<String> data) {
    for (String value : data) {
        System.out.println(value);
    }
}

Еще один практический момент: iterator обычно fail-fast для большинства стандартных коллекций. Если структура модифицируется во время обхода нечерез сам iterator, получишь ConcurrentModificationException. Это защита от неочевидных ошибок, а не потокобезопасность. Для многопоточного сценария нужны отдельные concurrent-структуры или синхронизация.

Collection: общий поведенческий контракт коллекций элементов

Collection<E> расширяет Iterable<E> и добавляет базовые операции работы с группой элементов: add, remove, contains, size, isEmpty, clear, iterator. Это слой, где описывается, что вообще значит «коллекция элементов», до разделения на порядок, уникальность и очередь.

Ключевая инженерная идея: Collection задает минимальный доменный язык операций, но не гарантирует конкретную асимптотику и не навязывает модель хранения. Например, contains есть везде, но в ArrayList это линейный проход, а в HashSet обычно почти O(1). Одинаковый метод — разная стоимость из-за разной внутренней структуры.

Collection<String> tags = new ArrayList<>();
tags.add("java");
tags.add("spring");

boolean hasJava = tags.contains("java");
int count = tags.size();

Полезно помнить, что не все операции обязательны для любой реализации. В некоторых коллекциях часть операций может быть unsupported и бросать UnsupportedOperationException, особенно если это immutable-объекты (List.of(...), Set.of(...)). Поэтому при проектировании API нужно четко понимать, ожидаешь ли ты изменяемую коллекцию или только read-only контракт.

С точки зрения архитектуры Collection дает правильную степень абстракции для сервисных методов, где не важна конкретика структуры. Если метод «получает набор элементов и фильтрует», часто достаточно сигнатуры через Collection или Iterable, а выбор ArrayList/LinkedHashSet/... должен оставаться на стороне вызывающего кода.

List: упорядоченная последовательность с индексом и дубликатами

List<E> выбирают, когда порядок элементов семантически важен и когда нужен доступ по позиции. List допускает дубликаты, и это принципиально: одинаковые значения могут иметь разный смысл из-за позиции или контекста обработки.

Внутри List-модели чаще всего используются две реализации: ArrayList и LinkedList. ArrayList хранит данные в динамическом массиве. Это дает очень быстрый доступ get(i), потому что индекс переводится в адрес почти напрямую. Цена — дорогие вставки в середину: элементы приходится сдвигать. Также при росте массива периодически происходит resize и копирование.

List<String> users = new ArrayList<>();
users.add("u1");
users.add("u2");
users.add(1, "u1.5"); // сдвиг части массива вправо
System.out.println(users.get(2)); // u2

LinkedList хранит цепочку узлов, где каждый узел знает соседей. Это дешево для вставок и удалений вблизи найденной позиции или на концах, но плохо для случайного доступа по индексу, потому что нужен пошаговый проход по ссылкам. На практике это означает: если у тебя много get(i) в цикле, LinkedList обычно будет заметно хуже.

List<String> events = new LinkedList<>();
events.add("A");
events.add("B");
events.remove(0); // структурная операция без сдвига массива

Нельзя выбирать LinkedList только по аргументу «вставки O(1)». В реальных системах основная нагрузка часто приходится на чтение и итерацию с CPU-кеш-локальностью, где ArrayList выигрывает за счет непрерывной памяти. Поэтому ArrayList — дефолт почти для всех обычных сценариев, если нет доказанной причины выбрать LinkedList.

Set: модель уникальности и проверка принадлежности

Set<E> выражает семантику «элемент либо есть, либо его нет». Дубликаты не разрешены. Если попытаться добавить то же значение повторно, размер множества не изменится. Это не просто удобство, это способ зафиксировать бизнес-инвариант данных в типе.

Самая частая реализация — HashSet. Под капотом хеш-таблица распределяет элементы по bucket-ам по результату hashCode. При совпадении hash работает сравнение через equals. Поэтому корректность HashSet напрямую зависит от корректно реализованных equals/hashCode у пользовательских классов. Если контракт сломан, множество начинает «терять» элементы логически: они вроде добавлены, но поиск ведет себя непредсказуемо.

Set<String> roles = new HashSet<>();
roles.add("ADMIN");
roles.add("ADMIN");
roles.add("USER");

System.out.println(roles.size()); // 2
System.out.println(roles.contains("USER")); // true

LinkedHashSet сохраняет порядок вставки, что важно для стабильного вывода или детерминированных тестов. TreeSet хранит элементы отсортированными (натуральный порядок или Comparator) и поддерживает range-операции, но за это платит O(log n) на основные операции.

Set<Integer> sorted = new TreeSet<>();
sorted.add(40);
sorted.add(10);
sorted.add(25);
System.out.println(sorted); // [10, 25, 40]

Практический вывод: выбирай Set, когда уникальность — часть бизнес-правила, а не постобработка «потом уберем дубли». Тогда сама структура защищает инвариант в каждом месте кода.

Map: индексирование по ключу и модель key-value

Map<K, V> не наследует Collection, потому что хранит не отдельные элементы, а пары ключ-значение. Ключевая роль Map в backend — быстрая адресация данных по ключу: id пользователя, код заказа, composite key, имя фича-флага, кэш-ключ.

HashMap — базовый выбор по умолчанию. Он дает быстрые put/get/remove в среднем и хорошо подходит для индексации. Но «быстрый в среднем» означает зависимость от качества хеширования ключей и распределения bucket-ов. Если много коллизий, производительность деградирует.

Map<Long, String> userById = new HashMap<>();
userById.put(101L, "Alice");
userById.put(102L, "Bob");

String name = userById.get(102L); // Bob

LinkedHashMap полезен, когда важен предсказуемый порядок итерации. В режиме access-order его часто используют как основу простых LRU-подобных кэшей. TreeMap держит ключи отсортированными и дает операции навигации (firstKey, lastKey, ceilingKey, диапазоны), что удобно для временных шкал и range-запросов в памяти.

Map нужно воспринимать как in-memory индекс. Если у тебя есть частый поиск по атрибуту, построение Map может радикально снизить сложность с O(n) на каждый поиск до почти O(1) среднего доступа. Это один из самых сильных приемов оптимизации бизнес-кода без преждевременной микротюнинга.

Queue: очередность обработки, FIFO и приоритет

Queue<E> выражает не просто хранение, а порядок потребления элементов. Для стандартной очереди это FIFO: первый пришел — первый обработан. Это напрямую маппится на реальные сценарии: обработка задач, событий, команд, сообщений.

Важные методы: offer (добавить), poll (забрать и удалить голову), peek (посмотреть голову без удаления). В отличие от add/remove/element, методы offer/poll/peek лучше для надежного кода, потому что возвращают «мягкие» значения в пограничных случаях вместо исключений.

Queue<String> tasks = new ArrayDeque<>();
tasks.offer("import-users");
tasks.offer("send-report");

String first = tasks.poll(); // import-users
String next = tasks.peek();  // send-report

ArrayDeque обычно лучший выбор для очереди/стека в однопоточном коде: компактная память и быстрые операции на концах. PriorityQueue работает иначе: она возвращает элемент с лучшим приоритетом, а не с самым ранним временем вставки. Внутри — бинарная куча, поэтому полная итерация не дает «глобально отсортированный список».

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(50);
pq.offer(10);
pq.offer(30);

System.out.println(pq.poll()); // 10 (минимум по умолчанию)

Это критичный момент для корректности: если нужна строгая FIFO-обработка, PriorityQueue не подходит. Если нужна обработка по весу/сроку/приоритету — подходит идеально.

Что выбрать в реальной задаче

Хороший выбор структуры начинается не с Big-O таблицы, а с вопроса «какую семантику нужно выразить». Если нужна последовательность с позициями — это List. Если нужен инвариант уникальности — Set. Если нужен быстрый доступ по ключу — Map. Если важен порядок обработки задач — Queue.

Когда семантика выбрана верно, производительность чаще всего «приходит бесплатно», потому что структура уже оптимизирована под нужный тип операций. Когда семантика выбрана неверно, даже быстрый код начинает усложняться костылями: ручное удаление дублей, дополнительные сортировки, линейные поиски внутри циклов.

Практический инженерный паттерн: проектируй API к интерфейсу (List, Set, Map, Queue), а реализацию выбирай по профилю нагрузки и инвариантам. Не делай оптимизацию заранее «на глаз», но и не игнорируй внутренние модели хранения. Понимание того, как структура держит данные в памяти, дает тебе контроль над поведением системы в продакшене.