Java Collection Framework - part 1

Огромное количество классов для работы с колекциями в Java, может пугать. Но за ними кроются конкретные реализации алгоритмов, применение которых сделают ваши програмы более читабельными, быстрими и стабильными. Ниже представлена краткая и агрегированая информация по интерфейсах и классах. Выбрав нужный не забудте посмотреть подробности в Java API.

Интерфейсы:

• Collection: - описывает группу объектов (элементов). Определяет методы для получения итератора, добавления, удаления элементов, проверки на вхождение элемента в даную колекцию, преобразования колекции к масиву.
  При помощи утилитного класса java.util.Collections вы можете произвести такие действия над вашей колекцией:
  • synchronizedCollection - синхронизирует все методы (реализуя паттерн Decorator)
  • unmodifiableCollection - возвращает колекцию при попытке модификации которой будет брошено исключение UnsupportedOperationException(реализация - паттерн Decorator)
  • checkedCollection - возвращает колекцию гарантированно содержащую заданый тип. При попытке вставить елемент другого типа будет брошено исключение ClassCastException(реализация - паттерн Decorator)
  также он предоставляет методы для добавления нескольких елементов к колекции, например так: Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon"); проверки содержат ли колекции не одинаковые елементы disjoint, подсчет числа вхождения данного елемента в колекцию frequency, Нахождение max и min елемента колекции (сложность O(n)).
• 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) (не считая затраты на блокирову)