Почему у разных объектов могут быть одинаковые hashCode

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

Понимаете ли вы, что совпадение хеш-кодов это норма, а не дефект, и держите ли в голове контракт equals и hashCode. Вопрос простой на входе, но почти всегда служит трамплином. Следом спрашивают: что произойдёт с HashMap, если у всех ключей вернуть из hashCode() константу.

Как отвечать

• диапазон значений: hashCode() возвращает int, то есть около 4,3 миллиарда вариантов, а различных объектов может быть сколько угодно. Отобразить бесконечное множество в конечное без совпадений невозможно, коллизии заложены математикой;
• контракт: равные по equals объекты обязаны давать равный хеш. Обратное не требуется, разные объекты могут иметь общий хеш, и это законное поведение;
• живой пример: "Aa".hashCode() и "BB".hashCode() оба дают 2112, формула строки 31 * h + c порождает такие пары пачками;
• что делает HashMap: берёт хеш, домешивает старшие биты (h ^ (h >>> 16)) и берёт остаток по размеру таблицы. Номер корзины у двух ключей может совпасть, даже когда сами хеши разные;
• корзина: сначала связный список. При восьми элементах в одной корзине и таблице от 64 ячеек список превращается в красно-чёрное дерево, и поиск возвращается к логарифму.

Дальше про практику: коллизия ничего не теряет, элементы внутри корзины различит equals. Плохая хеш-функция бьёт по скорости, а не по корректности. Objects.hash(a, b) удобен, но создаёт массив на каждый вызов, поэтому в горячем коде его иногда раскрывают вручную. У record реализация генерируется компилятором по всем компонентам.

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

Называют hashCode адресом объекта в памяти. Адреса там нет: значение вычисляется один раз, сохраняется в заголовке объекта и не переживает перезапуск JVM.

Кладут в хеш изменяемое поле, потом правят объект после вставки в HashSet и не находят его. Ключ ищется в корзине по новому хешу, а лежит он в старой.

Переопределяют только equals, оставив хеш от Object. Два логически равных объекта попадают в разные корзины, и коллекция спокойно хранит дубликаты.