🟢 Junior Level

Ні! Два об’єкти з однаковим hashCode() не обов’язково рівні за equals(). Це називається колізія — і це нормальна ситуація.

Проста аналогія: Дві людини можуть жити в одному під’їзді (однаковий “хеш”), але це різні люди (не рівні за “equals”).

Класичний приклад:

System.out.println("Aa".hashCode());       // 2112
System.out.println("BB".hashCode());       // 2112
System.out.println("Aa".equals("BB"));     // false — різні рядки!

HashMap вміє обробляти колізії — вона зберігає кілька елементів в одному бакеті і розрізняє їх через equals().

🟡 Middle Level

Чому колізії неминучі

hashCode() повертає int — це 32 біти, ~4.3 млрд значень. А унікальних об’єктів може бути більше, ніж вміщується в пам’ять JVM. Навіть рядки довжиною до 10 символів — це 26^10 = 141 трильйон комбінацій. За принципом Діріхле колізії неминучі.

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

Крок	Метод	Призначення
1. Грубий відсів	hashCode()	Визначає бакет, відсіює 99.9%
2. Точна перевірка	equals()	Знаходить конкретний ключ в бакеті

Чому HashMap швидша: двоступеневий фільтр унікальний для хеш-колекцій. У ArrayList пошук — лінійний equals() для КОЖНОГО елемента (O(n)). У TreeMap — compareTo() для кожного вузла (O(log n)). У HashMap — hashCode спочатку відкидає 99.9% кандидатів, і equals викликається тільки для 1-2 елементів.

Продуктивність:

• Різні hashCode → equals() не викликається (швидко)
• Однаковий hashCode → викликається equals() (повільніше, але точно)

Чому важлива унікальність hashCode

Якщо всі ключі мають однаковий hashCode:

• Всі елементи в одному бакеті
• HashMap деградує до O(n) (список) або O(log n) (дерево)
• Система стає вразливою до DoS-атак

Практичні приклади колізій

// Рядки
"Aa".hashCode() == "BB".hashCode() // 2112

// Реальна колізія:
new Long(1).hashCode() == 1
new Long(4294967297L).hashCode() == 1  // Той самий hashCode!

// Поганий hashCode
class BadKey {
    @Override public int hashCode() { return 1; } // ЗАВЖДИ 1!
}

🔴 Senior Level

Математика колізій

Парадокс днів народження

Парадокс днів народження: у групі з 23 осіб ймовірність збігу днів народження > 50%. Аналогічно в HashMap: навіть при 5 елементах і 16 бакетах ймовірність колізії > 50%. Це НЕ інтуїтивно, але статистично доведено.

Impact на продуктивність

Сценарій	Середня довжина ланцюжка	Складність
Хороший hashCode	1-2	O(1)
Середній hashCode	3-5	O(1) (з великою константою)
Поганий hashCode (константа)	n	O(n) або O(log n)

Hash Flooding Attack

Зловмисник підбирає ключі з однаковим хешем:

• Java 7: 100% завантаження CPU (O(n²) при вставці)
• Java 8+: пом’якшено через treeification (O(n log n)), але overhead залишається

Internal Mechanics: Treeification при колізіях

При 8+ елементах в одному бакеті і capacity >= 64:

// Якщо ключі реалізують Comparable — використовується compareTo()
// Якщо ні — tieBreakOrder() через System.identityHashCode()

Реалізація Comparable для ключів прискорює treeification.

Edge Cases

1. Всі hashCode = 1: У Java 7 — фатальна деградація. У Java 8+ — дерево, але величезний overhead
2. hashCode залежить від mutable полів: після зміни ключа хеш змінюється, елемент “губиться”
3. Системний hashCode: System.identityHashCode() може збігатися для різних об’єктів (це не UUID)

Best Practices

• Мінімізуйте колізії через якісний hashCode()
• Використовуйте прості числа (31, 37, 41) як множники
• Включайте всі значущі поля з equals() в hashCode()
• Для production: моніторьте розподіл hashCode через unit-тести

---

🎯 Шпаргалка для співбесіди

Обов’язково знати:

• НІ: однаковий hashCode ≠ рівні об’єкти — це називається колізія
• Класичний приклад: “Aa” і “BB” обидва дають 2112, але “Aa”.equals(“BB”) = false
• HashMap використовує двоступеневий фільтр: hashCode (грубий відсів) → equals (точна перевірка)
• Парадокс днів народження: при 23 елементах і 365 бакетах ймовірність колізії > 50%
• 2^32 (~4.3 млрд) значень int не покривають нескінченну множину можливих об’єктів
• Поганий hashCode (константа) = всі елементи в одному бакеті = деградація до O(n)

Часті уточнюючі питання:

• Чому колізії неминучі? — принцип Діріхле: нескінченна множина → скінченний діапазон int
• Як HashMap розрізняє елементи в одному бакеті? — через equals() за ланцюжком/деревом
• Що таке Hash Flooding Attack? — зловмисник генерує ключі з однаковим hashCode → DoS
• Чи можна повністю уникнути колізій? — ні, тільки мінімізувати якісним hashCode

Червоні прапорці (НЕ говорити):

• «Колізія = баг в hashCode» — ні, колізії нормальні, баг = ЗАВЖДИ повертати константу
• «При колізії HashMap губить дані» — ні, equals знаходить елемент всередині бакета
• «hashCode повинен бути унікальним» — математично неможливо для нескінченної множини

Пов’язані теми:

• [[4. Що таке колізія в HashMap]]
• [[5. Як HashMap обробляє колізії]]
• [[7. Що таке контракт equals() і hashCode()]]
• [[8. Якщо два об’єкти рівні за equals(), що можна сказати про їх hashCode()]]