Каркас коллекций Java представляет собой набор классов и интерфейсов , реализующих часто используемые структуры данных коллекций . [1]
Хотя он и называется фреймворком , он работает в стиле библиотеки . Фреймворк коллекций предоставляет как интерфейсы, определяющие различные коллекции, так и классы, которые их реализуют.
Collections и массивы похожи тем, что оба содержат ссылки на объекты и ими можно управлять как группой. Однако, в отличие от массивов, Collections не нужно назначать определенную емкость при создании экземпляра. Collections могут автоматически увеличиваться и уменьшаться в размере при добавлении или удалении объектов.
Collections не может содержать примитивные типы данных, такие как int, long, или double. [2] Вместо этого Collections может содержать классы-оболочки , такие как java.lang.Integer, java.lang.Long, или java.lang.Double. [3]
Collections являются универсальными и, следовательно, инвариантными, но массивы являются ковариантными . Это можно считать преимуществом универсальных объектов, например, Collectionпо сравнению с массивами, поскольку при определенных обстоятельствах использование универсального объекта Collectionвместо массива предотвращает исключения времени выполнения, вместо этого выдавая исключение времени компиляции, чтобы сообщить разработчику о необходимости исправить код. Например, если разработчик объявляет объект Object[]и присваивает Object[]объект значению, возвращаемому новым Long[]экземпляром с определенной емкостью, исключение времени компиляции не будет выдано. Если разработчик попытается добавить Stringк этому Long[]объекту, программа Java выдаст исключение ArrayStoreException. С другой стороны, если разработчик вместо этого объявил новый экземпляр как Collection<Object>, ArrayList<Long>компилятор Java (правильно) выдаст исключение времени компиляции, чтобы указать, что код написан с несовместимым и неправильным типом, тем самым предотвращая любые потенциальные исключения времени выполнения. Разработчик может исправить код, создав экземпляр Collection<Object>как ArrayList<Object>объект. Если код использует Java SE7 или более поздние версии, разработчик может создать экземпляр Collection<Object>как ArrayList<>объект, используя оператор diamond [2]
Collections являются общими и, следовательно, овеществленными , но массивы не овеществлены. [2]
CollectionРеализации в версиях платформы Java до JDK 1.2 включали несколько классов структур данных, но не содержали фреймворк коллекций. [4] Стандартные методы группировки объектов Java были через массив, Vectorи Hashtableклассы, которые, к сожалению, было нелегко расширить, и не реализовывали стандартный интерфейс членов. [5] [ требуется лучший источник ]
Для удовлетворения потребности в повторно используемых структурах данных коллекций было разработано несколько независимых фреймворков, [4] наиболее используемыми из которых являются пакет коллекций Дуга Ли [ 6] и библиотека ObjectSpace Generic Collection Library (JGL) [7], главной целью которой было соответствие стандартной библиотеке шаблонов C++ (STL). [8] [ требуется лучший источник ]
Фреймворк коллекций был спроектирован и разработан в первую очередь Джошуа Блохом и был представлен в JDK 1.2 . Он повторно использовал многие идеи и классы из пакета Collections Дуга Ли , который в результате был объявлен устаревшим. [6] Sun Microsystems решила не использовать идеи JGL, поскольку им нужен был компактный фреймворк, а согласованность с C++ не была одной из их целей. [9] [ требуется лучший источник ]
Позже Дуг Ли разработал пакет параллелизма , включающий новые классы, связанные с коллекциями. [10] Обновленная версия этих утилит параллелизма была включена в JDK 5.0 в JSR 166 .
Почти все коллекции в Java являются производными от java.util.Collectionинтерфейса. Collectionопределяет основные части всех коллекций.
Интерфейс имеет методы add(E e)и remove(E e)для добавления и удаления из a Collectionсоответственно. Он также имеет toArray()метод , который преобразует Collectionв массив Objects в Collection(с возвращаемым типом Object[]). [11] Наконец, contains(E e)метод проверяет, существует ли указанный элемент в Collection.
Интерфейс Collectionявляется подинтерфейсом java.lang.Iterable, поэтому любой Collectionможет быть целью оператора for-each . ( IterableИнтерфейс предоставляет iterator()метод, используемый операторами for-each.) Все Collections имеют , java.util.Iteratorкоторый проходит по всем элементам в Collection.
Collectionявляется универсальным. Any Collectionможет хранить любые Object. Например, любая реализация Collection<String>содержит объекты. При использовании объектов из реализации Stringне требуется приведение типов . [12] Обратите внимание, что угловые скобки могут содержать аргумент типа, который указывает, какой тип содержит . [13]StringCollection<String>< >Collection
Существует несколько общих типов Collection: очереди , карты , списки и наборы .
Очереди позволяют программисту вставлять элементы в определенном порядке и извлекать эти элементы в том же порядке. Примером является список ожидания. Базовые интерфейсы для очередей называются Queue.
Словари/карты хранят ссылки на объекты с ключом поиска для доступа к значениям объекта. Одним из примеров ключа является идентификационная карта. Базовый интерфейс для словарей/карт называется Map.
Списки — это конечные коллекции, в которых одно и то же значение может храниться несколько раз.
Наборы — это неупорядоченные коллекции, которые можно итерировать и которые содержат каждый элемент не более одного раза. Базовый интерфейс для наборов называется Set. [3]
Списки реализованы в фреймворке коллекций через java.util.Listинтерфейс. Он определяет список как по сути более гибкую версию массива. Элементы имеют определенный порядок, и допускаются дублирующие элементы. Элементы могут быть размещены в определенном положении. Их также можно искать в списке.
Существует несколько конкретных классов, реализующих List, включая AbstractListи все его соответствующие подклассы, а также CopyOnWriteArrayList.
Прямые подклассы AbstractListкласса включают AbstractSequentialList, ArrayListи Vector.
AbstractListявляется примером скелетной реализации , которая использует и объединяет преимущества интерфейсов и абстрактных классов, упрощая для разработчика разработку собственной реализации для данного интерфейса. [14]
Класс java.util.ArrayListреализует Listкак массив. Всякий раз, когда Listтребуются функции, специфичные для a, класс перемещает элементы внутри массива, чтобы сделать это.
Класс java.util.LinkedListхранит элементы в узлах, каждый из которых имеет указатель на предыдущий и следующий узлы в List. ListМожно перемещаться, следуя указателям, и элементы можно добавлять или удалять, просто меняя указатели, чтобы поместить узел в нужное место. [15]
Класс Vectorимеет Stackв качестве своего прямого подкласса. Это пример нарушения принципа композиции по наследованию в библиотеках платформы Java, поскольку в информатике вектор, как правило, не является стеком . [16] Композиция была бы более уместна в этом сценарии. [16]
extendsКласс Stack java.util.Vectorс пятью операциями, которые позволяют Vectorобрабатывать a как Stack. Стеки создаются с помощью java.util.Stack. StackПредлагает методы для помещения нового объекта в Stack(метод push(E e)) и для получения объектов из Stack(метод pop()). A Stackвозвращает объект в соответствии с принципом «последним пришел — первым ушел» (LIFO), например, объект, который был помещен последним в , Stackвозвращается первым. java.util.Stack— это стандартная реализация стека, предоставляемая Java.
Класс Stackпредставляет собой стек объектов типа «последний пришел — первый ушел» (LIFO). Класс Stack имеет пять дополнительных операций, которые позволяют Vectorобрабатывать a как Stack. Предоставляются обычные операции push(E e)и pop(), а также метод ( peek()) для просмотра верхнего элемента в Stack, метод для проверки того, Stackявляется ли , пустым ( empty()) и метод для поиска Stackэлемента и определения того, насколько он далек от вершины ( search(Object o)). Когда a Stackсоздается впервые, он не содержит элементов.
Расширяет CopyOnWriteArrayListкласс Objectи не расширяет никакие другие классы. CopyOnWriteArrayListобеспечивает потокобезопасность без выполнения чрезмерной синхронизации. [17]
В некоторых сценариях синхронизация обязательна. Например, если метод изменяет статическое поле, и метод должен вызываться несколькими потоками, то синхронизация обязательна, и утилиты параллелизма, такие как , CopyOnWriteArrayListне должны использоваться. [17]
Однако синхронизация может повлечь за собой накладные расходы производительности. Для сценариев, где синхронизация не является обязательной, то это CopyOnWriteArrayListжизнеспособная, потокобезопасная альтернатива синхронизации, которая использует многоядерные процессоры и приводит к более высокой загрузке ЦП . [17]
Интерфейс java.util.Queueопределяет структуру данных очереди, которая хранит элементы в порядке их вставки. Новые добавления идут в конец строки, а элементы удаляются с начала. Он создает систему «первым пришел — первым вышел» . Этот интерфейс реализуется java.util.LinkedList, java.util.ArrayDeque, и java.util.PriorityQueue.
Прямые подклассы AbstractQueueкласса включают ArrayBlockingQueue, ConcurrentLinkedQueue, DelayeQueue, LinkedBlockingDeque, LinkedBlockingQueue. LinkedTransferQueueи PriorityBlockingQueue.
Обратите внимание, что ArrayDequeи ConcurrentLinkedDequeоба расширяют AbstractCollection, но не расширяют какие-либо другие абстрактные классы, такие как AbstractQueue.
AbstractQueueявляется примером скелетной реализации .
Класс java.util.PriorityQueueреализует java.util.Queue, но также изменяет его. [18] PriorityQueue имеет дополнительный comparator()метод. [18] Вместо того, чтобы упорядочивать элементы в порядке их вставки, они упорядочиваются по приоритету. Метод, используемый для определения приоритета, — это либо метод java.lang.Comparable#compareTo(T)в элементах, либо метод, заданный в конструкторе. Класс создает его, используя кучу для сохранения сортировки элементов. [19]
Класс java.util.concurrent.ConcurrentLinkedQueueрасширяет . реализует интерфейс. [20]java.util.AbstractQueueConcurrentLinkedQueuejava.util.Queue
Класс ConcurrentLinkedQueueпредставляет собой потокобезопасную коллекцию, поскольку для любого элемента an, помещенного внутрь a ConcurrentLinkedQueue, библиотека коллекций Java гарантирует, что элемент будет безопасно опубликован , позволяя любому потоку получить элемент из коллекции. [21] Объект считается безопасно опубликованным , если состояние объекта становится видимым для всех других потоков в тот же момент времени. [21] Безопасная публикация обычно требует синхронизации публикующего и потребляющего потоков. [21]
Интерфейс java.util.concurrent.BlockingQueueрасширяется Queue. [20]
Интерфейс BlockingQueueимеет следующие прямые подинтерфейсы: BlockingDequeи TransferQueue. BlockingQueueработает как обычный Queue, но добавления в и удаления из BlockingQueueблокируются. [22] Если remove(Object o)вызывается для пустого BlockingQueue, его можно настроить на ожидание либо указанного времени, либо неопределенного времени для появления элемента в BlockingQueue. Аналогично, добавление элемента с помощью метода add(Object o)подлежит необязательному ограничению емкости на BlockingQueue, и метод может ждать, пока место станет доступным в , BlockingQueueпрежде чем вернуться. BlockingQueueИнтерфейс вводит метод take(), который удаляет и получает заголовок BlockingQueue, и ждет, пока BlockingQueueне перестанет быть пустым, если это необходимо. [23] [24]
Интерфейс Dequeрасширяет интерфейс Queue. [25] Deque создает двустороннюю очередь. В то время как обычный Queueпозволяет вставлять только в конец и удалять в начало, Dequeпозволяет вставлять или удалять как в начало, так и в конец. A Dequeпохож на Queue, который может использоваться вперед или назад, или и то и другое одновременно. Кроме того, могут быть созданы как прямой, так и обратный итератор. Интерфейс Dequeреализуется java.util.ArrayDequeи java.util.LinkedList. [26]
LinkedList, конечно, также реализует Listинтерфейс и может также использоваться как таковой. Но у него также есть Queueметоды. LinkedListреализует java.util.Dequeинтерфейс, что дает ему большую гибкость. [27]
ArrayDequeреализует Queueкак массив. Подобно LinkedList, ArrayDequeтакже реализует java.util.Dequeинтерфейс. [27]
Интерфейс java.util.concurrent.BlockingDequeрасширяет java.util.concurrent.BlockingQueue. [25] BlockingDeque похож на BlockingQueue. Он предоставляет те же методы для вставки и удаления с ограничениями по времени для ожидания возможности вставки или удаления. Однако интерфейс также обеспечивает гибкость Deque. Вставки и удаления могут выполняться на обоих концах. Функция блокировки объединена с функцией Deque. [28]
Интерфейс Java java.util.Setопределяет Set. В A Setне может быть дубликатов элементов. Кроме того, в Setне установлен порядок. Таким образом, элементы не могут быть найдены по индексу. Setреализуется java.util.HashSet, java.util.LinkedHashSet, и java.util.TreeSet.
Существует несколько реализаций интерфейса Set, включая AbstractSetи его подклассы, а также конечный статический внутренний класс (где и являются формальными параметрами типа).ConcurrentHashMap.KeySetView<K,V>KV
AbstractSetпредставляет собой скелетную реализацию интерфейса Set. [14]
Прямые подклассы AbstractSetвключают ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSetи TreeSet.
Класс EnumSetрасширяет AbstractSet. EnumSetКласс не имеет публичных конструкторов и содержит только статические методы фабрики. [29]
EnumSetсодержит статический метод фабрики . [30] Этот метод является методом агрегации. [29] Он принимает несколько параметров, учитывает тип параметров, а затем возвращает экземпляр с соответствующим типом. [29] По состоянию на 2018 год в реализации Java SE8 OpenJDK используются две реализации , которые невидимы для клиента, а именно и . [29] Если больше не обеспечивает никаких преимуществ производительности для небольших типов перечисления, его можно удалить из библиотеки без отрицательного влияния на библиотеку коллекций Java. [29]EnumSet.of()EnumSetRegularEnumSetJumboEnumSetRegularEnumSet
EnumSetявляется хорошей заменой для битовых полей , которые являются типом набора, как описано ниже. [30]
Традиционно, когда разработчики сталкивались с элементами перечислимого типа, которые необходимо было поместить в набор, разработчик использовал шаблон перечисления int, в котором каждой константе присваивалась различная степень числа 2. [30] Это битовое представление позволяет разработчику использовать побитовую операцию ИЛИ, так что константы можно было объединить в набор, также известный как битовое поле . Это битовое представление позволяет разработчику выполнять эффективные операции на основе наборов и побитовую арифметику, такую как пересечение и объединения. [30]
Однако существует множество проблем с подходом представления битовых полей . Битовое поле менее читабельно, чем константа int enum. [30] Кроме того, если элементы представлены битовыми полями, невозможно выполнить итерацию по всем этим элементам. [30]
Рекомендуемый альтернативный подход заключается в использовании EnumSet, где вместо битового поля используется int enum . [30] Этот подход использует EnumSetдля представления набора значений, принадлежащих к одному Enumтипу. [30] Поскольку EnumSetреализует Setинтерфейс и больше не требует использования побитовых операций, этот подход более типобезопасен. [30] Кроме того, существует множество статических фабрик, которые позволяют создавать экземпляры объектов, например, метод method . [30]EnumSet.of()
После введения подход представления EnumSetбитового поля считается устаревшим. [30]
HashSetиспользует хэш-таблицу. Точнее, он использует java.util.LinkedHashMapдля хранения хэшей и элементов, а также для предотвращения дубликатов.
Класс java.util.LinkedHashSetрасширяется HashSetпутем создания двусвязного списка, который связывает все элементы по порядку их вставки. Это гарантирует, что порядок итерации по Setявляется предсказуемым.
CopyOnWriteArraySetявляется параллельной заменой для synchronized Set. Он обеспечивает улучшенную параллельность во многих ситуациях, устраняя необходимость выполнять синхронизацию или создавать копию объекта во время итерации, аналогично тому, как CopyOnWriteArrayListдействует как параллельная замена для synchronized List. [31]
С другой стороны, подобно CopyOnWriteArrayList, CopyOnWriteArraySetне следует использовать, когда синхронизация обязательна.
Интерфейс java.util.SortedSetрасширяет интерфейс java.util.Set. В отличие от обычного Set, элементы в SortedSetсортируются либо методом элемента compareTo(T o), либо методом, предоставленным конструктору SortedSet. Первый и последний элементы SortedSetмогут быть извлечены с помощью методов first()и last()соответственно, а подмножества могут быть созданы с помощью минимальных и максимальных значений, а также с началом или окончанием в начале или конце SortedSet. java.util.TreeSetКласс реализует SortedSetинтерфейс. [32]
Интерфейс java.util.NavigableSetрасширяет интерфейс java.util.SortedSetи имеет несколько дополнительных методов. Методы floor(E e), ceiling(E e), lower(E e)и higher(E e)находят элемент в наборе, который близок к параметру. Кроме того, Setпредоставляется нисходящий итератор по элементам в . Как и в случае SortedSet, java.util.TreeSetреализует NavigableSet. [33]
java.util.TreeSetиспользует красно-черное дерево , реализованное с помощью java.util.TreeMap. Красно-черное дерево гарантирует отсутствие дубликатов. Кроме того, оно позволяет TreeSetреализовать java.util.SortedSet. [34]
ConcurrentSkipListSetдействует как параллельная замена для реализаций synchronized SortedSet. Например, он заменяет , TreeSetкоторый был обернут методом synchronizedMap. [35]
Карты определяются интерфейсом java.util.Mapна Java.
Карты — это структуры данных, которые связывают ключ с элементом. Это позволяет карте быть очень гибкой. Если ключ — это хэш-код элемента, то Mapпо сути это Set. Если это просто увеличивающееся число, то это становится списком.
Примеры Mapреализаций включают java.util.HashMap, java.util.LinkedHashMap, и java.util.TreeMap.
AbstractMapявляется примером скелетной реализации . [14]
Прямые подклассы класса AbstractMapвключают ConcurrentSkipListMap, EnumMap, HashMap, и IdentityHashMap.TreeMapWeakHashMap
EnumMapextends AbstractMap. EnumMapимеет сравнимую скорость с порядково-индексированным массивом. [36] Это происходит потому, что EnumMapвнутренне использует массив, а детали реализации полностью скрыты от разработчика. [36] Следовательно, EnumMap получает безопасность типов, а Mapтакже преимущества производительности массива. [36]
HashMapиспользует хэш-таблицу . Хэши ключей используются для поиска элементов в различных корзинах. Это HashMapколлекция на основе хэша. [37]
LinkedHashMapрасширяется HashMapпутем создания двусвязного списка между элементами, что позволяет получать к ним доступ в том порядке, в котором они были вставлены в карту. LinkedHashMapсодержит protected removeEldestEntryметод, который вызывается методом putвсякий раз, когда к нему добавляется новый ключ Map. [38] Удаляет Mapсвою самую старую запись всякий раз, когда removeEldestEntryвозвращает true. [38] Метод removeEldestEntryможно переопределить. [38]
TreeMap, в отличие от HashMapи LinkedHashMap, использует красно-черное дерево. Ключи используются как значения для узлов в дереве, а узлы указывают на элементы в Map. [39]
ConcurrentHashMapпохож на HashMapи также является коллекцией на основе хеша. [37] Однако есть ряд отличий, таких как различия в используемой ими стратегии блокировки.
Использует ConcurrentHashMapсовершенно другую стратегию блокировки для обеспечения улучшенной масштабируемости и параллелизма. [37] ConcurrentHashMap не синхронизирует каждый метод, используя одну и ту же блокировку. [37] Вместо этого ConcurrentHashMapиспользуйте механизм, известный как чередование блокировок . [37] Этот механизм обеспечивает более мелкозернистый механизм блокировки. [37] Он также допускает более высокую степень общего доступа. [37]
ConcurrentSkipListMapдействует как параллельная замена для реализаций синхронизированного SortedMap. ConcurrentSkipListMapочень похож на ConcurrentSkipListSet, поскольку ConcurrentSkipListMapзаменяет , TreeMapкоторый был обернут методом synchronizedMap. [35]
Интерфейс java.util.SortedMapрасширяет интерфейс java.util.Map. Этот интерфейс определяет , Mapкоторый сортируется по предоставленным ключам. Используя, еще раз, compareTo()метод или метод, предоставленный в конструкторе для SortedMap, пары ключ-элемент сортируются по ключам. Первый и последний ключи в Mapможно вызвать с помощью методов firstKey()и lastKey()соответственно. Кроме того, подкарты можно создавать из минимальных и максимальных ключей с помощью метода subMap(K fromKey, K toKey). SortedMapреализуется с помощью java.util.TreeMap. [40]
Интерфейс java.util.NavigableMapрасширяется java.util.SortedMapразличными способами. Можно вызывать методы, которые находят ключ или запись карты, которая ближе всего к заданному ключу в любом направлении. Карта также может быть обращена, и из нее может быть сгенерирован итератор в обратном порядке. Он реализован с помощью java.util.TreeMap. [41]
Интерфейс java.util.concurrent.ConcurrentMapрасширяет java.util.Mapинтерфейс. Этот интерфейс является потокобезопасным Mapинтерфейсом, представленным в Java Collections Framework версии 1.5 языка программирования Java. [20]
Каркас коллекций Java расширен библиотекой Apache Commons Collections, которая добавляет такие типы коллекций, как сумка и двунаправленная карта, а также утилиты для создания объединений и пересечений. [42]
Google выпустила собственные библиотеки коллекций как часть библиотек Guava .
До того, как Collections дебютировали так желанно, стандартными методами группировки объектов Java были массив, Vector и Hashtable. Все три коллекции имеют разные методы и синтаксис для доступа к членам: массивы используют символы квадратных скобок ([]), Vector использует метод elementAt, а Hashtable использует методы
и
.
getput
Sun Java Development Kit JDK1.2 наконец-то включает стандартный набор классов коллекций. Несмотря на некоторые различия в дизайне и реализации, пакет JDK1.2 содержит большинство тех же основных абстракций, структуры и функциональности, что и этот пакет. По этой причине этот пакет collections НЕ будет в дальнейшем обновляться.
Как и сама Java, библиотека Java Generic Library во многом заимствует из лагеря C++: она берет лучшее из STL C++, оставляя недостатки C++ позади. Большинство программистов на C++ сегодня знают о своей STL, но немногим удается использовать ее потенциал.
Сравнение JGL от ObjectSpace Inc. и Collections Framework от Sun похоже на сравнение яблок и киви. На первый взгляд кажется, что эти два фреймворка соревнуются за одних и тех же разработчиков, но после более внимательного изучения становится ясно, что их нельзя сравнивать справедливо, не признав сначала, что у этих двух фреймворков разные цели. Если, как говорится в документации Sun, Collections собирается гомогенизировать собственные API Sun (основной API, расширения и т. д.), то, очевидно, Collections должен стать отличной новостью и хорошей вещью даже для самого фанатичного поклонника JGL. Если Sun не нарушит своего обещания в этой области, я буду рад вложить свои ресурсы в серьезное принятие Collections.
Примечание: После выпуска J2SE 5.0 этот пакет переходит в режим обслуживания: будут выпущены только существенные исправления. Пакет J2SE5 java.util.concurrent включает улучшенные, более эффективные и стандартизированные версии основных компонентов этого пакета.
