Java Collections

В Java для упрощения работы с большими объемами динамических данных были созданы collections. К основным реализациям относят List, Set и Queue. Начнем разбираться что для чего нужно и как их применять.


List, Set и Queue расширяют интерфейс Collection, который в свою очередь расширяет интерфейс Iterable. Это основные, но не все реализации Collection. Их на самом тебе гораздо больше. 

Для справки: 

Классы наследующие Collection - AbstractCollection, AbstractList, AbstractQueue, AbstractSequentialList, AbstractSet, ArrayBlockingQueue, ArrayDeque, ArrayList, AttributeList, BeanContextServicesSupport, BeanContextSupport, ConcurrentLinkedDeque, ConcurrentLinkedQueue, ConcurrentSkipListSet, CopyOnWriteArrayList, CopyOnWriteArraySet, DelayQueue,EnumSet, HashSet, JobStateReasons, LinkedBlockingDeque, LinkedBlockingQueue, LinkedHashSet, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, RoleList, RoleUnresolvedList, Stack, SynchronousQueue, TreeSet, Vector.

Давайте рассмотрим, зачем нужен каждый. 

List - Представляет собой неупорядоченную коллекцию, в которой допустимы дублирующие значения. Иногда их называют последовательностями. Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу.

Set - описывает неупорядоченную коллекцию, не содержащую повторяющихся элементов. Это соответствует математическому понятию множества (set). 

Queue - это коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки. В дополнение к базовым операциям интерфейса Collection, очередь предоставляет дополнительные операции вставки, получения и контроля.

Теперь перейдем к более детальной реализации каждой коллекции, рассмотрим только основные, наиболее распространенные реализации: 

List

ArrayList - пожалуй самая часто используемая коллекция. ArrayList инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов. Так как ArrayList использует массив, то время доступа к элементу по индексу минимально (В отличии от LinkedList). При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево, при этом реальный размер массива (его емкость, capacity) не изменяется. Если при добавлении элемента, оказывается, что массив полностью заполнен, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент.

LinkedList - двусвязный список. Это структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и две ссылки на следующий и предыдущий узел списка. Доступ к произвольному элементу осуществляется за линейное время (но доступ к первому и последнему элементу списка всегда осуществляется за константное время — ссылки постоянно хранятся на первый и последний). В целом же, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций.

Set

HashSet - коллекция, не позволяющая хранить одинаковые объекты(как и любой Set), инкапсулирует в себе объект HashMap (то-есть использует для хранения хэш-таблицу). Выгода от хеширования состоит в том, что оно обеспечивает константное время выполнения методов add(), contains(),remove() и size() , даже для больших наборов. Если Вы хотите использовать HashSet для хранения объектов своих классов, необходимо переопределить методы hashCode() и equals(), иначе два логически-одинаковых объекта будут считаться разными, так как при добавлении элемента в коллекцию будет вызываться метод hashCode() класса Object (который вернет разный хэш-код для ваших объектов). Важно отметить, что класс HashSet не гарантирует упорядоченности элементов, поскольку процесс хеширования сам по себе обычно не порождает сортированных наборов. 

Если вам нужны сортированные наборы, то лучшим выбором может быть другой тип коллекций, такой как класс TreeSet. 

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

TreeSet - коллекция, которая хранит свои элементы в виде упорядоченного по значениям дерева. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов. TreeSet хорош тем, что для операций add, remove и contains потребуется гарантированное время log(n). 

Queue 

PriorityQueue - это очередь с упорядочиванием элементов либо по их натуральному порядку (используя интерфейс Comparable), либо с помощью интерфейса Comparator, полученному в конструкторе. 

Устаревшие коллекции, их использование не рекомендуется, но не запрещается: 

1. Enumeration — аналог интерфейса Iterator. 

2. Vector — аналог класса ArrayList; поддерживает упорядоченный список элементов, хранимых во "внутреннем" массиве. 

3. Stack — класс, производный от Vector, в который добавлены методы вталкивания (push) и выталкивания (pop) элементов, так что список может трактоваться в терминах, принятых для описания структуры данных стека (stack). 

4. Dictionary — аналог интерфейса Map, хотя представляет собой абстрактный класс, а не интерфейс. 

5. Hashtable — аналог HashMap. Все методы Hashtable, Stack, Vector являются синхронизированными, что делает их менее эффективными в одно поточных приложениях. 

Так же многие говоря о Collection некоторые подразумевают, что и Map тоже реализует данный интерфейс. Но на самом деле это не так. Map сам является интерфейсов верхнего уровня. Тем самым Map не является Collection.

Выводы:
1. ArrayList - если необходимо хранить большое количество элементов с постоянным чтением и добавлением повторяющихся элементов.
2. LinkedList - если чтение и добавление происходят в основном в начале или конце списка.
3. Set - для хранения не повторяющихся элементов.