Интерфейс Set в Java

Set<E> — это Collection<E> с одним дополнительным правилом: без дубликатов. Сам интерфейс почти не добавляет новых методов — он наследует add, remove, contains, size, iterator и остальные. Меняется только то, что обещают эти методы: add(e) возвращает false (и ничего не изменяет), если равный элемент уже есть в множестве; два множества equals, если содержат одинаковые элементы независимо от порядка; hashCode — это сумма хешей элементов, поэтому равные множества всегда дают одинаковый результат.

Этот простой контракт — «элементы уникальны» — оказывается именно тем, что нужно для проверки вхождения, дедупликации, пересечения/объединения и тысячи других паттернов, которые неудобно реализовывать через List.

Что считается дубликатом

Set определяет дубликаты по equals (а в хеш-based множествах — ещё и по hashCode как функции разбиения по бакетам). Это не сравнение по ссылке и не «выглядит одинаково при выводе». Если вы помещаете свой класс в Set, необходимо переопределить оба метода вместе; контракт рассматривается в главе equals and hashCode.

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("java");      // add returns false; the set still has one element
tags.add(new String("java")); // also false — equals, not reference

Распространённая ловушка: хранить изменяемые элементы и модифицировать их, пока они находятся в хеш-based множестве. Хеш элемента меняется, множество ищет его в неправильном бакете, и contains начинает давать неверный результат. Правило: если вы поместили объект в хеш-множество, считайте его эффективно неизменяемым с этого момента. У TreeSet та же ловушка, но с compareTo.

Четыре стандартные реализации

В java.util входят четыре реализации Set, покрывающие почти все сценарии использования:

Класс	Внутренняя структура	Порядок	Null-элементы	Типичное применение
`HashSet`	хеш-таблица	отсутствует	один `null` допускается	по умолчанию — быстрейшие проверки вхождения
`LinkedHashSet`	хеш-таблица + двусвязный список	порядок вставки	один `null` допускается	когда порядок итерации должен совпадать с порядком вставки
`TreeSet`	красно-чёрное дерево	естественный / компараторный порядок	`null` не допускается	когда нужна сортированная итерация или диапазонные запросы
`EnumSet`	битовый вектор	порядок объявления enum	`null` не допускается	для `Set<MyEnum>` — компактный, быстрый, упорядоченный

Первые три реализации рассматриваются в следующих трёх главах; EnumSet разбирается позже вместе с EnumMap.

Массовые операции: объединение, пересечение, разность

Set наследует четыре массовые операции из Collection, и на множестве они обретают классические теоретико-множественные значения:

addAll(other) — объединение (на месте). После вызова a содержит все элементы обеих сторон.
retainAll(other) — пересечение (на месте). После вызова a содержит только элементы, присутствовавшие и в other.
removeAll(other) — разность (на месте). После вызова a содержит только элементы, которых не было в other.
containsAll(other) — проверка подмножества. Возвращает true, если каждый элемент other есть в a.

Эти операции изменяют получатель. Если нужна неразрушающая версия, сначала скопируйте: Set<E> u = new HashSet<>(a); u.addAll(b);.

Равенство и хеш-коды множеств

Контракт Set для equals необычен: два множества равны, если содержат одинаковые элементы, независимо от порядка или типа реализации. HashSet, LinkedHashSet и TreeSet с одинаковыми элементами считаются равными друг другу.

Set<Integer> a = new HashSet<>(List.of(1, 2, 3));
Set<Integer> b = new TreeSet<>(List.of(3, 2, 1));
System.out.println(a.equals(b));   // true

Именно поэтому массовые операции и фабричные методы неизменяемых коллекций могут свободно работать с разными реализациями — соблюдается лишь правило «одинаковые элементы».

Фабрики для read-only и неизменяемых множеств

Начиная с Java 9 самый простой способ создать небольшое фиксированное множество — Set.of(...):

Set<String> primary = Set.of("red", "green", "blue");

Set.of возвращает неизменяемое множество, которое не допускает null-элементов и выбрасывает исключение, если при создании переданы дубликаты. Для защитного снимка существующего множества используйте Set.copyOf(existing) — тоже неизменяемое, тоже не принимает null.

Для представления, скрывающего мутации (исходное множество можно изменять, но через представление добавлять нельзя), используйте Collections.unmodifiableSet(s). Глава о неизменяемых коллекциях в этой части расскажет, когда что выбирать.

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

Программа ниже использует все четыре реализации, демонстрирует массовые операции на реальных данных и показывает, как различается порядок итерации у HashSet, LinkedHashSet и TreeSet.

java— editable, runs on the server

import java.util.*;

public class SetShowcase {
  public static void main(String[] args) {
    // --- Deduplication via add() returning false ---
    String[] tokens = { "java", "javascript", "java", "python", "java" };
    Set<String> seen = new HashSet<>();
    for (String t : tokens) {
      boolean added = seen.add(t);
      System.out.println("  add(" + t + ") -> " + added);
    }
    System.out.println("unique tokens: " + seen + "  size=" + seen.size());

// --- Set algebra ---
    Set<Integer> backend  = new HashSet<>(List.of(1, 2, 3, 4));
    Set<Integer> frontend = new HashSet<>(List.of(3, 4, 5, 6));

Set<Integer> union = new HashSet<>(backend);
    union.addAll(frontend);
    System.out.println("\nunion:        " + new TreeSet<>(union));

Set<Integer> intersection = new HashSet<>(backend);
    intersection.retainAll(frontend);
    System.out.println("intersection: " + new TreeSet<>(intersection));

Set<Integer> only = new HashSet<>(backend);
    only.removeAll(frontend);
    System.out.println("only backend: " + new TreeSet<>(only));

// --- equals across implementations ---
    Set<Integer> hs = new HashSet<>(List.of(1, 2, 3));
    Set<Integer> ts = new TreeSet<>(List.of(3, 2, 1));
    System.out.println("\nHashSet == TreeSet?  " + hs.equals(ts));

// --- Iteration order differs by implementation ---
    List<String> input = List.of("gamma", "alpha", "beta", "alpha");
    Set<String> h = new HashSet<>(input);
    Set<String> l = new LinkedHashSet<>(input);
    Set<String> t = new TreeSet<>(input);
    System.out.println("\nHashSet iter:        " + h + "  (unspecified)");
    System.out.println("LinkedHashSet iter:  " + l + "  (insertion)");
    System.out.println("TreeSet iter:        " + t + "  (sorted)");
  }
}

Что стоит отметить по результатам выполнения:

add вернул false для каждого дубликата \"java\" — вот как написать дедупликатор в две строки.
Объединение, пересечение и разность — это один вызов addAll/retainAll/removeAll каждый — копируйте сначала, если не хотите потерять оригинал.
Три реализации содержат одинаковые элементы и считаются равными, но порядок итерации у них очень разный. Выбирайте реализацию по нужному порядку, а не по привычке.

Что дальше

Наиболее распространённая реализация Set — основанная на хеш-таблице, и именно к ней обращаются по умолчанию. Следующая глава посвящена HashSet: мы рассмотрим коэффициент загрузки, перехеширование и что означает «почти константное время» на практике.

Практика

Что возвращает `set.add(x)`, если `x` уже является элементом `set`, согласно контракту `Set`?

`false`, и множество не изменяется`true`, и существующий элемент заменяется новым`null`, сигнализируя о дубликатеВыбрасывается `IllegalStateException`, поскольку множества отклоняют дубликаты