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