Set. Первое знакомство

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

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

В рамках сегодняшнего урока мы познакомимся с основными интерфейсами-наследниками Set’а и их методами, а также наиболее популярными реализациями этого типа коллекций.

Правда, устройство реализаций будем разбирать постепенно в дальнейшем – пока у нас недостаточно знаний, чтобы детально ознакомиться с внутренней кухней Set’ов.

Но сначала несколько слов о вариантах применения.

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

В конечном итоге, Set’ы применяются везде, где есть необходимость обработать массив уникальных данных (с точки зрения процента таких ситуаций, правильнее будет сказать «массив данных, где нет необходимости в элементах-дубликатах»). На практике – это абсолютное большинство задач.

На самом деле, даже те из задач (исключая, возможно, самые простые), которые мы ранее решали через массив, могут быть решены через те или иные реализации Set’ов. И в ряде случаев такое решение будет даже более удобным.

Интерфейс Set

Этот пункт будет очень коротким. Set как наследник Collection, наиболее близок к своему родительскому интерфейсу: у него вообще нет собственных методов, исключая статические. Лишь те, которые определены в Collection.

Статические же методы представлены перегруженными of() и методом copyOf(). Они уже знакомы нам по интерфейсу List и работают, в целом, по тем же принципам: возвращают неизменяемую коллекцию. В нашем случае – типа Set. Неизменяемость, в данном случае, означает невозможность изменения состава элементов – методы добавления и удаления элементов приводят к выбросу исключения.

Интерфейс SortedSet

Интерфейс, являющийся предком всех Set’ов, хранящих данные в упорядоченном виде. Правила игры при создании объектов Set’ов, реализующих этот интерфейс, обычно такие же, как и при использовании PriorityQueue – либо Set должен быть параметризован классом, реализующим Comparable, либо в конструктор должен быть передан компаратор.

Пренебрежение этими правилами, вероятнее всего, приведет к исключению при попытке обработки данного сета – включая добавление в него элементов.

Итак, какие же методы есть у данного интерфейса (честно говоря, они не слишком популярны, но иногда бывают нужны)?

Предлагаю ознакомиться с ними в статье на metanit (пока лишь пункт «SortedSet»): https://metanit.com/java/tutorial/5.5.php

По сути, все методы SortedSet сводятся либо к получения минимального/максимального элемента, либо к получению диапазона значений (меньших/больших заданного, между двумя заданными).

Эта функциональность может быть полезна для проектов, хранящих большое количество данных in memory (в памяти, в нашем случае – в переменных). Но в большинстве коммерческих проектов основное взаимодействие происходит с данными, хранящимися в базах данных (БД), откуда выбираются лишь необходимые в каждом конкретном случае наборы данных. Таким образом, для большинства проектов ценность специфических методов SortedSet не сильно высока. Что, впрочем, не отменяет того, что стоит помнить об их существовании.

Интерфейс NavigableSet

Является наследником SortedSet и выглядит куда более дружелюбной концепцией, нежели предок.

Причина такого заключения кроется в названии и методах – они дают достаточно гибкие возможности по получению элементов, так или иначе сравниваемых с другими элементами. Еще одним аргументом в пользу большего дружелюбия этого интерфейса может быть отсутствие публичных наследников (вернее, реализаций) SortedSet, исключая тех, которые реализуют NavigableSet.

Итак, методы, предоставляемые интерфейсом NavigableSet (пункт «NavigableSet»): https://metanit.com/java/tutorial/5.5.php

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

Получение меньшего/большего элемента, относительно переданного параметром: ceiling(), higher(), floor() и lower(). Используя их, помните, что объект, переданный параметром, может отсутствовать в Set’е. В зависимости от этого, поведение ceiling() и higher() (или floor() и lower()) может быть одинаковым или различным;
Имитация двунаправленной очереди: pollFirst() и pollLast(). Если обработка коллекции сводится к многократному вызову одного из этих методов – подумайте о том, чтобы использовать PriorityQueue;
SortedSet на максималках. headSet(), tailSet() и subSet() с дополнительным булевым параметром (или двумя). Перегружают соответствующие методы SortedSet, добавляя возможность включить в выборку (или исключить из нее) объект-ограничитель, если он есть в Set’е. Чем-то напоминает поведение элементов из первой группы;
Развернулся и алга. descendingSet().

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

Класс HashSet

Является одной из двух публичных реализаций интерфейса Set в java.util. Представляет собой неупорядоченный набор данных. Если вам нужна коллекция, которая просто хранит набор уникальных объектов и не предоставляет дополнительной функциональности – это ваш выбор.

Пример использования и описание конструкторов можно найти в статье: https://metanit.com/java/tutorial/5.4.php

Класс LinkedHashSet

Данный класс реализует интерфейс Set, а также является прямым наследником HashSet.

Конструкторы идентичны конструкторам предка.

Отличительной особенностью LinkedHashSet является то, что он сохраняет порядок добавления элементов. Т.е., при последовательной обработке (например, через foreach), элементы будут обработаны в порядке добавления.

В остальном не отличается от HashSet. Если зайти в исходники, вы увидите, что LinkedHashSet содержит лишь конструкторы и собственную реализацию метода spliterator(). Все остальное поведение реализовано в суперклассе.

Класс TreeSet

Является единственным публичным наследником NavigableSet в пакете java.util. Хранит элементы в упорядоченном (на основании компаратора или Comparable.compareTo()) виде. При последовательной обработке, элементы будут обработаны в порядке, определенным условием сортировки. Порядок добавления элементов не будет играть роли.

Более подробно с использованием TreeSet, а также с его конструкторами, предлагаю ознакомиться в статье (пункт TreeSet): https://metanit.com/java/tutorial/5.5.php

Другие реализации

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

Переходя к потокобезопасным вариантам, legacy-коллекций, соответствующих Set’у, нет (по крайней мере, в том виде, в котором мы рассматривали их ранее).

Из коллекций в java.util.concurrent стоит выделить ConcurrentSkipListSet. Реализует NavigableSet.

Аналог HashSet в java.util.concurrent тоже есть. Но собственного публичного класса у него нет, поэтому с этой реализацией мы познакомимся позже.

С теорией на сегодня все!

Переходим к практике:

Задача 1:

Реализуйте задачу из урока 40, используя Set, вместо Queue. Продумайте, как можно эффективно реализовать задачу, чтобы сохранить принцип FIFO при обработке заданий.

Задача 2:

Реализуйте задачу 2 из урока 26, используя Set.

Если что-то непонятно или не получается – welcome в комменты к посту или в лс:)

Канал: https://t.me/+relA0-qlUYAxZjI6

Мой тг: https://t.me/ironicMotherfucker

Дорогу осилит идущий!