Что происходит в HashMap при коллизии ключей?
Коллизии кладутся в один bucket; HashMap ищет нужный ключ через equals, а длинную цепочку (≥8 при таблице ≥64) превращает в красно-чёрное дерево.
Подробно
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.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗Новый ключ перезаписывает старый, раз у них один hashCode
- ✓Ключи кладутся в один bucket и различаются через equals; длинная цепочка становится деревом
- ✗HashMap сразу увеличивает таблицу вдвое, чтобы ключи разошлись
- ✗Второй ключ ищет следующую свободную ячейку массива (открытая адресация)
Что спросят дальше
- Как связаны equals и hashCode?
- Когда происходит resize HashMap?
Разбор темы
- HashMap изнутри: бакеты, treeify, resize
Таблица бакетов, перемешивание хеша и индекс, превращение цепочки в дерево, ресайз и load factor, контракт ключа.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.