Пользователь
0,0
рейтинг
16 сентября 2014 в 19:24

Разработка → Справочник по Java Collections Framework из песочницы

JAVA*
Данная публикация не является полным разбором или анализом (не покрывает пакет 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. Который является отличным дополнением к изложенному материалу.
Алексей Супрун @ASuprun
карма
7,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (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 становится снова меньше, то он возвращается к «плоской» структуре (односвязный список). Но, так как в данной статье не объясняется внутреннее устройство коллекций, то для того чтобы связно изложить этот материал, прийдётся углубляться, что не помещается в рамки этого поста.

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

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