ArrayList
Поддерживает динамические массивы.
По мере добавления элементов в список, емкость внутреннего массива автоматически увеличивается.
- Использует под капотом обычный массив
- Быстрый доступ к элементам по индексу за константное время O(1)
- Быстрая вставка и удаление элементов с конца за константное время O(1)
- Доступ к элементам по значению за линейное время O(n)
- Медленная вставка и удаление элементов из середины
- Хранит любые значения в том числе и null
- Не синхронизирован
- Автоматически увеличивается, но не уменьшается
LinkedList
Использует для хранения двусвязный список.
Поэтому Итератор поддерживает обход в обе стороны.
Помимо интерфейса List реализует интерфейсы Dequeue и Queue.
Соединяет функциональность работы со списком и функциональность очереди.
- Каждый элемент содержит ссылки на предыдущий и следующий элементы
- Позволяет хранить повторяющиеся объекты, в том числе null
- Быстрая вставка и удаление первого, последнего и элемента из середины списка за константное время O(1)
- Долгое время поиска позиции элемента за линейное время O(n)
- Операции поиска элемента по значению выполняются за линейное время O(n)
- Не синхронизирован
Используется когда необходимо часто добавлять или удалять элементы, особенно в начало списка. Либо когда нужна вставка элемента в конец за гарантированное время.
Queue
Интерфейс Queue расширяет Collection.
Определяет поведение класса в качестве однонаправленной очереди.
Работает по принципу first-in-first-out (FIFO).
Не может хранить значение null.
PriorityQueue
Класс PriorityQueue – очередь с приоритетами.
По умолчанию размещает элементы согласно естественному порядку сортировки используя Comparable: элементу с наименьшим значением присваивается наибольший приоритет.
- Не хранит значение null
- Не хранит non-comparable объекты
- Не потокобезопасен
- Можно указать порядок размещения, используя Comparator.
Set
Множество однотипных элементов.
Добавляет ограничение, которое запрещает повторяющиеся элементы.
- Хранит только уникальные элементы
- Уникальность определяется за счет контракта hashcode() equals()
- Нет индексов
HashSet
- Основан на хэш таблице
- Элементы не упорядочены, порядок элементов может меняться
- Операции add(), remove(), contains() и size() за константное время O(1)
- Под капотом HashMap с заглушками значений
Не имеет собственной реализации – под капотом использует HashMap.
В качестве значения value HashMap используется заглушка.
Значения HashSet – это ключи внутренней HashMap.
LinkedHashSet
LinkedHashSet поддерживает связанный список элементов множества, в том порядке, в котором они были добавлены.
Это позволяет выполнять упорядоченную итерацию по множеству.
- Элементы в порядке добавления
- За счет этой особенности - работает дольше чем HashSet
TreeSet
Класс TreeSet реализует интерфейс NavigableSet, который поддерживает элементы в отсортированном по возрастанию порядке.
- Элементы хранятся в отсортированном порядке по возрастанию
- Под капотом использует TreeMap
- Для хранения объектов использует бинарное красно-черное дерево
- Сортировка происходит благодаря тому, что все добавляемые элементы реализуют интерфейсы Comparator и Comparable
- Временная сложность базовых операций add(), remove(), contains() медленнее, чем в хэш-множествах, но быстрее, чем в списках: O(log(n))
Если TreeSet пустой – можно положить единственное значение null
При этом все операции кроме size() и clear() перестанут работать.
В непустой TreeSet положить null уже нельзя из-за вызова compareTo().
HashMap
HashMap использует хэш - таблицу, в которой ключи отсортированы относительно значений их хэш-кодов.
Bucket – это элемент (ячейка) внутреннего массива HashMap.
В нем хранятся узлы Nodes.
- Хранит значения в произвольном порядке
- Структура хранения данных: bucket (корзина)
- Ключ и значение могут быть null
- Объекты с null ключами всегда записываются в нулевую ячейку массива.
Время поиска элемента в наихудшем случае с O(n) до O(log(n)) во время коллизий. Cохранение и извлечение элементов из HashMap занимает постоянное время O(1).
TreeMap
Структура хранения данных красно-черное сбалансированное дерево.
По-умолчанию TreeMap сортируется по ключам с использованием принципа натуральной сортировки, но это поведение может быть настроено под конкретную задачу при помощи объекта класса Comparator.
- Красно-черное сбалансированное дерево
- Все элементы отсортированы в порядке возрастания ключа
- Порядок сортировки может быть задан Comparator и Comparable