Java Collections

Коллекциями/контейнерами в Java принято называть классы, основная цель которых – хранить набор других элементов.

Коллекции могут хранить любые ссылочные типы данных.

List — это упорядоченный список. Объекты хранятся в порядке их добавления в список. Доступ к элементам списка осуществляется по индексу.

Set — множество неповторяющихся объектов. В коллекции этого типа разрешено наличие только одной ссылки типа null.

Queue — коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки. В дополнение к базовым операциям интерфейса Collection, очередь предоставляет дополнительные операции вставки, получения и контроля.
Очереди обычно, но не обязательно, упорядочивают элементы в FIFO (first-in-first-out, «первым вошел — первым вышел») порядке.
Метод offer() вставляет элемент в очередь, если это не удалось — возвращает false. Этот метод отличается от метода add() интерфейса Collection тем, что метод add() может неудачно добавить элемент только с использованием unchecked исключения.
Методы remove() и poll() удаляют верхушку очереди и возвращают ее. Какой элемент будет удален (первый или последний) зависит от реализации очереди.
Методы remove() и poll() отличаются лишь поведением, когда очередь пустая: метод remove() генерирует исключение, а метод poll() возвращает null.
Методы element() и peek() возвращают (но не удаляют) верхушку очереди.
java.util.Queue реализует FIFO–буфер. Позволяет добавлять и получать объекты. При этом объекты могут быть получены в том порядке, в котором они были добавлены. Реализации: java.util.ArrayDeque, java.util.LinkedList.
java.util.Deque наследует java.util.Queue. Двунаправленная очередь. Позволяет добавлять и удалять объекты с двух концов. Так же может быть использован в качестве стека.
Реализации: java.util.ArrayDeque, java.util.LinkedList.

Интерфейс java.util.Map используется для отображения каждого элемента из одного множества объектов (ключей) на другое (значений). При этом, каждому элементу из множества ключей ставится в соответствие множество значений. В то же время одному элементу из множества значений может соответствовать 1, 2 и более элементов из множества ключей. Интерфейс java.util.Mapописывает функциональность ассоциативных массивов.
Реализации: java.util.HashMap, java.util.LinkedHashMap, java.util.TreeMap, java.util.WeakHashMap.
java.util.SortedMap наследует java.util.Map. Реализации этого интерфейса обеспечивают хранение элементов множества ключей в порядке возрастания (см. java.util.SortedSet). Реализации: java.util.TreeMap.

ArrayList реализован внутри в виде обычного массива. Поэтому при вставке элемента в середину, приходится сначала сдвигать на один все элементы после него, а уже затем в освободившееся место вставлять новый элемент. Зато в нем быстро реализованы взятие и изменение элемента – операции get, set, так как в них мы просто обращаемся к соответствующему элементу массива.

LinkedList реализован внутри по-другому. Он реализован в виде связного списка: набора отдельных элементов, каждый из которых хранит ссылку на следующий и предыдущий элементы. Чтобы вставить элемент в середину такого списка, достаточно поменять ссылки его будущих соседей. А вот чтобы получить элемент с номером 130, нужно пройтись последовательно по всем объектам от 0 до 130.Другими словами операции set и get тут реализованы очень медленно.

Если необходимо вставлять (или удалять) в середину коллекции много элементов, то лучше использовать LinkedList. Во всех остальных случаях – ArrayList.

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

Название Hash… происходит от понятия хэш-функция. Хэш-функция — это функция, сужающая множество значений объекта до некоторого подмножества целых чисел.
Класс Object имеет метод hashCode(), который используется классом HashSet для эффективного размещения объектов, заносимых в коллекцию. В классах объектов, заносимых в HashSet, этот метод должен быть переопределен (override).
HashSet реализован на основе хеш-таблицы, а TreeSet — на основе бинарного дерева.
HashSet гораздо быстрее чем TreeSet (константное время против логарифмического для большинства операций, таких как add, remove, contains), но TreeSet гарантирует упорядоченность объектов. Оба не синхронизированы.

HashSet
• предоставляет константное время для add(), remove(), contains() и size()
• порядок элементов в контейнере может меняться
• производительность итерации по контейнеру зависит от емкости и «коэффициента загрузки» (рекомендуется оставлять load factor значением по умолчанию равным 0.75, что является хорошим компромиссом между временем доступа и объемом хранимых данных)

TreeSet
• время для базовых операций add(), remove(), contains() — log(n)
• гарантирует порядок элементов
• не предоставляет каких-либо параметров для настройки производительности
• предоставляет дополнительные методы для упорядоченного списка: first(), last(), headSet(), tailSet() и т.д.

• TreeMap реализован на красно-черном дереве, время добавления/поиска/удаления элемента — O(log N), где N — число элементов в TreeMap на данный момент.
• У HashMap время доступа к отдельному элементу — O(1) при условии, что хэш-функция (Object.hashCode()) определена нормально (что является правдой в случае Integer).
• Общая рекомендация — если не нужна упорядоченность, использовать HashMap. Исключение — ситуация с вещественными числами, которые в качестве ключей почти всегда очень плохи. Для них нужно использовать TreeMap, предварительно поставив ему компаратор, который сравнивает вещественные числа так, как это нужно в данной задаче. Например, для обычных геометрических задач два вещественных числа могут считаться равными, если отличаются не более, чем на 1e-9.