Как устроена HashMap внутри?

🟢 Junior Level

HashMap — это коллекция в Java, которая хранит данные в формате “ключ-значение” (Map). Она позволяет очень быстро находить, добавлять и удалять элементы по ключу.

Основная идея: HashMap использует хеш-таблицу — внутренний массив бакетов (корзин).

Почему это быстро: В отличие от ArrayList, который перебирает все элементы (O(n)), HashMap по хешу идёт сразу в нужную ячейку — как по номеру ячейки камеры хранения, а не перебирая все камеры подряд. Когда вы добавляете элемент, HashMap вычисляет специальный номер (хеш) ключа и определяет, в какую корзину его положить. При поиске она снова вычисляет этот хеш и идёт сразу в нужную корзину.

Пример:

Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);  // hashCode("Alice") = 63154590 → index = 15 → table[15]
ages.put("Bob", 25);    // hashCode("Bob") = 66133 → index = 5 → table[5]
System.out.println(ages.get("Alice")); // 30 — тот же хеш, тот же индекс 15

Когда использовать:

Когда нужно быстро находить данные по ключу
Когда порядок элементов не важен
Когда нужен один из самых быстрых вариантов для поиска (в среднем O(1))

Когда НЕ использовать HashMap

Нужен порядок вставки — берите LinkedHashMap
Нужна сортировка по ключу — TreeMap
Многопоточный доступ — ConcurrentHashMap
Критична память при малом количестве элементов — ArrayList с линейным поиском может быть экономичнее

🟡 Middle Level

Как это работает внутри

HashMap состоит из нескольких ключевых полей:

transient Node<K,V>[] table; // Массив бакетов (инициализируется лениво при первом put)
int threshold;               // Порог расширения (capacity * loadFactor)
final float loadFactor;      // Коэффициент загрузки (по умолчанию 0.75)
transient int size;          // Текущее количество элементов

Механика put():

При первом put() создаётся массив из 16 бакетов (ленивая инициализация, Java 8+). В Java 7 массив создавался при конструировании.
Вычисляется hash(key) — перемешанный (spread) хеш-код ключа.

Перемешивание — старшие биты хеш-кода ‘смешиваются’ с младшими через XOR. XOR — побитовая операция: если биты разные → 1, одинаковые → 0. Это минимизирует коллизии даже при плохой hashCode-функции: разница в старших битах ‘переносится’ в младшие, которые используются для индексации.

Определяется индекс бакета: index = (n - 1) & hash
Если бакет пуст — создаётся новая Node
Если бакет занят — проверяется equals() для поиска существующего ключа
Если ключ найден — значение перезаписывается, если нет — добавляется новая нода

Механика get():

Вычисляется хеш ключа
Определяется индекс бакета
В бакете ищется элемент через equals()

Типичные ошибки

Использование mutable-объектов как ключей — если изменить поля ключа после put(), элемент станет недоступным
Непереопределённый hashCode при переопределённом equals — равные объекты попадут в разные бакеты
Конкурентный доступ — HashMap не потокобезопасна

Сравнение с альтернативами

Реализация	Сложность поиска	Порядок	Потокобезопасность
HashMap	O(1)	Нет	Нет
TreeMap	O(log n)	Сортировка	Нет
LinkedHashMap	O(1)	Порядок вставки	Нет
ConcurrentHashMap	O(1)	Нет	Да

🔴 Senior Level

Internal Implementation

Функция хеширования (spread):

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Операция XOR между старшими и младшими 16 битами минимизирует коллизии при небольших массивах, где индекс определяется только младшими битами через маску (n-1).

Определение индекса:

index = (n - 1) & hash;

Вместо % используется & — это работает в десятки раз быстрее. Требует, чтобы размер массива всегда был степенью двойки.

Архитектурные Trade-offs

Метод цепочек (Separate Chaining) vs Открытая адресация:

HashMap использует метод цепочек — коллизии разрешаются связными списками/деревьями в каждом бакете
✅ Плюсы: устойчив к плохим хеш-функциям, проще удаление
❌ Минусы: аллоцирует отдельные объекты Node (накладные расходы на память, плохая cache locality)
Открытая адресация (как в ThreadLocalMap) экономит память, но страдает от clustering

Treeification (Java 8+):

При 8 элементах в бакете и capacity >= 64 связный список превращается в красно-чёрное дерево.

Красно-чёрное дерево — сбалансированное бинарное дерево поиска, где каждая вершина ‘покрашена’ в красный или чёрный цвет. Правила раскраски гарантируют баланс: поиск всегда O(log n).

Гистерезис — зазор между порогами прямого (8 → дерево) и обратного (6 → список) преобразования. Это предотвращает ‘churn’ (дребезг) — когда структура бесконечно переключается туда-сюда при колебаниях нагрузки.

Сложность поиска в худшем случае: O(n) -> O(log n)
TreeNode занимает ~2x больше памяти, чем Node
Порог обратного преобразования: 6 элементов (гистерезис для предотвращения churn)

Edge Cases

Hash Flooding Attack — злоумышленник подбирает ключи с одинаковым хешем; до Java 8 это вызывало DoS через O(n); в Java 8+ защита через treeification
Concurrent resize — в Java 7 при параллельном ресайзе возникало зацикливание списка; в Java 8+ исправлено через tail insertion, но потеря данных всё ещё возможна
Null-ключ — всегда попадает в table[0], так как hash(null) = 0

Производительность

Средний случай: O(1) для get/put/remove
Худший случай: O(log n) (Java 8+), O(n) (Java 7)
Амортизированная стоимость put: O(1) (resize — O(n), но происходит редко)
Memory footprint: каждая Node — заголовок объекта + int hash + K key + V value + Node next ≈ 32-48 байт на запись (без учёта ключа/значения)

Resize Optimization

При удвоении массива (Java 8+) не нужно пересчитывать хеши. Проверяется один бит:

if ((e.hash & oldCap) == 0) {
    // Остаётся на том же индексе
} else {
    // Перемещается на oldIndex + oldCapacity
}

Production Experience

В высоконагруженных системах частые ресайзы вызывают latency spikes. Рекомендуется задавать initialCapacity = (expectedSize / 0.75) + 1, чтобы избежать O(n)-операций в runtime.

Best Practices для Highload

Используйте ConcurrentHashMap для многопоточного доступа
Предварительно рассчитывайте capacity
Используйте иммутабельные ключи с качественным hashCode
Избегайте null-ключей для лучшей переносимости

🎯 Шпаргалка для интервью

Обязательно знать:

HashMap = массив бакетов + связные списки/деревья (Java 8+)
put/get работают за O(1) в среднем случае
Ленивая инициализация: массив создаётся при первом put
Spread-функция: XOR старших и младших 16 бит для равномерного распределения
Индексация через (n-1) & hash — быстрее деления
При 8 элементах в бакете и capacity >= 64 — treeification (список → красно-чёрное дерево)
null-ключ допускается один, всегда в table[0]
Не потокобезопасна — для многопоточности ConcurrentHashMap

Частые уточняющие вопросы:

Почему capacity всегда степень двойки? — чтобы использовать быструю битовую маску вместо деления
Что такое load factor 0.75? — баланс между памятью и коллизиями, обоснован распределением Пуассона
Что будет при плохом hashCode? — все элементы в одном бакете, деградация до O(n) или O(log n)
Почему не использовать HashMap в многопоточности? — data race, потеря данных, corruption при resize

Красные флаги (НЕ говорить):

«HashMap использует деление для индексации» — нет, битовая маска
«HashMap потокобезопасна» — нет, это ConcurrentHashMap
«При 8 элементах всегда дерево» — только если capacity >= 64

Связанные темы:

[[2. Что такое bucket (корзина) в HashMap]]
[[4. Что такое коллизия в HashMap]]
[[5. Как HashMap обрабатывает коллизии]]
[[16. Что такое load factor в HashMap]]
[[20. Какова временная сложность операций get() и put() в HashMap]]