Как устроен 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 (сегментированная/по-бакетная синхронизация, без блокировки на чтение).