Коллекции в Java | Java Collections

Java Collections это унифицированная архитектура для хранения и обработки групп объектов. Она включает ключевые интерфейсы: List для упорядоченных списков с доступом по индексу, Set для хранения уникальных элементов и Queue для структур типа "очередь". Отдельно стоит интерфейс Map для работы с парами "ключ-значение".

Кратко

• Java Collections Framework появился в JDK 1.2 и решает то, чего не умеют массивы: менять размер на ходу, знать реальное количество элементов и искать без предварительной сортировки.
• Корень иерархии это Collection, наследник Iterable. Отсюда и обязанность любой коллекции отдавать итератор и работать в цикле for-each.
• List хранит элементы по порядку и разрешает дубликаты, Set запрещает дубликаты и ничего не обещает про порядок, Queue обслуживает элементы в порядке очереди.
• Map стоит в стороне: пары «ключ-значение» коллекцией не считаются, поэтому Map не наследуется от Collection, а отдает три представления (keySet, values, entrySet).
• Два главных списка отличаются устройством: ArrayList это массив с доступом по индексу за одно действие, LinkedList это цепочка узлов со ссылками на соседей.
• Vector и Stack остались с первых версий Java: вместо первого документация советует ArrayList, вместо второго реализации Deque.

Теперь, когда у нас есть общее представление, давайте углубимся в детали Java коллекций. Чтобы понять, почему этот фреймворк так важен, начнем с проблемы, которую он решает, то есть с ограничений обычных массивов, и постепенно выстроим всю иерархию коллекций. Большая часть работы кода это обработка данных в том или ином виде. Получить список пользователей, получить список адресов и т.д. Как-то их отсортировать, выполнить поиск, сопоставить. Именно поэтому знание коллекций считается одним из основных навыков. Именно поэтому хочется поговорить про это. Кроме того, одними из самых частых вопросов на собеседованиях на Java разработчика являются коллекции. Например, "нарисуйте иерархию коллекций". Поможет нам на нашем пути онлайн компилятор. Например, можно использовать JDoodle Online Java Compiler.

Почему одних массивов не хватает

Путь знакомства с любыми структурами данных начинается с обычных переменных (Variables). И основы языка (т.е. Language Basics) начинаются с Variables. Поэтому, напишем простенький код:

public static void main(String[] args) {
	String user = "Max";
	System.out.println("Hello, " + user);
}

Он всем хорош, кроме того, что мы понимаем, что данный код хорош и красив только для одной переменной. Что делать, если их несколько? Для хранения данных одного типа придумали массивы (Arrays). В том самом Trail от Oracle есть отдельный раздел, посвященный массивам. Этот раздел так и называется: "Arrays". Работа с массивами тоже довольно проста:

import java.util.Arrays;
class Main {
  public static void main(String[] args) {
    String[] users = new String[2];
    users[0] = "Max";
    users[1] = "John";
    System.out.println("Hello, " + Arrays.toString(users));
  }
}

Массивы решают проблему с хранением нескольких значений в одном месте. Но накладывает ограничение: размер массива постоянен. Если, как в примере, мы сказали что размер = 2, значит он равен двум. И все. Если мы хотим массив больше, нужно создать новый экземпляр. Кроме того, поиск элемента тоже сложная вещь для массива. Есть метод Arrays.binarySearch, но данный поиск работает только на сортированном массиве (для несортированного массива результат неопределен или попросту непредсказуем). То есть поиск нас будет обязывать каждый раз сортировать. Удаление тоже лишь очищает значение. Поэтому мы еще и не знаем, сколько в массиве реально данных, знаем только сколько ячеек в массиве. Чтобы освежить знания про массивы:

• "JavaRush: Массивы в Java"

И как следствие развития языка Java в JDK 1.2 появился Java Collections Framework, о котором мы и будем сегодня говорить.

Что такое коллекции

Начать стоит с самого начала. Почему коллекции (Collection) в Java? Сам термин берет свое начало из таких вещей, как "Теория типов" и "Абстрактные типы данных". Но если не смотреть на какие-то высокие материи, то когда у нас несколько вещей, то мы можем назвать их "коллекция вещей". Те, кто собирает предметы. Вообще само слово коллекционировать происходит от лат. collectio «собирание, сбор». То есть коллекция это сбор чего-то, контейнер для каких-то элементов. Итак, у нас есть коллекция элементов. Что мы можем захотеть с ней делать: Как видно, мы можем захотеть довольно логичные вещи. А еще мы понимаем, что мы можем захотеть что-то делать с несколькими коллекциями: Соответственно, для описание такого общего поведения для всех коллекций написали разработчики Java интерфейс java.util.Collection.

Интерфейс Collection

Интерфейс Collection это то место, откуда берут начало все коллекции. Collection это идея, это представление о том, как должны себя вести все коллекции. Поэтому, термин "Коллекция" выражена в виде интерфейса. Естественно, интерфейсу нужны реализации. Интерфейс java.util.Collection имеет абстрактный класс AbstractCollection, то есть некоторая "абстрактная коллекция", которая представляет собой скелет для остальных реализаций (о чем написано в JavaDoc над классом java.util.AbstractCollection). Говоря о коллекциях вернемся еще раз вспомним, что мы хотим итерироваться по ним. Это значит, что мы хотим перебирать элементы один за другим. Это очень важная концепция. Поэтому, интерфейс Collection наследуется от Iterable. Это очень важно, т.к. во-первых, все что Iterable должно уметь возвращать Iterator по своему содержимому. А во-вторых, все что Iterable может использоваться в циклах for-each-loop. И именно при помощи итератора в AbstractCollection реализованы такие методы, как contains, toArray, remove. И путь к познанию коллекций начинается с одной из самых распространенных структур данных, со списка, т.е. List.

Списки (List)

Итак, списки занимают важное место в иерархии коллекций: Как мы видим, списки реализуют интерфейс java.util.List. Списки выражают то, что у нас есть коллекция элементов, которые расположены в некоторой последовательности друг за другом. Каждый элемент имеет индекс (как в массиве). Как правило, список позволяет иметь элементы с одинаковым значением. Как мы уже сказали выше, List знает про индекс элемента. Это позволяет получить (get) элемент по индексу или задать значением для определенного индекса (set). Методы коллекций add, addAll, remove позволяют указать индекс, с которого необходимо их выполнять. Кроме того, у List есть своя версия итератора, которая называется ListIterator. Этот итератор знает про индекс элемента, поэтому он умеет итерироваться не только вперед, но и назад. Его даже можно создать от определенного места в коллекции.

ArrayList и LinkedList

Среди всех реализаций можно выделить две наиболее часто используемые: ArrayList и LinkedList. Во-первых, ArrayList это список (List) на основе массива (Array). Это позволяет добиться "Произвольного доступа" к элементам. Произвольный доступ это возможность сразу достать элемент по индексу, а не перебирать все элементы, пока не найдем элемент с нужным индексом. Именно массив как основа позволяет этого достичь. Напротив, LinkedList это связанный (Linked) список (List). Каждая запись в связанном списке представлена в виде узла Node, который хранит сами данные, а так же ссылку на следующий (next) и предыдущий (previous) узел. В Java 6 и раньше этот внутренний класс назывался Entry, но при переписывании LinkedList в Java 7 его переименовали, и в исходниках JDK сегодня именно Node. Таким образом LinkedList реализует "Последовательный доступ". Понятно, что чтобы найти 5-тый элемент нам придется пройти от первого элемента до последнего, т.к. у нас нет напрямую доступа к пятому элементу. Мы можем получить к нему доступ только от 4-го элемента. Разница в их концепции приведена ниже: В работе, как Вы понимаете, тоже есть разница. Например, добавление элементов. В LinkedList элементы просто связываются, как звенья в цепи. Но вот ArrayList хранит элементы в массиве. А массив, как мы знаем, не может изменять свой размер. Как же работает тогда ArrayList? А работает он очень просто. Когда заканчивается место в массиве, то он увеличивается в 1.5 раза. До Java 15 это была одна строчка прямо в методе grow: int newCapacity = oldCapacity + (oldCapacity >> 1); Сейчас расчет вынесен в служебный метод ArraysSupport.newLength, но «предпочтительный прирост» передается туда все тем же выражением oldCapacity >> 1, то есть те же плюс 50 процентов. Другим отличием в работе является любое смещение элементов. Например, при добавлении в середину или удалении элементов. Чтобы удалить из LinkedList элемент достаточно убрать ссылки на этот элемент. В случае с ArrayList мы вынуждены каждый раз сдвигать элементы при помощи метода System.arraycopy. Таким образом, чем больше элементов, тем больше действий придется совершить.

Vector и Stack: наследие первых версий

Рассмотрев ArrayList нельзя не вспомнить про его "предшественника", про класс java.util.Vector. Отличается Vector от ArrayList тем, что методы для работы с коллекцией (добавление, удаление и т.д.) синхронизированы. То есть если один поток (Thread) будет добавлять элементы, то другие потоки будут ждать, пока первый поток не закончит свою работу. Так как потокобезопасность зачастую не требуется, рекомендуется использовать в таких случаях класс ArrayList, о чем прямым текстом сказано в JavaDoc для класса Vector. Кроме того, Vector увеличивает свой размер не в 1.5 раза, как ArrayList, а в 2 раза. В остальном поведение такое же: за Vector скрывается хранилище элементов в виде массива и добавление/удаление элементов имеют те же последствия, что и в ArrayList. На самом деле, про Vector мы вспомнили не просто так. Если посмотреть в Javadoc, то мы увидим в "Direct Known Subclasses" такую структуру, как java.util.Stack. Стэк это интересная структура, которая является LIFO структурой last-in-first-out (последним пришел, первым ушел). Стэк в переводе с английского это стопка (как стопка книг, например). Стэк реализует дополнительные методы: peek (взглянуть, посмотреть), pop (вытолкнуть), push (затолкать). Метод peek переводится как взглянуть (например, peek inside the bag переводится как "заглянуть внутрь мешка", а peek through the keyhole переводится как "подглядывать в замочную скважину"). Данный метод позволяет посмотреть "на вершину" стэка, т.е. получить последний элемент не снимая (т.е. не удаляя) его из стэка. Метод push заталкивает (добавляет) в стэк новый элемент и возвращает его же, а метод pop элемент выталкивает (удаляет) и возвращает удаленный. Во всех трех случаях (т.е. peek, pop и push) мы работаем только с последним элементом (т.е. с "вершиной стэка"). В этом основная особенность структуры стэк. Кстати, на понимание стэков есть интересная задача, описанная в книге "Карьера программиста" (Cracking the Coding Interview), где используя структуру "стэк" (LIFO) нужно реализовать структуру "очередь" (FIFO). Выглядит это следующим образом: Разбор этой задачи можно посмотреть тут. Вот мы плавно и переходим к новой структуре данных, к очереди.

Очередь (Queue)

Очередь (Queue) это структура, знакомая нам из жизни. Очереди в магазины, к врачам. Кто первее пришел (First In), тот первее и выйдет из очереди (First Out). В Java очередь представлена интерфейсом java.util.Queue. Согласно Javadoc очереди, очередь добавляет следующие методы: Как видите, есть методы-приказы (их невыполнение чревато исключением): add, remove и element. И есть методы-просьбы (невозможность их выполнить не приводит к ошибкам, вместо этого возвращается false или null): offer, poll и peek. Кроме того, можно получить элемент без удаления (peek или элемент).

Deque: очередь с двух концов

У интерфейса очереди есть так же полезный наследник, Deque. Это так называемая "двусторонняя очередь". То есть такая очередь позволяет использовать эту структуру как с начала, так и с конца. В документации сказано, что "Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class.", то есть вместо Stack рекомендуется использовать реализации Deque. В Javadoc показано, какие методы описывает интерфейс Deque: Давайте посмотрим, какие есть реализации. И увидим интересный факт: в стан очередей "затесался" LinkedList ) То есть LinkedList реализует как интерфейс List, так и Deque.

PriorityQueue: очередь с приоритетом

Но есть и "только очереди", например PriorityQueue. Про нее не часто вспоминают, а зря. Во-первых, в этой очереди нельзя использовать "non-comparable objects", т.е. должен быть или Comparator указан или все объекты должны быть comparable. Во-вторых, "this implementation provides O(log(n)) time for the enqueuing and dequeuing methods". Логарифмическая сложность тут не просто так. Реализована PriorityQueue на основе "кучи". В Javadoc сказано: "Priority queue represented as a balanced binary heap". Само же хранилище для этого обычный массив. Который растет при необходимости. Когда куча небольшая, она растет в 2 раза. А потом на 50%. Комментарий из кода: "Double size if small; else grow by 50%". Очередь с приоритетом и Binary Heap это отдельная тема. Поэтому для дополнительной информации:

• Фоксфорд: Информатика. Структуры данных: Куча (heap)"
• "Introduction to Binary Heaps (MaxHeaps)"

В качестве реализации java.util.Deque можно привести класс java.util.ArrayDeque. То есть списки можно реализовать при помощи связанного списка и массива и очереди тоже можно реализовать при помощи массива или при помощи связанного списка.

Блокирующие очереди

Интерфейсы Queue и Deque имеют наследников, представляющих "блокирующую очередь": BlockingQueue и BlockingDeque. Вот изменение интерфейса в сравнении с обычными очередями: Давайте посмотрим на какие-нибудь примеры блокирующих очередей. А они ведь интересные. Например, BlockingQueue реализуют: PriorityBlockingQueue, SynchronousQueue, ArrayBlockingQueue, DelayQueue, LinkedBlockingQueue. А вот BlockingDeque реализуют из стандартного Collection Frameworks всего LinkedBlockingDeque. Каждая очередь это тема отдельного обзора. А в рамках данного обзора изобразим иерархию классов не только с List, но и с Queue: Как мы видим из схемы, интерфейсы и классы Java Collections Framework сильно переплетены. Давайте добавим еще одну ветвь иерархии, Set.

Set

Set переводится как "набор". От очереди и списка Set отличается большей абстракцией над хранением элементов. Set это как мешок с предметами, где неизвестно, как лежат предметы и в каком порядке они легли. В Java такой набор представлен интерфейсом java.util.Set. Как сказано в документации, Set это "collection that contains no duplicate elements". Интересно, что сам интерфейс Set долгое время не добавлял к интерфейсу Collection ни одного своего метода, а лишь уточнял требования (про то, что не должно содержать дубликатов). Своими у него стали только статические фабрики Set.of в Java 9 и Set.copyOf в Java 10, но это методы класса, а не объекта, так что на поведение самого набора они не влияют. Кроме того, из прошлого описания следует, что просто так из Set нельзя получить элемент. Для получения элементов используется Iterator.

SortedSet и NavigableSet

Set имеет еще несколько связанных с собой интерфейсов. Первый это SortedSet. Как и следует из названия, SortedSet указывает на то, что такой набор отсортирован, а следовательно элементы реализуют интерфейс Comparable или указан Comparator. Кроме того, SortedSet предлагает несколько интересных методов: Кроме того, есть методы first (самый маленький по значению элемент) и last (самый большой по значению элемент). У SortedSet есть наследник, NavigableSet. Цель этого интерфейса: описать методы навигации, которые нужны для более точного определения подходящих элементов. Из интересного: NavigableSet добавляет к привычному iterator (который идет от меньшего к большему) итератор для обратного порядка, descendingIterator. Кроме того, NavigableSet позволяет при помощи метода descendingSet получить вид на себя (View), в котором элементы идут в обратном порядке. Это называется View, потому что через полученный элемент можно изменять элементы изначального Set. То есть по сути это представление изначальных данных другим способом, а не их копия. Интересно, что NavigableSet, подобно Queue, умеет pollFirst (минимальный) и pollLast (максимальный) элементы. То есть получает этот элемент и убирает из набора. Какие же есть реализации? Во-первых, самая известная реализация, на основе хэш-кода, это HashSet. Другая не менее известная реализация, на основе красно-черного дерева, это TreeSet. Давайте дорисуем нашу схему: В рамках коллекций осталось разобрать иерархию отшельников, которая на первый взгляд стоит в стороне: java.util.Map.

Карты (Map)

Карты это такая структура данных, в которой данные хранятся по ключу. Например, ключом может служить ID или код города. И именно по этому ключу будут искаться данные. Интересно, что карты вынесены отдельно. По словам разработчиков маппинг "ключ - значение" не является коллекцией. И карты можно скорей представить как коллекция ключей, коллекция значений, коллекция пар "ключ - значение". Вот такой вот интересный зверь. Какие же методы предоставляют карты? Давайте посмотрим на Java API интерфейса java.util.Map. Т.к. карты не являются коллекциями (не наследуются от Collections), то они не содержат метод contains. И это ведь логично. Карта состоит из ключей и значений. Что из этого должен проверять метод contains и как не запутаться? Поэтому, интерфейс Map имеет две разные версии: containsKey (содержит ли ключ) и containsValue (содержит ли значение). При помощи keySet позволяет получить набор ключей (тот самый Set). А при помощи метода values можем получить коллекцию значений в карте. Ключи в карте уникальны, что подчеркивается структурой данных Set. Значения же могут повторяться, что подчеркивает структура данных Collection. Кроме того, при помощи метода entrySet можем получить набор пар "ключ - значение". Хотелось бы еще увидеть, что HashMap очень похож на HashSet, а TreeMap на TreeSet. У них даже схожие интерфейсы: NavigableSet и NavigableMap, SortedSet и SortedMap. Итак, наша финальная карта будет выглядеть следующим образом: Закончить можно занимательным фактом: самые ходовые наборы внутри себя используют Map. HashSet держит внутри HashMap, TreeSet держит TreeMap, добавляемые значения становятся ключами, а значением везде лежит один и тот же объект-заглушка. Правилом для всех наборов это не является: скажем, EnumSet работает на битовой маске, а CopyOnWriteArraySet на массиве. Занимательно это потому, что Map не является коллекцией и возвращает Set, который является коллекцией, но по факту реализован как Map. Немного сюр, но вот так вот вышло )

Что изменилось в Java 21: Sequenced Collections

Все схемы выше рисуют иерархию такой, какой она была много лет подряд. Но в Java 21 в нее добавили целый слой, и знать о нем стоит: на собеседовании по свежей версии про него спрашивают. Проблема, которую решали, звучит так. Порядок элементов есть у List, у Deque, у SortedSet и у LinkedHashSet, а вот общего интерфейса, который этот порядок описывал бы, не было: их общий предок Collection про порядок ничего не знает. В итоге каждая коллекция изобретала свой способ достать первый и последний элемент:

// List
list.get(0);
list.get(list.size() - 1);

// Deque
deque.getFirst();
deque.getLast();

// SortedSet
sortedSet.first();
sortedSet.last();

// LinkedHashSet
linkedHashSet.iterator().next();
// а последнего элемента нет вовсе, только перебор всего набора

Четыре разных написания одного и того же, причем у LinkedHashSet последний элемент было не достать иначе, чем перебрав весь набор целиком. Именно с этого списка и начинается JEP 431, в котором предложили новые интерфейсы. Java 21 добавила три штуки, и встали они ровно посередине иерархии:

• SequencedCollection с методами getFirst, getLast, addFirst, addLast, removeFirst, removeLast и reversed. Его наследуют List, Deque, SortedSet и NavigableSet, то есть он вклинился прямо между Collection и доброй половиной схемы.
• SequencedSet это одновременно и SequencedCollection, и Set. Реализуют его LinkedHashSet, TreeSet и ConcurrentSkipListSet.
• SequencedMap делает то же самое для карт: firstEntry, lastEntry, pollFirstEntry, pollLastEntry, putFirst, putLast, reversed плюс три представления sequencedKeySet, sequencedValues и sequencedEntrySet. Его наследуют SortedMap и NavigableMap, а реализуют LinkedHashMap, TreeMap и ConcurrentSkipListMap.

Теперь одно и то же для любой упорядоченной коллекции пишется одинаково:

list.getLast();
deque.getLast();
treeSet.getLast();
linkedHashSet.getLast();

// и обход с конца для любой из них
for (String s : list.reversed()) {
    System.out.println(s);
}

Метод reversed() стоит запомнить отдельно. Он возвращает не копию, а вид (View) на ту же самую коллекцию в обратном порядке, так что перебрать с конца что угодно теперь можно одной строчкой, а не через descendingSet у одних и ListIterator у других. И оговорка про схемы выше: они нарисованы до Java 21, этого слоя на них нет. Держи в голове, что между Collection и парой List с Deque теперь стоит SequencedCollection, а над SortedSet и SortedMap появились SequencedSet и SequencedMap. Ту же схему удобно держать и в виде таблицы: картинку не процитируешь, а строчку из таблицы вспомнить легко.

Заключение

Хорошая новость: на этом данный обзор заканчивается. Плохая новость это очень обзорная статья. Каждая реализация каждой из коллекций в Java заслуживает отдельную статью, а еще на каждый скрытый от наших глаз алгоритм. Но цель данного обзора - вспомнить, какие они есть и какие связи между интерфейсами. Надеюсь, у Вас получится после вдумчивого прочтения нарисовать по памяти схему коллекций.

Вопросы и ответы

Почему Map не входит в Collection?

Потому что Collection описывает набор одиночных элементов, а Map хранит пары. У Map нет ни метода add, ни метода iterator, они бы там просто не имели смысла. Добраться до содержимого можно через три представления: keySet отдает набор ключей, values коллекцию значений, entrySet набор пар. Вот они уже настоящие коллекции.

Чем ArrayList отличается от LinkedList?

Устройством. ArrayList хранит элементы в массиве и достает элемент по индексу за одно действие, зато при вставке и удалении в середину сдвигает весь хвост через System.arraycopy. LinkedList хранит элементы связанными узлами: вставка и удаление это переброс пары ссылок, зато до пятого элемента придется дойти от первого. На практике почти всегда берут ArrayList, LinkedList оправдан при частых вставках в начало и середину.

Зачем нужны Vector и Stack, если есть ArrayList и Deque?

Это классы из первых версий Java, оставленные ради совместимости. Vector отличается от ArrayList только тем, что его методы синхронизированы, и его собственная документация советует брать ArrayList, если потокобезопасность не нужна. Stack унаследован от Vector, и документация Deque прямо говорит, что вместо устаревшего класса Stack следует использовать реализации Deque, например ArrayDeque.

Чем SortedSet отличается от обычного Set?

Обычный Set ничего не обещает про порядок элементов. SortedSet держит их отсортированными, поэтому его элементы обязаны реализовывать Comparable либо при создании набора нужно передать Comparator. Отсюда же берутся методы first, last, headSet, tailSet и subSet. NavigableSet добавляет к этому поиск ближайших соседей и обход в обратную сторону.

Почему у Queue по два метода на каждую операцию?

Потому что на неудачу можно реагировать двумя способами. Методы add, remove и element бросают исключение, если операцию выполнить нельзя. Методы offer, poll и peek в той же ситуации возвращают специальное значение, false или null. Первую тройку берут, когда пустая очередь это ошибка, вторую, когда это штатная ситуация.

Правда ли, что Set внутри устроен как Map?

Для самых ходовых реализаций да. HashSet держит внутри HashMap, TreeSet держит TreeMap: добавляемые значения становятся ключами, а значением везде лежит один и тот же объект-заглушка. Но общим правилом это не является: EnumSet работает на битовой маске, а CopyOnWriteArraySet на массиве с копированием при записи.

Читайте также

• Подробный разбор класса ArrayList
• Подробный разбор класса HashMap
• Интерфейс Map в Java: ответы на частые вопросы
• Топ 10 вопросов о коллекциях в Java