equals() и hashCode() в Java или попугаи-неразлучники в ваших программах. Часть 2

В предыдущей части, если не читали вот она, мы подробно рассмотрели работу метода equals(), его контракт, ошибки и их исправления. Теперь настала очередь второго попугая-неразлучника – метода hashCode().

При переопределении метода equals() мы всегда должны переопределять метод hashCode(). Метод hashCode() – вычисляет целочисленное значение для конкретного элемента класса, чтобы использовать его для быстрого поиска и доступа к этому элементу в hash-структурах данных, например, HashMap, HashSet и прочих. Почему важно переопределять hashCode() всегда вместе с методом equals()? Развернуто ответим на этот вопрос. Пожалуй, необходимо и достаточно знать два важных аспекта, чтобы понять, почему необходимо делать переопределение методов вместе:

  1. Hash-код объекта используется для быстрой навигации в Hash – таблицах. Поэтому достаточно понять сам процесс поиска/вставки/удаления элемента в этих таблицах
  2. Связь equals() и hashCode(). Если два объекта o1 и o2 являются equals() (o1.equals(o2) = true), то они должны иметь одинаковый hash-код. Обратное – не обязательно.

Что такое хеш-таблицы (Hash Tables)?

пример hash table

Хэш – таблицы – это своего рода ассоциативный массив, хранящий значения в виде “ключ-значение”. Рассмотрим работу вставки элемента в хеш-таблицу:

  1. На входе мы получаем key – некий объект.
  2. Для объекта вызывается метод hashCode(), который вернет hash-код объекта – целое число.
  3. По этому числу мы находим соответствующий ему bucket – определенная структура, хранящая в себе все объекты с одинаковыми hash-кодом. В нашем случае это будет список.
  4. В найденный bucket мы записываем объект key.

На деле все просто, но если еще раз перечитать контракт hashCode() и equals(), то все становиться немного труднее: возможны коллизии – два разных объекта имеют одинаковый hash-код. Что делать? Эта проблема и ее решение отражены на рисунке выше. Два объекта John Smith и Sandra Dee имеют один и тот же hash-код. Для разрешения это коллизии мы просто берем за структуру bucket направленный список. И сохраняем два значения по одному hash-коду.

Как сломать хеш – таблицу?

При неверной реализации метода hashCode() мы можем легко сломать hash-таблицу. Вернее даже сказать не сломать, а сделать ее вырожденной. Например, переопределив метод hashCode() следующим образом

мы выродим таблицу в простой список. Из-за того, что для каждого объекта hashCode() будет вычисляться один и тот же все они попадут в один bucket и все выгоды hash-таблицы будут потеряны для нас.

Так же стоит помнить, что при повторном вызове hashCode() для конкретного объекта всегда должно возвращаться одинаковое значение! Иначе корректная работа таких структур данных как HashMap или HashSet будет нарушена. Продемонстрируем это на примере:

Как вы думаете, что выведется? Правильно, null!

Почему так произошло? Когда мы вызываем метод get(), то как параметр-ключ передаем новый объект, который равен (если верить методу equals()) тому, который уже лежит в persons. Мы ожидаем получить 1, но имеем null и все потому что нарушен контракт equals() и hashCode(). В нашей реализации hashCode() для каждого нового объекта будет свой уникальный hash-код, и когда будет вызван метод get() класса HashMap, он вызовет метод hashCode(), получит hash-код объекта, попытается найти соответствующий ему bucket и, не найдя его, вернет null.

Правильная реализация hashCode()

Чтобы избежать проблем нам необходимо корректно переопределять hashCode(). Рассмотрим два варианта.

  1. Использовать метод hash класса Objects. Для класса Person это будет выглядеть следующим образом :

Прекрасная реализация в одну строчку. Из минусов – не подойдет вам, в случаем высоких требований к производительности приложения. В этом случае используйте второй способ

2. Напишите свою реализацию, используя следующий алгоритм:

  1. Создайте переменную result и положите в нее значение hashCode() первого значимого поля класса. Если поле примитив, то используйте вызов Type.hashCode(value), если экземпляр класса, то рекурсивно вычисляйте hashCode() для полей класса, либо используйте уже готовый метод hashCode() этого класса. Если поле массив, то рекурсивно вычисляйте hashCode() каждого элемента.
  2. Вычислите hashCode() каждого значимого поля и скомбинируйте следующим образом : result = 31 * result + Type.hashCode(value)
  3. Верните результат

Для нашего примера реализация следующая:

Вы можете придумать свою собственную реализацию hashCode(), главное, помните о его контракте!

Оставить комментарий:

Ваш email не будет опубликован.

Site Footer