Стандартные реализации

List Implementations

LinkedList

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

Благодаря этому, добавление и удаление из середины, доступ по индексу, значению происходит за линейное время O(n), а из начала и конца за константное O(1).

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

ArrayList

Является реализацией динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Как можно догадаться из названия, его реализация основана на обычном массиве.

Данную реализацию следует применять, если в процессе работы с коллекцией предплагается частое обращение к элементам по индексу. Из-за особенностей реализации поиндексное обращение к элементам выполняется за константное время O(1).

Но данную коллекцию рекомендуется избегать, если требуется частое удаление/добавление элементов в середину коллекции.

Vector

Реализация динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента.

В Vector, в отличии от других реализаций List, все операции с данными являются синхронизированными. В качестве альтернативы часто применяется аналог — ArrayList. (Синхронизированный динамический массив)

Stack

Является частично синхронизированной коллекцией (кроме метода добавления push()).

После добавления в Java 1.6 интерфейса Deque, рекомендуется использовать именно реализации этого интерфейса, например ArrayDeque.

CopyOnWriteArrayList

Все операции по изменению коллекции (add, set, remove) приводят к созданию новой копии внутреннего массива. Тем самым гарантируется, что при проходе итератором по коллекции не кинется ConcurrentModificationException.

Следует помнить, что при копировании массива копируются только референсы (ссылки) на объекты (shallow copy), т.ч. доступ к полям элементов не thread-safe.

CopyOnWrite коллекции удобно использовать, когда write операции довольно редки, например при реализации механизма подписки listeners и прохода по ним.

Set Implementations

HashSet

Реализация интерфейса Set, базирующаяся на HashMap. Внутри использует объект HashMap для хранения данных.

В качестве ключа используется добавляемый элемент, а в качестве значения — объект-пустышка (new Object()). Из-за особенностей реализации порядок элементов не гарантируется при добавлении.

LinkedHashSet

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

TreeSet

Аналогично другим классам-реализациям интерфейса Set содержит в себе объект NavigableMap, что и обуславливает его поведение. TreeSet is a NavigableSet implementation backed by TreeMap instance.

Предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием “natural ordering”.

CopyOnWriteArraySet

Имплементация интерфейса Set, использующая за основу CopyOnWriteArrayList. В отличии от CopyOnWriteArrayList, дополнительных методов нет.

ConcurrentSkipListSet

Имплементация Set интерфейса, выполненная на основе ConcurrentSkipListMap.

Queue Implementations

PriorityQueue

Особенностью данной очереди является возможность управления порядком элементов. По-умолчанию, элементы сортируются с использованием «natural ordering», но это поведение может быть переопределено при помощи объекта Comparator, который задаётся при создании очереди. Данная коллекция не поддерживает null в качестве элементов.

Приоритетная очередь реализована на АТД - Двоичная куча.

ConcurrentLinkedQueue

В имплементации используется wait-free алгоритм от Michael & Scott, адаптированный для работы с garbage collector’ом. Этот алгоритм довольно эффективен и, что самое важное, очень быстр, т.к. построен на CAS.

Метод size() может работать долго, т.ч. лучше постоянно его не дергать.

ArrayBlockingQueue

Класс блокирующей очереди, построенный на классическом кольцевом буфере.

Помимо размера очереди, доступна возможность управлять «честностью» блокировок. Если fair=false (по умолчанию), то очередность работы потоков не гарантируется. Более подробно о «честности» можно посмотреть в описании ReentrantLock’a.

DelayQueue

Неограниченная очередь блокирования элементов DelayQueue реализует интерфейс Delayed и позволяет извлекать элемент с некоторой временно́й задержкой. Если задержка не истекла, то метод poll вернет null. Очередь не разрешает запись нулевых элементов. Метод класса getDelay(TimeUnit.NANOSECONDS) вернет значение меньше или равное нулю, если время еще не истекло.

Метод size возвращает общее количество элементов с истекшим и неистекшим временем задержки.

LinkedBlockingQueue

Блокирующая очередь на связанных нодах, реализованная на «two lock queue» алгоритме: один лок на добавление, другой на вытаскивание элемента. За счет двух локов, по сравнению с ArrayBlockingQueue, данный класс показывает более высокую производительность, но и расход памяти у него выше.

Размер очереди задается через конструктор и по умолчанию равен Integer.MAX_VALUE.

PriorityBlockingQueue

Является многопоточной оберткой над PriorityQueue. При вставлении элемента в очередь, его порядок определяется в соответствии с логикой Comparator’а или имплементации Comparable интерфейса у элементов. Первым из очереди выходит самый наименьший элемент.

SynchronousQueue

Эта очередь работает по принципу один вошел, один вышел.

Каждая операция вставки блокирует «Producer» поток до тех пор, пока «Consumer» поток не вытащит элемент из очереди и наоборот, «Consumer» будет ждать пока «Producer» не вставит элемент.

fair = true - ожидающие потоки выстраиваются в честную очередь. fair = false - ожидающие потоки выстраиваются в стек

LinkedTransferQueue

Реализация TransferQueue на основе алгоритма Dual Queues with Slack. Активно использует CAS и парковку потоков, когда они находятся в режиме ожидания.

LinkedBlockingDeque

Двунаправленная блокирующая очередь на связанных нодах, реализованная как простой двунаправленный список с одним локом.

Размер очереди задается через конструктор и по умолчанию равен Integer.MAX_VALUE.

ArrayDeque

Эта коллекция представляет собой реализацию с использованием массивов (Реализация на динамическом циклическом массиве), подобно ArrayList, но не позволяет обращаться к элементам по индексу и хранение null.

Как заявлено в документации, коллекция работает быстрее чем Stack, если используется как LIFO коллекция, а также быстрее чем LinkedList, если используется как FIFO.

Grow: Double capacity if small; else grow by 50%

ConcurrentLinkedDeque

Не блокирующая двусторонняя очередь, сравнительно схожа с реализацией ConcurrentLinkedQueue.

На практике, ConcurrentLinkedDeque стоит использовать только, если обязательно нужно LIFO, т.к. за счет двунаправленности нод данный класс проигрывает по производительности на 40% по сравнению с ConcurrentLinkedQueue.

Map Implementations

Hashtable

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

Эта коллекция была реализована раньше, чем Java Collection Framework, но в последствии была включена в его состав.

Как и другие коллекции из Java 1.0, Hashtable является синхронизированной (почти все методы помечены как synchronized). Из-за этой особенности у неё имеются существенные проблемы с производительностью и, начиная с Java 1.2, в большинстве случаев рекомендуется использовать другие реализации интерфейса Map ввиду отсутствия у них синхронизации.

HashMap

Коллекция является альтернативой Hashtable. Двумя основными отличиями от Hashtable являются то, что HashMap не синхронизирована и HashMap позволяет использовать null как в качестве ключа, так и значения.

Так же как и Hashtable, данная коллекция не является упорядоченной: порядок хранения элементов зависит от хэш-функции. Добавление элемента выполняется за константное время O(1), но время удаления, получения зависит от распределения хэш-функции. В идеале является константным, но может быть и линейным O(n).

Ссылки:

Страница в википедии

LinkedHashMap

Упорядоченная реализация хэш-таблицы. Здесь, в отличии от HashMap, порядок итерирования равен порядку добавления элементов. Данная особенность достигается благодаря двунаправленным связям между элементами (аналогично LinkedList). Но это преимущество имеет также и недостаток — увеличение памяти, которое занимет коллекция.

WeakHashMap

Реализация хэш-таблицы, которая организована с использованием weak references. Другими словами, Garbage Collector автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элеметна нет жёстких ссылок.

IdentityHashMap

Отличие от HashMap состоит в том, что при сравнении элементов используется сравнение ссылок, а не значений.

TreeMap

Реализация Map основанная на красно-чёрных деревьях. Как и LinkedHashMap является упорядоченной. По-умолчанию, коллекция сортируется по ключам с использованием принципа “natural ordering”, но это поведение может быть настроено под конкретную задачу при помощи объекта Comparator, которые указывается в качестве параметра при создании объекта TreeMap.

EnumMap

A specialized Map implementation for use with enum type keys. Enum maps are represented internally as arrays. This representation is extremely compact and efficient.

Enum maps are maintained in the natural order of their keys (the order in which the enum constants are declared).

ConcurrentSkipListMap

Данные сортируются по ключу и гарантируется усредненная производительность log(N) для containsKey, get, put, remove и других похожих операций. Алгоритм работы основан на SkipList

ConcurrentHashMap

В отличие от Hashtable и блоков synhronized на HashMap, данные представлены в виде сегментов, разбитых по hash’ам ключей. В результате, для доступ к данным лочится по сегментам, а не по одному объекту.

В дополнение, итераторы представляют данные на определенный срез времени и не кидают ConcurrentModificationException.

concurrencyLevel — ожидаемое количество одновременно пишущих потоков. Значение по умолчанию 16. Влияет на размер коллекции в памяти и производительность.