Обзор Java Collections Framework

Почти каждая программа рано или поздно работает с группой объектов — заказами в очереди на отправку, словами в документе, пользователями онлайн, списком задач для рабочего потока. Java отвечает на вопрос «где хранить такую группу» с помощью Collections Framework: согласованного набора интерфейсов из java.util, множества реализаций за ними и одного утилитного класса алгоритмов (Collections), который работает через интерфейсы, а не через конкретные реализации. Эта глава — карта фреймворка: что в него входит, почему он устроен именно так и какое семейство использовать в каждой ситуации. Каждая последующая глава этой части детально разбирает один из элементов этой карты.

Почему фреймворк, а не просто классы

До Java 1.2 существовали классы для групп (Vector, Hashtable, Stack), но не было общего интерфейса — нельзя было написать метод, принимающий «любой список» и работающий со всеми тремя. Collections Framework решил это, разделив что такое группа (интерфейс) и как она хранится (реализация). Выгода очевидна каждый день:

// You program against the interface, not the class.
List<String> names = new ArrayList<>();
// Later, swap in a different implementation without touching the rest of the code:
List<String> names = new LinkedList<>();

Каждый метод, вызываемый на names, определён в List. Выбор между ArrayList и LinkedList — это решение о производительности, а не об API. Можно также написать метод void print(List<String> xs) один раз и передавать в него любую реализацию.

Четыре корневых интерфейса

Фреймворк организован вокруг четырёх корневых интерфейсов. Выбирайте тот, контракт которого соответствует вашим данным:

• Collection<E> — корень. Группа элементов типа E. Ничего не сказано о порядке, дубликатах или индексировании.
• List<E> — упорядоченная коллекция с доступом по индексу. Дубликаты допустимы. Думайте о ней как о «массиве, который растёт» или «связной последовательности». ArrayList, LinkedList, Vector.
• Set<E> — коллекция, запрещающая дубликаты. Математическое множество. Может быть упорядоченным или нет. HashSet, LinkedHashSet, TreeSet.
• Map<K, V> — поиск по ключу. Не является Collection (её элементы — пары ключ-значение, а не одиночные значения), но входит во фреймворк. HashMap, LinkedHashMap, TreeMap.

Ещё два интерфейса стоят рядом с List и Set как специализации Collection:

• Queue<E> — коллекция «следующий в очереди». По умолчанию FIFO. LinkedList, ArrayDeque, PriorityQueue.
• Deque<E> — двусторонняя очередь. Добавление и удаление с обоих концов. ArrayDeque, LinkedList.

Каждый класс коллекций из стандартной библиотеки реализует хотя бы один из этих интерфейсов.

Выбирайте семейство по поведению, затем класс по стоимости операций

Решение принимается в два этапа:

1. Что нужно данным? Упорядоченность с дубликатами → List. Без дубликатов → Set. Поиск по ключу → Map. Производитель/потребитель → Queue или Deque.
2. Внутри семейства — каковы паттерны доступа? Произвольный доступ по индексу → ArrayList. Частые добавления/удаления в начале → LinkedList или ArrayDeque. Сортированный обход → TreeSet / TreeMap. Просто «быстрое хранилище» → HashSet / HashMap.

Краткая шпаргалка по основным классам:

Vector, Stack и Hashtable — классы, существовавшие до версии 1.2. Они по-прежнему есть в JDK для обратной совместимости, но в новом коде их использовать не стоит. Их современные замены разбираются в отдельных главах.

Generics делают коллекции типобезопасными

Каждый интерфейс и класс коллекций является обобщённым. Вы параметризуете его типом элемента при объявлении, и компилятор контролирует это в дальнейшем:

List<String> names = new ArrayList<>();
names.add("Ada");
names.add(42);          // ❌ compile error — Integer is not a String
String first = names.get(0);   // no cast needed

Оператор <> справа просит компилятор вывести тип из левой части — это экономит написание кода без потери безопасности. Предыдущая часть книги (Generics) содержит правила, лежащие в основе всего этого; остальная часть раздела предполагает, что вы её прочитали.

Алгоритмы живут в классе Collections

Операции, не привязанные к конкретной реализации — сортировка, перемешивание, разворот, бинарный поиск, минимум, максимум, частота, обёртки неизменяемых коллекций — находятся в статическом утилитном классе java.util.Collections. Обратите внимание на s в конце: Collection (интерфейс) — это одна сущность; Collections (класс) — это инструментарий:

List<Integer> xs = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6));
Collections.sort(xs);                    // mutates xs
int idx = Collections.binarySearch(xs, 5);
List<Integer> ro = Collections.unmodifiableList(xs);

В конце этой части мы посвящаем три главы классу Collections — поиску, сортировке и неизменяемым обёрткам — потому что именно в утилитном классе сосредоточена большая часть практической работы.

Полный вводный обзор

Программа ниже берёт по одному представителю из каждого семейства и демонстрирует операции, которые вы будете использовать снова и снова. Не беспокойтесь о понимании каждой строки — каждый класс получит свою собственную главу. Цель — увидеть форму фреймворка: одни и те же имена методов, одни и те же паттерны, одна и та же модель итерации.

Обратите внимание на три вещи в выводе:

1. Set незаметно убрал дубликат "Effective Java". Таков контракт — никакого дополнительного кода с вашей стороны не требуется.
2. Queue вернула элементы в порядке добавления. offer ставит в очередь, peek смотрит на голову без удаления, poll удаляет и возвращает элемент.
3. Цикл for-each работает с каждой Collection. Карты итерируются через entrySet(), keySet() или values() — в зависимости от того, что нужно.

Вот фреймворк в миниатюре.

Что дальше

Вы увидели карту. Остальная часть раздела 11 подробно описывает каждую область. Естественная отправная точка — корень, от которого наследуют все коллекции: интерфейс Collection, где один раз определены методы add, remove, contains, size и iterator().

Практика