Обзор 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

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

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

Операции, не привязанные к конкретной реализации — сортировка, перемешивание, разворот, бинарный поиск, min, max, частота, неизменяемые обёртки — живут в статическом служебном классе 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. Map обходятся через entrySet(), keySet() или values() в зависимости от того, что вам нужно.

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

Что дальше

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

Practice