Java Collection Framework: Полное руководство для разработчиков

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() – Возвращает количество элементов в этом множестве.

Следует проявлять большую осторожность, если изменяемые объекты используются в качестве элементов множества. Поведение множества непредсказуемо, если значение объекта изменяется таким образом, который влияет на сравнения на 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) – добавляет в коллекцию все объекты из отображения map
• V remove(Object k) – удаляет объект с ключом k
• int size() – возвращает количество элементов коллекции

Это основные методы, которые предоставляет интерфейс 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());

Реализации коллекций

После того, как мы рассмотрели основные интерфейсы Java Collection Framework, пришло время поговорить про конкретные реализации.

ArrayList

ArrayList в Java — это динамический массив, который хранит свои элементы в массиве. Размер этого массива (емкость ArrayList) автоматически увеличивается, когда мы добавляем больше элементов, чем он может вместить. Внутри, ArrayList использует массив объектов (Object[]) для хранения элементов.

Каждый экземпляр 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. Ссылки ранее существующих узлов пока не изменены.
• Теперь последовательно заменяются ссылки: для элемента, следующего за новым элементом, заменяется ссылка на предыдущий элемент. Для предшествующего новому элементу заменяется ссылка на следующий элемент.
• И в последнюю очередь увеличивается размер списка.

Удаление элемента из связного списка по значению:

1. Сначала искомый объект сравнивается по порядку со всеми элементами, сохраненными в узлах списка, начиная с нулевого узла.
2. Когда найден узел, элемент которого равен искомому объекту, первым делом элемент сохраняется в отдельной переменной.
3. Потом переопределяются ссылки соседних узлов так, чтобы они указывали друг на друга.
4. Затем обнуляется значение узла, который содержит удаляемый объект, а также уменьшается размер коллекции.

В заключение отмечу, что как и 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), то старый элемент затирается новым

По хорошему, каждый bucket должен хранить малое количество объектов, а лучше один, это дает нам константную скорость доступа к объекту - O(1). Но все мы понимаем что без коллизий не обойтись, поэтому один bucket может разрастись до больших размеров, особенно при плохой реализации метода hashCode(). Это в свою очередь это приводит к ухудшению времени поиска этого объекта - O(n). Поэтому был встроен специальный защитный механизм.

Когда связный список разрастается до 8 элементов, он превращается в сбалансированное дерево. Такой ход, дает нам более производительное время доступа к обьекту - O(log(n)).

TreeMap

TreeMap является реализацией интерфейса SortedMap, который расширяет интерфейс Map в Java. TreeMap хранит пары ключ-значение, отсортированные по ключам, что обеспечивается структурой данных под названием красно-черное дерево.

Красно-черное дерево – это усовершенствованная версия бинарного дерева поиска, с дополнительным атрибутом – "цвет" (красный/черный). Это означает, что поиск, вставка и удаление элементов выполняются за время O(log(n)), где n - количество элементов в дереве.

Требования красно-черного дерева:

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

Понимаем красно-черное дерево. Часть 1. Введение

Часть 1. ВведениеЧасть 2. Балансировка и вставкаДовольно долгое время я воевал с красно-черным деревом (далее - кчд). Вся информация, которую я находил, была в духе &quot;листья и корень дерева всегда...

HabrНикита

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 читайте в отдельной статье 👇

Глубокое погружение в Stream API Java: Понимание и Применение

В этой статье мы погрузимся в мир Stream API, узнаем, что это такое и как этим пользоваться, разберем реальные примеры и советы по лучшим практикам.

struchkov.devStruchkov Mark

Лучшие практики

Использование 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. Продолжайте изучение, экспериментируйте и становитесь лучше!