Как устроен HashMap внутри? Что происходит при put и get, и что такое тремификация корзин?
Короткий ответ
- Внутри — массив корзин (bucket), индекс считается из hashCode ключа
- Коллизии решаются связным списком внутри корзины
- С Java 8 длинная корзина (8+) превращается в красно-чёрное дерево
- При заполнении выше load factor 0.75 массив удваивается, элементы перераспределяются
- get: hashCode → индекс → поиск по equals внутри корзины
- Средняя сложность O(1), в худшем случае O(log n) благодаря деревьям
HashMap — массив корзин с разрешением коллизий списком или деревом, расширяющийся при превышении load factor.
Как сказать вслух
пример ответаHashMap хранит данные в массиве корзин. Когда я кладу пару ключ-значение, у ключа берётся hashCode, из него вычисляется индекс корзины. Если там уже есть элементы, идём по ним и сравниваем ключи через equals. С восьмой версии длинные цепочки коллизий превращаются в дерево, чтобы поиск не деградировал до линейного. А когда карта заполняется примерно на три четверти, массив удваивается и всё перераспределяется.
Подробный ответ
Основной ответ
HashMap — это массив Node[], размер которого всегда степень двойки. Для ключа вычисляется hashCode, дополнительно перемешивается (hash ^ (hash >>> 16)), и индекс берётся как hash & (length - 1). При коллизии элементы корзины образуют связный список; с Java 8, если в корзине 8+ узлов и таблица не меньше 64, список перестраивается в красно-чёрное дерево — поиск становится O(log n) вместо O(n). При превышении порога capacity * loadFactor (по умолчанию 0.75) происходит resize: массив удваивается, узлы раскладываются по новым корзинам. get повторяет путь: хеш, индекс, затем сравнение ключей сначала по хешу, потом через equals.
Ключевые моменты
- Индекс корзины. hash & (length - 1) — поэтому размер массива всегда степень двойки, а старшие биты подмешиваются сдвигом.
- Коллизии. Список → красно-чёрное дерево при 8+ элементах; защита от атак с одинаковыми хешами.
- Resize. Удвоение при превышении load factor 0.75; дорогая операция, поэтому ёмкость стоит задавать заранее.
- Требования к ключу. Корректные и согласованные equals/hashCode; изменяемый ключ после put «теряется» в карте.
Практический контекст
Это самый частый вопрос по коллекциям: через него проверяют и структуры данных, и контракт equals/hashCode. На практике знание помогает выбирать начальную ёмкость для больших карт, понимать, почему мутабельные ключи — беда, и когда взять LinkedHashMap (порядок) или TreeMap (сортировка). Сильный ответ связывает устройство с асимптотикой и упоминает тремификацию как защиту от деградации.
Частые ошибки
- Говорят, что HashMap сортирует или сохраняет порядок вставки — это LinkedHashMap/TreeMap
- Не могут объяснить, зачем ключу одновременно equals и hashCode
- Забывают, что resize не потокобезопасен — для конкурентного доступа нужен ConcurrentHashMap