Почему в HashSet игнорируются одинаковые значения, а в HashMap значения перезаписываются?

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

Знаете ли вы, что обе коллекции это одна и та же хеш-таблица, и держите ли в голове контракт equals и hashCode. На Android вопрос обычно имеет второе дно: помните ли вы про цену такой таблицы в памяти.

Как отвечать

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

Добавление идёт так: считается hashCode(), по нему выбирается корзина, внутри корзины кандидаты сравниваются через equals(). Дальше поведение расходится:

• HashSet.add() при совпадении ничего не меняет и возвращает false, в множестве остаётся первый элемент;
• HashMap.put() при совпадении ключа заменяет значение и возвращает старое.

Тонкость, которую любят спрашивать следом: put заменяет значение, но не ключ. Объект-ключ в таблице остаётся тот, что положили первым, новый выбрасывается. Для множества это выглядит как «дубликат проигнорирован», хотя механизм тот же самый.

Set<String> s = new HashSet<>();
s.add("a"); // true
s.add("a"); // false, размер остался 1

Если контракт нарушен, например equals переопределён, а hashCode нет, два логически равных объекта попадут в разные корзины и спокойно уживутся в множестве.

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

Говорят «HashSet сравнивает элементы через equals». Сначала считается хеш, и если корзины разные, equals даже не вызовется. Отсюда правило: равные объекты обязаны давать равный хеш, обратное не требуется.

Второе: кладут в множество изменяемый объект и потом правят у него поле, которое участвует в hashCode. Элемент остаётся лежать в старой корзине, contains его больше не находит, и удалить штатно тоже нельзя.

Третье: тянут HashMap под десяток ключей в горячем коде экрана. Таблица держит массив корзин и отдельный узел на каждую запись. Для небольших коллекций в Android есть ArrayMap, а для целочисленных ключей SparseArray, который вдобавок не упаковывает ключи в объекты.