Якщо два об’єкти мають однаковий hashCode(), чи обов’язково вони рівні за equals()

Якщо два об'єкти мають однаковий hashCode(), чи обов'язково вони рівні за equals()

Ситуація, за якої два логічно різних об'єкти (a.equals(b) == false) повертають однакове цілочислове значення hashCode(), називається колізією геш-функції (Hash Collision). Це ці...

🟢 Junior Level

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

НІ, КАТЕГОРИЧНО НЕ ОБОВ’ЯЗКОВО!

Ситуація, за якої два логічно різних об’єкти (a.equals(b) == false) повертають однакове цілочислове значення hashCode(), називається колізією геш-функції (Hash Collision). Це цілком штатне, нормальне та математично очікуване явище під час роботи з будь-якими геш-таблицями в Java.

У специфікації мови Java (java.lang.Object) діє суворе одностороннє правило логічної імплікації:

Рівність за equals() $\implies$ Рівність за hashCode() (ОБОВ’ЯЗКОВА пряма вимога);
Рівність за hashCode() $\not\implies$ Рівність за equals() (Логічна рівність об’єктів НЕ гарантується).

Колізії є математично неминучими через принцип Діріхле (Pigeonhole Principle): метод hashCode() повертає 32-бітний примітив int (лише $2^{32} \approx 4.29 \times 10^9$ унікальних значень), тоді як простір можливих внутрішніх станів об’єктів у пам’яті JVM є нескінченним.

Приклади гарантованих колізій у стандартних класах JDK

public class StandardJdkCollisionsDemo {
    public static void main(String[] args) {
        // 1. Класична колізія рядків: "Aa" та "BB"
        // Формула String.hashCode(): 31 * char[0] + char[1]
        // "Aa": 31 * 65 + 97 = 2015 + 97 = 2112
        // "BB": 31 * 66 + 66 = 2046 + 66 = 2112
        String s1 = "Aa";
        String s2 = "BB";

        System.out.println("Геш s1: " + s1.hashCode()); // 2112
        System.out.println("Геш s2: " + s2.hashCode()); // 2112
        System.out.println("Рядки рівні за equals? " + s1.equals(s2)); // false!

        // 2. Довші рядки з ідентичним гешем: "Siblings" та "Teheran"
        System.out.println("Siblings hash: " + "Siblings".hashCode()); // 231609873
        System.out.println("Teheran hash: " + "Teheran".hashCode());   // 231609873

        // 3. Колізія чисел Long: 1L та 4294967297L (1 + 2^32)
        // Метод Long.hashCode() згортає 64 біти в 32: (int)(v ^ (v >>> 32))
        Long l1 = 1L;
        Long l2 = 4294967297L;
        System.out.println("l1 hash: " + l1.hashCode()); // 1
        System.out.println("l2 hash: " + l2.hashCode()); // 1
        System.out.println("Longs рівні за equals? " + l1.equals(l2)); // false!
    }
}

🟡 Middle Level

Двоступеневий фільтр пошуку в `HashMap`

Архітектура HashMap та HashSet спроектована з чітким урахуванням того, що нерівні об’єкти можуть мати однакові геш-коди:

                          Запит map.get(key)
                                   │
                                   ▼
          [ 1-й ЕТАП: hashCode() — Швидкий грубий фільтр ]
         Обчислення індексу бакета: index = (n - 1) & hash
                 Миттєво відсікає 99.9% чужих бакетів!
                                   │
                                   ▼
            [ 2-й ЕТАП: equals() — Точний повільний фільтр ]
                Пошук усередині знайденого бакета:
           Порівняння p.hash == hash && (p.key == key || key.equals(p.key))
           Точно ідентифікує цільовий об'єкт серед наявних колізій

Оновлення значення проти додавання колізії

Коли в HashMap викликається метод put(key, value) і геш ключа збігається з уже наявним у бакеті елементом, мапа обов’язково викликає equals():

Якщо key.equals(existingKey) == true:
Мапа визначає, що це один і той самий ключ. Значення наявного вузла перезаписується новим (node.value = value), а метод put() повертає старе значення. Кількість елементів (size) не змінюється.
Якщо key.equals(existingKey) == false:
Мапа фіксує колізію. Створюється новий вузол Node<K,V>, який додається в кінець однозв’язного списку бакета (Tail Insertion в Java 8+). У мапі тепер зберігаються обидва елементи, а лічильник записів інкрементується (size++).

🔴 Senior Level

Механізм розв’язання конфліктів у червоно-чорному дереві `TreeNode`

Що робить HashMap, коли в одному бакеті накопичується $\ge 8$ елементів з абсолютно однаковим значенням hashCode()?

Червоно-чорне дерево вимагає чіткого впорядкування вузлів ($<$ або $>$). Якщо геш-коди вузлів повністю ідентичні, бінарне розгалуження за значенням hash неможливе. HotSpot C2 вирішує цей тупик через такий багаторівневий арбітраж:

// Фрагмент логіки вставки в TreeNode (HotSpot HashMap):
int dir;
Class<?> kc;
// 1. Спроба порівняння через інтерфейс Comparable
if ((kc = comparableClassFor(k)) != null &&
    (dir = compareComparables(kc, k, pk)) != 0) {
    // Напрямок ліворуч/праворуч визначено методом compareTo()!
} 
// 2. Якщо Comparable відсутній або compareTo() повернув 0 (але equals == false)
else {
    // Рекурсивний обхід обох піддерев (find)
    // Якщо вузол не знайдено — детермінований арбітраж через System.identityHashCode:
    dir = tieBreakOrder(k, pk);
}

comparableClassFor: перевіряється, чи реалізує клас ключа інтерфейс Comparable<MyClass>. Якщо так, викликається метод k.compareTo(pk).
Фоллбек через tieBreakOrder: якщо клас не імплементує Comparable, JVM порівнює назви класів у вигляді рядків (getClass().getName()), а якщо й вони збігаються — викликає нативний System.identityHashCode(k) (адресний псевдовипадковий геш із заголовка Mark Word), гарантуючи стабільне детерміноване балансування дерева.

Атака Hash-Flooding DoS через штучно скомпільовані колізії

Геш-функція String.hashCode() є поліноміальною: $h = s[0] \cdot 31^{n-1} + s[1] \cdot 31^{n-2} + \dots + s[n-1]$ Оскільки $31 \times 65 + 97 = 31 \times 66 + 66 = 2112$, пари символів "Aa" та "BB" дають однаковий внесок у суму.

Зловмисник може згенерувати $2^{16} = 65\,536$ рядків комбінаціями пар "Aa" та "BB": "AaAaAaAa", "AaAaAaBB", "AaAaBBAa", "AaAaBBBB"…
Усі ці $65\,536$ рядків матимуть абсолютно однаковий hashCode()!

У Java 7: відправка HTTP POST-форми з такими параметрами на сервер призводила до створення єдиного зв’язного списку з 65 536 вузлів. Вставка кожного нового ключа вимагала $O(n)$ порівнянь, що давало сумарну складність $O(n^2)$. Процесор зависав на 100% на кілька хвилин (DoS-атака).
У Java 8+: при досягненні 8 елементів ланцюжок перетворюється на червоно-чорне дерево (treeification), зменшуючи складність операцій до $O(n \log n)$ і нівелюючи вразливість.

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

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

Однаковий hashCode() НЕ гарантує рівності за equals(). Збіг геш-кодів у нерівних об’єктів називається колізією. Це математично неминуче явище через принцип Діріхле (32-бітний int має лише 4.3 млрд значень, а кількість станів об’єктів нескінченна). У HashMap збіг гешів лише направляє елементи в один бакет, де вони мирно співіснують у ланцюжку або червоно-чорному дереві та розрізняються викликом equals(). Перезапис значення відбувається виключно тоді, коли equals() == true.

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

Питання 1: Чому в Java `hashCode()` повертає 32-бітний `int`, а не 64-бітний `long`, що могло б мінімізувати колізії?

Відповідь:

Економія пам’яті: поле final int hash кешується в кожному вузлі Node<K,V>. Тип long збільшив би обсяг кожного вузла на 8 байтів (з урахуванням вирівнювання пам’яті в 64-бітній JVM), що на мільйонах записів створило б суттєвий оверхед;
Апаратна оптимізація: операції з 32-бітними цілими числами апаратно прискорені на всіх процесорних архітектурах;
Розмір масиву бакетів: індекс бакета обчислюється бітовою маскою (n - 1) & hash за молодшими 4–20 бітами. Перехід на 64-бітний геш ніяк не захистив би від колізій бакетів у таблицях розумного розміру.

Питання 2: Як згенерувати довільну кількість різних рядків із абсолютно ідентичним `hashCode()` для стандартного класу `String`?

Відповідь: Базовим будівельним блоком є будь-яка двозбіркова пара рядків із рівним гешем: наприклад, "Aa" та "BB" (обидва повертають 2112). Оскільки алгоритм String.hashCode() використовує лінійне поліноміальне множення на 31, будь-яка конкатенація блоків "Aa" та "BB" однакової довжини дає однаковий підсумковий результат. Комбінуючи $K$ таких блоків декартівським добутком, можна згенерувати $2^K$ унікальних рядків з ідентичним hashCode() (наприклад, "AaAa", "AaBB", "BBAa", "BBBB" для $K=2$).

Питання 3: Що станеться в `HashMap`, якщо метод `hashCode()` для всіх ключів повертатиме фіксовану константу (наприклад, `return 42;`)?

Відповідь: Усі записи потраплятимуть в один-єдиний бакет (індекс (n - 1) & 42). До 8 елементів вони формуватимуть однозв’язний список із лінійною складністю пошуку $O(n)$. При додаванні 8-го елемента (якщо загальна місткість $\ge 64$) бакет перетвориться на збалансоване червоно-чорне дерево, і складність стабілізується на рівні $O(\log n)$. HashMap не втратить дані та збереже коректність бізнес-логіки, проте втратить перевагу константного часу доступу $O(1)$.

Питання 4: Як `HashMap` відрізняє вставку нового запису від оновлення значення наявного ключа при повному збігу `hashCode()`?

Відповідь: При збігу гешів HashMap переходить до другого ступеня перевірки: викликає key.equals(existingNode.key). Якщо equals() повертає true, мапа констатує збіг ключів і перезаписує значення поля node.value. Якщо equals() повертає false, мапа ідентифікує це як колізію двох різних ключів і додає новий вузол у ланцюжок або дерево.

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

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

❌ «Ідеальна геш-функція зобов’язана повністю унеможливлювати колізії.»
Правильно: Будь-яка геш-функція загального призначення не може усунути колізії через принцип Діріхле. Її мета — рівномірний псевдовипадковий розподіл ключів.

❌ «При збігу hashCode() старий елемент видаляється з HashMap.»
Правильно: Якщо equals() == false, обидва елементи зберігаються в бакеті як різні вузли.