Интерфейсы:
-
Collection: - описывает группу объектов (элементов). Определяет методы для получения итератора, добавления, удаления элементов, проверки на вхождение элемента в даную колекцию, преобразования колекции к масиву.
При помощи утилитного класса java.util.Collections вы можете произвести такие действия над вашей колекцией:- synchronizedCollection - синхронизирует все методы (реализуя паттерн Decorator)
- unmodifiableCollection - возвращает колекцию при попытке модификации которой будет брошено исключение UnsupportedOperationException(реализация - паттерн Decorator)
- checkedCollection - возвращает колекцию гарантированно содержащую заданый тип. При попытке вставить елемент другого типа будет брошено исключение ClassCastException(реализация - паттерн Decorator)
- List: - список - упорядоченная последовательность объектов.
Елементы упорядоченны - имеют свои индексы. Интерфейс описывает методы для добавления, замещения, удаления елементов по индексу. Также методы для получения индекса елемента и ListIterator - который кроме елементов может возвращать их индексы. Класс java.util.Collections кроме операций аналогичных операциям с колекцией описывает также операции:
Поиска и сортировки- sort - стабильная сортировка модифицированым методом mergesort, сложность O(n log(n)))
- binarySearch - поиск елемента в отсортированой колекции. Сложность для RandomAcсess листов O(log n), иначе O(n)
- copy - копирует все елементы в доругой список
- fill - заполняет лист одним и тем же елементом
- indexOfSubList, lastIndexOfSubList - возвращает первый (последний) индекс вхождения одного списка в другой, или же -1, Использует "brute force" стратегию :)
- shuffle - рандомно перемешывает список, сложность O(n)
- swap - меняет два елемента списка местами
- reverse - разворачивает список, сложность O(n)
- rotate - сдвигает елементы списка, сложность O(n)
-
Queue: - очередь в которой елементы выстроены по принципу FIFO (first-in-first-out).
Определяет методы добавления в конец очереди и извлечения первого елемента из очереди(offer(e), poll()). Также есть метод peek() - получить первый елемент в очереди без его удаления.
Класс java.util.Collections определяет операции аналогичные операциям с колекциями. -
Deque: - двунаправленная очередь, добавлять и извлекать елементы которой можно как с конца, так и сначала. Используется для реализации стратегий как LIFO(Stack), так и FIFO.
Кроме методов Queue определяет методы для работы со стеком: push(e), pop() - добавление в начало и извлечение первого елемента, peek() - возвратит первый елемент без его удаления. Также есть метод для получения обратного итератора: descendingIterator()
Вы можете преобразовать Deque в Queue при помощи java.util.Collections (реализация - паттерн Decorator). -
BlockingQueue: - блокирующая очередь для передачи данных между потоками.
Читающий поток будет остановлен пока не появится хотя бы одна запись в очереди. Пишущий поток будет остановлен если превышен предел елементов в очереди. если же елементов станет меньше он продолжит свою работу.
remainingCapacity - возвращает число свободных слотов Существует 4 набора методов для вставки и получения елементов:- add(e), element(), remove() - добавить, достать, удалить, при запрете операции в данный момент (отсутствии елементов, или заполнености очереди) бросается исключение IllegalStateException
- offer(e), poll() - добавить/извлечть елемент, без блокировки потока, при запрете операции будет возвращен результат false или null
- offer(e, time, unit), poll(time, unit) - добавить/извлечь елемент, c блокировкой не дольше заданого интервала
- put(e), take() - добавить/извлечть елемент c блокировкой потока до выполнения операции
- drainTo(Collection) - извлечь все елементы из очереди и поместить в колекцию
-
BlockingDeque: - блокирующая двунаправленная очередь, для передачи данных между потоками.
Аналогична BlockingQueue но позволяет добавлять и извлекать елементы с обоих концов.
Методы имеют приставки к именам First - означает начало и Last - хвост очереди.
Также есть методы removeFirstOccurrence(e)/removeLastOccurrence(e) - удаляющие первое или последнее вхождение данного елемента.
Классы:
-
ArrayList: - представляет масив длинна которого меняется автоматически (динамический масив)
Сойства:- методы не синхронизированы (нельзя использовать в нескольких потоках)
- сложность операций size, isEmpty, get, set, iterator, listIterator, add - O(1)
- add - работает медленнее чем в LinkedList
- Если был получен iterator или listIterator, а затем была изменена структура списка, будет брошен ConcurrentModificationException. Но это поведение не гарантируется при изменении структуры несколькими потоками
-
Vector: - представляет масив длинну которого можно увеличивать
Сойства:- методы синхронизированы (безопасно использовать в нескольких потоках, но меньшая производительность при работе с одним)
- setSize - устанавливает новый размер масива
- add(int index,E element) добавляет елемент в определенную позицию, или же бросает ArrayIndexOutOfBoundsException
- Не рекомендуется завязывать логику программы на ConcurrentModificationException, несмотря на синхронизированость методов. Это исключение призвано только для выявления багов
-
Stack: - представляет старую реализацию стекаLIFO
Сойства:- К методам Vector добавляет push(e), pop()
- методы синхронизированы
- Более согласованую абстракцию LIFO представляет интерфейс Deque и его реализация ArrayDeque
-
CopyOnWriteArrayList: - потоко-безопасный вариант ArrayList
Сойства:- Все операции изменяющие структуру применяются к новой копии существующего масива данных. Для быстрого копирования используется нейтивные системные функции. Тоесть если один поток хочет читать масив - он получает снимок текущего масива и дальше читает его (возможно устаревшие данные), а другой в это время, может без боязненно его изменять.
- Операции связанные с изменением структуры синхронизированны. Тоесть в любой момент временни только один поток может изменять структуру
- Операции связанные с чтением не блокируют запись
- Вы не сможете изменять структуру данного листа через итератор (так как итератор работает с более старым снимком данных). Операции итератора remove, set, add будут бросать UnsupportedOperationException
-
LinkedList: - Связаный список (двусвязный список)
Сойства:- Методы не синхронизированы (нельзя использовать в нескольких потоках)
- Сложность операций get, isEmpty, remove, insert - в конец и начало списка одинакова (O(1))
- Сложность операций get(index) - O(n)
- Если был получен iterator или listIterator, а затем была изменена структура списка, будет брошен ConcurrentModificationException. Но это поведение не гарантируется при изменении структуры несколькими потоками
-
PriorityQueue: - бесконечная очередь на базе структуры heap
Сойства:- Методы не синхронизированы (нельзя использовать в нескольких потоках), многопоточная реализация PriorityBlockingQueue
- Сложность операций получения елемнетовpeek, element, size - O(1)
- Сложность операций вставки и извлеченияoffer, poll, remove(), add - O(log(n)
- Сложность операций доступа к конкретному елементу remove(Object), contains(Object) - O(n)
- iterator() - обходит очередь в произвольном порядке
- Для обхода кучи в порядке убывания/возростания елементов используйте конструкцию Arrays.sort(pq.toArray()) - сложность O(n*log(n))
-
ConcurrentLinkedQueue: - бесконечная очередь потокобезопасная очередь
Элементы хранятся в отдельных объектах (нодах), которые связываются посредством ссылок. Изменения структуры отслеживаются через AtomicReferenceFieldUpdater класс. Сойства:- Методы не синхронизированы, но структура этой очереди позволяет множеству потоков работать с одной и той же очередью безопасно
- Сложность операции size - O(n)!
-
ArrayDeque: - реализация двусвязной очереди на базе динамического масива
Сойства:- Методы не синхронизированы (нельзя использовать в нескольких потоках)
- Сложность операций добавления и извлечения елементов в оба конца очереди - O(1)
- Сложность операций для работы с конкретным елементом remove(Object), contains, iterator.remove() - O(n)
- Если был получен iterator или descendingIterator, а затем была изменена структура очереди, будет брошен ConcurrentModificationException. Но это поведение не гарантируется при изменении структуры несколькими потоками
-
ArrayBlockingQueue: - блокирующая очередь на базе масива постоянной длинны
Описывает класический буффер ограниченой длинны для обмена данными между потоками.
Сойства:- После создания нельзя изменить размер буффера
-
LinkedBlockingQueue: - Блокирующая очередь на базе связаного списка
Элементы хранятся в отдельных объектах (нодах), которые связываются посредством ссылок. Описывает буффер произвольной длинны для обмена данными между потоками. Сойства:- При создании можно задать размер буфера, по умолчанию он неограничен. После создания изменять размер буффера нельзя
- Очередь не ограничена, но можно нарватся на OutOfMemoryError
- Сложность добавления, извлечения елементов O(1) (не считая затраты на блокирову)
- Сложность изменения, получения конкретного елемента O(n) (не считая затраты на блокирову)
-
PriorityBlockingQueue: - блокирующай вариант PriorityQueue
Сойства:- При создании можно задать размер буфера, по умолчанию он неограничен. После создания изменять размер буффера нельзя
- Очередь не ограничена, но можно нарватся на OutOfMemoryError
-
SynchronousQueue: - блокирующая очередь, для синхронизации двух потоков.
Аналог ArrayBlockingQueue с размером буфера 1. -
DelayQueue: - неограниченая очередь, елементы которой стают доступны другому потоку только по истечении заданого времени.
Сойства:- Каждому елементу задается свое время после которого он станет доступен, для чтения в очереди
- size() - возвращает общее число как доступных так и не доступных елементов
- Очередь не ограничена, но можно нарватся на OutOfMemoryError
-
LinkedBlockingDeque: - Блокирующая двунаправленная очередь на базе связаного списка
Элементы хранятся в отдельных объектах (нодах), которые связываются посредством ссылок. Описывает буффер произвольной длинны для обмена данными между потоками. Сойства:- При создании можно задать размер буфера, по умолчанию он неограничен. После создания изменять размер буффера нельзя
- Очередь не ограничена, но можно нарватся на OutOfMemoryError
- Сложность добавления, извлечения елементов с обоих концов очереди O(1) (не считая затраты на блокирову)
- Сложность изменения, получения конкретного елемента (remove(Object), contains(Object), iterator.remove()) O(n) (не считая затраты на блокирову)
