Как устроен HashMap в Java: внутри, коллизии, equals/hashCode
Устройство: массив бакетов
Внутри HashMap — массив «корзин» (bucket). При put(key, value):
- считается
key.hashCode(), доп. перемешивается (чтобы старшие биты влияли на выбор бакета); - по хэшу выбирается индекс бакета:
hash & (n-1), где n — размер массива (степень двойки); - в бакете ищется ключ по
equals; если такой есть — значение перезаписывается, иначе добавляется новая запись.
Аналогия: библиотека.
hashCode — номер стеллажа (быстро находим нужный), equals — сверка конкретной книги на полке. Без правильного стеллажа книгу пришлось бы искать по всей библиотеке — это O(n).Коллизии: список, потом дерево
Если в один бакет попадают разные ключи (коллизия), они складываются в связный список. Когда список в бакете дорастает до 8 элементов (и массив ≥ 64), он превращается в красно-чёрное дерево — поиск в бакете становится O(log k) вместо O(k). Это защита от вырождения при плохих хэшах или хэш-атаках.
Load factor и resize
Когда заполнено больше loadFactor (по умолчанию 0.75) от ёмкости, массив увеличивается вдвое, и все записи перераспределяются (rehash). Resize — дорогая операция; если знаешь размер заранее, задай начальную ёмкость, чтобы избежать лишних расширений.
Контракт equals/hashCode — почему обязателен
Если положить ключом свой объект и не переопределить
equals/hashCode (или сделать их несогласованными) — «одинаковые» объекты попадут в разные бакеты, и get не найдёт значение. Правило: равные объекты обязаны иметь равный hashCode. Обратное не требуется.Частые вопросы на собеседовании
— Сложность get/put у HashMap?
В среднем O(1); в худшем O(log n) (дерево в бакете) или O(n) при плохом хэше без дерева.
— Что будет, если hashCode всегда возвращает 0?
Все ключи в одном бакете → HashMap выродится в список/дерево, операции станут O(n)/O(log n).
— HashMap потокобезопасен?
Нет. Для конкурентного доступа — ConcurrentHashMap (сегментированная/по-бакетная синхронизация, без блокировки на чтение).
Ещё разборы
Читайте также
Spring на собеседовании: бины, прокси, транзакции — что спрашивают
Разбор Spring для собеседования: жизненный цикл бина, как работают прокси, где ловушки @Transactional. Вопросы с коротки…Многопоточность в Java: вопросы на собеседовании и короткие ответы
Разбор ключевых тем многопоточности Java — потоки, блокировки, пулы, race condition — с вопросами и ответами, которые ре…Пул соединений с БД: как устроен HikariCP и почему он быстрее всех
Разбор пула соединений: зачем нужен, как работает HikariCP изнутри, настройка maximumPoolSize, утечки соединений и типич…ReadWriteLock и striped locking: когда synchronized уже не хватает
Разбираем ReentrantReadWriteLock, StampedLock и striped locking — как масштабировать блокировки под высокий read-нагрузк…SQL на собеседовании: вопросы и задачи для бэкендера
Разбор SQL-секции на бэкенд-собеседовании: задачи на JOIN, GROUP BY, дубликаты, топ-N и нарастающий итог, вопросы про ин…Партиции, офсеты и consumer lag в Kafka: как не терять сообщения
Разбор внутреннего устройства Kafka: партиции, офсеты, lag, коммиты и типичные ошибки при обработке сообщений на собесед…
Разбор Spring для собеседования: жизненный цикл бина, как работают прокси, где ловушки @Transactional. Вопросы с коротки…Многопоточность в Java: вопросы на собеседовании и короткие ответы
Разбор ключевых тем многопоточности Java — потоки, блокировки, пулы, race condition — с вопросами и ответами, которые ре…Пул соединений с БД: как устроен HikariCP и почему он быстрее всех
Разбор пула соединений: зачем нужен, как работает HikariCP изнутри, настройка maximumPoolSize, утечки соединений и типич…ReadWriteLock и striped locking: когда synchronized уже не хватает
Разбираем ReentrantReadWriteLock, StampedLock и striped locking — как масштабировать блокировки под высокий read-нагрузк…SQL на собеседовании: вопросы и задачи для бэкендера
Разбор SQL-секции на бэкенд-собеседовании: задачи на JOIN, GROUP BY, дубликаты, топ-N и нарастающий итог, вопросы про ин…Партиции, офсеты и consumer lag в Kafka: как не терять сообщения
Разбор внутреннего устройства Kafka: партиции, офсеты, lag, коммиты и типичные ошибки при обработке сообщений на собесед…