Что происходит при коллизиях в HashMap

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

Знаете ли вы механику разрешения коллизий в конкретной реализации и понимаете ли, почему важен хороший hashCode.

Как отвечать

Коллизия это когда два разных ключа попадают в одну корзину. Индекс считается из хеша по остатку от размера таблицы, а размер невелик, поэтому совпадения неизбежны и это норма.

Что происходит дальше:

• ключи в корзине хранятся связным списком. При добавлении карта проходит по нему, сравнивая сначала хеши, потом equals. Нашёлся равный ключ, значение заменяется; не нашёлся, узел добавляется в конец;
• начиная с восьми элементов в корзине и при размере таблицы не меньше 64, список превращается в красно-чёрное дерево. Поиск в такой корзине становится логарифмическим вместо линейного. При уменьшении до шести узлов дерево сворачивается обратно;
• если таблица меньше 64, вместо превращения в дерево происходит её увеличение вдвое, потому что перераспределение обычно решает проблему дешевле.

Зачем это сделано: до Java 8 при плохом хеше карта вырождалась в список, и поиск становился линейным. Это была не только проблема производительности, но и уязвимость: подобрав ключи с одинаковым хешем, можно было положить сервер запросом с большим количеством параметров.

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

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

Считают коллизию ошибкой.

Не знают про превращение списка в дерево.

Забывают, что перед equals сравниваются хеши, и это делает проверку дешёвой.

Не могут объяснить, почему изменение ключа после вставки ломает поиск.