Set: HashSet, LinkedHashSet, TreeSet

Set поверх Map

HashSet внутри — это HashMap, где элементы множества лежат как ключи, а значением служит общий объект-заглушка PRESENT. Поэтому уникальность и производительность HashSet полностью определяются устройством HashMap.

Это объясняет, почему у Set нет доступа по индексу: под капотом хеш-таблица, а не последовательность.

// упрощённо изнутри HashSet:
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();
public boolean add(E e) { return map.put(e, PRESENT) == null; }

Три реализации

HashSet — без гарантий порядка, операции в среднем O(1). LinkedHashSet — сохраняет порядок вставки (поверх LinkedHashMap), почти та же скорость. TreeSet — упорядоченное множество поверх TreeMap, O(log n), с навигацией NavigableSet (floor/ceiling/subSet).

Выбор тот же, что и для соответствующих Map: нужен порядок вставки — LinkedHashSet, нужна сортировка и диапазоны — TreeSet, иначе HashSet.

Уникальность и контракт

В HashSet/LinkedHashSet уникальность определяется equals/hashCode элементов, в TreeSet — результатом сравнения (compareTo/compare). Положив объект с «плохим» equals/hashCode, легко получить дубликаты или потерю элементов.

Как и с ключами Map, изменять поля элемента, влияющие на хеш или сравнение, после добавления в Set нельзя — элемент станет недостижим.

Операции над множествами

Set умеет теоретико-множественные операции прямо из коробки: addAll — объединение, retainAll — пересечение, removeAll — разность. Читается это компактно, но у removeAll и retainAll есть ловушка производительности, о которой почти не пишут.

AbstractSet.removeAll выбирает направление обхода по размерам: если аргумент меньше самого множества, он перебирает аргумент и удаляет элементы; иначе перебирает своё содержимое и спрашивает contains у аргумента. Во втором случае всё упирается в скорость contains у переданной коллекции — а у списка это O(n).

Отсюда практическое правило: передавать в такие операции List нельзя, если он хоть сколько-нибудь большой. Обернуть его в HashSet — одна строка, которая превращает квадратичную операцию в линейную.

Set<Long> active = ...;      // 50 000 элементов
List<Long> banned = ...;     // 100 000 элементов — больше множества

active.removeAll(banned);                 // O(n*m): обход active и contains по списку
active.removeAll(new HashSet<>(banned));  // O(n+m): contains по хешу

null и неизменяемые множества

Правила про null у реализаций разные, и это регулярный источник NPE. HashSet и LinkedHashSet допускают ровно один null. TreeSet не допускает его вовсе: элемент нужно сравнивать, а сравнить null естественным порядком нельзя — получите NullPointerException уже на добавлении.

Фабрики Set.of строже всех: они запрещают null, а на повторяющемся элементе бросают IllegalArgumentException прямо при создании. Ещё одна их особенность специально сделана неудобной — порядок итерации у Set.of рандомизирован и меняется между запусками JVM, чтобы никто не начал на него полагаться.

Наконец, стоит различать копию и представление: Set.copyOf делает независимый снимок, а Collections.unmodifiableSet возвращает лишь неизменяемый вид поверх исходного множества. Если оригинал продолжают менять, изменения будут видны через «неизменяемую» обёртку.

EnumSet: множество на битовой маске

Для элементов-перечислений в JDK есть специализированная реализация, о которой часто забывают и зря кладут enum в HashSet.

EnumSet хранит множество как битовую маску: одно значение long на 64 константы, а для перечислений покрупнее — массив long. Принадлежность, добавление и удаление превращаются в побитовые операции, объединение и пересечение — в OR и AND над словами. Это быстрее хеш-таблицы и на порядок компактнее по памяти, а итерация идёт в порядке объявления констант.

Правило простое: если элементы — enum, берите EnumSet (и EnumMap для карт). Исключение только одно — null в EnumSet положить нельзя.

enum Role { USER, EDITOR, ADMIN }

EnumSet<Role> editors = EnumSet.of(Role.EDITOR, Role.ADMIN);
EnumSet<Role> all = EnumSet.allOf(Role.class);
EnumSet<Role> readers = EnumSet.complementOf(editors);  // {USER}

boolean canEdit = editors.contains(user.role());   // проверка бита

Как отвечать на собеседовании

Ключевой инсайт: HashSet — это HashMap с элементами-ключами. Дальше выбор реализации (Hash/Linked/Tree) и зависимость уникальности от equals/hashCode (или сравнения в TreeSet) показывают системное понимание, а не заучивание трёх классов.