Какую коллекцию использовать для множества уникальных объектов в Java

Что проверяют

Знаете ли вы реализации Set и, главное, на чём держится уникальность. Почти всегда следом спрашивают про equals и hashCode или просят объяснить, что будет, если изменить объект после добавления в HashSet.

Как отвечать

Ответ по умолчанию: интерфейс Set, а реализацию выбирают по требованиям к порядку и многопоточности.

• HashSet: внутри HashMap, операции в среднем за O(1), порядок не гарантирован, допускает один null. Выбор по умолчанию;
• LinkedHashSet: то же плюс порядок вставки. С Java 21 реализует SequencedSet с getFirst(), getLast() и reversed();
• TreeSet: красно-чёрное дерево, O(log n), элементы отсортированы по Comparable или переданному Comparator. Даёт floor, ceiling, subSet для диапазонов;
• EnumSet: для перечислений, внутри битовая маска, быстрее и компактнее всех остальных;
• ConcurrentHashMap.newKeySet() или ConcurrentSkipListSet: для доступа из нескольких потоков, второй ещё и сортирует;
• Set.of(...): неизменяемое множество. На дубликате в аргументах бросает IllegalArgumentException, null не принимает.

Затем объясните механику. HashSet находит корзину по hashCode, а внутри неё сравнивает через equals. Поэтому в своём классе нужно согласованно переопределить оба метода, иначе два одинаковых по смыслу объекта окажутся в множестве дважды. Удобно брать record: для него equals и hashCode генерируются по всем компонентам. Можно добавить, что с Java 8 при большом числе коллизий корзина превращается в дерево, и худший случай становится O(log n), а не O(n).

Где спотыкаются

Переопределяют только equals. Объекты с разными хэшами попадают в разные корзины, и contains возвращает false для логически равного элемента.

Меняют поле, участвующее в hashCode, у объекта, который уже лежит в HashSet. Элемент остаётся в старой корзине, найти и удалить его больше нельзя.

Не знают, что TreeSet определяет уникальность через compareTo или компаратор, а не через equals. Компаратор, сравнивающий только по имени, склеит двух разных людей с одинаковым именем.