Справочник по Java Collections Framework

Данная публикация не является полным разбором или анализом (не покрывает пакет java.util.concurrent). Это, скорее, справочник, который поможет начинающим разработчикам понять ключевые отличия одних коллекций от других, а более опытным разработчикам просто освежить материал в памяти.

Что такое Java Collections Framework?


Java Collection Framework — иерархия интерфейсов и их реализаций, которая является частью JDK и позволяет разработчику пользоваться большим количесвом структур данных из «коробки».

Базовые понятия


На вершине иерархии в Java Collection Framework располагаются 2 интерфейса: Collection и Map. Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части по типу хранения данных: простые последовательные наборы элементов и наборы пар «ключ — значение» (словари).

image

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 вместо HashSet. Благодаря этому отличию порядок элементов при обходе коллекции является идентичным порядку добавления элементов.

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.util.concurrent. Который является отличным дополнением к изложенному материалу.
Поделиться публикацией
Похожие публикации
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 21
  • 0
    Очень похоже на главу из книги с ссылками на офф. документацию. Можно уточнить источник(и), кроме статей с хабра?
    • 0
      Дело в том, что все источники, которые были использованы в статье — указаны. Статья самописная и копипаста не имеет.
    • –1
      А почему про Stream не написали?
      • 0
        а какое отношение Stream имеет к Java Collections Framework?
        • 0
          Ну как бы все коллекции от него наследуются. И почти все самые важные методы работы с коллекциями содержатся именно там.
          • 0
            Допустим, вы говорите про тот самый Stream, который появился в Java 8. Можете показать хотя бы одну коллекцию, которая наследуется от него?
            • 0
              Блин, и правда мой косяк. Они же все просто имеют метод stream(). Но мне кажется не рассказывать про stream когда говоришь про коллекции уже как-то неправильно.
              • 0
                Стримы это вполне отдельная автономная сущность. Для них коллекции это не более чем источник (коих еще очень много кроме коллекций). Так что лучше рассказывать отдельно.
      • +1
        Еще для начинающих разработчиков следовало бы уточнить затраты по памяти/времени на типичные операции.
        • 0
          Извиняюсь не сразу заметил, что часть характеристик вы указали, но лучше бы увидеть единую таблицу.
          • +2
            Да, я тоже думаю, что таблица не помешает. Как раз сейчас работаю над этим
        • 0
          Пара неточностей, как мне кажется:

          HashSet — реализация интерфейса Set, базирующаяся на HashTable. Внутри использует объект HashMap для хранения данных.

          Не очень понял почему базируется на HashTable, если под капотом HashMap?

          LinkedHashSet — отличается от HashSet только тем, что в основе лежит LinkedHashSet вместо HashSet.

          Наверно, здесь имелось в виду, что в основе лежит LinkedHashMap вместо HashMap?
          • 0
            Спасибо за правку. Действительно немного напутал. Исправил
          • 0
            Лучше почитать статьи товарища tarzan82, у него более подробно про все коллекции:
            LinkedHashMap
            ArrayList
            LinkedList
            HashMap
            • 0
              Как было сказано в начале, статья — не является подробным обзором, а лишь краткий справочник. И, как Вы могли заметить, я указал эти статьи в качестве дополнительного материала для более детального ознакомления
              • 0
                Да, не заметил сразу. Извиняюсь.
            • 0
              Также в статье можно было бы показать какие улучшения получили HashMap в java8.
              • 0
                Всё дело в том, что статья и так получилась довольно объёмная. А нововведения и изменения Collections Framework в Java 8 — это материал для другой вполне самодостаточной статьи. Тем более что целью статьи было всё же создать лаконичный справочник-памятку, а не подробный анализ.
                • 0
                  Но Вы приводите ссылку на более раннюю статью, в которой написано, что на один bucket приходится цепочка элементов. Важный момент в java8 — это то, что теперь bucket ссылается на бинарное дерево. и мне кажется, это стоит упоминания.
                  • 0
                    Биндерево только когда длинна цепочки превышает 8, что при адекватном лоад факторе и вменяемой реализации хеш-кода не происходит никогда.
                    • 0
                      Ну то что в Java 8 bucket — бинарное дерево — не совсем верно. Потому как деревом он становится только в том случае, если его размер больше TREEIFY_THRESHOLD. Причём данный процесс оборотный, то есть если по каким-то причинам bucket становится снова меньше, то он возвращается к «плоской» структуре (односвязный список). Но, так как в данной статье не объясняется внутреннее устройство коллекций, то для того чтобы связно изложить этот материал, прийдётся углубляться, что не помещается в рамки этого поста.

                      Но Ваше замечание действительно достойное внимания, потому считаю, что лучшим решением будет уточнить актуальность ссылки. Что и сделано.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.