🟢 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]]