Для хранения наборов данных в Java существуют массивы. Однако их не всегда удобно использовать. Главным ограничением является фиксированная длина массива. Эту проблему в Java решают коллекции.
Однако суть не только в гибких по размеру наборах элементов, но в и том, что классы коллекций реализуют различные алгоритмы и структуры данных, такие как множество, очередь, дерево и ряд других.
Все коллекции образуют стройную и логичную структуру. В основе любой колеекции лежит использование того или иного интерфейса, который определяет ее базовый функционал.
Иерархия коллекций
Примерно так выглядит основная иерархия коллекций. Мы по порядку, сверху вниз, разберем каждый класс, и каждый интерфейс.

Map не наследуется от интерфейса Collection, но входит в состав фреймворка Collections.
Интерфейс Iterable
Самый первый интерфейс, который наследуют все остальные коллекции это Iterable
. Самый важный метод этого интерфейса это Iterator<T> iterator();
Скорее всего вы уже видели такую реализацию for
:
final List<String> names = List.of("mark", "mike", "kate");
for (String name : names) {
System.out.println(name);
}
Она возможно благодаря Iterable
и Iterator<T>
. Если мы откроем байткод примера выше, то увидим, что имено Iterator
используется для этого for
.

Даже, если вы не умеете читать байткод, легко увидите вызов метода iterator()
, который и возвращает Iterator
. И далее использование методов итератора, поговорим о нем поподробнее.
Интерфейс Iterator
Это интерфейс курсора, у которого основные методы это:
E next();
– Позволяет получить следующий элемент коллекции.boolean hasNext();
– Возвращаетtrue
, если следующий элемент коллекции есть.void remove();
– Удаляет текущий элемент.
Рассмотрим пример использования итератора. Создадим список имен, после чего получим итератор коллекции, пройдемся по всем элементам и удалим всех "mike"
.
final List<String> names = new ArrayList<>(List.of("mark", "mike", "kate"));
final Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
final String name = iterator.next();
if ("mike".equals(name)) {
iterator.remove();
}
}
System.out.println(names); // [mark, kate]
Интерфейс Collection<T>
Интерфейс Collection
является обобщенным и расширяет интерфейс Iterable
, поэтому все объекты коллекций можно перебирать в цикле по типу for-each
.
Этот интерфейс содержит основные методы, для работы с коллекциями. Он используется там, где требуется максимальная универсальность. Например, если ваш методу не важно какую коллекцию принимать для работы.
У JDK нет ни одной прямой реализации этого интерфейса, есть только его наследники интерфейсы, такие как List
, Set
, и другие.
Все коллекции (за исключением Map
), получают следующие методы:
boolean add(E item);
– Добавление элемента в коллекцию. При удачном добавлении возвращает true, при неудачном –false
boolean addAll(Collection<?> c)
– Добавляет все элементы указанной коллекции в эту коллекцию.void clear()
– Удаляет все элементы из коллекцииboolean contains(Object item)
– возвращаетtrue
, если объект содержится в коллекции, иначе возвращаетfalse
boolean containsAll(Collection<?> c)
– возвращает true, если указанная коллекция содержится в этой коллекции, иначе возвращаетfalse
boolean retainAll(Collection<?>c)
– удаление из этой коллекции всех элементов переданной коллекцииboolean isEmpty()
– возвращаетtrue
, если коллекция пуста, иначе возвращаетfalse
.boolean remove(Object item)
– позволяет удалить элемент из коллекцииint size()
– возвращает число элементов в коллекцииObject[] toArray()
– возвращает обычный массив, содержащий все элементы коллекции
Все эти и остальные методы, реализуются всеми коллекциями, поэтому общие принципы работы с коллекциями будут одни и те же. Единообразный интерфейс упрощает понимание и работу с различными типами коллекций.
Интерфейс List
Для создания простых списков применяется интерфейс List
, который расширяет функцональность интерфейса Collection
. Элементы в этих коллекциях должны быть упорядоченны. Пользователь может получить доступ к элементу коллекции по индексу (позиция в списке). Списки позволяют сохранять повторяющиеся элементы.
Помимо Iterator
списки также могут вернуть Listerator
, который позволяет вставку и замену элементов, а также двунаправленный доступ.
Основные методы List
:
void add(int index, object obj)
– вставляет элементobj
в позициюindex
. Старые элементы, начиная с позицииindex
, сдвигаются, их индексы увеличиваются на единицу.boolean addAll(int index, Collection coll)
– вставляет все элементы коллекцииcoll
object get(int index)
– возвращает элемент, находящийся на позицииindex
int indexOf(Object obj)
– возвращает индекс первого появления элементаobj
в коллекцииint lastindexOf(object obj)
– возвращает индекс последнего появления элементаobj
в коллекцииListiterator listiterator()
– возвращает итератор коллекцииListiterator listiterator(int index)
– возвращает итератор коллекции начиная с элемента с позициейindex
Object set(int index, object obj)
– заменяет элемент, находящийся на позицииindex
, элементомobj
List subList(int from, int to)
– возвращает часть коллекции от позицииfrom
включительно до позицииto
исключительно.
Интерфейс Set
Как следует из названия, этот интерфейс моделирует адстракцию математического множества. Поэтому Set
это коллекция, которая не содержит повторяющиеся элементы. Эквивалентность элементов проверяется с помощью метода equals()
.
Основные методы:
add(Object o)
– Добавление элемента в коллекцию, если он отсутствует. Возвращаетtrue
, если элемент добавлен.addAll(Collection c)
– Добавление элементов коллекции, если они отсутствуют.clear()
– Удаление всех элементов из коллкецииcontains(Object o)
– Проверка присутствия элемента в наборе. Возвращает true, если элемент найден.containsAll(Collection c)
– Проверка присутсвия коллекции в наборе. Возвращает true, если все элементы содержатся в наборе.isEmpty()
– Проверка наличия элементов. Возвращает true если в коллекции нет ни одного элемента.iterator()
– Функция получения итератора коллекции.remove(Object o)
– Удаление элемента из набора.removeAll(Collection c)
– Удаление из набора всех элементов переданной коллекции.retainAll(Collection c)
– Удаление элементов, не принадлежащих переданной коллекции.size()
– Количество элементов в коллекции
Следует проявлять большую осторожность, если изменяемые объекты используются в качестве элементов набора. Поведение множества непредсказуемо, если значение объекта изменяется таким образом, который влияет на сравнения на equals()
. Приведу пример

Создаем два разных объекта, добавляем их в множество. После этого изменяем один объект так, чтобы mark.equals(mike);
стало true
. И вот у нас множество содержащее одинаковые элементы. Причем, если попытаться положить еще один такой же элемент, то затрется только один из них.
Интерфейс Queue
Очереди представляют структуру данных, работающую по принципу FIFO. То есть чем раньше был добавлен элемент в коллекцию, тем раньше он из нее удаляется. Это стандартная модель однонаправленной очереди.
Основные методы:
E element()
— возвращает, но не удаляет, элемент из начала очереди. Если очередь пуста, генерирует исключениеNoSuchElementException
boolean offer(E obj)
— добавляет элементobj
в конец очереди. Если элемент удачно добавлен, возвращает true, иначе - falseE peek()
— возвращает без удаления элемент из начала очереди. Если очередь пуста, возвращает значениеnull
E poll()
— возвращает с удалением элемент из начала очереди. Если очередь пуста, возвращает значениеnull
E remove()
— возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключениеNoSuchElementException
Интерфейс Deque
Интерфейс Deque
расширяет вышеописанный интерфейс Queue
и определяет поведение двунаправленной очереди, которая работает как обычная однонаправленная очередь, либо как стек, действующий по принципу LIFO.
То есть мы можем добавить элемент не только в начала, но и в конец. И соответственно удалить элемент не только из конца, но и из начала.
Основные методы:
void addFirst(E obj)
— добавляет элемент в начало очередиvoid addLast(E obj)
— добавляет элементobj
в конец очередиE getFirst()
— возвращает без удаления элемент из головы очереди. Если очередь пуста, генерирует исключениеNoSuchElementException
E getLast()
— возвращает без удаления последний элемент очереди. Если очередь пуста, генерирует исключениеNoSuchElementException
boolean offerFirst(E obj)
— добавляет элемент obj в самое начало очереди. Если элемент удачно добавлен, возвращает true, иначе -false
boolean offerLast(E obj)
— добавляет элемент obj в конец очереди. Если элемент удачно добавлен, возвращает true, иначе -false
E peekFirst()
— возвращает без удаления элемент из начала очереди. Если очередь пуста, возвращает значениеnull
E peekLast()
— возвращает без удаления последний элемент очереди. Если очередь пуста, возвращает значениеnull
E pollFirst()
— возвращает с удалением элемент из начала очереди. Если очередь пуста, возвращает значениеnull
E pollLast()
— возвращает с удалением последний элемент очереди. Если очередь пуста, возвращает значениеnull
E pop()
— возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключениеNoSuchElementException
void push(E element)
— добавляет элемент в самое начало очередиE removeFirst()
— возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключениеNoSuchElementException
E removeLast()
— возвращает с удалением элемент из конца очереди. Если очередь пуста, генерирует исключениеNoSuchElementException
boolean removeFirstOccurrence(Object obj)
— удаляет первый встреченный элементobj
из очереди. Если удаление произшло, то возвращает true, иначе возвращаетfalse
.boolean removeLastOccurrence(Object obj)
— удаляет последний встреченный элементobj
из очереди. Если удаление произшло, то возвращает true, иначе возвращаетfalse
.
Интерфейс Map
Объект, который сопоставляет ключам некоторые значения. Map
не может содержать повторяющиеся ключи. Каждый ключ может соответствовать не более одному значению.
Здесь присутствет такая же проблема что и описанная ранее в Set
.
Основные методы:
boolean containsKey(Object k)
– возвращает true, если коллекция содержит ключk
boolean containsValue(Object v)
– возвращает true, если коллекция содержит значениеv
Set<Map.Entry<K, V>> entrySet()
– возвращает набор элементов коллекции. Все элементы представляют объектMap.Entry
V get(Object k)
– возвращает значение объекта, ключ которого равен k. Если такого элемента не окажется, то возвращается значениеnull
V put(K k, V v)
– помещает в коллекцию новый объект с ключомk
и значением v. Если в коллекции уже есть объект с подобным ключом, то он перезаписывается. После добавления возвращает предыдущее значение для ключаk
, если он уже был в коллекции. Если же ключа еще не было в коллекции, то возвращается значениеnull
V putIfAbsent(K k, V v)
: помещает в коллекцию новый объект с ключомk
и значениемv
, если в коллекции еще нет элемента с подобным ключом.Set<K> keySet()
– возвращает набор всех ключей отображенияCollection<V> values()
– возвращает набор всех значений отображенияvoid putAll(Map<? extends K, ? extends V> map)
– добавляет в коллекцию все объекты из отображения mapV remove(Object k)
– удаляет объект с ключомk
int size()
– возвращает количество элементов коллекции
Интерфейс Map.Entry
Элемент коллекции Map
– пара ключ-значение.
Основные методы:
V getValue()
– возвращает значение объекта отображенияK getKey()
– возвращает ключ объекта отображенияV setValue(V v)
– устанавливает для текущего ключа значениеv
Приведу пример, зачем все это нужно. Допустим вы баррин, и у вас есть холлопы. В какой-то момент вы решили собрать с барщину (ренту) с тех, у кого богатсва превысили 100 золотых. Повезло, что данные о холопах вы харнили в Map
, где ключем выступает имя холопа, а значением его богатсва.
final Map<String, Integer> customers = new HashMap<>(
Map.of("Холоп 1", 100, "Холоп 2", 20, "Холоп 3", 200)
);
final Set<Map.Entry<String, Integer>> entries = customers.entrySet();
int coffers = 0;
for (Map.Entry<String, Integer> entry : entries) {
final Integer wealth = entry.getValue();
if (wealth > 100) {
entry.setValue(wealth - 10);
coffers += 10;
}
}
System.out.println("\nКазна пополнилась на " + coffers + " золотых, Миллорд!");
System.out.println(customers.values());
То есть вам нужно только вызвать метод entrySet()
, получить множество значений "ключ-значение". Пройтись по множеству циклом, найти всех холопов, у которых больше 100 золотых, вычесть у них 10 золотых и добавить их в козну. При этом не забыв обновить баланс холопам, то есть вызвав метод setValue()
.
Реализации коллекций
После того, как мы рассмотрели основные интерфейсы Java Collection Framewor, пришло время поговорить про конкретные реализации.
ArrayList
Как не сложно догадаться по названию это реализация интерфейса List
.
Как и обычный массив он содержит элементы, к которым можно получить доступ по целочисленному индексу. Если зайти в реализацию этого класса, то можно увидеть, что он сохраняет элементы в обычный массив и управляет его расширением.

Стоит так же упомянуть, что до появления Java Collection Framework существовал класс Vector
, который в последствии был включен в Java Collection. В отличии от всех реализаций колекции, Vector
синхронизирован. Если потокобезопасная реализация не требуется, рекомендуется использовать ArrayList
вместо Vector
.
Каждый экземпляр ArrayList
имеет емкость (CAPACITY). Емкость – это размер массива, который используется для хранения элементов. По мере добавления элементов в ArrayList
его емкость автоматически увеличивается.

Начальный размер capacity равен 10. Вы можете передать свое значение capacity используя конструктор public ArrayList(int initialCapacity)
.
Автоматически массив не уменьшается, поэтому если из массива часто удаляются элементы, и при этом не добавляется новых, имеет смысл использовать метод trimToSize();
. Этот метод есть только у ArrayList
и отсутсвует у List
.
Выводы
- Использует внутри простой массив;
- Быстрый доступ к элементам по индексу за время O(1);
- Доступ к элементам по значению за линейное время O(n);
- Позволяет хранить любые значения в том числе и
null
; - Не синхронизирован
- Автоматически не уменьшается
LinkedList
Использует для хранения двусвязный список. Работает как и ожидается от двусвязного списка. Помимо List
также реализует Dequeue
и Queue
. То есть он соединяет функциональность работы со списком и фукциональность очереди.

Класс LinkedList содержит три основных поля:
Node<E> first
– ссылка на первый элемент спискаNode<E> last
– ссылка на второй элемент спискаint size
– размер коллекции
Для установки ссылок на предыдущий и следующий элементы LinkedList
использует объекты своего вложенного класса Node
:

Добавление элементов в конец списка
- Создание нового узла (
Node
). - Установка объекта в поле
item
этого узла. - Добавление ссылки узла в конец списка.
- Установку ссылок на соседние узлы.
Добавление эелмента в середину списка
- Осуществляется проверка значения позиции добавления. Если позиция отрицательная, или больше размера списка, то будет сгенирировано исключение
IndexOutOfBoundsException
. - Если позиция добавления равна размеру коллекции, то осуществляются действия описанные в "Добавление эелмента в середину списка"
- Если же позиция не равна размеру списка, то осуществляется вставка перед элементом, который до этой вставки имеет заданный индекс.
- Для начала с помощью метода
node(index)
определяется узел, находящийся в данный момент под индексом, под который нам необходимо вставить новый узел. Поиск данного узла осуществляется с помощью простого циклаfor
по половине списка (в зависимости от значения индекса — либо с начала до элемента, либо с конца до элемента). Далее создается узел для нового элемента, ссылка на предыдущий элемент устанавливается на узел на позиции index-1, а ссылка на следующий элемент устанавливается на узел c позицией index+1. Ссылки ранее существующих узлов пока не изменены. - Теперь последовательно заменяются ссылки: для элемента, следующего за новым элементом, заменяется ссылка на предыдущий элемент. Для предшествующего новому элементу заменяется ссылка на следующий элемент.
- И в последнюю очередь увеличивается размер списка.
Удаление элемента из связного списка по значению:
- Сначала искомый объект сравнивается по порядку со всеми элементами, сохраненными в узлах списка, начиная с нулевого узла.
- Когда найден узел, элемент которого равен искомому объекту, первым делом элемент сохраняется в отдельной переменной.
- Потом переопределяются ссылки соседних узлов так, чтобы они указывали друг на друга.
- Затем обнуляется значение узла, который содержит удаляемый объект, а также уменьшается размер коллекции.
На собеседованиях часто спрашивают, когда выгоднее использовать LinkedList
, а когда — ArrayList
.
Правильный ответ таков: если добавлять и удалять элементы с произвольными индексами в списке нужно чаще, чем итерироваться по нему, то лучше LinkedList
. В остальных случаях — ArrayList
.
В целом так и есть, но при добавлении элементов в ArrayList
или их удалении вызывается нативный метод System.arraycopy()
. В нём используются ассемблерные инструкции для копирования блоков памяти. Так что даже для больших массивов эти операции выполняются за приемлемое время. Поэтому использование LinkedList
довольное редкое явление.
Выводы
- не синхронизирован;
- позволяет хранить любые объекты, в том числе
null
и повторяющиеся; - за константное время O(1) выполняются операции вставки и удаления первого и последнего элемента, операции вставки и удаления элемента из середины списка. Не учитывая время поиска позиции элемента, который осуществляется за линейное время O(n);
- за линейное время O(n) выполняются операции поиска элемента по индексу и по значению.
HashMap
Реализация Map
на основе хэш-таблицы. Эта реализация разрешает null ключи и null
значения. Класс HashMap
примерно эквивалентен Hashtable
, за исключением того, что он несинхронизирован и допускает значения null
.
Этот класс не дает никаких гарантий относительно порядка отображения; в частности, это не гарантирует, что порядок будет оставаться постоянным с течением времени.
В основе HashMap
лежит массив, элементы которого часто называются корзинами ("bucket").


Экземпляр HashMap
имеет два параметра, которые влияют на его производительность: начальная емкость (initial capacity) и коэффициент загрузки (load factor).
Емкость - это количество сегментов в хеш-таблице, то есть длинна массива. Должно быть равно степени двойки, по умолчанию 16.
Коэффициент загрузки - это мера того, насколько может быть заполнена хеш-таблица до того, как ее емкость автоматически увеличится. Когда количество записей в хеш-таблице превышает произведение коэффициента загрузки и текущей емкости, хеш-таблица перестраивается. По умолчанию коэфицент загрузки равен 0.75.
Как добавляется элемент?
- Ключ проверяется на равенство
null
. Если это проверка вернула true, будет вызван методputForNullKey(value)
- Далее генерируется хэш на основе ключа. Для генерации используется метод hash(), в который передается ключ. Этот метод путем математических операций возвращает целое число return
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
. - Это число определяет позицию в массиве, куда будет добавлен элемент.
- Если ячейка пуста, то создается
Node
, в которую записывается ключ и его значение. - Если ячека уже была занята. То ключи сверяются с помощью
equals
. Если ключ не был найден, то создается новая Node. Получается связаный список. Такое может случиться, так какhashCode()
разных объектов, может давать одинаковое значение. - Если ключи совпали (
key.equals(newKey)==true
), то старый элемент затирается новым
- Если ячейка пуста, то создается
По хорошему, каждый bucket должен хранить малое количество объектов, а лучше один, это дает нам константную скорость доступа к объекту - O(1). Но все мы понимаем что без коллизий не обойтись, поэтому один bucket может разрастись до больших размеров, особенно при плохой реализации метода hashCode()
. Это в свою очередь это приводит к ухудшению времени поиска этого объекта - O(n). Поэтому был встроен специальный защитный механизм.
Когда связный список разрастается до 8 элементов, он превращается в сбалансированное дерево. Такой ход, дает нам более производительное время доступа к обьекту - O(log(n)).
Это изменение затронуло не всех а лишь: HashMap
, LinkedHashMap
и ConcurrentHashMap
. Например Hashtable
- исключили из списка изменений, по причине что в некоторых приложениях как раз таки необходимо сохранять историю заполнения бакета.
TreeMap
TreeMap
— реализация Map
основанная на красно-черных деревьях. По-умолчанию, коллекция сортируется по ключам с использованием принципа натуральной сортировки, но это поведение может быть настроено под конкретную задачу при помощи объекта класса Comparator
, о котором мы поговорим ниже.
Красно-черное дерево – это усовершенствованная версия двоичного дерева поиска, с дополнительным атрибутом – "цвет" (красный/черный).
Красно-черное дерево – в отличие от бинарного самобалансирующееся, что обеспечивает логарифмическую сложность операций: добавления, удаления и поиска узла.

Требования красно-черного дерева:
- каждый узел либо красный, либо черный
- корень дерева – всегда черный
- Листья (так называемые null-узлы) окрашены в черный цвет и не хранят никаких данных.
- Каждый красный узел имеет 2-ух черных потомков
- Пути от узла к его листьям должны содержать одинаковое количество черных узлов
HashSet
Тут стоит только позавидовать смекалочке разработчиков JDK, ведь если посмотреть в конструкторы HashSet
, то

Та дам, под капотом HashSet
оказывается трудится HashMap
. Как же так вышло то? И как это работает?
А работает это так.


Значением для множества выступает ключ хэшмапы, а вместо полезной нагрузки для хэш-мапы кладется обычный объект пустышка.
Вывод:
- предоставляет константное время для add(), remove(), contains() и size()
- порядок элементов может меняться
TreeSet
Думаю, что теперь я никого не удивлю, если скажу, что TreeSet
использует под капотом TreeMap
. Ну а что, с HashSet
же нормально получилось :)

Выводы:
- время для базовых операций add(), remove(), contains() — log(n)
- гарантирует порядок элементов
Сортировка коллекций
Прошли те времена, когда вам руками нужно было писать "пузырьковую" сортировку. Теперь все гораздо проще.
Интерфейс Comparator<T>
Создайте класс, который будет реализовывать интерфейс Comparator
. В этом классе вам нужно реализовать метод compare(T o1, T o2)
.
package dev.struchkov.collection.comparator;
import java.util.Comparator;
public class PersonComparator implements Comparator<Person> {
@Override
public int compare(Person o1, Person o2) {
return o1.getAge() - o2.getAge();
}
}
Логика тут простая. Если объект о1 меньше, чем объект о2, то вам необходимо вернуть отрицательное число. Если объекты равны, то ноль. Если объект o1 больше, чем o2, то возвращаем положительное число. Каким образом сравнивать можете придумать самостоятельно.

Если вам нужен обратный порядок сортировки, то не нужно создавать еще один компоратор, можно воспользоваться методом reversed()
.

Компаратор также можно передавать в конструктор TreeSet, чтобы обеспечить нужный порядок множества.
Интерфейс Comparable<T>
Не обязательно создавать отдельный класс для сортировки. Можно имплементировать интерфейс Comparable
у того класса, который необходимо будет сортировать. То есть в данном примере у Person
.
Необходимо будет также реализовать один метод, с такой же логикой, что и у компоратора.
@Override
public int compareTo(Person o) {
return this.age - o.getAge();
}

Обратный порядок сортировки делается также методом reverse()
;

Итог
Коллекции — это мощный инструмент в руках Java разработчика. И теперь вы знаете о них основную информацию. Рекомендую потренировать и пописать программы с использованием коллекций.
Удачи 🤞