Як HashMap визначає в який бакет покласти елемент

HashMap визначає індекс кошика (бакета) для збереження або пошуку елемента за строгим триетапним конвеєром:

🟢 Junior Level

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

HashMap визначає індекс кошика (бакета) для збереження або пошуку елемента за строгим триетапним конвеєром:

Виклик hashCode() ключа: середовище виконання запитує 32-бітний «цифровий відбиток» ключа (int h = key.hashCode()). Для ключа null геш-код завжди приймається рівним 0.
Бітове перемішування (Spread / Perturbation Function): старші 16 бітів вихідного гешу додаються побітовим XOR із молодшими 16 бітами: h ^ (h >>> 16). Це захищає від колізій на невеликих таблицях, де індекс визначається лише молодшими розрядами.
Накладання бітової маски: індекс кошика обчислюється операцією побітового «І» з маскою розміру масиву: 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;
    // ...
}

Навіщо кешувати геш у вузлі:

Швидке відсікання при пошуку та порівнянні: при виклику get(key) у ланцюжку колізій перевіряється:
```
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
```
Порівняння цілих чисел p.hash == hash виконується за частку наносекунди. Якщо геші не збіглися, важкий метод key.equals(k) (який у рядків вимагає побайтового порівняння масивів byte[]) навіть не викликається!
Миттєвий ресайз: при подвоєнні місткості таблиці перераховувати 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 це рішення було повністю видалено:

Нестабільність порядку: рандомізований hashSeed призводив до того, що порядок обходу мапи змінювався між запусками JVM, ламаючи серіалізацію та клієнтські тести.
Оверхед на обчислення: MurmurHash3 вимагав десятків інструкцій CPU на кожен виклик.
Червоно-чорні дерева (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))))

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

p.hash == hash (Найдешевше): порівняння примітивів у регістрах процесора (1 такт). Відсікає $99.99\%$ чужих вузлів у кошику.
(k = p.key) == key (Порівняння посилань): перевіряє ідентичність вказівників у купі. Якщо передано той самий об’єкт (наприклад, статичний рядок-константу), дорогий equals не викликається.
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()`?

Відповідь:

Продуктивність пошуку: виклик key.hashCode() — це віртуальний виклик методу. Якщо в кошику виник ланцюжок колізій, повторний виклик hashCode() для кожного вузла витрачав би процесорний час. Порівняння вже збереженого примітиву p.hash == hash виконується за 1 такт.
Захист від змін ключа: якщо ключ був мутабельним об’єктом і його стан змінився після вставки, key.hashCode() повернув би нове значення. Збережений у Node первинний геш дозволяє мапі хоча б коректно перемістити ноду при ресайзі.
Оптимізація ресайзу: при подвоєнні таблиці розділення елементів на два кошики перевіряється через (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» (коротке замикання) від дешевого до дорогого:

p.hash == hash: найшвидше порівняння цілих чисел у регістрі CPU. Не збіглося — одразу перехід до наступної ноди.
(k = p.key) == key: перевірка рівності посилань у пам’яті. Якщо посилання рівні (той самий об’єкт у купі), метод equals() не викликається взагалі.
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 біти, тому колізії неминучі за принципом Діріхле.