Среда коллекций Java

редактировать
java.util.Collection класс и иерархия интерфейса Java java.util.Map иерархия классов и интерфейсов

Структура Java коллекций - это набор классов и интерфейсов, которые реализуют часто повторно используемую коллекцию структуры данных.

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

Содержание

  • 1 Отличия от массивов
  • 2 История
  • 3 Архитектура
    • 3.1 Три типа коллекции
    • 3.2 Интерфейс списка
    • 3.3 Класс стека
    • 3.4 Интерфейсы очередей
    • 3.5 Интерфейсы двусторонней очереди (deque)
    • 3.6 Установка интерфейсов
    • 3.7 Сопоставление интерфейсов
  • 4 Расширения среды коллекций Java
  • 5 См. Также
  • 6 Ссылки

Отличия от массивов

Коллекции и массивы похожи в том, что они содержат ссылки на объекты, и ими можно управлять как группой. Однако, в отличие от массивов, коллекциям не нужно назначать определенную емкость при создании экземпляров. Коллекции также могут автоматически увеличиваться и уменьшаться в размере при добавлении или удалении объектов. Коллекции не могут содержать элементы базовых типов данных (примитивные типы), такие как int, long или double; вместо этого они содержат классы-оболочки, такие как Integer, Long или Double.

History

Реализации коллекций в версиях платформы Java до JDK 1.2 включали несколько структур данных классы, но не содержали рамки коллекций. Стандартные методы группировки Java-объектов осуществлялись через классы array, Vector и Hashtable, которые, к сожалению, было нелегко расширить и не реализовали стандартный интерфейс-член.

Для удовлетворения потребности в повторно используемой коллекции структуры данных, было разработано несколько независимых фреймворков, наиболее часто используемыми из которых являются пакет коллекций Дуга Ли и общая библиотека коллекций (JGL), главной целью которых было согласование с C ++ Стандартная библиотека шаблонов (STL).

Фреймворк коллекций был разработан и разработан в основном Джошуа Блох и был представлен в JDK 1.2. Он повторно использовал многие идеи и классы из пакета Doug Lea's Collections, который в результате был признан устаревшим. Sun Microsystems предпочла не использовать идеи JGL, потому что им нужна была компактная структура, а согласованность с C ++ не была одной из них. их целей.

Дуг Ли позже разработал параллелизм пакет, содержащий новые классы, связанные с коллекциями. Обновленная версия этих утилит параллелизма была включена в JDK 5.0 начиная с JSR 166.

Архитектура

Почти все коллекции в Java являются производными от интерфейса java.util.Collection. Коллекция определяет основные части всех коллекций. В интерфейсе указаны методы add () и remove () для добавления и удаления из коллекции соответственно. Также требуется метод toArray (), который преобразует коллекцию в простой массив всех элементов в коллекции. Наконец, метод contains () проверяет, находится ли указанный элемент в коллекции. Интерфейс Collection является подинтерфейсом java.lang.Iterable, поэтому любой Collection может быть целью оператора for-each. (Интерфейс Iterable предоставляет метод iterator (), используемый операторами for-each.) Все коллекции имеют итератор, который просматривает все элементы в коллекции. Кроме того, Collection - это общий. Любую коллекцию можно записать для хранения любого класса. Например, Collection может содержать строки, а элементы из коллекции могут использоваться как строки без необходимости приведения типов. Обратите внимание, что угловые скобки <>могут содержать аргумент типа, указывающий, какой тип содержит коллекция.

Три типа коллекции

Есть три общих типа коллекции: упорядоченные списки, словари / карты и наборы.

Упорядоченные списки позволяют программисту вставлять элементы в определенном порядке и извлекать эти элементы в том же порядке. Примером может служить лист ожидания. Базовые интерфейсы для упорядоченных списков называются List и Queue.

Словари / Карты хранят ссылки на объекты с ключом поиска для доступа к значениям объекта. Одним из примеров ключа является идентификационная карта. Базовый интерфейс словарей / карт называется Карта.

Наборы - это неупорядоченные коллекции, которые можно повторять и которые содержат каждый элемент не более одного раза. Базовый интерфейс для наборов называется Set.

Интерфейс списка

Списки реализуются в структуре коллекций через интерфейс java.util.List. Он определяет список как более гибкую версию массива. Элементы имеют определенный порядок, и разрешены повторяющиеся элементы. Элементы можно размещать в определенном месте. Их также можно искать в списке. Два примера конкретных классов, реализующих List:

  • java.util.ArrayList, который реализует список как массив. Когда требуются функции, специфичные для списка, класс перемещает элементы внутри массива, чтобы это сделать.
  • java.util.LinkedList. Этот класс хранит элементы в узлах, каждый из которых имеет указатель на предыдущий и следующий узлы в списке. По списку можно перемещаться, следуя указателям, а элементы можно добавлять или удалять, просто изменяя указатели вокруг, чтобы разместить узел в нужном месте.

Класс стека

Стеки создаются с помощью java.util.Stack. Стек предлагает методы для помещения нового объекта в стек (метод push ()) и получения объектов из стека (метод pop ()). Стек возвращает объект в соответствии с последним вошел - первым вышел (LIFO), например объект, который был помещен в стек последним, возвращается первым. java.util.Stack - это стандартная реализация стека, предоставляемая Java. Класс Stack представляет стек объектов в порядке очереди (LIFO). Он расширяет класс java.util.Vector пятью операциями, которые позволяют рассматривать вектор как стек. Предоставляются обычные операции push и pop, а также метод для просмотра верхнего элемента в стеке, метод для проверки того, пуст ли стек, и метод для поиска элемента в стеке и определения того, насколько далеко он сверху. Когда стопка создается впервые, она не содержит элементов.

Интерфейсы очередей

Интерфейс java.util.Queue определяет структуру данных очереди, в которой элементы хранятся в том порядке, в котором они вставлены. Новые дополнения идут в конец строки, а элементы удаляются с лицевой стороны. Он создает систему «первым пришел - первым обслужен». Этот интерфейс реализован с помощью java.util.LinkedList, java.util.ArrayDeque и java.util.PriorityQueue. LinkedList, конечно же, также реализует интерфейс List и также может использоваться как один. Но в нем также есть методы очереди. ArrayDeque реализует очередь как массив. И LinkedList, и ArrayDeque также реализуют интерфейс java.util.Deque, что придает ему большую гибкость.

java.util.Queue можно использовать более гибко с его подчиненным интерфейсом, java.util.concurrent.BlockingQueue. Интерфейс BlockingQueue работает как обычная очередь, но добавление и удаление из очереди блокируются. Если remove вызывается в пустой очереди, его можно настроить на ожидание в указанное время или неопределенное время, пока элемент не появится в очереди. Точно так же добавление элемента подлежит дополнительному ограничению емкости в очереди, и метод может дождаться, пока в очереди станет доступно пространство, прежде чем вернуться.

java.util.PriorityQueue реализует java.util.Queue, но также изменяет его. Вместо того, чтобы упорядочивать элементы в порядке их вставки, они упорядочиваются по приоритету. Метод, используемый для определения приоритета, - это либо метод compareTo () в элементах, либо метод, указанный в конструкторе. Класс создает это, используя кучу для сортировки элементов.

Интерфейсы двусторонней очереди (deque)

Интерфейс java.util.Queue расширяется с помощью java.util.Deque субинтерфейс. Deque создает двустороннюю очередь. В то время как обычная очередь допускает только вставки сзади и удаление спереди, двухсторонняя очередь позволяет вставлять или удалять как спереди, так и сзади. Двухсторонняя очередь похожа на очередь, которую можно использовать вперед или назад, или и то, и другое одновременно. Кроме того, можно сгенерировать итераторы как вперед, так и назад. Интерфейс Deque реализуется с помощью java.util.ArrayDeque и java.util.LinkedList.

Интерфейс java.util.concurrent.BlockingDeque работает аналогично java.util.concurrent.BlockingQueue. Предусмотрены те же методы для вставки и удаления с ограничениями по времени ожидания возможности вставки или удаления. Однако интерфейс также обеспечивает гибкость двухсторонней очереди. Вставки и удаления могут происходить с обоих концов. Функция блокировки сочетается с функцией deque.

Интерфейсы установки

Интерфейс Java java.util.Set определяет набор. В наборе не может быть повторяющихся элементов. Кроме того, в наборе нет установленного порядка. Таким образом, элементы не могут быть найдены по индексу. Набор реализуется с помощью java.util.HashSet, java.util.LinkedHashSet и java.util.TreeSet. HashSet использует хеш-таблицу. В частности, он использует java.util.HashMap для хранения хэшей и элементов и предотвращения дублирования. java.util.LinkedHashSet расширяет это, создавая двусвязный список, который связывает все элементы в порядке их вставки. Это гарантирует, что порядок итераций по набору предсказуем. java.util.TreeSet использует красно-черное дерево, реализованное java.util.TreeMap. Красно-черное дерево следит за тем, чтобы не было дубликатов. Кроме того, он позволяет TreeSet реализовывать java.util.SortedSet.

Интерфейс java.util.Set расширен интерфейсом java.util.SortedSet. В отличие от обычного набора, элементы в отсортированном наборе сортируются либо методом элемента compareTo (), либо методом, предоставленным конструктору отсортированного набора. Первый и последний элементы отсортированного набора могут быть извлечены, а подмножества могут быть созданы с помощью минимального и максимального значений, а также начала или окончания в начале или в конце отсортированного набора. Интерфейс SortedSet реализуется с помощью java.util.TreeSet.

java.util.SortedSet дополнительно расширяется через интерфейс java.util.NavigableSet. Он похож на SortedSet, но есть несколько дополнительных методов. Методы floor (), потолка (), lower () и upper () находят в наборе элемент, близкий к параметру. Кроме того, предоставляется убывающий итератор по элементам в наборе. Как и SortedSet, java.util.TreeSet реализует NavigableSet.

Интерфейсы карт

Карты определяются интерфейсом java.util.Map в Java. Карты - это простые структуры данных, которые связывают ключ с элементом. Это позволяет карте быть очень гибкой. Если ключом является хэш-код элемента, карта по сути представляет собой набор. Если это просто увеличивающееся число, оно становится списком. Карты реализуются с помощью java.util.HashMap, java.util.LinkedHashMap и java.util.TreeMap. HashMap использует хэш-таблицу . Хэши ключей используются для поиска элементов в различных корзинах. LinkedHashMap расширяет это, создавая двусвязный список между элементами, позволяя получать к ним доступ в том порядке, в котором они были вставлены на карту. TreeMap, в отличие от HashMap и LinkedHashMap, использует красно-черное дерево. Ключи используются в качестве значений для узлов в дереве, а узлы указывают на элементы на карте.

Интерфейс java.util.Map расширен его субинтерфейсом java.util.SortedMap. Этот интерфейс определяет карту, отсортированную по предоставленным ключам. Снова используя метод compareTo () или метод, предоставленный в конструкторе для отсортированной карты, пары ключ-элемент сортируются по ключам. Можно вызвать первый и последний ключи на карте. Кроме того, подкарты могут быть созданы из минимального и максимального ключей. SortedMap реализуется java.util.TreeMap.

Интерфейс java.util.NavigableMap расширяет java.util.SortedMap различными способами. Могут быть вызваны методы, которые находят ключ или запись карты, ближайшую к данному ключу в любом направлении. Карту также можно перевернуть, и из нее можно сгенерировать итератор в обратном порядке. Это реализовано с помощью java.util.TreeMap.

Расширения среды коллекций Java

Структура коллекций Java расширена библиотекой Apache Commons Collections, которая добавляет такие типы коллекций в качестве пакета и двунаправленной карты, а также утилит для создания объединений и пересечений.

Google выпустил собственные библиотеки коллекций как часть библиотек guava.

См. также

  • значок Портал компьютерного программирования

Ссылки

В Wikibook Программирование на Java есть страница по теме: Коллекции
Последняя правка сделана 2021-05-24 03:57:44
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте