Какие интерфейсы расширяют интерфейс collection
Обновлено: 05.07.2024
Интерфейс Observer определяет всего один метод, update (Observable o, Object arg) , который вызывается, когда обозреваемый объект изменяется.
Класс Observable предназначен для поддержки обозреваемого объекта в парадигме MVC (model-view-controller), которая, как и другие проектные решения и шаблоны, описана в специальной литературе. Этот класс должен быть унаследован, если возникает необходимость в том, чтобы отслеживать состояние какого-либо объекта. Обозреваемый объект может иметь несколько обозревателей. Соответственно, они должны реализовать интерфейс Observer .
После того, как в состоянии обозреваемого объекта что-то меняется, необходимо вызвать метод notifyObservers , который, в свою очередь , вызывает методы update у каждого обозревателя.
Рассмотрим пример организации взаимодействия классов:
В результате работы на консоль будет выведено:
На практике использовать Observer не всегда удобно, так как в Java отсутствует множественное наследование и Observer необходимо наследовать в самом начале построения иерархии классов. Как вариант, можно предложить определить интерфейс , задающий функциональность, сходную с Observer , и реализовать его в подходящем классе.
Собираем все воедино
Итак, смотрим на получившейся диаграмму классов:
Как видим диаграмма достаточно массивная. Но такая архитектура считается эталонной в OOП.
Реализации интерфейса Map
Интерфейс Map соотносит уникальные ключи со значениями. Ключ — это объект, который вы используете для последующего извлечения данных. Задавая ключ и значение, вы можете помещать значения в объект карты. После того как это значение сохранено, вы можете получить его по ключу. Интерфейс Map — это обобщенный интерфейс, объявленный так, как показано ниже.
interface Мар<К, V>
Здесь К указывает тип ключей, а V — тип хранимых значений.
Иерархия классов очень похожа на иерархию Set'а:
Синхронизированные коллекции
Получить синхронизированные объекты коллекций можно с помощью статических методов synchronizedMap и synchronizedList класса Collections.
Map m = Collections.synchronizedMap(new HashMap());
List l = Collections.synchronizedList(new ArrayList());
Кроме того всегда существует возможность "классической" синхронизации с помощью блока synchronized.
Интерфейс Collection
Давайте рассмотрим основные интерфейсы, относящиеся к Collection:
Как видно с диаграммы, интерфейс Collection не является базовым (какая интрига :D). Интерфейс Collection расширяет интерфейс Iterable, у которого есть только один метод iterator(). Это значит что любая коллекция, которая есть наследником Iterable должна возвращать итератор.
Базовые интерфейсы
В библиотеке коллекций Java существует два базовых интерфейса, реализации которых и представляют совокупность всех классов коллекций:
1. Collection - коллекция содержит набор объектов (элементов). Здесь определены основные методы для манипуляции с данными, такие как вставка (add, addAll), удаление (remove, removeAll, clear), поиск (contains)
2. Map - описывает коллекцию, состоящую из пар "ключ — значение". У каждого ключа только одно значение, что соответствует математическому понятию однозначной функции или отображения (тар). Такую коллекцию часто называют еще словарем (dictionary) или ассоциативным массивом (associative array). Никак НЕ относится к интерфейсу Collection и является самостоятельным.
Хотя фреймворк называется Java Collections Framework, интерфейс map и его реализации входят в фреймворк тоже !
Интерфейсы Collection и Map являются базовыми, но они не есть единственными. Их расширяют другие интерфейсы, добавляющие дополнительный функционал. О них мы ещё поговорим.
Коллекции
Зачастую в программе работа идет не с одним объектом, а с целой группой более или менее однотипных экземпляров (например, автопарк организации). Проще всего сделать это с помощью массивов. Однако, несмотря на то, что это достаточно эффективное решение для многих случаев, оно имеет некоторые ограничения. Так, обращаться к элементу массива можно только по его номеру (индексу). Также необходимо заранее задать длину массива и больше ее не менять.
Массивы существовали в Java изначально. Кроме того, было определено два класса для организации более эффективной работы с наборами объектов: Hashtable и Vector . В JDK 1.2 набор классов, поддерживающих работу с коллекциями, был существенно расширен.
Существует несколько различных типов классов-коллекций. Все они разрабатывались, по возможности, в соответствии с единой логикой и определенными интерфейсами и там, где это возможно, работа с ними унифицирована. Однако все коллекции отличаются внутренними механизмами хранения, скоростью доступа к элементам, потребляемой памятью и другими деталями. Например, в некоторых коллекциях объекты (также называемые элементами коллекций), могут быть упорядочены, в некоторых - нет. В некоторых типах коллекций допускается дублирование ссылок на объект , в некоторых - нет. Далее мы рассмотрим каждый из классов-коллекций.
Классы, обеспечивающие манипулирование коллекциями объектов, объявлены в пакете java.util .
Интерфейсы
Интерфейс Collection
Данный интерфейс является корнем всей иерархии классов-коллекций. Он определяет базовую функциональность любой коллекции - набор методов, которые позволяют добавлять, удалять, выбирать элементы коллекции. Классы, которые реализуют интерфейс Collection , могут содержать дубликаты и пустые ( null ) значения.
AbstractCollection , как абстрактный класс, служит основой для создания конкретных классов коллекций и содержит реализацию некоторых методов, определенных в интерфейсе Collection .
Интерфейс Set
Классы, которые реализуют этот интерфейс, не допускают наличия дубликатов. В коллекции этого типа разрешено наличие только одной ссылки типа null . Интерфейс Set расширяет интерфейс Collection , таким образом, любой класс, имплементирующий Set , реализует все методы, определенные в Collection . Любой объект, добавляемый в Set , должен реализовать метод equals , чтобы его можно было сравнить с другими.
AbstractSet , являясь абстрактным классом, представляет собой основу для реализации различных вариантов интерфейса Set .
Интерфейс List
Классы, реализующие этот интерфейс, содержат упорядоченную последовательность объектов (объекты хранятся в том порядке, в котором они были добавлены). В JDK 1.2 был переделан класс Vector , так, что он теперь реализует интерфейс List . Интерфейс List расширяет интерфейс Collection , и любой класс, имплементирующий List , реализует все методы, определенные в Collection , и в то же время вводятся новые методы, которые позволяют добавлять и удалять элементы из списка. List также обеспечивает ListIterator , который позволяет перемещаться как вперед, так и назад по элементам списка.
AbstractList , как абстрактный класс, представляет собой основу для реализации различных вариантов интерфейса List .
Рис. 14.1. Основные типы для работы с коллекциями.
Интерфейс Map
Классы, которые реализуют этот интерфейс, хранят неупорядоченный набор объектов парами ключ/значение. Каждый ключ должен быть уникальным. Hashtable после модификации в JDK 1.2 реализует интерфейс Map. Порядок следования пар ключ/значение не определен.
Интерфейс Map не расширяет интерфейс Collection . AbstractMap , будучи абстрактным классом, представляет собой основу для реализации различных вариантов интерфейса Map .
Интерфейс SortedSet
Этот интерфейс расширяет Set , требуя, чтобы содержимое набора было упорядочено. Такие коллекции могут содержать объекты, которые реализуют интерфейс Comparable , либо могут сравниваться с использованием внешнего Comparator .
Интерфейс SortedMap
Этот интерфейс расширяет Map , требуя, чтобы содержимое коллекции было упорядочено по значениям ключей.
Интерфейс Iterator
В Java 1 для перебора элементов коллекции использовался интерфейс Enumeration . В Java 2 для этих целей должны применяться объекты, которые реализуют интерфейс Iterator . Все классы, которые реализуют интерфейс Collection , должны реализовать метод iterator , который возвращает объект, реализующий интерфейс Iterator . Iterator весьма похож на Enumeration , с тем лишь отличием, что в нем определен метод remove , который позволяет удалить объект из коллекции, для которой Iterator был создан.
Таким образом, подводя итог, перечислим интерфейсы, используемые при работе с коллекциями:
Aбстрактные классы, используемые при работе с коллекциями
java.util.AbstractCollection - данный класс реализует все методы, определенные в интерфейсе Collection , за исключением iterator и size , так что для того, чтобы создать немодифицируемую коллекцию, нужно переопределить эти методы. Для реализации модифицируемой коллекции необходимо еще переопределить метод public void add(Object o) (в противном случае при его вызове будет возбуждено исключение UnsupportedOperationException ).
Необходимо также определить два конструктора: без аргументов и с аргументом Collection . Первый должен создавать пустую коллекцию, второй - коллекцию на основе существующей. Данный класс расширяется классами AbstractList и AbstractSet .
java.util.AbstractList - этот класс расширяет AbstractCollection и реализует интерфейс List . Для создания немодифицируемого списка необходимо имплементировать методы public Object get(int index) и public int size() . Для реализации модифицируемого списка необходимо также реализовать метод public void set(int index,Object element) (в противном случае при его вызове будет возбуждено исключение UnsupportedOperationException ).
В отличие от AbstractCollection , в этом случае нет необходимости реализовывать метод iterator , так как он уже реализован поверх методов доступа к элементам списка get, set, add, remove .
java.util.AbstractSet - данный класс расширяет AbstractCollection и реализует основную функциональность, определенную в интерфейсе Set . Следует отметить, что этот класс не переопределяет функциональность, реализованную в классе AbstractCollection .
java.util.AbstractMap - этот класс расширяет основную функциональность, определенную в интерфейсе Map . Для реализации немодифицируемого класса, унаследованного от AbstractMap , достаточно определить метод entrySet , который должен возвращать объект, приводимый к типу AbstractSet . Этот набор ( Set ) не должен обеспечивать методов для добавления и удаления элементов из набора. Для реализации модифицируемого класса Map необходимо также переопределить метод put и добавить в итератор, возвращаемый entrySet().iterator() , поддержку метода remove .
java.util.AbstractSequentialList - этот класс расширяет AbstractList и является основой для класса LinkedList. Основное отличие от AbstractList заключается в том, что этот класс обеспечивает не только последовательный, но и произвольный доступ к элементам списка, с помощью методов get(int index) , set(int index, Object element) , add(int index, Object element) и remove(int index) . Для того, чтобы реализовать данный класс, необходимо переопределить методы listIterator и size . Причем, если реализуется немодифицируемый список, для итератора достаточно реализовать методы hasNext, next, hasPrevious, previous и index . Для модифицируемого списка необходимо дополнительно реализовать метод set , а для списков переменной длины еще и add , и remove .
Конкретные классы коллекций
java.util.ArrayList - этот класс расширяет AbstractList и весьма похож на класс Vector . Он также динамически расширяется, как Vector , однако его методы не являются синхронизированными, вследствие чего операции с ним выполняются быстрее. Для того, чтобы воспользоваться синхронизированной версией ArrayList , можно применить вот такую конструкцию:
java.util.LinkedList - представляет собой реализацию интерфейса List . Он реализует все методы интерфейса List , помимо этого добавляются еще новые методы, которые позволяют добавлять, удалять и получать элементы в конце и начале списка. LinkedList является двухсвязным списком и позволяет перемещаться как от начала в конец списка, так и наоборот. LinkedList удобно использовать для организации стека.
Классы LinkedList и ArrayList имеют схожую функциональность. Однако с точки зрения производительности они отличаются. Так, в ArrayList заметно быстрей (примерно на порядок) осуществляются операции прохода по всему списку (итерации) и получения данных. LinkedList почти на порядок быстрее выполняет операции удаления и добавления новых элементов.
java.util.Hashtable - расширяет абстрактный класс Dictionary . В JDK 1.2 класс Hashtable также реализует интерфейс Map . Hashtable предназначен для хранения объектов в виде пар ключ/значение. Из самого названия следует, что Hаshtable использует алгоритм хэширования для увеличения скорости доступа к данным. Для того, чтобы выяснить принципы работы данного алгоритма, рассмотрим несколько примеров.
Предположим, имеется массив строк, содержащий названия городов. Для того, чтобы найти элемент массива, содержащий название города, в общем случае требуется просмотреть весь массив, а если необходимо найти все элементы массива, то для поиска каждого, в среднем, потребуется просматривать половину массива. Такой подход может оказаться приемлемым только для небольших массивов.
Как уже отмечалось ранее, для того, чтобы увеличить скорость поиска, используется алгоритм хэширования. Каждый объект в Java унаследован от Object . Как уже отмечалось ранее, hash определено как целое число, которое уникально идентифицирует экземпляр класса Object и, соответственно, все экземпляры классов, унаследованных от Object . Это число возвращает метод hashCode() . Именно оно используется при сохранении ключа в Hashtable следующим образом: разделив длину массива, предназначенного для хранения ключей, на код, получаем некое целое число, которое служит индексом для хранения ключа в массиве array.length % hashCode() .
Далее, если необходимо добавить новую пару ключ/значение, вычисляется новый индекс, и если этот индекс совпадает с уже имеющимся, то создается список ключей, на который указывает элемент массива ключей. Таким образом, при обратном извлечении ключа необходимо вычислить индекс массива по тому же алгоритму и получить его. Если ключ в массиве единственный, то используется значение элемента массива, если хранится несколько ключей, то необходимо обойти список и выбрать нужный.
Есть несколько соображений, относящихся к производительности классов, использующих для хранения данных алгоритм хэширования. В частности, размер массива. Если массив окажется слишком мал, то связанные списки будут слишком длинными и скорость поиска станет существенно снижаться, так как просмотр элементов списка будет такой же, как в обычном массиве. Чтобы этого избежать, задается некий коэффициент заполнения. При заполнении элементов массива, в котором хранятся ключи (или списки ключей) на эту величину, происходит увеличение массива и производится повторное реиндексирование. Таким образом, если массив окажется слишком мал, то он будет быстро заполняться и будет производиться операция повторного индексирования, которая отнимает достаточно много ресурсов. С другой стороны, если массив сделать большим, то при необходимости просмотреть последовательно все элементы коллекции, использующей алгоритм хэширования, придется обрабатывать большое количество пустых элементов массива ключей.
Начальный размер массива и коэффициент загрузки коллекции задаются при конструировании. Например:
Существует также конструктор без параметров, который использует значения по умолчанию 101 для размера массива (в последней версии значение уменьшено до 11) и 0.75 для коэффициента загрузки.
Использование алгоритма хэширования позволяет гарантировать, что скорость доступа к элементам коллекции такого типа будет увеличиваться не линейно, а логарифмически. Таким образом, при частом поиске каких-либо значений по ключу имеет смысл задействовать коллекции, применяющие алгоритм хэширования.
java.util.HashMap - этот класс расширяет AbstractMap и весьма похож на класс Hashtable . HashMap предназначен для хранения пар объектов ключ/значение. Как для ключей, так и для элементов допускаются значения типа null . Порядок хранения элементов в этой коллекции не совпадает с порядком их добавления. Порядок элементов в коллекции также может меняться во времени. HashMap обеспечивает постоянное время доступа для операций get и put .
Итерация по всем элементам коллекции пропорциональна ее емкости. Поэтому имеет смысл не делать размер коллекций чрезмерно большим, если достаточно часто придется осуществлять итерацию по элементам.
Методы HashMap не являются синхронизированными. Для того, чтобы обеспечить нормальную работу в многопоточном варианте, следует использовать либо внешнюю синхронизацию потоков, либо синхронизированный вариант коллекции.
java.util.TreeMap - расширяет класс AbstractMap и реализует интерфейс SortedMap . TreeMap содержит ключи в порядке возрастания. Используется либо натуральное сравнение ключей, либо должен быть реализован интерфейс Comparable . Реализация алгоритма поиска обеспечивает логарифмическую зависимость времени выполнения основных операций ( containsKey, get, put и remove ). Запрещено применение null значений для ключей. При использовании дубликатов ключей ссылка на объект, сохраненный с таким же ключом, будет утеряна. Например:
Класс Collections
Класс Collections является классом-утилитой и содержит несколько вспомогательных методов для работы с классами, обеспечивающими различные интерфейсы коллекций. Например, для сортировки элементов списков, для поиска элементов в упорядоченных коллекциях и т.д. Но, пожалуй, наиболее важным свойством этого класса является возможность получения синхронизированных вариантов классов-коллекций. Например, для получения синхронизированного варианта Map можно использовать следующий подход:
Как уже отмечалось ранее, начиная с JDK 1.2, класс Vector реализует интерфейс List . Рассмотрим пример сортировки элементов, содержащихся в классе Vector .
Данная публикация не является полным разбором или анализом (не покрывает пакет java.util.concurrent ). Это, скорее, справочник, который поможет начинающим разработчикам понять ключевые отличия одних коллекций от других, а более опытным разработчикам просто освежить материал в памяти.
Что такое Java Collections Framework?
Java Collection Framework — иерархия интерфейсов и их реализаций, которая является частью JDK и позволяет разработчику пользоваться большим количесвом структур данных из «коробки».
Базовые понятия
На вершине иерархии в Java Collection Framework располагаются 2 интерфейса: Collection и Map . Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части по типу хранения данных: простые последовательные наборы элементов и наборы пар «ключ — значение» (словари).
Collection — этот интерфейс находится в составе JDK c версии 1.2 и определяет основные методы работы с простыми наборами элементов, которые будут общими для всех его реализаций (например size() , isEmpty() , add(E e) и др.). Интерфейс был слегка доработан с приходом дженериков в Java 1.5. Также, в версии Java 8, было добавлено несколько новых методов для работы с лямбдами (такие как stream() , parallelStream() , removeIf(Predicate<? super E> filter) и др.).
Важно также отметить, что эти методы были реализованы непосредственно в интерфейсе как default -методы.
Map. Данный интерфейс также находится в составе JDK c версии 1.2 и предоставляет разработчику базовые методы для работы с данными вида «ключ — значение».Также как и Collection , он был дополнен дженериками в версии Java 1.5 и в версии Java 8 появились дополнительные методы для работы с лямбдами, а также методы, которые зачастую реализовались в логике приложения ( getOrDefault(Object key, V defaultValue) , putIfAbsent(K key, V value) ).
Интерфейс Map [doc]
Hashtable — реализация такой структуры данных, как хэш-таблица. Она не позволяет использовать null в качестве значения или ключа. Эта коллекция была реализована раньше, чем Java Collection Framework, но в последствии была включена в его состав. Как и другие коллекции из Java 1.0, Hashtable является синхронизированной (почти все методы помечены как synchronized ). Из-за этой особенности у неё имеются существенные проблемы с производительностью и, начиная с Java 1.2, в большинстве случаев рекомендуется использовать другие реализации интерфейса Map ввиду отсутствия у них синхронизации.
HashMap — коллекция является альтернативой Hashtable . Двумя основными отличиями от Hashtable являются то, что HashMap не синхронизирована и HashMap позволяет использовать null как в качестве ключа, так и значения. Так же как и Hashtable , данная коллекция не является упорядоченной: порядок хранения элементов зависит от хэш-функции. Добавление элемента выполняется за константное время O(1), но время удаления, получения зависит от распределения хэш-функции. В идеале является константным, но может быть и линейным O(n). Более подробную информацию о HashMap можно почитать здесь (актуально для Java < 8).
LinkedHashMap — это упорядоченная реализация хэш-таблицы. Здесь, в отличии от HashMap , порядок итерирования равен порядку добавления элементов. Данная особенность достигается благодаря двунаправленным связям между элементами (аналогично LinkedList ). Но это преимущество имеет также и недостаток — увеличение памяти, которое занимет коллекция. Более подробная информация изложена в этой статье.
TreeMap — реализация Map основанная на красно-чёрных деревьях. Как и LinkedHashMap является упорядоченной. По-умолчанию, коллекция сортируется по ключам с использованием принципа "natural ordering", но это поведение может быть настроено под конкретную задачу при помощи объекта Comparator , который указывается в качестве параметра при создании объекта TreeMap .
WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references. Другими словами, Garbage Collector автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элеметна нет жёстких ссылок.
Интерфейс List [doc]
Реализации этого интерфейса представляют собой упорядоченные коллекции. Кроме того, разработчику предоставляется возможность доступа к элементам коллекции по индексу и по значению (так как реализации позволяют хранить дубликаты, результатом поиска по значению будет первое найденное вхождение).
Vector — реализация динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Vector появился в JDK версии Java 1.0, но как и Hashtable , эту коллекцию не рекомендуется использовать, если не требуется достижения потокобезопасности. Потому как в Vector , в отличии от других реализаций List , все операции с данными являются синхронизированными. В качестве альтернативы часто применяется аналог — ArrayList .
Stack — данная коллекция является расширением коллекции Vector . Была добавлена в Java 1.0 как реализация стека LIFO (last-in-first-out). Является частично синхронизированной коллекцией (кроме метода добавления push() ). После добавления в Java 1.6 интерфейса Deque , рекомендуется использовать именно реализации этого интерфейса, например ArrayDeque .
ArrayList — как и Vector является реализацией динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Как можно догадаться из названия, его реализация основана на обычном массиве. Данную реализацию следует применять, если в процессе работы с коллекцией предплагается частое обращение к элементам по индексу. Из-за особенностей реализации поиндексное обращение к элементам выполняется за константное время O(1). Но данную коллекцию рекомендуется избегать, если требуется частое удаление/добавление элементов в середину коллекции. Подробный анализ и описание можно почитать в этом хабратопике.
LinkedList — ещё одна реализация List . Позволяет хранить любые данные, включая null . Особенностью реализации данной коллекции является то, что в её основе лежит двунаправленный связный список (каждый элемент имеет ссылку на предыдущий и следующий). Благодаря этому, добавление и удаление из середины, доступ по индексу, значению происходит за линейное время O(n), а из начала и конца за константное O(1). Так же, ввиду реализации, данную коллекцию можно использовать как стек или очередь. Для этого в ней реализованы соответствующие методы. На Хабре также есть статья с подробным анализом и описанием этой коллекции.
Интерфейс Set [doc]
Представляет собой неупорядоченную коллекцию, которая не может содержать дублирующиеся данные. Является программной моделью математического понятия «множество».
HashSet — реализация интерфейса Set , базирующаяся на HashMap . Внутри использует объект HashMap для хранения данных. В качестве ключа используется добавляемый элемент, а в качестве значения — объект-пустышка (new Object()). Из-за особенностей реализации порядок элементов не гарантируется при добавлении.
LinkedHashSet — отличается от HashSet только тем, что в основе лежит LinkedHashMap вместо HashMap . Благодаря этому отличию порядок элементов при обходе коллекции является идентичным порядку добавления элементов.
TreeSet — аналогично другим классам-реализациям интерфейса Set содержит в себе объект NavigableMap , что и обуславливает его поведение. Предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator , либо сохраняет элементы с использованием "natural ordering".
Интерфейс Queue [doc]
Этот интерфейс описывает коллекции с предопределённым способом вставки и извлечения элементов, а именно — очереди FIFO (first-in-first-out). Помимо методов, определённых в интерфейсе Collection, определяет дополнительные методы для извлечения и добавления элементов в очередь. Большинство реализаций данного интерфейса находится в пакете java.util.concurrent и подробно рассматриваются в данном обзоре.
PriorityQueue — является единственной прямой реализацией интерфейса Queue (была добавлена, как и интерфейс Queue, в Java 1.5), не считая класса LinkedList , который так же реализует этот интерфейс, но был реализован намного раньше. Особенностью данной очереди является возможность управления порядком элементов. По-умолчанию, элементы сортируются с использованием «natural ordering», но это поведение может быть переопределено при помощи объекта Comparator , который задаётся при создании очереди. Данная коллекция не поддерживает null в качестве элементов.
ArrayDeque — реализация интерфейса Deque, который расширяет интерфейс Queue методами, позволяющими реализовать конструкцию вида LIFO (last-in-first-out). Интерфейс Deque и реализация ArrayDeque были добавлены в Java 1.6. Эта коллекция представляет собой реализацию с использованием массивов, подобно ArrayList , но не позволяет обращаться к элементам по индексу и хранение null . Как заявлено в документации, коллекция работает быстрее чем Stack , если используется как LIFO коллекция, а также быстрее чем LinkedList, если используется как FIFO.
Заключение
Java Collections Framework содержит большое количество различных структур данных, доступных в JDK «из коробки», которые в большинстве случаев покрывают все потребности при реализации логики приложения. Сравнение временных характеристик основных коллекций, которые зачастую используются в разработке приложений приведено в таблице:
При необходимости, разработчик может создать собственную реализацию, расширив или переопределив существующую логику, либо создав свою собственную реализацию подходящего интерфейса с нуля. Также существует некоторое количество готовых решений, которые являются альтернативой или дополнением к Java Collections Framework. Наиболее популярными являются Google Guava и Commons Collections.
При написании программы очень часто возникает потребность хранить набор каких-либо объектов. Это могут быть числа, строки, объекты пользовательских классов и т.п. В данной статье я постараюсь классифицировать и описать основные классы коллекций простым языком.
У некоторых читателей может возникнуть вопрос: зачем нам коллекции, если у нас есть массивы ? В самом деле, многие используют коллекции там где нужно и не нужно. Но бывают ситуации, когда необходимо например динамическое изменение размера структуры данных, или автоматическое упорядочение структуры данных по мере добавления элементов и т.п.
В данной статье речь пойдет именно о Java Collections Framework, так как существуют многочисленные альтернативы:
1. Guava(Google Collections Library) - Библиотека добавляет несколько полезных реализаций структур данных, таких как мультимножество, мультиотображение и двунаправленное отображение. Улучшена эффективность.
2. Trove library - Реализация коллекций, позволяющая хранить примитивы (в Java Collections Framework примитивы хранить нельзя, только оберточные типы), что позволяет повысить эффективность работы.
3. PCJ(Primitive Collections for Java) - так же как и Trove предназначены для примитивных типов, что позволит повысить эффективность.
4. Наконец Вы сами можете написать собственную коллекцию (тот же связной список). Но данный подход не рекомендуется :)
Реализации интерфейса Queue
Здесь я привел очень упрощенную иерархию.
PriorityQueue - единственная прямая реализация интерфейса Queue (не считая LinkedList, который больше является списком, чем очередью).
Эта очередь упорядочивает элементы либо по их натуральному порядку (используя интерфейс Comparable), либо с помощью интерфейса Comparator, полученному в конструкторе.
Заключение
Надеюсь эта статья была вам полезной. Если в комментариях наберётся достаточно пожеланий, я напишу вторую часть статьи, где приведу примеры использования всех этих коллекций. (Представьте только: на собеседовании вас спрашивают про иерархию коллекций в java, а Вы им рисуете предыдущий рисунок. Как они будут удивлены :D)
Спасибо за внимание .
1). Чуть добавлю про Vector и Hashtable. Хоть они официально и не deprecated, их реализация оставляет желать лучшего. Синхронизация в них реализована для каждого метода по отдельности, а обычно требуется выполнить целую последовательность действий.
В результате пример:
Один поток итеративно проходит по Вектору, второй что-то пытается изменить -> ConcurrentModificationException.
В итоге оборачиваем Vector в еще один блок синхронизации -> двойной проигрыш в производительности.
Один вопрос к Вам:
посмотрел реализацию Collections.SynchronizedList
А чем это отличается от Vector за исключением того, что в SynchronizedList используют левый объект монитора, а в Vector синхронизируют методы (мьютекс - сам экземпляр класса)?
2). "ArrayList - его преимущество в навигации по коллекции." - будь я новичком, не понял бы. Лучше: доступ к элементам напрямую по индексу.
3). "И если при добавлении в ArrayList превышается его объем, размер массива увеличивается вдвое"
Не совсем, есть еще loadFactor (default - 0,75). То, есть capacity увеличится вдвое, когда кол-во элементов превысит loadFactor * capacity.
Реализации интерфейса Set
Смотрим следующую диаграмму. Пытаемся вникнуть :)
HashSet - коллекция, не позволяющая хранить одинаковые объекты(как и любой Set). HashSet инкапсулирует в себе объект HashMap (то-есть использует для хранения хэш-таблицу).
Как большинство читателей, вероятно, знают, хеш-таблица хранит информацию, используя так называемый механизм хеширования, в котором содержимое ключа используется для определения уникального значения, называемого хеш-кодом. Этот хеш-код затем применяется в качестве индекса, с которым ассоциируются данные, доступные по этому ключу. Преобразование ключа в хеш-код выполняется автоматически — вы никогда не увидите самого хеш-кода. Также ваш код не может напрямую индексировать хеш-таблицу. Выгода от хеширования состоит в том, что оно обеспечивает константное время выполнения методов add(), contains(), remove() и size() , даже для больших наборов.
Если Вы хотите использовать HashSet для хранения объектов СВОИХ классов, то вы ДОЛЖНЫ переопределить методы hashCode() и equals(), иначе два логически-одинаковых объекта будут считаться разными, так как при добавлении элемента в коллекцию будет вызываться метод hashCode() класса Object (который скорее-всего вернет разный хэш-код для ваших объектов).
Важно отметить, что класс HashSet не гарантирует упорядоченности элементов, поскольку процесс хеширования сам по себе обычно не порождает сортированных наборов. Если вам нужны сортированные наборы, то лучшим выбором может быть другой тип коллекций, такой как класс TreeSet.
LinkedHashSet - поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать упорядоченную итерацию вставки в набор. То есть, когда идет перебор объекта класса LinkedHashSet с применением итератора, элементы извлекаются в том порядке, в каком они были добавлены.
TreeSet - коллекция, которая хранит свои элементы в виде упорядоченного по значениям дерева. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов. TreeSet хорош тем, что для операций add, remove и contains потребуется гарантированное время log(n).
Реализации интерфейса List
Сразу смотрим на иерархию классов.
Красным здесь выделены интерфейсы, зеленым - абстрактные классы, а синим готовые реализации. Сразу хочу заметить что здесь не вся иерархия, а только основная её часть.
Как видим на рисунке, между интерфейсом и конкретной реализацией коллекции существует несколько абстрактных классов. Это сделано для того, что бы вынести общий функционал в абстрактный класс, таким образом реализовать повторное использование кода.
ArrayList - пожалуй самая часто используемая коллекция. ArrayList инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов.
Так как ArrayList использует массив, то время доступа к элементу по индексу минимально (В отличии от LinkedList). При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево, при этом реальный размер массива (его емкость, capacity) не изменяется. Если при добавлении элемента, оказывается, что массив полностью заполнен, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент.
LinkedList - Двусвязный список. Это структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и две ссылки («связки») на следующий и предыдущий узел списка. Доступ к произвольному элементу осуществляется за линейное время (но доступ к первому и последнему элементу списка всегда осуществляется за константное время — ссылки постоянно хранятся на первый и последний, так что добавление элемента в конец списка вовсе не значит, что придется перебирать весь список в поисках последнего элемента). В целом же, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций.
Устаревшие коллекции
Следующие коллекции являются устаревшими, и их использование не рекомендуется, но не запрещается.
1. Enumeration — аналог интерфейса Iterator.
2. Vector — аналог класса ArrayList; поддерживает упорядоченный список элементов, хранимых во "внутреннем" массиве.
3. Stack — класс, производный от Vector, в который добавлены методы вталкивания (push) и выталкивания (pop) элементов, так что список может трактоваться в терминах, принятых для описания структуры данных стека (stack).
4. Dictionary — аналог интерфейса Map, хотя представляет собой абстрактный класс, а не интерфейс.
5. Hashtable — аналог HashMap.
Все методы Hashtable, Stack, Vector являются синхронизированными, что делает их менее эффективными в одно поточных приложениях.
Читайте также: