Что такое Java Collection Framework?

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

Однако суть не только в гибких по размеру наборах элементов, но в и том, что классы коллекций реализуют различные алгоритмы и структуры данных, такие как множество, очередь, дерево и ряд других.

Все коллекции образуют стройную и логичную структуру. В основе любой колеекции лежит использование того или иного интерфейса, который определяет ее базовый функционал.

Иерархия коллекций

Примерно так выглядит основная иерархия коллекций. Мы по порядку, сверху вниз, разберем каждый класс, и каждый интерфейс.

Интерфейс 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, иначе - false
• E 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) – добавляет в коллекцию все объекты из отображения map
• V 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.

Как и обычный массив он содержит элементы, к которым можно получить доступ по целочисленному индексу. Если зайти в реализацию этого класса, то можно увидеть, что он сохраняет элементы в обычный массив и управляет его расширением.

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

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

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

В целом так и есть, но при добавлении элементов в 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-ух черных потомков
• Пути от узла к его листьям должны содержать одинаковое количество черных узлов

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

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

HabrНикита

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 разработчика. И теперь вы знаете о них основную информацию. Рекомендую потренировать и пописать программы с использованием коллекций.

Удачи 🤞