Как эффективно найти место для новой пары ключ-значение внутри бакета HashMap

Что проверяют

Знаете ли вы, как работает putVal в java.util.HashMap на самом деле, а не в учебном варианте с % и связным списком. Следом почти всегда спрашивают про resize и про то, когда бакет превращается в дерево.

Как отвечать

Путь новой пары:

• хэш: HashMap.hash() берёт key.hashCode() и подмешивает старшие биты в младшие, h ^ (h >>> 16). У ключа null хэш 0, он всегда в бакете 0;
• индекс: ёмкость всегда степень двойки, поэтому вместо деления берут (n-1) & hash. Это быстрее и не даёт отрицательных индексов;
• пустой бакет: туда кладётся новый Node, и всё. Сам массив создаётся лениво при первом put, по умолчанию на 16 ячеек;
• бакет занят: сначала сравнивается хэш и только при совпадении == или equals(). Ключ нашёлся, значение заменяется (при putIfAbsent нет). Не нашёлся, узел добавляется в хвост списка;
• дерево: когда список становится длиннее 8 узлов (TREEIFY_THRESHOLD), бакет превращается в красно-чёрное дерево, но только если таблица не меньше 64 (MIN_TREEIFY_CAPACITY), иначе вместо этого таблица расширяется;
• resize: если после вставки size превысил threshold (ёмкость на load factor 0.75, для 16 это 12), таблица удваивается. Узлы бакета делятся по биту hash & oldCap: остаются на месте или сдвигаются на oldCap, без пересчёта хэша.

Что зависит от вас: хороший hashCode(), согласованный с equals(), неизменяемые ключи и заранее заданный размер через HashMap.newHashMap(expected) (Java 19+), чтобы не платить за серию resize. Внутри дерева порядок идёт по хэшу, затем по compareTo, поэтому при массовых коллизиях помогает, если ключи реализуют Comparable.

Где спотыкаются

Пишут Math.abs(key.hashCode()) % length. Для Integer.MIN_VALUE метод Math.abs возвращает отрицательное число, и индекс вылетает за границы массива.

Говорят, что resize запускается по средней длине списков или по числу занятых бакетов. Порог считается от общего числа элементов size.

Утверждают, что дерево появляется всегда, как только в бакете больше 8 элементов, и забывают про условие на 64. На маленькой таблице длинная цепочка сначала приводит к расширению массива.