🟢 Junior Level

HashMap определяет номер корзины (бакета) в два шага:

1. Берёт хеш-код ключа — вызывает key.hashCode(), который возвращает 32-битное число — «цифровой отпечаток» объекта. Хороший hashCode равномерно распределяет объекты по всему диапазону int, плохой — группирует их.
2. Перемешивает биты — делает XOR хеш-кода с самим собой, сдвинутым на 16 позиций
3. Накладывает маску — использует формулу (размер_массива - 1) & хеш

Простой пример:

String key = "hello";
int hash = key.hashCode();           // Например, 99162322
int index = (16 - 1) & hash;         // При размере 16: index = 2

Почему так быстро: Вместо деления (которое медленное) используется побитовое И (&), которое выполняется за 1 такт процессора.

🟡 Middle Level

Шаг 1: Функция перемешивания бит (Perturbation)

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

Зачем XOR и сдвиг на 16?

• Размер массива обычно мал (16, 32, 64…), поэтому для индекса используются только младшие биты
• Если hashCode() различается только в старших битах — будут коллизии
• Сдвиг >>> 16 перемещает старшие биты в младшие
• XOR подмешивает информацию из старших бит в младшие
• Результат: даже при плохом hashCode элементы распределятся равномерно

Почему именно XOR и сдвиг на 16? Функция перемешивания (в оригинале ‘perturbation function’ — от лат. ‘perturbare’, ‘перемешивать’) — её задача убедиться, что даже если hashCode() различается только в старших битах, после перемешивания различие окажется и в младших.

Шаг 2: Магия степени двойки

int index = (n - 1) & hash;

Если n = 16 (2^4):

n-1 = 15 => 0000 1111 (маска)
hash   => 1101 0110
&      => 0000 0110 (результат: 6)

Это математически эквивалентно hash % 16. & выполняется за 1 такт (побитовая операция), тогда как % требует деления — 10-50 тактов в зависимости от процессора.

Кэширование hashCode

String кэширует свой hashCode в приватном поле hash. При частых операциях с HashMap это даёт огромный прирост производительности.

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

1. Плохой hashCode — если всегда возвращает 1, все элементы попадут в один бакет
2. Изменяемый ключ — изменение полей ключа после put изменит хеш, и элемент станет недоступным

Не пытайтесь «улучшить» хеширование

Не создавайте экзотические формулы хеширования без профилирования. Стандартная spread-функция OpenJDK тщательно протестирована. Плохая «оптимизация» часто хуже дефолтной.

🔴 Senior Level

Internal Implementation

В исходном коде OpenJDK (HashMap.java):

// putVal метод:
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

Определение индекса происходит при каждой операции — get, put, remove. Поэтому оптимизация хеширования критична.

Почему степень двойки — обязательна

Если бы размер был 15 (не степень двойки):

n-1 = 14 => 0000 1110 (маска)

Младший бит всегда обнуляется — все нечётные бакеты (1, 3, 5…) никогда не используются. Это приводит к 50% потерь capacity и удвоенным коллизиям.

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

• Вычисление hash: O(1), 2 операции (XOR + сдвиг)
• Определение индекса: O(1), 2 операции (& и вычитание)
• Общий overhead: минимальный, но вызывается миллиарды раз в крупных приложениях

Edge Cases

1. key == null: hash(null) возвращает 0, null всегда в table[0]
2. hashCode() = константа: все элементы в одном бакете, деградация до O(n)/O(log n)
3. Строки с одинаковым hashCode: "Aa" и "BB" оба дают 2112 — это известная коллизия в Java

Security: Hash Flooding

Злоумышленник может подобрать ключи с одинаковым хешем. В Java 8+ treeification защищает от DoS, но нагрузка на CPU всё равно возрастает из-за балансировки дерева.

Оптимизация для Record

В Java 14+ типы record генерируют hashCode() автоматически на основе всех компонентов. Это гарантирует хороший контракт, но для сложных record-ов с полями-коллекциями hashCode может быть дорогим.

---

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

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

• Шаг 1: hash(key) = key.hashCode() ^ (key.hashCode() >>> 16) — spread-функция
• Шаг 2: index = (n-1) & hash — битовая маска вместо %
• XOR перемешивает старшие биты в младшие — защищает от плохих hashCode
• & выполняется за 1 такт, % требует 10-50 тактов
• String кэширует hashCode — повторные вызовы O(1)
• null даёт hash = 0, всегда в table[0]
• При степени двойки != 2^n формула ломается — нечётные бакеты не используются

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

• Почему именно XOR и сдвиг 16? — 32-битный int, половина битов старшие, половина младшие; XOR подмешивает старшие в младшие
• Что если hashCode = константа? — все элементы в одном бакете, деградация до O(n)
• Почему не использовать %? — деление медленное (10-50 тактов), & = 1 такт
• String “Aa” и “BB” дают одинаковый hashCode? — да, 2112 — это известная коллизия

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

• «HashMap использует hashCode напрямую» — нет, есть spread-функция
• «Индекс = hashCode % size» — нет, (n-1) & hash
• «Можно улучшить spread-функцию» — стандартная OpenJDK тщательно протестирована

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

• [[1. Как устроена HashMap внутри]]
• [[4. Что такое коллизия в HashMap]]
• [[7. Что такое контракт equals() и hashCode()]]
• [[15. Почему String часто используется как ключ в HashMap]]