Java Collection Framework – это, безусловно, одна из важнейших составляющих языка программирования Java, которая активно используется для хранения, извлечения и обработки данных. В этой статье я расскажу вам о Java Collection Framework, о его значении, основах и уникальных свойствах, и о том, как правильно его использовать в процессе разработки. 📚
Определение Java Collection Framework
Java Collection Framework (JCF) – это собрание классов и интерфейсов в Java, предназначенных для хранения и обработки данных в оперативной памяти. Он предоставляет различные абстракции для работы с группами (или, как их ещё называют, коллекциями) объектов, что позволяет эффективно решать самые разнообразные задачи.
JCF включает в себя несколько основных интерфейсов, таких как Collection
, List
, Set
, Queue
, Deque
и Map
. Каждый из этих интерфейсов обладает уникальными возможностями и способами работы с данными. Например, интерфейс List
предназначен для работы с упорядоченными коллекциями данных, Set
– для работы с уникальными элементами, а Map
– для хранения пар ключ-значение.
Основы Java Collection Framework
Для эффективного использования JCF, важно разобраться в его структуре – иерархии интерфейсов и классов. Это позволит нам выбирать наиболее подходящий тип коллекции для конкретной задачи.
Иерархия интерфейсов JCF
Все начинается с интерфейса Iterable
, который является корневым для всех типов коллекций и предоставляет возможность перебирать элементы коллекции.
for (Type variable : iterableCollection) {
// Code block
}
От Iterable
наследуется интерфейс Collection
, который является фундаментом для большинства других интерфейсов коллекций. Он включает в себя базовые методы, такие как add()
, remove()
, contains()
, size()
и другие.
Collection
имеет три основных подинтерфейса: List
, Set
и Queue
.
List
представляет собой упорядоченную коллекцию, которая может содержать дубликаты. Примерами реализации этого интерфейса служатArrayList
,LinkedList
.Set
– это коллекция, которая не может содержать дубликаты. Примеры реализации этого интерфейса включаютHashSet
,LinkedHashSet
иTreeSet
.Queue
используется для хранения элементов, которые обрабатываются в определенном порядке.PriorityQueue
иLinkedList
- это примеры реализации этого интерфейса.
Интерфейс Deque
расширяет Queue
и добавляет функциональность для вставки, удаления и проверки элементов с обоих концов очереди.
Следующий важный интерфейс в иерархии - Map
. Он не наследуется от Collection
, но является неотъемлемой частью JCF. Map
хранит элементы в форме пар ключ-значение и не может содержать дубликаты ключей. Примеры реализации Map
включают HashMap
, TreeMap
и LinkedHashMap
.

Общие операции с коллекциями
Java Collection Framework предоставляет набор стандартных операций, которые можно выполнять на любой коллекции. Они включают в себя добавление элементов, удаление элементов, поиск элементов и другие действия. Рассмотрим их подробнее:
Добавление элементов: Для добавления элементов в коллекцию используется метод add()
. В случае с List
и Queue
элементы добавляются в конец коллекции. Для Set
порядок добавления элементов не гарантируется. В Map
элементы добавляются в виде пары ключ-значение.
List<String> list = new ArrayList<>();
list.add("Java"); // Добавляем элемент в список
Set<String> set = new HashSet<>();
set.add("Java"); // Добавляем элемент в множество
Map<String, String> map = new HashMap<>();
map.put("Key", "Value"); // Добавляем пару ключ-значение в map
Удаление элементов: Для удаления элементов из коллекции используется метод remove()
. Этот метод удаляет первый найденный элемент, который равен указанному. В случае с Map
, элемент удаляется по ключу.
list.remove("Java"); // Удаляем элемент из списка
set.remove("Java"); // Удаляем элемент из множества
map.remove("Key"); // Удаляем элемент из map по ключу
Поиск элементов: Метод contains()
используется для проверки, содержит ли коллекция определенный элемент. В случае с Map
, можно использовать методы containsKey()
или containsValue()
.
boolean existsInList = list.contains("Java"); // Проверяем наличие элемента в списке
boolean existsInSet = set.contains("Java"); // Проверяем наличие элемента в множестве
boolean existsInMap = map.containsKey("Key"); // Проверяем наличие ключа в map
Размер коллекции: Метод size()
используется для получения количества элементов в коллекции.
int sizeOfList = list.size(); // Получаем размер списка
int sizeOfSet = set.size(); // Получаем размер множества
int sizeOfMap = map.size(); // Получаем размер map
Эти операции являются основными и наиболее часто используемыми при работе с коллекциями в Java. Однако в зависимости от конкретного типа коллекции доступны и другие методы.
🌳 Иерархия интерфейсов JCF
Рассмотрим по порядку все основные интерфейсы JCF.
Интерфейс Iterable
и Iterator
Iterable
является корневым интерфейсом для всех коллекций в Java. Основным методом Iterable
является iterator()
, который возвращает объект Iterator
.
Iterator
используется для перебора элементов коллекции. Итератор предоставляет для этого три метода:
E next();
– Позволяет получить следующий элемент коллекции.boolean hasNext();
– Возвращаетtrue
, если следующий элемент есть.void remove();
– Удаляет текущий элемент.
Эти интерфейсы позволяют объектам быть целевыми для оператора "for-each", что упрощает итерацию по коллекциям.
final List<String> names = List.of("mark", "mike", "kate");
for (String name : names) { // цикл for-each
System.out.println(name);
}
Если мы откроем байткод примера выше, то увидим, что имено Iterator
используется для этого "for-each".

Даже, если вы не умеете читать байткод, легко увидите вызов метода iterator()
, который и возвращает Iterator
.
Рассмотрим еще один частый пример использования итератора: удаление элементов при обходе коллекции. Создадим список имен, после чего получим итератор коллекции, пройдемся по всем элементам и удалим всех "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
и является основным интерфейсом для всех типов коллекций в Java. Он предоставляет базовые методы, которые доступны для любой коллекции, включая методы для добавления, удаления и поиска элементов, а также получения размера коллекции.
У JDK нет ни одной прямой реализации этого интерфейса, есть только его наследники интерфейсы, такие как List
, Set
, и другие.
Все коллекции (за исключением Map
), получают следующие методы:
boolean add(E item);
– Этот метод используется для добавления элемента в коллекцию. Он возвращаетtrue
, если коллекция изменилась в результате вызова.void clear()
– Удаляет все элементы из этой коллекции.boolean contains(Object item)
– Этот метод используется для проверки, содержит ли коллекция указанный элемент.boolean isEmpty()
– Этот метод возвращаетtrue
, если коллекция пуста, иначе возвращаетfalse
.boolean remove(Object item)
– Этот метод используется для удаления одного экземпляра указанного элемента из этой коллекции, если он присутствует.int size()
– Этот метод возвращает количество элементов в этой коллекции.
Это основные методы, которые предоставляет интерфейс Collection
, и которые могут быть использованы для выполнения основных операций над коллекцией.
Интерфейс List
Интерфейс List
в Java Collection Framework представляет упорядоченную коллекцию (также известную как последовательность). Интерфейс 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)
– Этот метод используется для получения элемента из списка по указанному индексу.int indexOf(Object obj)
– Возвращает индекс первого вхождения указанного элемента в этом списке или -1, если этот список не содержит элемента.int lastindexOf(object obj)
– Возвращает индекс последнего вхождения указанного элемента в этом списке или -1, если этот список не содержит элемента.Object set(int index, object obj)
– Используется для замены элемента в этом списке на указанной позиции на указанный элемент.List subList(int from, int to)
– возвращает часть коллекции от позицииfrom
включительно до позицииto
исключительно.
Это основные методы, которые предоставляет интерфейс List
, и которые могут быть использованы для выполнения операций над списками, таких как добавление, удаление, получение и замена элементов.
Интерфейс Set
Интерфейс Set
представляет неупорядоченную коллекцию элементов, в которой каждый элемент является уникальным, то есть без дубликатов. Уникальность элементов проверяется с помощью метода equals()
. Интерфейс Set
расширяет Collection
.
Рассмотрим основные методы, предоставляемые интерфейсом Set
:
add(Object o)
– Добавляет указанный элемент в это множество, если он еще не присутствует. Если это множество уже содержит указанный элемент, вызов оставляет множество неизменным и возвращаетfalse
.addAll(Collection c)
– Добавление элементов коллекции, если они отсутствуют.clear()
– Удаляет все элементы из этого множества. Множество будет пустым после вызова этого метода.contains(Object o)
– Проверка присутствия элемента в наборе. Возвращает true, если элемент найден.containsAll(Collection c)
– Проверка присутсвия коллекции в наборе. Возвращает true, если все элементы содержатся в наборе.isEmpty()
– Возвращаетtrue
, если это множество не содержит элементов.remove(Object o)
– Удаляет указанный элемент из этого множества, если он присутствует.size()
– Возвращает количество элементов в этом множестве.
List
, Set
не предоставляет методы для доступа к элементам по индексу, поскольку наборы не упорядочены.Следует проявлять большую осторожность, если изменяемые объекты используются в качестве элементов множества. Поведение множества непредсказуемо, если значение объекта изменяется таким образом, который влияет на сравнения на equals()
. Приведу пример

Создаем два разных объекта, добавляем их в множество. После этого изменяем один объект так, чтобы mark.equals(mike);
стало true
. И вот у нас множество содержащее одинаковые элементы. Причем, если попытаться положить еще один такой же элемент, то затрется только один из них.
Интерфейс Queue
Интерфейс Queue
в Java Collection Framework предоставляет функциональность, характерную для очереди - структуры данных, работающей по принципу "первый пришел, первый обслужен" (FIFO). Интерфейс Queue
расширяет Collection
.
Рассмотрим основные методы, предоставляемые интерфейсом Queue
:
boolean offer(E obj)
— Вставляет указанный элемент в эту очередь, если это возможно сделать немедленно, не нарушая ограничений очереди. В отличие от методаadd
, этот метод не выдает исключение, если добавить элемент не удается.E peek()
— Возвращает, но не удаляет головной элемент этой очереди, или возвращаетnull
, если этой очереди пуста.E poll()
— Удаляет и возвращает головной элемент этой очереди, или возвращаетnull
, если этой очереди пуста.E remove()
— Удаляет и возвращает головной элемент этой очереди. Если очередь пуста, генерирует исключениеNoSuchElementException
.
Это основные методы, которые предоставляет интерфейс Queue
, и которые могут быть использованы для выполнения операций над очередью, таких как добавление, удаление и просмотр элементов.
Интерфейс Deque
Интерфейс Deque
(Double Ended Queue) в Java Collection Framework представляет двустороннюю очередь, где добавление, удаление и поиск элементов могут происходить с обоих концов. Интерфейс Deque
расширяет Queue
.
То есть мы можем добавить элемент не только в начала, но и в конец. И соответственно удалить элемент не только из конца, но и из начала.
Рассмотрим основные методы, предоставляемые интерфейсом Deque
:
void addFirst(E obj)
— вставляет указанный элемент в начало очереди.void addLast(E 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
.
Это основные методы, которые предоставляет интерфейс Deque
, и которые могут быть использованы для выполнения операций над двусторонней очередью, таких как добавление, удаление и просмотр элементов с обоих концов.
Интерфейс Map
Интерфейс Map
в Java Collection Framework представляет объект, который хранит пары ключ/значение. Он не является частью коллекции, но все еще является частью Collection Framework. В отличие от других интерфейсов, Map
не наследуется от Collection
, поэтому его поведение немного отличается.
Рассмотрим основные методы, предоставляемые интерфейсом Map
:
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
, и которые могут быть использованы для выполнения операций над картой, таких как добавление, удаление и просмотр элементов.
Интерфейс Map.Entry
Интерфейс Map.Entry
в Java используется для работы с элементами Map
. Он представляет пару ключ-значение и имеет методы, которые позволяют получить и изменить ключ и значение пары.
Методы интерфейса Map.Entry
:
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()
, получить множество значений "ключ-значение" (Map.Entry
). Пройтись по множеству циклом, найти всех холопов, у которых больше 100 золотых, вычесть у них 10 золотых и добавить их в козну. При этом не забыв обновить баланс холопам, то есть вызвав метод setValue()
.
Реализации коллекций
После того, как мы рассмотрели основные интерфейсы Java Collection Framework, пришло время поговорить про конкретные реализации.
ArrayList
ArrayList
в Java — это динамический массив, который хранит свои элементы в массиве. Размер этого массива (емкость ArrayList
) автоматически увеличивается, когда мы добавляем больше элементов, чем он может вместить. Внутри, ArrayList
использует массив объектов (Object[]
) для хранения элементов.

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

Когда элементы добавляются в ArrayList
и его емкость становится недостаточной, его емкость увеличивается. Новая емкость рассчитывается как старая емкость * 1.5 + 1
. То есть, если у нас было место для 10 элементов, теперь будет 16. Внутренний массив создается заново с новой емкостью и старые элементы копируются в новый массив. Это довольно затратная операция, поэтому если изначально известно, что ArrayList
будет хранить много элементов, рекомендуется задавать достаточно большую начальную емкость.
Удаление элементов из ArrayList
также может быть затратной операцией, особенно если удаляется элемент из середины списка. При удалении элемента, все элементы, следующие за ним, сдвигаются на одну позицию назад, что требует копирования данных.
При этом размер внутреннего массива автоматически не уменьшается, поэтому если из массива часто удаляются элементы, и при этом не добавляется новых, имеет смысл использовать метод trimToSize();
. Этот метод есть только у ArrayList
и отсутсвует у List
.
ArrayList
не синхронизирован, то есть не является потокобезопасным. Если несколько потоков изменяют ArrayList
одновременно, его состояние может стать непредсказуемым.
Выводы
- Использует внутри простой массив;
- Автоматически не уменьшается;
- Не является потокобезопасным;
- Быстрый доступ к элементам по индексу за время O(1);
- Доступ к элементам по значению за линейное время O(n);
- Позволяет хранить любые значения в том числе и
null
;
LinkedList
LinkedList
реализует интерфейс List
и Deque
. Он представляет собой двусвязный список, что означает, что каждый элемент списка (обычно называемый "узел") содержит ссылку как на следующий, так и на предыдущий узел в списке.

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

Добавление элементов в конец списка
- Создание нового узла (
Node
). - Установка объекта в поле
item
этого узла. - Добавление ссылки узла в конец списка.
- Установку ссылок на соседние узлы.
Добавление эелмента в середину списка
- Осуществляется проверка значения позиции добавления. Если позиция отрицательная, или больше размера списка, то будет сгенирировано исключение
IndexOutOfBoundsException
. - Если позиция добавления равна размеру коллекции, то осуществляются действия описанные в "Добавление элемента в середину списка"
- Если же позиция не равна размеру списка, то осуществляется вставка перед элементом, который до этой вставки имеет заданный индекс.
- Для начала с помощью метода
node(index)
определяется узел, находящийся в данный момент под индексом, под который нам необходимо вставить новый узел. Поиск данного узла осуществляется с помощью простого циклаfor
по половине списка (в зависимости от значения индекса — либо с начала до элемента, либо с конца до элемента). Далее создается узел для нового элемента, ссылка на предыдущий элемент устанавливается на узел на позиции index-1, а ссылка на следующий элемент устанавливается на узел c позицией index+1. Ссылки ранее существующих узлов пока не изменены. - Теперь последовательно заменяются ссылки: для элемента, следующего за новым элементом, заменяется ссылка на предыдущий элемент. Для предшествующего новому элементу заменяется ссылка на следующий элемент.
- И в последнюю очередь увеличивается размер списка.
Удаление элемента из связного списка по значению:
- Сначала искомый объект сравнивается по порядку со всеми элементами, сохраненными в узлах списка, начиная с нулевого узла.
- Когда найден узел, элемент которого равен искомому объекту, первым делом элемент сохраняется в отдельной переменной.
- Потом переопределяются ссылки соседних узлов так, чтобы они указывали друг на друга.
- Затем обнуляется значение узла, который содержит удаляемый объект, а также уменьшается размер коллекции.
В заключение отмечу, что как и ArrayList
, LinkedList
не синхронизирован. Если требуется потокобезопасность, можно использовать Collections.synchronizedList
.
Выводы
- Не является потокобезопасным;
- позволяет хранить любые объекты, в том числе
null
и повторяющиеся; - за константное время O(1) выполняются операции вставки и удаления первого и последнего элемента, операции вставки и удаления элемента из середины списка. Не учитывая время поиска позиции элемента, который осуществляется за линейное время O(n);
- за линейное время O(n) выполняются операции поиска элемента по индексу и по значению.
HashMap
HashMap
является одной из наиболее широко используемых реализаций интерфейса Map
в Java, которая хранит данные в форме пар "ключ-значение".
Под капотом HashMap
представляет собой массив (таблицу) с элементами типа Node
. При создании HashMap
, инициализируется этот массив:
transient Node<K,V>[] table;

Каждый Node
представляет собой связный список или bucket, который содержит четыре поля: int hash
, K key
, V value
, Node<K,V> next
.

Экземпляр HashMap
имеет два параметра, которые влияют на его производительность: начальная емкость (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
), то старый элемент затирается новым
- Если ячейка пуста, то создается
null
ключами всегда записываются в нулевую ячейку массива.По хорошему, каждый bucket должен хранить малое количество объектов, а лучше один, это дает нам константную скорость доступа к объекту - O(1). Но все мы понимаем что без коллизий не обойтись, поэтому один bucket может разрастись до больших размеров, особенно при плохой реализации метода hashCode()
. Это в свою очередь это приводит к ухудшению времени поиска этого объекта - O(n). Поэтому был встроен специальный защитный механизм.
Когда связный список разрастается до 8 элементов, он превращается в сбалансированное дерево. Такой ход, дает нам более производительное время доступа к обьекту - O(log(n)).
TreeMap
TreeMap
является реализацией интерфейса SortedMap
, который расширяет интерфейс Map
в Java. TreeMap
хранит пары ключ-значение, отсортированные по ключам, что обеспечивается структурой данных под названием красно-черное дерево.
Красно-черное дерево – это усовершенствованная версия бинарного дерева поиска, с дополнительным атрибутом – "цвет" (красный/черный). Это означает, что поиск, вставка и удаление элементов выполняются за время O(log(n)), где n - количество элементов в дереве.

Требования красно-черного дерева:
- каждый узел либо красный, либо черный
- корень дерева – всегда черный
- листья (так называемые
null
-узлы) окрашены в черный цвет и не хранят никаких данных. - каждый красный узел имеет 2-ух черных потомков
- пути от узла к его листьям должны содержать одинаковое количество черных узлов
HashSet
HashSet
использует хеш-таблицу для хранения элементов, и поэтому его операции add()
, remove()
и contains()
имеют постоянное время выполнения - O(1). Он не поддерживает дубликаты элементов.
Тут стоит только позавидовать смекалочке разработчиков JDK, ведь если посмотреть в конструкторы HashSet
, то

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


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

Выводы:
- log(n) для базовых операций
add()
,remove()
,contains()
- гарантирует порядок элементов
Производительность различных коллекций
Важным аспектом работы с коллекциями в Java является понимание их производительности в зависимости от операций, которые вы собираетесь выполнять. Различные реализации коллекций имеют разные характеристики производительности, и выбор оптимального типа коллекции может существенно улучшить производительность вашего приложения
ArrayList vs LinkedList
ArrayList
и LinkedList
имеют разные временные сложности для различных операций. Вставка, удаление и доступ к элементу в середине списка для ArrayList
требует времени O(n), тогда как для LinkedList
эти операции выполняются за время O(1).
Но стоит отметить, что при добавлении элементов в ArrayList
или их удалении вызывается нативный метод System.arraycopy()
. В нём используются ассемблерные инструкции для копирования блоков памяти. Так что даже для больших массивов эти операции выполняются за приемлемое время. Поэтому использование LinkedList
довольное редкое явление.
С другой стороны, доступ к произвольному элементу ArrayList
занимает время O(1), тогда как для LinkedList
это займет время O(n), поскольку потребуется обойти список от начала до нужного элемента.
HashSet vs TreeSet
HashSet
обеспечивает константное время выполнения для основных операций (add()
, remove()
, contains()
и size()
), поскольку оно использует хэш-таблицу.
TreeSet
, в свою очередь, гарантирует O(log(n)) время выполнения для тех же операций за счет использования красно-черного дерева. Однако, TreeSet
поддерживает порядок элементов.
HashMap vs TreeMap
Как и в случае с HashSet
и TreeSet
, HashMap
предоставляет константное время выполнения для основных операций, таких как put()
, get()
и remove()
.
TreeMap
гарантирует O(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 Collection Framework не являются потокобезопасными. Например, классы ArrayList
, LinkedList
, HashSet
, LinkedHashSet
, HashMap
и LinkedHashMap
не обеспечивают потокобезопасность.
Потокобезопасные коллекции
В Java Collection Framework существуют потокобезопасные коллекции, такие как Vector
и Hashtable
, которые являются предшественниками ArrayList
и HashMap
соответственно. Они обеспечивают потокобезопасность путем синхронизации всех своих методов. Однако, использование этих коллекций может привести к падению производительности из-за оверхеда, связанного с синхронизацией.
Java предоставляет также набор потокобезопасных коллекций в пакете java.util.concurrent
, таких как CopyOnWriteArrayList
, ConcurrentHashMap
, ConcurrentLinkedQueue
и другие. Эти коллекции обеспечивают более высокую производительность в многопоточной среде, чем Vector
или Hashtable
.
Синхронизированные обертки
Если вам нужно создать потокобезопасную коллекцию из не потокобезопасной коллекции, вы можете использовать синхронизированные обертки из класса Collections
, например, Collections.synchronizedList(new ArrayList<...>())
.
ConcurrentModificationException
При итерации по коллекции и одновременном изменении её через другой поток, Java может выбросить ConcurrentModificationException
. Это исключение бросается, чтобы указать, что в процессе итерации структура коллекции была некорректно изменена.
Использование Stream API
В Java 8 был введен новый компонент, Stream API, который предоставляет функциональные методы для обработки коллекций. Это помогает писать более чистый и компактный код, особенно при работе с большими наборами данных.
Подробнее про работу и использование Stream API читайте в отдельной статье 👇

Лучшие практики
Использование Java Collection Framework может быть довольно прямолинейным и простым, но существуют некоторые "лучшие практики", которые могут сделать ваш код более эффективным и надежным.
Интерфейсы вместо конкретных реализаций
Вместо того чтобы напрямую привязываться к конкретной реализации коллекции, используйте интерфейс. Это дает вам гибкость в будущем изменить реализацию без необходимости менять код, который использует коллекцию.
List<String> myList = new ArrayList<>(); // Вместо: ArrayList<String> myList = new ArrayList<>();
Методы equals()
и hashCode()
Если вы храните пользовательские объекты в коллекциях, особенно в Set
и Map
, убедитесь, что вы правильно переопределили методы equals()
и hashCode()
. Это обеспечивает правильное сравнение объектов и корректное поведение коллекций.
Collections
: утилитарные классы
Класс Collections
предоставляет ряд полезных утилитарных функций для работы с коллекциями. Это включает в себя методы для создания неизменяемых коллекций, сортировки коллекций, поиска элементов в коллекциях и многого другого.
Collections.sort(myList); // Сортирует список myList
Использование java.util.Objects
В Java 7 был добавлен класс java.util.Objects
, который содержит статические утилиты, которые полезны при работе с объектами, и могут помочь в предотвращении NullPointerException
.
Objects.requireNonNull(myList, "Список не должен быть null");
Заключение
Java Collection Framework - это основной и мощный инструмент для программиста на Java. Этот фреймворк предлагает множество решений для организации и обработки данных в приложениях.
Он предоставляет ряд встроенных интерфейсов и классов, которые позволяют реализовать различные структуры данных, такие как списки, множества и карты. Он также предоставляет методы для выполнения распространенных операций, таких как добавление, удаление и поиск элементов в коллекции.
Важно понимать иерархию и основные принципы работы Java Collection Framework, чтобы использовать его на полную мощь. Необходимо тщательно выбирать конкретные реализации в зависимости от требований и характеристик вашего проекта, и всегда следовать лучшим практикам и рекомендациям, чтобы обеспечить эффективность и надежность вашего кода.
Надеюсь, эта статья помогла вам лучше понять Java Collection Framework и его возможности. В конце концов, основой становится практика: чем больше вы работаете с этим фреймворком, тем больше опыта вы получаете, и тем лучше вы понимаете, как использовать его наилучшим образом.
Помните, что хорошее знание Java Collection Framework – это ключ к успешному программированию на Java. Продолжайте изучение, экспериментируйте и становитесь лучше!