Для чего полезен HashSet?

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

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

Как отвечать

HashSet хранит уникальные элементы и даёт проверку вхождения, добавление и удаление в среднем за постоянное время. Внутри это HashMap, где ваши элементы это ключи, а значение общая заглушка.

Для чего полезен на практике:

• проверка принадлежности: главный сценарий. Проверять contains в списке значит проходить его целиком, то есть O(n), а в цикле это уже квадрат. Замена списка на HashSet превращает такой код в линейный;
• удаление дубликатов: new HashSet<>(list) за один проход;
• запоминание увиденного: обход графа, поиск первого повторяющегося элемента, дедупликация потока;
• операции над множествами: retainAll даёт пересечение, removeAll разность, addAll объединение.

Требования, без которых он работает неправильно:

• корректные equals и hashCode. Они должны быть согласованы: равные объекты обязаны иметь равный хеш. Забыли переопределить hashCode, и одинаковые по смыслу объекты окажутся в разных корзинах, а множество наполнится дублями;
• элементы не должны меняться после добавления в полях, участвующих в хеше. Изменили поле, и объект остался в старой корзине: contains его больше не найдёт, а удалить его не получится.

Чего он не даёт: порядок не гарантирован и может меняться при перестроении таблицы. Нужен порядок вставки, берут LinkedHashSet, нужна сортировка, берут TreeSet ценой логарифма. Допускается один null.

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

Переопределяют equals без hashCode.

Кладут в множество изменяемый объект и меняют его.

Полагаются на порядок обхода.

Продолжают искать в списке там, где нужно множество, и получают квадратичную сложность.