понедельник, 2 апреля 2012 г.

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) (не считая затраты на блокирову)

2 комментария:

Анонимный комментирует...

Коротко и ясно. Спасибо. Ждем статью про Мапы

Анонимный комментирует...

Большое спасибо!