HashMap изнутри: бакеты, treeify, resize

Таблица бакетов

HashMap хранит данные в массиве Node[] table — это «бакеты» (корзины). Каждый Node держит hash ключа, сам ключ, значение и ссылку next на следующий узел в том же бакете.

Длина таблицы всегда степень двойки. Это позволяет вычислять индекс бакета быстрой битовой операцией index = (n - 1) & hash вместо дорогого деления по модулю.

Перемешивание хеша

Перед вычислением индекса hashCode ключа «перемешивается»: hash = h ^ (h >>> 16). Поскольку индекс берёт только младшие биты ((n-1) & hash), без перемешивания старшие биты hashCode не влияли бы на бакет, и хеши, различающиеся только сверху, давали бы коллизии.

XOR со сдвигом «подмешивает» старшие биты в младшие, снижая кластеризацию при посредственных hashCode — дёшево и эффективно.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// индекс бакета: (table.length - 1) & hash

Коллизии и treeify

Ключи с одинаковым индексом попадают в один бакет и образуют связный список. Поиск в нём линейный, поэтому при плохом распределении производительность деградирует.

Чтобы ограничить деградацию, длинная цепочка превращается в красно-чёрное дерево (treeify) при ≥ 8 узлах в бакете, но только если таблица уже ≥ 64; иначе вместо treeify делается resize. При уменьшении дерево разворачивается обратно в список при ≤ 6 узлах. В дереве поиск — O(log n), и для упорядочивания узлов используются hash и, при возможности, Comparable ключа.

Resize и load factor

threshold = capacity × loadFactor (по умолчанию 0.75). Как только size превышает threshold, таблица удваивается, и элементы перераспределяются. 0.75 — компромисс: меньше даёт меньше коллизий, но больше памяти и ресайзов; больше экономит память ценой длинных цепочек. Распределение по Пуассону показывает, что при 0.75 длинные бакеты крайне редки.

При удвоении узел остаётся в текущем бакете или уезжает в бакет index + oldCapacity — это решает один «новый» бит хеша, поэтому перераспределение дешевле полного пересчёта. Если итоговый размер известен, задавайте начальную ёмкость, чтобы избежать серии ресайзов.

Контракт ключа

Корректность HashMap держится на контракте equals/hashCode: равные ключи обязаны иметь равный hashCode, иначе put и get «разойдутся» по разным бакетам и значение потеряется.

Ключи должны быть фактически неизменяемыми по полям, участвующим в hashCode: если у лежащего в карте ключа изменить такое поле, его хеш-бакет перестанет соответствовать, и элемент станет недостижим. HashMap допускает один null-ключ (бакет 0) и null-значения.

Как отвечать на собеседовании

Эталонный разбор: таблица степени двойки → индекс (n-1)&hash → перемешивание h^(h>>>16) → коллизии списком → treeify при 8 и таблице ≥64 → resize при load factor 0.75 с делением бакета по одному биту. Свяжите всё с контрактом equals/hashCode и неизменяемостью ключа — это уровень, на котором видно, что человек реально шарит.