🔑 Раздел 10 · Вопрос #9

Если два объекта имеют одинаковый hashCode(), обязательно ли они равны по equals()

Ситуация, при которой два логически разных объекта (a.equals(b) == false) имеют одинаковое значение hashCode(), называется коллизией хеш-функции (Hash Collision). Это абсолютно...

🔑 HashMap equals hashCode 📄 Исходный Markdown

🟢 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 (всего $\approx 4.29 \times 10^9$ уникальных значений), в то время как число возможных состояний объектов в оперативной памяти бесконечно.

Примеры гарантированных коллизий в стандартных классах 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))
          Точно идентифицирует целевой объект среди коллизий

Обновление значения vs Добавление коллизии

Когда в HashMap вызывается метод put(key, value) и хеш ключа совпадает с уже существующим в корзине элементом, мапа проверяет равенство ключей через equals():

  1. Если k.equals(existingKey) == true:
    Мапа считает, что это тот же самый ключ. Значение старого узла перезаписывается новым (e.value = value), а метод put() возвращает старое значение. Размер мапы (size) не меняется.
  2. Если k.equals(existingKey) == false:
    Мапа фиксирует коллизию. Создается новый узел Node<K,V>, который привязывается к концу связного списка в корзине (Tail Insertion). В мапе теперь хранятся оба элемента, а размер мапы увеличивается (size++).

🔴 Senior Level

Механизм разрешения конфликтов в красно-черном дереве TreeNode

Что делает HashMap, когда в одной корзине накапливается $\ge 8$ элементов с абсолютно одинаковым hashCode()?

Красно-черное дерево поиска требует четкого упорядочивания ($<$ или $>$). Если хеш-коды одинаковы, бинарное сравнение по hash становится бесполезным. HotSpot решает эту дилемму следующим каскадом:

// Фрагмент логики вставки в TreeNode (HotSpot):
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);
}
  1. comparableClassFor: проверяется, реализует ли класс ключа Comparable<MyClass>. Если да, вызывается k.compareTo(pk).
  2. Fallback через 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: отправка формы с такими строками на сервер (Tomcat) приводила к построению связного списка длиной 65 536 элементов. Вставка каждого элемента требовала $O(n)$ сравнений. Вся операция занимала $O(n^2)$ времени — процессор зависал на 100% на несколько минут (DoS-атака).
  • В Java 8+: при 8 элементах список превращается в красно-черное дерево, снижая сложность до $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, что сильно сократило бы вероятность коллизий?

Ответ:

  1. Память и размеры структур: поле final int hash хранится в каждом узле Node<K,V>. Использование long увеличило бы размер ноды на 8 байт (с учетом выравнивания памяти в 64-битной JVM), что создало бы гигантский оверхед на миллиардах записей;
  2. Аппаратная эффективность: 32-битные операции с целыми числами аппаратно оптимизированы на всех процессорных архитектурах;
  3. Размер таблицы: реальные коллекции HashMap редко содержат более нескольких миллионов элементов. Индекс корзины все равно берется по младшим 4–20 битам маски (n - 1) & hash, поэтому 64-битный хеш никак не спас бы от коллизий корзин.

Вопрос 2: Как сгенерировать произвольное количество строк с абсолютно одинаковым hashCode() для стандартного String?

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

Вопрос 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(candidateKey). Если equals() возвращает true, мапа констатирует совпадение ключей и перезаписывает существующее значение в поле Node.value. Если equals() возвращает false, мапа считает это коллизией и создает новый узел в списке или дереве.

3. Типичные ошибки и Red Flags

❌ “Если хеши совпали, то и объекты равны по equals.”
Правильно: Это ошибка начинающих. Равенство хешей — лишь необходимое, но недостаточное условие эквивалентности.

❌ “Хорошая хеш-функция должна гарантировать отсутствие коллизий.”
Правильно: Хеш-функция общего назначения в принципе не может исключить коллизии из-за принципа Дирихле. Она обязана лишь обеспечивать равномерное псевдослучайное распределение.

❌ “При совпадении hashCode() старый элемент удаляется из HashMap.”
Правильно: Если equals() == false, оба элемента сохраняются в структуре корзины.

4. Связанные вопросы