Получить доступ

Что происходит в HashMap при коллизии ключей?

MiddleКоллекции
Коротко

Коллизии кладутся в один bucket; HashMap ищет нужный ключ через equals, а длинную цепочку (≥8 при таблице ≥64) превращает в красно-чёрное дерево.

Так подсказку видит пользователь sotto на живом собеседовании — за пару секунд, пока вы думаете вслух.

Попробуйте сами

HashMap: put, коллизия и resize

Подробно

HashMap считает hash, выбирает bucket и сравнивает ключи внутри bucket через equals. Если ключ равен существующему — значение обновляется; если нет — добавляется новая запись. В Java 8+, когда цепочка в одном bucket достигает 8 элементов И таблица уже не меньше 64, она treeify-ится в красно-чёрное дерево (поиск O(log n) вместо O(n)); если таблица меньше 64, вместо дерева делается resize. При уменьшении до 6 элементов дерево возвращается в список.

Что хотят услышать

  • Bucket (обязательно) — По hashCode выбирается bucket; разные ключи могут попасть в один bucket.
  • Проверка equals (обязательно) — Внутри bucket ключи различаются через equals; равный ключ заменяет значение.
  • Tree bins — В Java 8+ длинная цепочка может превращаться в красно-чёрное дерево при достаточном размере таблицы.

Частые ошибки

  • Думать, что одинаковый hashCode означает равные объекты.
  • Забывать про equals при поиске внутри bucket.

Что спросят дальше

  • Как связаны equals и hashCode?
  • Когда происходит resize HashMap?

Разбор темы

Связанные вопросы

Закрытая бета

Подсказки на собеседовании — в реальном времени

sotto слышит вопрос интервьюера и показывает короткий ответ и план, как в блоке «Коротко». Оставьте контакт — пришлём доступ и промокод.

  • Промокод на 2 часа — сверх пробных 30 минут
  • Программа для Windows — скачать сразу, войти — через Яндекс ID или VK ID
  • Прямая связь с разработчиком: что улучшить — сделаем