Как работает HashMap
Вопрос
Расскажите, как работает HashMap: что происходит при put и get, как решаются коллизии и что будет при росте.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Массив корзин, индекс (n-1) & hash, hash с подмешанными старшими битами
Коллизии: цепочка, внутри сравнение hash и equals
Treeify при 8 узлах и таблице от 64, обратно при 6
Load factor 0.75, удвоение таблицы и перераскладка узлов
Требования к ключу: корректные equals/hashCode, неизменяемость
Не потокобезопасен, для потоков ConcurrentHashMap
Что могут спросить следом
- Почему размер таблицы степень двойки?
- Зачем деревья, если хорошие хеши дают короткие цепочки?
- Как ведёт себя null-ключ?
Разбор
HashMap это массив корзин, размер степень двойки. При put берётся hashCode ключа, к младшим битам подмешиваются старшие (h ^ h >>> 16), индекс считается как (n - 1) & hash, это дешёвая замена остатку от деления. Если корзина пуста, кладём узел. Если нет, идём по цепочке, сравнивая сначала хеш, потом equals: нашли ключ, заменяем значение, нет, добавляем узел. get идёт тем же путём. С Java 8 цепочка длиной 8 при таблице от 64 корзин превращается в красно-чёрное дерево, чтобы плохие хеши или атака коллизиями не давали O(n). Когда элементов больше capacity × 0.75, таблица удваивается, и узлы делятся по одному новому биту: остаются на месте или сдвигаются на старую ёмкость. Ключ должен иметь согласованные equals и hashCode и не меняться после вставки. Null-ключ разрешён и лежит в корзине 0. Для многопоточного доступа беру ConcurrentHashMap.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.