Set

Определение и инвариант

Set<E> — множество: оно не содержит двух элементов, равных по своему контракту. Метод add возвращает false, если эквивалентный элемент уже присутствует.

Set<String> roles = new HashSet<>();
roles.add("reader"); // true
roles.add("reader"); // false

Равенство самих множеств не зависит от порядка обхода: два Set равны, если содержат одинаковые элементы.

Основные реализации

Реализация	Порядок	Операции	Основа
HashSet	не гарантирован	в среднем O(1)	хеш-таблица
LinkedHashSet	порядок вставки	в среднем O(1)	хеш-таблица и связный порядок
TreeSet	сортировка	O(log n)	сбалансированное дерево
EnumSet	естественный порядок enum	очень компактные операции	битовое представление

HashSet реализован поверх хеш-карты: элементы множества становятся ключами, а значения внутри карты — служебная заглушка. Это деталь реализации, но она объясняет зависимость от equals и hashCode.

Равенство, хеш и изменяемые элементы

Для HashSet должно выполняться правило: равные объекты имеют одинаковый hashCode.

record UserId(long value) {}
 
Set<UserId> ids = new HashSet<>();
ids.add(new UserId(42));
 
boolean exists = ids.contains(new UserId(42)); // true

Нельзя менять поля, участвующие в equals/hashCode, пока объект лежит в хеш-множестве. Иначе он физически останется в прежней корзине, но поиск по новому хешу его не найдёт.

Для TreeSet уникальность определяется сравнением компаратора или compareTo: если сравнение вернуло 0, второй объект считается дубликатом, даже когда equals возвращает false. Желательно, чтобы порядок был согласован с equals.

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

Set<String> actual = new HashSet<>(Set.of("A", "B", "C"));
Set<String> expected = Set.of("B", "C", "D");
 
Set<String> intersection = new HashSet<>(actual);
intersection.retainAll(expected); // [B, C]
 
Set<String> difference = new HashSet<>(actual);
difference.removeAll(expected);   // [A]
 
Set<String> union = new HashSet<>(actual);
union.addAll(expected);            // A, B, C, D

Копия нужна, если исходное множество нельзя изменять.

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

HashSet допускает один null, TreeSet с естественным порядком обычно не может его сравнить, а Set.of не принимает null и дубликаты. Это свойства реализаций, не общего интерфейса.

Ловушки

• Полагаться на порядок HashSet.
• Забывать переопределить hashCode вместе с equals.
• Менять ключевые поля объекта после добавления.
• Считать, что TreeSet определяет дубликат через equals.
• Создавать Set там, где количество повторений имеет смысл: множество потеряет эту информацию.

Вопросы на собеседовании

1. Как HashSet определяет, что элемент уже существует?
2. Чем отличаются HashSet, LinkedHashSet и TreeSet?
3. Что произойдёт, если изменить поле, участвующее в hashCode, у элемента множества?
4. Почему TreeSet может «потерять» объект, не равный по equals существующему?
5. Как получить пересечение и разность двух множеств?

Связанные заметки

Collection · Иерархия коллекций · Map · HashMap · Equals и hashCode · Comparator Java