Что такое коллизии и как они связаны с hashCode

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

Понимаете ли вы устройство хеш-таблицы в Java, а не только словарное определение коллизии, и знаете ли контракт между equals и hashCode, который на практике ломают чаще всего.

Как отвечать

Развести два уровня. Коллизия хеш-кодов это когда разные объекты дают одинаковое значение hashCode, и она неизбежна: объектов больше, чем значений типа int. Коллизия корзин это когда объекты попадают в одну ячейку таблицы, и случается она гораздо чаще, потому что индекс получают из младших битов хеша. Именно поэтому хеш перед этим перемешивают, подмешивая старшие биты к младшим.

Разрешаются коллизии в HashMap цепочкой внутри корзины. Когда цепочка становится длинной, а таблица достаточно большой, она перестраивается в сбалансированное дерево, и поиск в корзине из линейного превращается в логарифмический. Это защита от вырожденного случая, а не индульгенция плохому hashCode. Открытая адресация тоже существует, но применяется в других структурах.

Контракт стоит проговорить дословно: равные по equals объекты обязаны давать равный hashCode, обратное неверно. Поэтому оба метода переопределяют вместе и по одному и тому же набору полей, и в этот набор берут только то, что участвует в равенстве.

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

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

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

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