HashMap в Java: как устроена внутри - Вопросы

Внутри HashMap лежит массив Node<K,V>[] table — бакеты. Ячейка массива либо пуста (null), либо хранит первый узел цепочки. Узел Node содержит хеш ключа, сам ключ, значение и ссылку next на следующий узел того же бакета; он же реализует Map.Entry, поэтому entry.setValue() меняет значение прямо в карте.

Длина таблицы — всегда степень двойки, по умолчанию 16; массив создаётся лениво, при первом put(). Хеш вычисляется один раз и хранится в узле: при поиске сначала сравниваются числа hash, и только при совпадении вызывается equals(). С Java 8 слишком длинная цепочка превращается в красно-чёрное дерево из узлов TreeNode.

Сначала метод hash() перемешивает биты: h ^ (h >>> 16), где h = key.hashCode(). Затем индекс берётся по младшим битам: index = (n - 1) & hash, где n — длина таблицы. Для null-ключа хеш равен 0, поэтому он всегда лежит в бакете 0.

Перемешивание нужно, потому что в маленькой таблице индекс зависит только от нескольких младших бит: ключи Integer 0, 65536 и 131072 без него легли бы в один бакет 0, а после hash() попадают в бакеты 0, 1 и 2.

Когда n — степень двойки, n - 1 состоит из одних единиц (15 = 0b1111), и hash & (n - 1) даёт тот же результат, что остаток от деления, но без деления и без проблем с отрицательными хешами. Поэтому HashMap округляет ёмкость вверх до степени двойки и растёт только удвоением.

put(key, value) вычисляет hash(key), при необходимости создаёт таблицу через resize() и находит бакет (n - 1) & hash. Если бакет пуст, туда кладётся новый узел. Иначе метод идёт по цепочке и для каждого узла проверяет p.hash == hash && (p.key == key || key.equals(p.key)): нашёлся равный ключ — значение заменяется, старое возвращается, размер не меняется.

Если равного ключа нет, новый узел добавляется в конец цепочки (в Java 7 — в начало), size увеличивается, и при size > threshold вызывается resize(). Метод возвращает null.

Коллизия — это попадание разных ключей в один бакет, например у строк "Aa" и "BB" одинаковый хеш-код 2112. Коллизии нормальны: ключи различаются через equals(), но чем их больше, тем медленнее поиск.

Коэффициент загрузки (load factor, по умолчанию 0,75) задаёт порог threshold = capacity * loadFactor. Как только число пар становится больше порога, HashMap создаёт массив вдвое длиннее и переносит в него узлы: для карты по умолчанию (ёмкость 16, порог 12) это происходит на 13-м элементе.

hashCode() при этом повторно не вызывается — хеш хранится в узле. Новый индекс зависит от одного бита hash & oldCap: если он 0, узел остаётся в бакете j, если 1 — переезжает в j + oldCap.

Если размер известен заранее, используют HashMap.newHashMap(n) (Java 19) или new HashMap<>((int) Math.ceil(n / 0.75)); new HashMap<>(n) вырастет раньше, чем в неё поместятся n пар. Уменьшаться таблица не умеет: после remove() и clear() длина массива сохраняется.

С Java 8 (JEP 180) слишком длинная цепочка в бакете превращается в красно-чёрное дерево: когда в бакете больше 8 узлов (TREEIFY_THRESHOLD = 8) и таблица содержит не меньше 64 бакетов (MIN_TREEIFY_CAPACITY = 64). При меньшей таблице вместо дерева выполняется resize(). Если при resize в дереве остаётся 6 узлов и меньше (UNTREEIFY_THRESHOLD = 6), оно снова становится списком.

Благодаря деревьям худший случай get() и put() — O(log n) вместо O(n) до Java 8; в среднем операции по-прежнему O(1). Узлы дерева упорядочиваются по хешу, а при равных хешах — через compareTo(), если ключи реализуют Comparable. Ещё одно изменение Java 8: новые узлы добавляются в конец цепочки, а при resize порядок узлов сохраняется — в Java 7 одновременный resize из двух потоков мог замкнуть список в кольцо.