Collections Framework: карта и выбор структуры

Иерархия интерфейсов

В основе — Iterable, от него Collection, а дальше три ветви: List (упорядоченная последовательность с дубликатами и доступом по индексу), Set (множество уникальных элементов) и Queue/Deque (очереди и двусторонние очереди).

Map стоит особняком: это не Collection, а отдельная иерархия пар ключ→значение. У неё есть подинтерфейсы SortedMap/NavigableMap (упорядоченные карты), а её views (keySet, values, entrySet) — это коллекции, через которые Map интегрируется во фреймворк.

Программируют против интерфейса (List, Map, Set), а конкретную реализацию выбирают под паттерн доступа — это позволяет менять структуру, не трогая остальной код. Ниже — по абзацу на каждую ключевую реализацию; внутреннему устройству каждой посвящён отдельный урок.

Списки и очереди: реализации

ArrayList — динамический массив: get/set по индексу O(1), add в конец амортизированно O(1), вставка/удаление в середину O(n) (сдвиг через arraycopy). Отличная cache locality, дефолтный выбор для списков.

LinkedList — двусвязный список: доступ по индексу O(n), реализует и List, и Deque. На практике почти всегда проигрывает ArrayList/ArrayDeque из-за оверхеда узлов и промахов кэша — берут редко.

ArrayDeque — двусторонняя очередь на кольцевом буфере: добавление/снятие с обоих концов O(1), отличная локальность. Современная замена и Stack (как стек), и LinkedList (как очередь); null хранить нельзя.

PriorityQueue — бинарная куча в массиве: offer/poll O(log n), peek O(1) (минимум/экстремум по Comparator). Важно: итерация по очереди НЕ отсортирована, гарантирован только порядок извлечения через poll.

Множества и карты: реализации

HashMap — хеш-таблица бакетов (с превращением длинной цепочки в дерево): get/put/contains в среднем O(1), порядок не гарантирован. LinkedHashMap — HashMap плюс связанный список записей: сохраняет порядок вставки (или доступа) и служит основой LRU-кэша. TreeMap — красно-чёрное дерево: O(log n), всегда отсортирована, реализует NavigableMap (floor/ceiling, диапазоны).

HashSet/LinkedHashSet/TreeSet — это множества поверх соответствующих карт (элемент хранится как ключ), поэтому их свойства и сложности повторяют HashMap/LinkedHashMap/TreeMap.

Hashtable — легаси: синхронизированная хеш-таблица, не допускающая null. В новом коде её не используют — для однопоточного доступа берут HashMap, для конкурентного ConcurrentHashMap; знать её стоит лишь как исторический контраст. Аналогично Vector/Stack вытеснены ArrayList/ArrayDeque.

Замечание про названия: в JDK нет класса «HashList». Если нужен «хеш + предсказуемый порядок» — это LinkedHashMap/LinkedHashSet (хеш-таблица + связанный список порядка); если нужен список — ArrayList или LinkedList.

Сложности операций — шпаргалка

Списки/очереди: ArrayList — индекс O(1), вставка в середину O(n); LinkedList — индекс O(n); ArrayDeque — концы O(1); PriorityQueue — offer/poll O(log n), peek O(1).

Множества/карты: Hash* — в среднем O(1) (худший O(log n) благодаря дереву в бакете); Tree* — O(log n) и упорядоченность; Linked*-варианты — как Hash*, плюс поддержание порядка.

Эти оценки — следствие устройства структур; в отдельных уроках разобрано, ПОЧЕМУ именно так (рост массива, бакеты и resize, красно-чёрное дерево, куча).

Конвертация между коллекциями

Базовые конвертации делаются через конструктор-копию и стоят O(n) (копируются ссылки на элементы): List→Set — new HashSet<>(list) (заодно убирает дубликаты), Set→List — new ArrayList<>(set), List→отсортированный — new TreeSet<>(list) или list.sort(...).

Коллекция ↔ массив: coll.toArray(new T[0]) даёт массив; Arrays.asList(arr) — список-ВИД фиксированного размера поверх массива (add/remove бросят исключение, но set работает и пишет в массив); Arrays.stream(arr) — поток по массиву.

Через Stream: stream.collect(Collectors.toList()/toSet()/toMap(...)) или современные toList()/Stream.toList() (неизменяемый результат). Для неизменяемой копии существующей коллекции — List.copyOf/Set.copyOf/Map.copyOf (Java 10+), тоже O(n).

List<Integer> list = List.of(1, 2, 2, 3);
Set<Integer> set = new HashSet<>(list);     // дедупликация, O(n)
List<Integer> back = new ArrayList<>(set);   // обратно в список, O(n)
Integer[] arr = list.toArray(new Integer[0]); // в массив

Неизменяемые и защитные коллекции

Неизменяемый снимок создают фабрики List.of/Set.of/Map.of (Java 9+): компактны, не принимают null, бросают UnsupportedOperationException на любую мутацию. Их возвращают из API и используют как константы. List.copyOf(coll) делает независимую неизменяемую КОПИЮ из существующей коллекции — после копирования изменения исходника на неё не влияют.

Collections.unmodifiableList(list) — это другое: read-only ВИД (обёртка) над существующим списком. Через обёртку менять нельзя, но это НЕ копия — изменения исходного списка видны сквозь неё. Зачем нужно: отдать наружу безопасный доступ к внутренней коллекции, не копируя её (например, геттер возвращает Collections.unmodifiableList(items), чтобы вызывающий код не сломал инварианты класса).

Отсюда правило выбора: нужен дешёвый read-only доступ к своим данным, которые вы сами контролируете — unmodifiable view; нужна гарантия, что результат не изменится никогда и ни от чего — отдавайте снимок (List.copyOf) или защитную копию (defensive copy) в конструкторе/геттере. Защитная копия — базовый приём дизайна неизменяемых классов.

// view: запрещает мутацию ИЗВНЕ, но отражает изменения items
public List<Item> items() { return Collections.unmodifiableList(items); }
// snapshot: независимая неизменяемая копия
public List<Item> snapshot() { return List.copyOf(items); }

Fail-fast и потокобезопасность

Базовые коллекции (ArrayList, HashMap, …) не потокобезопасны. Их итераторы fail-fast: структурное изменение во время обхода роняет ConcurrentModificationException через счётчик modCount — это защита от багов, а не гарантия многопоточности.

Для конкурентного доступа есть отдельное семейство (ConcurrentHashMap, CopyOnWriteArrayList) с weakly-consistent итераторами — ему посвящён отдельный урок. Старые обёртки Collections.synchronizedXxx берут единый замок и сильно уступают concurrent-коллекциям.

Выбор по паттерну доступа

Нужен индекс и обход по порядку — ArrayList. Нужна уникальность и быстрый поиск по значению — HashSet. Нужны пары и быстрый поиск по ключу — HashMap. Нужен порядок вставки — Linked*-варианты. Нужен отсортированный порядок и диапазонные запросы — TreeMap/TreeSet. Нужны очередь/стек — ArrayDeque. Нужна выборка минимума/максимума — PriorityQueue.

Антипаттерн — выбирать структуру по привычке (всюду ArrayList или HashMap) без учёта операций, которые реально выполняются чаще всего.

Как отвечать на собеседовании

Сильный ответ: уверенно рисуете иерархию (Collection vs Map), для каждой реализации называете устройство и сложности, и выбираете структуру от паттерна доступа. Умейте конвертировать (new HashSet<>(list) для дедупликации, toArray, copyOf) и объясните разницу снимка (List.copyOf) и view (Collections.unmodifiableList). Упомяните, что Hashtable/Vector/Stack — легаси, а fail-fast — это не потокобезопасность.