Что такое java collections

Коллекционер хорошего кода: что нужно знать о Java Collections Framework

Java Developer в NIX

Работа с массивами данных, их структурирование, поиск соответствий между ними, фильтрация — все это основа любой программы, написанной на Java. Поэтому программистам важно иметь в своем арсенале инструменты, которые максимально упростили бы и структурировали работу с этими данными. Именно здесь и берут свое начало коллекции фреймворков на Java.

Что такое Collections Framework

Любая коллекция на Java строго структурирована: одни интерфейсы подчиняют другие, последние же — расширяют функционал своих «‎‎старших братьев» по иерархии.

Структура Java Collections Framework

В основе иерархической структуры Java Collections Framework лежит интерфейс Collection. Это главенствующий интерфейс. Общая коллекция вмещает в себя все остальные виды коллекций и позволяет работать с группами объектов благодаря основным методам, среди которых:

Интерфейс Collection наследуется от Iterable, а значит все подчиненные ему коллекции являются итерируемыми вне зависимости от типа их реализации. Благодаря этому в Collection вы можете получить итератор, который позволит вам пройтись по другим интерфейсам коллекций.

Итератор позволит пройтись по другим интерфейсам коллекций

Интерфейсу Collections подчинены три главных интерфейса:

Интерфейс Map работает с данными типа «‎‎ключ/значение». Он стоит в этом списке отдельно, и чуть позже я объясню, почему это так. А пока давайте пройдемся по основным типам коллекций и выясним, за что отвечает каждая из них.

Интерфейс List и его реализации — ArrayList и LinkedList

List — это упорядоченная коллекция, наиболее часто используемая в Java Collections Framework. Этот интерфейс контролирует, где вставлен каждый элемент списка. При работе с List пользователю доступны элементы списка по их целочисленному индексу (позиции в списке).

Работа с интерфейсом List

Интерфейс List имеет две стандартные реализации — ArrayList и LinkedList.

Смысл в том, что можно написать и другие реализации, но в JDK уже есть две, которые доступны «‎‎из коробки».

ArrayList содержит внутри себя массив, длина которого будет увеличиваться автоматически при добавлении в него новых элементов.

Вторая имплементация интерфейса List — класс LinkedList. Это список с двумя связями, где каждый элемент содержит ссылку на предшествующий и следующий элементы списка.

Вторая имплементация интерфейса List — класс LinkedList

ArrayList и LinkedList — идентичны, то есть их методы полностью совпадают. Они оба могут добавлять и извлекать элементы из любой части списка. Так в чем же отличие? Главная разница между ними в цикломатической сложности операций — количестве линейно независимых маршрутов, проходящих через код программы. Чем меньшее количество маршрутных точек будет проходить каждая отдельно взятая команда, тем быстрее будет работать программа.

Для наглядности различий в цикломатической сложности между двумя классами рассмотрим таблицу:

Различия в цикломатической сложности между классами LinkedList и ArrayList

Это же касается и операции remove : для класса LinkedList ее цикломатическая сложность будет вдвое меньше, чем для ArrayList. Забегая наперед скажу, что именно ArrayList используют в подавляющем случае работ в интерфейсе List.

Интерфейс Set

Set — это коллекция, которая не содержит повторяющихся элементов. Этот интерфейс создан для моделирования абстракций математического множества.

Иерархия Set включает в себя два интерфейса — SortedSet и NavigableSet — и три основных класса. О последних расскажу подробнее:

Интерфейс Queue

Все мы не любим очереди: кому нравится напрасно тратить свое время в ожидании чего-то? Но вы точно полюбите очереди, если научитесь с ним работать 🙂 В Java Collections Framework за работу с очередью отвечает интерфейс Queue, который имеет довольно простую иерархию:

Queue способен упорядочить элементы в очереди по двум основным типам:

Интерфейс Map

Это коллекция предназначена для работы с данными типа «‎‎ключ/значение». Под ключом мы имеем ввиду объект, который используем для извлечения данных, которые он в себе содержит. В структурном плане Map не наследует коллекцию Iterable и имеет ряд уникальных методов, характерных только для него.

У этого интерфейса схожая с Set структурная иерархия классов. Map реализуется с помощью четырех имплементаций: HashMap, TreeMap (о них я писал выше), LinkedHashMap и WeakHashMap:

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

При этом именно Java Collections Framework включает в себя весь функционал, необходимый для написания многозадачного кода любой сложности.

Правильное понимание принципов работы с коллекциями останется одним из главных навыков для качественного программирования на Java.

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Источник

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

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

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

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

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

Интерфейс Map [doc]

Hashtable — реализация такой структуры данных, как хэш-таблица. Она не позволяет использовать null в качестве значения или ключа. Эта коллекция была реализована раньше, чем Java Collection Framework, но в последствии была включена в его состав. Как и другие коллекции из Java 1.0, Hashtable является синхронизированной (почти все методы помечены как synchronized ). Из-за этой особенности у неё имеются существенные проблемы с производительностью и, начиная с Java 1.2, в большинстве случаев рекомендуется использовать другие реализации интерфейса Map ввиду отсутствия у них синхронизации.

WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references. Другими словами, Garbage Collector автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элеметна нет жёстких ссылок.

Интерфейс List [doc]

Реализации этого интерфейса представляют собой упорядоченные коллекции. Кроме того, разработчику предоставляется возможность доступа к элементам коллекции по индексу и по значению (так как реализации позволяют хранить дубликаты, результатом поиска по значению будет первое найденное вхождение).

ArrayList — как и Vector является реализацией динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Как можно догадаться из названия, его реализация основана на обычном массиве. Данную реализацию следует применять, если в процессе работы с коллекцией предплагается частое обращение к элементам по индексу. Из-за особенностей реализации поиндексное обращение к элементам выполняется за константное время O(1). Но данную коллекцию рекомендуется избегать, если требуется частое удаление/добавление элементов в середину коллекции. Подробный анализ и описание можно почитать в этом хабратопике.

Интерфейс Set [doc]

Представляет собой неупорядоченную коллекцию, которая не может содержать дублирующиеся данные. Является программной моделью математического понятия «множество».

Интерфейс Queue [doc]

Этот интерфейс описывает коллекции с предопределённым способом вставки и извлечения элементов, а именно — очереди FIFO (first-in-first-out). Помимо методов, определённых в интерфейсе Collection, определяет дополнительные методы для извлечения и добавления элементов в очередь. Большинство реализаций данного интерфейса находится в пакете java.util.concurrent и подробно рассматриваются в данном обзоре.

Заключение

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

При необходимости, разработчик может создать собственную реализацию, расширив или переопределив существующую логику, либо создав свою собственную реализацию подходящего интерфейса с нуля. Также существует некоторое количество готовых решений, которые являются альтернативой или дополнением к Java Collections Framework. Наиболее популярными являются Google Guava и Commons Collections.

Источник

Готовимся к собеседованию: что нужно знать о коллекциях в Java

Освежаем знания о коллекциях в Java и закрепляем их на практике.

Коллекции в Java — одна из любимых тем на собеседованиях Java-разработчиков любого уровня. Без них не обходятся и экзамены на сертификат Java Professional.

Вспомним основные типы коллекций, их реализации в Java, проверим понимание на практике.

Что такое коллекции

Коллекции — это наборы однородных элементов. Например, страницы в книге, яблоки в корзине или люди в очереди.

Инструменты для работы с такими структурами в Java содержатся в Java Collections Framework. Фреймворк состоит из интерфейсов, их реализаций и утилитарных классов для работы со списками: сортировки, поиска, преобразования.

Фулстек-разработчик. Любимый стек: Java + Angular, но в хорошей компании готова писать хоть на языке Ада.

Галопом по Европам, или Кратко об интерфейсах

Set — это неупорядоченное множество уникальных элементов.

Например, мешочек с бочонками для игры в лото: каждый номер от 1 до 90 встречается в нём ровно один раз, и заранее неизвестно, в каком порядке бочонки вынут при игре.

List — упорядоченный список, в котором у каждого элемента есть индекс. Дубликаты значений допускаются.

Например, последовательность букв в слове: буквы могут повторяться, при этом их порядок важен.

Queue — очередь. В таком списке элементы можно добавлять только в хвост, а удалять — только из начала. Так реализуется концепция FIFO ( first in, first out) — «первым пришёл — первым ушёл». Вам обязательно напомнят это правило, если попробуете пролезть без очереди в магазине:

А ещё есть LIFO (last in, first out), то есть «последним пришёл — первым ушёл». Пример — стопка рекламных буклетов на ресепшене отеля: первыми забирают самые верхние (положенные последними). Структуру, которая реализует эту концепцию, называют стеком.

Deque может выступать и как очередь, и как стек. Это значит, что элементы можно добавлять как в её начало, так и в конец. То же относится к удалению.

Будет здорово, если на собеседовании вы назовёте Deque правильно: «дэк», а не «д экью», как часто говорят.

Map состоит из пар «ключ-значение». Ключи уникальны, а значения могут повторяться. Порядок элементов не гарантирован. Map позволяет искать объекты (значения) по ключу.

Пример: стопка карточек с иностранными словами и их значениями. Для каждого слова (ключ) на обороте карточки есть вариант перевода (значение), а вытаскивать карточки можно в любом порядке.

Не путайте интерфейс Collection и фреймворк Collections. Map не наследуется от интерфейса Collection, но входит в состав фреймворка Collections.

Соберём всё вместе

❌ для ключейСохраняется порядок добавления❌✅✅❌

Такие разные реализации

Реализаций интерфейсов так много, что при желании можно организовать вполне себе упорядоченный Map и даже отсортированное множество. Пройдёмся кратко по основным классам.

Реализации List

Класс ArrayList подойдёт в большинстве случаев, если вы уже определились, что вам нужен именно список (а не Map, например).

Строится на базе обычного массива. Если при создании не указать размерность, то под значения выделяется 10 ячеек. При попытке добавить элемент, для которого места уже нет, массив автоматически расширяется — программисту об этом специально заботиться не нужно.

Список проиндексирован. При включении нового элемента в его середину все элементы с б ольшим индексом сдвигаются вправо:

При удалении элемента все остальные с бо́льшим индексом сдвигаются влево:

Класс LinkedList реализует одновременно List и Deque. Это список, в котором у каждого элемента есть ссылка на предыдущий и следующий элементы:

Благодаря этому добавление и удаление элементов выполняется быстро — времязатраты не зависят от размера списка, так как элементы при этих операциях не сдвигаются: просто перестраиваются ссылки.

На собеседованиях часто спрашивают, когда выгоднее использовать LinkedList, а когда — ArrayList.

Правильный ответ таков: если добавлять и удалять элементы с произвольными индексами в списке нужно чаще, чем итерироваться по нему, то лучше LinkedList. В остальных случаях — ArrayList.

В целом так и есть, но вы можете блеснуть эрудицией — рассказать, что под капотом. При добавлении элементов в ArrayList (или их удалении) вызывается нативный метод System.arraycopy. В нём используются ассемблерные инструкции для копирования блоков памяти. Так что даже для больших массивов эти операции выполняются за приемлемое время.

Реализации Queue

Про одну из них, LinkedList, мы рассказали выше.

Класс ArrayDeque — это реализация двунаправленной очереди в виде массива с переменным числом элементов.

Новые значения можно добавлять в начало или конец списка, и удалять оттуда же. Причём эти операции выполняются быстрее, чем при использовании LinkedList.

Класс PriorityQueue — упорядоченная очередь. По умолчанию элементы добавляются в естественном порядке: числа по возрастанию, строки по алфавиту и так далее, либо алгоритм сравнения задаёт разработчик.

Этот класс может быть полезен, например, для нахождения n минимальных чисел в большом неупорядоченном списке:

Такая реализация выгоднее по скорости и объёму памяти, чем подход с сортировкой первоначального списка.

Реализации Set

Класс HashSet использует для хранения данных в хеш-таблице. Это значит, что при манипуляциях с элементами используется хеш-функция — hashCode() в Java.

Хеш-таблица — структура данных, в которой все элементы помещаются в бакеты (buckets), соответствующие результату вычисления хеш-функции.

Например, администратор в гостинице может класть ключ в коробку с номером от 1 до 9, вычисляя его по такому алгоритму: складывать все цифры номера, пока не получится одноразрядное число.

Здесь алгоритм вычисления — хеш-функция, а результат вычисления — хеш-код.

Тогда ключ от номера 356 попадёт в коробку 5 (3 + 5 + 6 = 14; 1 + 4 = 5), а ключ от номера 123 — в коробку с номером 6.

Добавление, поиск и удаление элементов при такой организации происходит за постоянное время, независимо от числа элементов в коллекции.

О классе TreeSet вспоминают в тех случаях, когда множество должно быть упорядочено. Каким образом упорядочивать — определяет разработчик при создании нового TreeSet. По умолчанию элементы располагаются в естественном порядке. Организованы они в виде красно-чёрного дерева.

Реализации Map

Класс HashMap хранит данные в виде хеш-таблицы, как и HashSet. Более того, HashSet внутри использует HashMap. При этом ключом выступает сам элемент.

Класс TreeMap строится тоже на базе красно-чёрного дерева. Элементы здесь упорядочены (в естественном или заданном при создании порядке) в каждый момент времени. При этом вставка и удаление более затратны, чем в случае с HashMap.

Класс LinkedHashMap расширяет возможности HashMap тем, что позволяет итерироваться по элементам в порядке их добавления. Как и в LinkedList, здесь каждая пара-значение содержит ссылку на предыдущий и последующий элементы.

Ещё один хитрый вопрос на собеседовании: в каких коллекциях допускаются null-элементы?

Ответ: почти во всех, но нельзя добавлять null-значения в упорядоченные структуры, которые при добавлении нового элемента используют сравнение.

Обоснование: мух советуют отделять от котлет — иными словами, нельзя сравнивать принципиально разные, несопоставимые вещи. Так же и в Java невозможно понять, что больше: null или число 1, или null или строка «hello».

Поэтому null-значения запрещены в TreeMap и TreeSet.

Ещё они недопустимы в ArrayDeque, так как методы этого класса (например, poll() — удаление элемента из начала очереди) используют null как признак пустоты коллекции.

Попрактикуемся

Чтобы убедиться, что вы не просто вызубрили теорию, а хорошо понимаете предмет, на собеседовании вам могут предложить задания вроде «что произойдёт при выполнении кода»

Разберём типовые задачи на понимание коллекций.

Задачи для ArrayList

Что будет напечатано после выполнения кода ниже:

Правильный ответ: test2:test4:test1:test4:test2:test3:

Элементы в ArrayList нумеруются начиная с нуля. Поэтому элемент с номером 1 — это test2.

Следующим действием мы добавляем строку «test4» в ячейку с индексом 1. При этом элементы с бо́льшим индексом сдвигаются вправо.

Вторая часть вывода ( test4) показывает, что теперь по индексу 1 извлекается именно test4.

Далее мы обходим все элементы списка и убеждаемся, что они выводятся именно в порядке добавления.

Что будет выведено при выполнении кода:

Правильный ответ: 2:2

Первая часть понятна: добавили два элемента, поэтому размер списка равен двум. Остаётся вопрос: почему не был удалён «test1»?

Перед удалением элемента его нужно найти в списке. ArrayList и остальные коллекции, которые не используют алгоритмы хеширования, применяют для поиска метод equals().

Строки сравниваются по значению, поэтому «test3» не эквивалентно «test1» и «test2». А раз ни один элемент не соответствует критерию поиска, ничего не удалится — размер списка останется прежним.

Проверьте себя: подумайте, что произойдёт, если вместо

Задачи для Set

Что выведет фрагмент кода ниже:

Правильный ответ: 3:, а дальше точно не известно.

Так как строки сравниваются по значению, а дубликаты во множествах недопустимы, второй «Иван» не станет частью множества. В итоге размер множества будет равен 3.

В каком порядке будут выведены элементы множества — определённо мы сказать не можем: во множествах порядок добавления не сохраняется.

Что выведет фрагмент кода:

Правильный ответ: 4.

Как же так, ведь во множество должны попадать уникальные элементы?

Прежде чем добавить новый элемент в множество, вычисляется его hashCode() — чтобы определить бакет, куда он может быть помещён.

Если бакет пуст, элемент будет добавлен. Иначе уже добавленные элементы с таким же значением хеша сравниваются с кандидатом при помощи метода equals(). Если дубликат не найден, новый элемент становится частью множества. Он попадёт в тот же бакет.

Мы добавляем в Set объекты типа Person — созданного нами класса. Этот класс, как и все ссылочные типы, наследуется от класса Object.

Так как мы не переопределили метод hashCode(), будет использована родительская реализация. В ней хеш вычисляется на основе данных адреса (реализация зависит от JVM).

Метод equals() тоже не переопределён. В классе-родителе этот метод просто сравнивает ссылки на объекты. Это значит, что даже если хеш случайно совпадёт для каких-то из четырёх элементов, equals() в любом случае вернёт false.

Таким образом, каждый из четырёх кандидатов попадёт в множество.

Проверьте себя: изменится ли что-нибудь, если переопределить hashCode() вот так:

А если ещё и equals() переопределить, как на фрагменте ниже:

Источник

Коллекции в Java: о чём многие забывают

Из опыта code-review и ответов на StackOverflow набралось немало моментов, касающихся Java Collections API, которые мне казались очевидными, но другие разработчики о них почему-то не знали или знали, но не чувствовали уверенности их применять. В этой статье я собираю в общую кучу всё, что накопилось.

Содержание:

List.subList

Про это уже писали, но стоит повторить. Наверно, самый недооценённый метод из Collections API. Бывает, что надо каким-то образом обработать часть списка (например, в алгоритмах семейства «разделяй и властвуй» или при распараллеливании задачи). Многие создают метод или класс, который завязывается на три параметра: List, from и to:

Так незачем делать. Реализации алгоритма должно быть плевать, что она обрабатывает часть списка. Пишите:

Даже если у вас всё в одном методе, удобнее воспользоваться расширенным циклом for, чем возиться с индексами:

Кроме того, subList — полнофункциональный список, он работает и на запись, внося соответствующие изменения в родительский список. Нужно удалить много элементов из середины списка? Ничего нет проще:

У популярных реализаций вроде ArrayList это выполняется очень быстро.

Надо выяснить, начинается ли список с определённых элементов? И тут subList в руки!

Надо добавить в один список все элементы другого списка за исключением первого? И тут subList придёт на помощь:

PriorityQueue

Если subList — самый недооценённый метод, то PriorityQueue — это, на мой взгляд, самый недооценённый класс. Многие сталкиваются с задачей отыскать, скажем, 10 минимальных значений большого несортированного списка. Чаще всего список сортируют и потом берут первые 10 значений. Если исходный список менять нельзя, придётся его ещё скопировать для сортировки. А ведь очередь с приоритетом легко справится с этой задачей:

Такой код в зависимости от данных может работать гораздо быстрее, чем сортировка. Например, для n = 10 и случайно заполненного списка из миллиона элементов очередь с приоритетом почти в сто раз обгоняет подход с сортировкой. При этом дополнительной памяти требуется O(n) и входные элементы можно обрабатывать в потоковом режиме (например, выбрать 10 наименьших чисел из входного файла).

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

EnumSet и EnumMap

До сих пор встречается код, где значения типа enum используют в качестве ключей в HashSet и HashMap. Хотя это работает, но оно неоправданно расточительно. Существующие специальные классы EnumSet и EnumMap значительно производительнее. Так если в enum не больше 64 разных значений, EnumSet хранит всё в одном поле типа long в битовой маске. EnumMap содержит все значения в обычном массиве той же длины, сколько элементов в enum, а ключи не хранит вовсе. Так как у каждого значения в enum есть порядковый номер ordinal(), можно легко перейти от enum-ключа к элементу массива. Также никогда не нужно менять размер массива.

Set.add(E) и Set.remove(E) возвращают булево значение

Часто вижу подобный код:

Не надо забывать, что операция добавления в Set возвращает true, если добавление успешно (то есть элемента не было) и false, если такой элемент уже был. Незачем усложнять код и два раза пробивать элемент по хэш-таблице или двоичному дереву, ведь можно написать:

Map.put(K, V), Map.remove(K), List.set(idx, E), List.remove(idx) возвращают предыдущий элемент

Из той же оперы ситуация. Методы, изменяющие или удаляющие элемент в коллекции возвращают предыдущее значение, и этим надо пользоваться. Не надо писать, например, так:

Map.keySet() и Map.values()

Многие почему-то забывают, что Map.keySet() и Map.values() возвращают отображения исходного Map, которые позволяют удалять элементы (если Map модифицируемый). Надо оставить в Map только записи с определёнными значениями (и любыми ключами)? Пожалуйста:

Arrays.asList может быть ключом

Arrays.asList() создаёт список из нужного числа элементов и у него как раз подходящие реализации equals и hashCode : никакой boilerplate не нужен. Так можно создать ключ любой длины, причём корректно обработаются null-значения и примитивы (брагодаря боксингу). Не сработает только, если вы хотите в составе ключа иметь массив.

Collections.min/max

К примеру, вам нужно найти ключ в Map, соответствующий максимальному значению. Пишите так:

Можно и через Stream API, но Collections.max() несколько быстрее. Если вы не можете использовать Java-8 и компараторы вроде Entry.comparingByValue() вам недоступны, их нетрудно написать.

Stack, Vector, Hashtable, LinkedList

Просто не используйте эти классы. Пользы от них никакой нет. Вместо Stack пользуйтесь ArrayDeque, вместо Vector — ArrayList, вместо Hashtable — HashMap. Если вам нужна потокобезопасность, они вам всё равно не помогут. Возможно, в девятке их всё-таки пометят @Deprecated (смотрите JEP 277).

На сегодня всё. Программируйте с удовольствием!

Источник