Якщо два об’єкти рівні за equals(), що можна сказати про їх hashCode()

Якщо два об'єкти рівні за equals(), що можна сказати про їх hashCode()

Якщо два об'єкти рівні за методом equals() (o1.equals(o2) == true), то їхні геш-коди ОБОВ'ЯЗКОВО повинні бути абсолютно однаковими (o1.hashCode() == o2.hashCode()).

🟢 Junior Level

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

Якщо два об’єкти рівні за методом equals() (o1.equals(o2) == true), то їхні геш-коди ОБОВ’ЯЗКОВО повинні бути абсолютно однаковими (o1.hashCode() == o2.hashCode()).

Це сувора вимога офіційної специфікації мови Java (java.lang.Object). Вона безпосередньо обумовлена архітектурою геш-таблиць, де пошук у HashMap та HashSet є двоетапним:

Перший етап (грубий і надшвидкий): за числовим значенням hashCode() визначається номер кошика (бакета).
Другий етап (точний): усередині знайденого бакета шукається конкретний вузол за допомогою виклику equals().

Якщо для логічно рівних об’єктів повернути різні геш-коди, HashMap обчислить для них різні індекси бакетів. У результаті пошук раніше доданого об’єкта здійснюватиметься в зовсім іншому кошику, метод get() поверне null, а колекція HashSet збереже дублікат.

Порівняльна таблиця логічних наслідків і залежностей

Твердження	Істинність	Чому саме так	Архітектурний наслідок у Java
$A.\text{equals}(B) \implies \text{hash}(A) == \text{hash}(B)$	✅ ІСТИНА (Обов’язково)	Пряма вимога контракту специфікації	Гарантує пошук в одному кошику (бакеті)
$\text{hash}(A) == \text{hash}(B) \implies A.\text{equals}(B)$	❌ ХИБНІСТЬ (Не обов’язково)	Колізія (різні об’єкти ділять один геш)	Розв’язується ланцюжками або червоно-чорними деревами
$A.\text{equals}(B) == \text{false} \implies \text{hash}(A) \ne \text{hash}(B)$	❌ ХИБНІСТЬ	Геші можуть збігатися у нерівних об’єктів	Звичайна геш-колізія
$\text{hash}(A) \ne \text{hash}(B) \implies A.\text{equals}(B) == \text{false}$	✅ ІСТИНА (Контрапозиція)	Різні геші математично гарантують нерівність	Миттєве відсіювання чужих об’єктів за 1 такт CPU

Демонстрація на Java 21

import java.util.HashMap;
import java.util.Objects;

public class EqualsHashCodeContractDemo {

    public record CorrectUser(int id, String name) {}

    public static void main(String[] args) {
        // Створюємо два логічно еквівалентні об'єкти в різних ділянках пам'яті купи (heap)
        CorrectUser u1 = new CorrectUser(101, "Alice");
        CorrectUser u2 = new CorrectUser(101, "Alice");

        // 1. Перевіряємо рівність за equals:
        System.out.println("u1.equals(u2): " + u1.equals(u2)); // true

        // 2. Їхні hashCode() ЗОБОВ'ЯЗАНІ повністю збігатися:
        System.out.println("Геші однакові: " + (u1.hashCode() == u2.hashCode())); // true

        // 3. Коректна поведінка в HashMap:
        HashMap<CorrectUser, String> cache = new HashMap<>();
        cache.put(u1, "VIP-Session");

        // Отримуємо значення за ДРУГИМ екземпляром-ключем u2:
        String session = cache.get(u2);
        System.out.println("Отримана сесія: " + session); // "VIP-Session" (успішно знайдено!)
    }
}

🟡 Middle Level

Фатальні наслідки порушення правила: $equals \implies hashCode$

Якщо розробник перевизначить equals(), але залишить дефолтний hashCode() від класу Object, кожен новий екземпляр класу отримуватиме унікальний identityHashCode.

Що ламається в системі:

Втрата елементів у HashMap (map.get(key) == null):
```
Map<MyKey, String> map = new HashMap<>();
map.put(new MyKey(1), "Found");
map.get(new MyKey(1)); // Поверне null!
```
Перший ключ потрапив, наприклад, у бакет 3. Другий ключ (хоч і рівний першому за equals()) обчислив інший геш і попрямував до бакета 11, який виявився порожнім.
Дублювання даних у HashSet:
Колекція HashSet реалізована поверх внутрішньої HashMap (з фіксованим dummy-значенням PRESENT). Якщо геші об’єктів відрізняються, вони потраплять у різні бакети і обидва додадуться до колекції. У результаті розмір множини зросте, порушуючи базовий інваріант унікальності.
Витоки пам’яті (Memory Leaks):
Спроба викликати map.remove(new MyKey(1)) не знайде вузол у цільовому бакеті та поверне null. Старий запис назавжди залишиться висіти в пам’яті всередині таблиці.

Гешування специфічних примітивів у JDK: `Double` та `Float`

При ручній реалізації hashCode() для дробових чисел неприпустимо виконувати просте приведення до цілого числа ((int) value), оскільки, наприклад, числа 1.2 та 1.8 отримають однаковий геш 1.

У стандартній бібліотеці JDK використовується бітове перетворення згідно зі стандартом IEEE 754:

// Із реалізації Double.hashCode():
public static int hashCode(double value) {
    long bits = doubleToLongBits(value);
    return (int)(bits ^ (bits >>> 32));
}

Метод Double.doubleToLongBits() зводить усі варіації NaN до єдиного канонічного бітового представлення, усуває приховані колізії та гарантує повну узгодженість між Double.valueOf(Double.NaN).equals(...) та hashCode().

🔴 Senior Level

Ефект Гейзенбага (Heisenbug) у високонавантажених системах

Найпідступніша властивість порушення контракту $equals \implies hashCode$ полягає в тому, що помилка часто не відтворюється в модульних тестах і маскується під час локальної розробки:

Нехай об'єкт A дорівнює об'єкту B за equals(), але:
hash(A) = 17 (бінарно: 0001 0001_b)
hash(B) = 33 (бінарно: 0010 0001_b)

У локальному тесті (таблиця початкової місткості 16):
- Індекс для A: 17 & 15 = 1
- Індекс для B: 33 & 15 = 1
- Випадковий збіг бакета! Геші були різними, проте побітова маска 0000 1111 відкинула старші біти. Обидва об’єкти потрапили в один кошик, метод equals() повернув true, і юніт-тест успішно пройшов! Інженер впевнений, що код абсолютно робочий.
У Production під навантаженням:
- Кількість записів перевищує поріг threshold, і HashMap подвоює місткість до 32 (n - 1 = 31 = 0001 1111_b).
- Індекс для A: 17 & 31 = 17
- Індекс для B: 33 & 31 = 1
- Об’єкти розлітаються по різних бакетах. Продакшн раптово повертає null та втрачає сесії клієнтів. Такі помилки називають «гейзенбагами», оскільки їх прояв залежить від динамічного стану таблиці.

Оптимізація відсіювання за контрапозицією: $\text{hash}_1 \ne \text{hash}_2 \implies o_1 \ne o_2$

За законами класичної логіки пряме твердження: $A \implies B \quad (equals \implies hashCode)$ строго еквівалентне закону контрапозиції: $\neg B \implies \neg A \quad (hash_A \ne hash_B \implies !equals)$

Це логічне правило лежить в основі екстремальної продуктивності платформи Java:

// Перевірка вузла в HotSpot HashMap.getNode():
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

Завдяки гарантії контрапозиції JVM спочатку порівнює два 32-бітні регістри процесора (p.hash == hash). Якщо вони не рівні, середовище виконання математично гарантує, що об’єкти не рівні за equals(), не витрачаючи час на дорогий виклик віртуального методу equals().

🎯 Шпаргалка для інтерв’ю

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

Якщо два об’єкти рівні за equals(), їхні hashCode() зобов’язані бути абсолютно однаковими. Зворотне твердження є хибним: однакові геш-коди не гарантують рівності об’єктів (це колізія). Якщо рівні об’єкти повертають різні геш-коди, вони потраплять у різні бакети HashMap: метод get() поверне null, а в HashSet виникнуть дублікати. Закон контрапозиції ($hash_1 \ne hash_2 \implies o_1 \ne o_2$) дозволяє HashMap відсіювати невідповідні об’єкти всього за 1 машинний такт процесора ще до виклику equals().

2. 4 каверзні питання з глибокими відповідями

Питання 1: Що відбудеться в `HashSet`, якщо додати два об’єкти, у яких `equals() == true`, але `hashCode()` повертає різні значення?

Відповідь: HashSet усередині використовує екземпляр HashMap, де збережені елементи є ключами, а значенням виступає константа-маркер PRESENT. Під час додавання другого об’єкта HashSet обчислить його геш. Оскільки геш відрізняється від першого, мапа помістить другий об’єкт в інший бакет. У підсумку HashSet збереже обидва логічно однакові об’єкти, грубо порушивши інваріант унікальності множини, а виклик set.size() поверне 2 замість 1.

Питання 2: Як ефект випадкового збігу бакета маскує порушення контракту `hashCode()` у тестах і чому він «вибухає» в продакшені?

Відповідь: У невеликих мапах (місткість 16) індекс бакета визначається лише молодшими 4 бітами (& 15). Якщо у рівних об’єктів різні геші випадково збіглися в молодших 4 бітах (наприклад, 17 і 33), вони потраплять в один бакет. Усередині бакета метод equals() поверне true, і юніт-тест завершиться успіхом. Проте у продакшені під час збільшення кількості записів відбувається rehashing (місткість зростає до 32, 64 тощо). Маска починає враховувати 5-й та 6-й біти, об’єкти гарантовано розлітаються по різних бакетах, і мапа перестає знаходити записи.

Питання 3: Чи зобов’язані два об’єкти з однаковим `hashCode()` бути рівними за `equals()`?

Відповідь: Категорично ні. Збіг гешів у нерівних об’єктів називається колізією. Діапазон hashCode() обмежений 32 бітами ($2^{32} \approx 4.3 \times 10^9$), тоді як кількість потенційних станів об’єктів нескінченна (принцип Діріхле). Однаковий геш зобов’язує HashMap лише розмістити їх в одному бакеті, де вони будуть розрізнятися за допомогою equals().

Питання 4: Як правильно реалізувати `hashCode()` для полів типів `double` та `float`?

Відповідь: Не можна застосовувати звичайне приведення до цілого типу (втрата точності дробової частини) або порівняння через ==. Для float використовується Float.floatToIntBits(f), а для double — Double.doubleToLongBits(d) із XOR-згорткою старших та молодших 32 бітів (int)(bits ^ (bits >>> 32)). Ці методи стандартизують представлення значення NaN (Not a Number) та коректно розрізняють +0.0 і -0.0, гарантуючи точну узгодженість між Double.equals() та hashCode().

3. Типові помилки та Red Flags

❌ «Якщо об’єкти рівні за equals, їхні геші МОЖУТЬ бути однаковими (бажано).»
Правильно: Вони ЗОБОВ’ЯЗАНІ бути суворо однаковими. Це непорушний контракт специфікації мови.

❌ «Якщо геші однакові, то й об’єкти гарантовано рівні за equals.»
Правильно: Це груба помилка плутанини причини та наслідку. Однаковий геш — це лише колізія.

❌ «Використання фізичної адреси в пам’яті як основи для бізнес-гешу.»
Правильно: Бізнес-геш повинен будуватися виключно на полях, які беруть участь у порівнянні equals().