🔑 Раздел 10 · Вопрос #3

Как HashMap определяет, в какой bucket положить элемент

HashMap определяет индекс корзины (бакета) для сохранения или поиска элемента по строгому трехэтапному конвейеру:

🔑 HashMap equals hashCode 📄 Исходный Markdown

🟢 Junior Level

Краткий ответ для собеседования (30 секунд)

HashMap определяет индекс корзины (бакета) для сохранения или поиска элемента по строгому трехэтапному конвейеру:

  1. Вызов hashCode() ключа: среда исполнения запрашивает 32-битный «цифровой отпечаток» ключа (int h = key.hashCode()). Для ключа null хеш-код всегда принимается равным 0.
  2. Битовое перемешивание (Spread / Perturbation Function): старшие 16 бит исходного хеша складываются побитовым XOR с младшими 16 битами: h ^ (h >>> 16). Это защищает от коллизий на небольших таблицах, где индекс определяется только младшими разрядами.
  3. Накладывание битовой маски: индекс корзины вычисляется операцией побитового «И» с маской размера массива: index = (table.length - 1) & hash. Так как размер массива всегда является степенью двойки ($2^n$), эта операция математически эквивалентна остатку от деления $hash \pmod{table.length}$, но выполняется процессором мгновенно за 1 такт.

Сравнительная таблица методов адресации ячейки

Механизм вычисления индекса Формула Такты CPU Поведение с отрицательными хешами Использование
Побитовое «И» (Bitwise AND) (n - 1) & hash 1 такт Автоматически дает диапазон $[0, n-1]$ Стандарт HashMap (требует $n = 2^k$)
Остаток от деления (Modulo) hash % n 20–40 тактов (idiv) Возвращает отрицательный индекс! Устаревший подход, требует Math.abs
Универсальное хеширование Murmur3 / CityHash 5–15 тактов Требует отдельного seed и рандомизации Удалено из Java 8 в пользу деревьев

Пошаговый расчет индекса на Java 21

public class BucketCalculationDemo {
    public static void main(String[] args) {
        String key = "interview";
        int capacity = 16; // Емкость таблицы по умолчанию

        // Шаг 1: Исходный hashCode
        int h = key.hashCode(); // 1421060965 (двоичное: 01010100 10110001 01100111 01100101)

        // Шаг 2: Функция перемешивания (Spread)
        int hash = (key == null) ? 0 : h ^ (h >>> 16);

        // Шаг 3: Наложение битовой маски (n - 1 = 15 = 0000 1111)
        int index = (capacity - 1) & hash;

        System.out.println("Исходный hashCode: " + h);
        System.out.println("Перемешанный hash: " + hash);
        System.out.println("Итоговый индекс корзины (0..15): " + index);

        // Особый случай: null-ключ всегда попадает в корзину 0
        int nullIndex = (capacity - 1) & 0;
        System.out.println("Индекс для null-ключа: " + nullIndex);
    }
}

🟡 Middle Level

Функция перемешивания (Perturbation Function): Зачем сдвиг на 16 бит

В классе java.util.HashMap функция вычисления хеша выглядит так:

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

Проблема без перемешивания:

Допустим, таблица имеет емкость $n = 16$. Маска (n - 1) равна $15$ (0000 0000 0000 0000 0000 0000 0000 1111_b).
При вычислении индекса через (n - 1) & hash участвуют только последние 4 младших бита. Старшие 28 бит хеша полностью отбрасываются.

Если у набора объектов ключи различаются только в средних или старших разрядах (например, последовательности чисел, кратные 16 или 32, адреса памяти, форматированные префиксы строк):

Key 1: 00110000 00000000 00000000 00000001 -> index = 1
Key 2: 01010000 00000000 00000000 00000001 -> index = 1
Key 3: 11110000 00000000 00000000 00000001 -> index = 1

Все эти элементы попадут в корзину 1, образовав гигантскую коллизию.

Как спасает h ^ (h >>> 16):

Тип int в Java имеет размерность ровно 32 бита. Беззнаковый сдвиг вправо h >>> 16 смещает верхнюю половину слова на место нижней. Побитовое исключающее «ИЛИ» (XOR) смешивает старшие 16 бит с младшими 16 битами. Теперь любое изменение в старших битах гарантированно изменит младшие биты, распределяя элементы равномерно по корзинам даже при примитивных хеш-кодах.

Кэширование хеша в ноде (Node.hash)

Каждый создаваемый узел Node<K,V> сохраняет вычисленный перемешанный хеш в неизменяемое поле:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // Кэшированное значение перемешанного хеша
    final K key;
    V value;
    Node<K,V> next;
    // ...
}

Зачем кэшировать хеш в узле:

  1. Быстрое отсечение при поиске и сравнении: при вызове get(key) в цепочке коллизий проверяется: 
    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

    Сравнение целых чисел p.hash == hash выполняется за долю наносекунды. Если хеши не совпали, тяжелый метод key.equals(k) (который у строк требует побайтового сравнения массивов byte[]) даже не вызывается!

  2. Мгновенный ресайз: при удвоении емкости таблицы пересчитывать key.hashCode() не требуется — берется сохраненное значение p.hash.

🔴 Senior Level

Проблема знакового бита и отрицательных hashCode()

В языке Java целое число int является знаковым (значения от $-2^{31}$ до $2^{31} - 1$). Метод hashCode() любого объекта может вернуть отрицательное число. Например:

"polygenelubricants".hashCode(); // -1257093246
Integer.valueOf(-42).hashCode(); // -42
Integer.MIN_VALUE;               // -2147483648

Почему классический оператор % опасен:

Если попытаться вычислить индекс через остаток от деления:

int index = hash % table.length; // -42 % 16 = -10 (ОТРИЦАТЕЛЬНЫЙ ИНДЕКС!)

Попытка доступа к table[-10] приведет к ArrayIndexOutOfBoundsException.
Попытка обойти это через Math.abs(hash) % table.length содержит скрытую мину: Math.abs(Integer.MIN_VALUE) возвращает отрицательное число (Integer.MIN_VALUE), так как положительный аналог не помещается в 32-битный int!

Битовая маска как элегантное решение:

При маске (n - 1) & hash: Число (n - 1) при степени двойки (например, $16 - 1 = 15$) имеет вид: 00000000 00000000 00000000 00001111
Старший знаковый бит маски всегда равен 0. Поэтому побитовое AND гарантированно обнуляет знак любого отрицательного числа, возвращая строго неотрицательный индекс в диапазоне от 0 до n - 1.

Эволюция защиты от Hash DoS: Отмена MurmurHash из Java 7

В Java 7u6 для защиты веб-серверов от DoS-атак (когда атакующий отправлял тысячи параметров с коллидирующими хешами) инженеры Oracle добавили альтернативное хеширование строк на базе 32-битного алгоритма MurmurHash3 с рандомизированной солью (hashSeed), включавшееся при превышении порога jdk.map.althashing.threshold.

Почему в Java 8 это решение было полностью удалено:

  1. Нестабильность порядка: рандомизированный hashSeed приводил к тому, что порядок обхода мапы менялся между запусками JVM, ломая сериализацию и клиентские тесты.
  2. Оверхед на вычисление: MurmurHash3 требовал десятков инструкций CPU на каждый вызов.
  3. Красно-черные деревья (Treeification): в Java 8 было принято стратегическое архитектурное решение: оставить быструю детерминированную функцию (h ^ (h >>> 16)), а деградацию времени поиска при коллизиях с $O(n)$ до $O(\log n)$ устранить на уровне структуры данных с помощью сбалансированных деревьев TreeNode.

Архитектурный разбор выражения поиска ключа HotSpot

Классическая строчка кода из HotSpot HashMap.getNode():

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

представляет собой шедевр микрооптимизации, выстроенный строго по возрастанию вычислительной сложности:

  1. p.hash == hash (Самое дешевое): сравнение примитивов в регистрах процессора (1 такт). Отсекает $99.99\%$ чужих узлов в корзине.
  2. (k = p.key) == key (Сравнение ссылок): проверяет идентичность указателей в куче. Если передан тот же самый объект (например, статическая строка-константа), дорогой equals не вызывается.
  3. key != null && key.equals(k) (Самое дорогое): вызывается виртуальный метод equals(), производящий глубокое посимвольное или полейное сравнение данных только тогда, когда хеши совпали, но ссылки на объекты разные.

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

1. 30-секундный эссенс (Elevator Pitch)

HashMap определяет корзину в три действия: берет key.hashCode(), перемешивает его функцией h ^ (h >>> 16) для влияния старших разрядов на младшие, и накладывает маску (table.length - 1) & hash. Использование битового AND вместо деления ускоряет расчет в 20–40 раз и автоматически нейтрализует отрицательные хеш-коды, не требуя Math.abs(). Вычисленный хеш сохраняется в поле Node.hash, исключая повторные пересчеты и отсекая несовпадающие ключи до вызова equals().

2. 4 каверзных вопроса с глубокими ответами

Вопрос 1: Что произойдет, если key.hashCode() вернет Integer.MIN_VALUE, и почему формула (n - 1) & hash безопасна?

Ответ: Значение Integer.MIN_VALUE в двоичном представлении равно 10000000 00000000 00000000 00000000. При традиционном делении MIN_VALUE % 16 или попытке взять Math.abs(Integer.MIN_VALUE) % 16 результат равен отрицательному числу (так как абсолютное значение от MIN_VALUE переполняет int и снова равно MIN_VALUE), что выбросило бы ArrayIndexOutOfBoundsException.
Формула (n - 1) & hash накладывает битовую маску, у которой все старшие биты (включая 31-й знаковый бит) равны нулю. В результате битового умножения отрицательное число гарантированно превращается в валидный положительный индекс без риска исключений.

Вопрос 2: Зачем HashMap сохраняет final int hash внутри объекта Node, если его всегда можно вызвать через key.hashCode()?

Ответ:

  1. Производительность поиска: вызов key.hashCode() — это виртуальный вызов метода. Если в корзине возникла цепочка коллизий, повторный вызов hashCode() для каждого узла тратил бы процессорное время. Сравнение уже сохраненного примитива p.hash == hash выполняется за 1 такт.
  2. Защита от изменений ключа: если ключ был мутабельным объектом и его состояние изменилось после вставки, key.hashCode() вернул бы новое значение. Сохраненный в Node первоначальный хеш позволяет мапе хотя бы корректно переместить ноду при ресайзе.
  3. Оптимизация ресайза: при удвоении таблицы разделение элементов на две корзины проверяется через (e.hash & oldCap) == 0 по сохраненному хешу без повторных вычислений.

Вопрос 3: Почему в Java 8 отказались от строкового хеширования MurmurHash (Alternative Hashing), появившегося в Java 7u6?

Ответ: Alternative Hashing генерировал случайный seed при старте JVM. Из-за этого порядок итерации строк в HashMap становился недетерминированным между запусками приложения, что приводило к трудноуловимым багам в клиентском коде, опиравшемся на порядок сериализации. Кроме того, расчет MurmurHash создавал постоянный оверхед по CPU. В Java 8 проблему DoS-атак на коллизии решили кардинально и детерминированно: внедрили красно-черные деревья при превышении 8 элементов в корзине, снизив время худшего сценария с катастрофического $O(n)$ до безопасного $O(\log n)$.

Вопрос 4: Как работает микрооптимизация сравнения ключа в выражении p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))?

Ответ: Проверка организована по принципу «Short-Circuit Evaluation» (короткое замыкание) от дешевого к дорогому:

  1. p.hash == hash: быстрейшее сравнение целых чисел в регистре CPU. Не совпало — сразу переход к следующей ноде.
  2. (k = p.key) == key: проверка равенства ссылок в памяти. Если ссылки равны (тот же самый объект в куче), метод equals() не вызывается вовсе.
  3. key != null && key.equals(k): вызывается только при совпадении хешей и несовпадении ссылок, минимизируя накладные расходы на тяжелые проверки равенства бизнес-сущностей.

3. Типичные ошибки и Red Flags

❌ “Индекс корзины вычисляется как hashCode % table.length.”
Правильно: Используется побитовое умножение (table.length - 1) & hash, где hash предварительно обработан функцией сдвига h ^ (h >>> 16).

❌ “Для ключа null вызывается null.hashCode().”
Правильно: Для null проверка выполняется явно: key == null ? 0 : .... null-ключ всегда имеет хеш 0 и гарантированно попадает в корзину с индексом 0.

❌ “Переопределение hashCode() гарантирует уникальность индекса корзины.”
Правильно: Даже если все объекты имеют уникальные 32-битные hashCode(), при маске из 16 корзин они проецируются всего в 4 бита, поэтому коллизии неизбежны по принципу Дирихле.

4. Связанные вопросы