Часто на собеседованиях задают вопросы по стандартным методам Object – equals() и hashCode(). Но знать об этих методах нужно не только для ответов на каверзные вопросы, но и для умения правильно писать код, не нарушая логику, и использовать структуры данных.
Хотя класс Object не абстрактный, и мы можем создать экземпляры, чаще всего этот класс используется для наследования (все объекты в Java являются потомками этого класса). В этом классе считается, что объекты равны, только если это один и тот же объект, а вместо вычисления хэша берётся идентификационный хэш объекта – то есть значение не связано с содержимым объекта.
В этой ситуации мы увидим, что два одинаковых на первых взгляд объекта на самом деле не равны, и их хэши разные.
Cat cat1 = new Cat(“barsik”);Cat cat2 = new Cat(“barsik”);System.out.println(cat1.equals(cat2)); System.out.println(cat1.hashCode() + “ “ + cat2.hashCode());
И может быть верно, что два кота с одним именем – это разные существа, ведь в жизни так и есть. Но не всегда бизнес-логика так щедра на разнообразие, и мы предполагаем, что объекты с одинаковым содержимым равны. Иногда хватит взглянуть лишь на одно поле (например, id из базы данных, так как оно уникально).
Именно поэтому необходимо переопределять метод equals().
Переопределение метода equals()
Во-первых, стоит помнить, что оператор сравнения == полезен лишь для примитивов и проверки ссылки на объект. Он не заглядывает внутрь объекта и признаёт равенство, только если в памяти это один и тот же объект. Поэтому для «глубокого» сравнения мы вызываем equals().
При переопределении этого метода нужно убедиться, что он отвечает нескольким требованиям, которые очевидны тем, кто помнит математику. Он должен быть:
- Рефлективным. То есть объект должен быть равен сам себе (если он, конечно, не null, но тогда мы и не сможем вызвать метод).
- Симметричным. То есть если первый объект равен второму, то и второй равен первому. Порядок не влияет на результат.
- Транзитивным. Если первый объект равен второму, а второй – третьему, то первый объект должен быть равен третьему.
- Стабильным. Если объекты не изменяются, то и результат сравнения всегда должен быть одинаковым.
Ситуации, в которых этот контракт нарушается, обычно происходят при наследовании, если у родительского класса метод переопределён, а у потомков добавлены новые поля, которые в сравнении не участвуют. Поэтому обязательно переписывать equals() в каждом классе иерархии. Как же это сделать?
Логично предположить, что объекты не могут быть равны, если они разных классов. Разные классы символизируют разные сущности в реальном мире, ну и чаще всего отличаются логикой. После этого сравнения можно уже сравнивать значимые поля.
Например, для объекта User с полями id, name и PhoneNumber метод будет выглядеть так:
public class User { private long id; private String name; private PhoneNumber number; <...> @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof User)) return false; User user = (User) o; return id == user.id && name.equals(user.name) && number.equals(user.number); }}
Нам важно проверить, какого класса аргумент, чтобы можно было привести его к нашему классу и получить доступ ко всем полям. Именно поэтому перед сравнением полей пишем User user = (User) o.
Альтернатива этому сравнению, но без использования instanceof будет сравнение через метод getClass(), но перед его вызовом нужно удостовериться, что переданный объект не null (в случае с instanceof это не требуется, так как null не считается инстансом никакого класса, и проверка всегда вернёт false):
if (o == null || getClass() != o.getClass()) return false;
В этом примере я сравнивал все поля. Примитивное поле id с помощью оператора ==, а остальные поля – объекты, поэтому их сравниваю уже через метод equals. Предполагаю, что в классе PhoneNumber метод тоже переопределён такими же добросовестными разработчиками. Переопределяйте методы – не подставляйте команду!
Но вместо этого можно использовать метод equals в классе Objects, который принимает два параметра и безопасно сравнивает их (нам не нужна проверка на null):
return id == user.id
&& Objects.equals(name, user.name)
&& Objects.equals(number, user.number);Результат будет тем же.
HashMap и hashcode()
Метод hashCode() менее понятен, так как равенство мы как-то ещё представляем себе в реальном мире, а вот хэши считать ежедневно нам не приходится. Поэтому часто у разработчиков есть соблазн не переопределять хэш – он тогда останется уникальным для каждого объекта. Но это создаёт проблемы при использовании таких структур, как HashMap или HashSet, который тоже основан на мапе. Технически в этом нет ошибки, но мы опять получаем ситуацию, в которой два абсолютно одинаковых объекта считаются разными.
Map<PhoneNumber, User> phoneBook = new HashMap<>();phoneBook.put(new PhoneNumber(“+7123456789”), anton);phoneBook.get(new PhoneNumber(“+7123456789”));
Мы ожидаем, что этот код вернёт нам Антона (его объект создан где-то выше, вне этого фрагмента). Но он вернёт вместо этого null, считая, что подобного телефона ещё нет в мапе. Даже если метод equals() переопределён, и эти телефонные номера считаются равными.
Дело в том, что такая мапа, как следует из названия класса, сравнивает ключи не только методом equals() – сначала она разбивает все ключи по категориям, которые основаны на хэшах из hashCode().
Именно поэтому при переопределении метода equals()всегда нужно переопределять метод hashCode(). Два равных объекта всегда должны возвращать одинаковый хэш.
Как работает HashMap
Перед тем, как займусь переопределением метода, можно немного покопаться в принципах работы хэшмапы.
Для пользователя эта структура позволяет хранить пары key-value и обращаться к значениям по ключу. Но она намного сложнее, чем обычный массив: данные хранятся не последовательно, а в связанных списках. Распределяются по спискам они в зависимости от хэша ключа: пары key-value, где у ключей равные хэши, помещаются в один список/бакет (такое совпадение называется коллизией).
Поэтому каждый элемент мапы под капотом содержит не только ключ и значение, но также хэш ключа и ссылку на следующий элемент.
Количество этих списков называется вместимостью мапы (capacity) и всегда равно степени двойки. Сначала их 16, потом число при необходимости увеличивается в два раза, и так далее. Тогда мапа самостоятельно перераспределяет объекты по спискам, исходя из новой вместимости. Чтобы узнать, в какой бакет поместить объект, используется формула с побитовым И:
index = (capacity - 1) & hash
Расширение и перераспределение происходит, когда размер мапы (size – число всех элементов, из всех бакетов вместе) превосходит 0.75 * capacity. То есть после добавления 13-го элемента, вместимость становится 32. А после добавления 25-го – уже 64. Это позволяет лучше распределять элементы и избегать ситуации, когда в одном бакете слишком много пар – ведь в связанном списке, чтобы добраться до нужного элемента, нужно пройти по всем прошлым. И если у нас будут слишком длинные списки, то это ставит под вопрос преимущества мапы.
Есть ещё одна «секретная» реорганизация. В случае, если в конкретном бакете в списке оказывается больше 8 элементов, а мапа уже расширилась до 64 бакетов, то этот переполненный бакет превратится красно-чёрное дерево. Это поможет ускорить поиск в бакете, не дожидаясь, когда мапа наполнится настолько, что можно будет увеличить вместимость и надеяться, что перераспределение внесёт баланс.
HashSet работает на основе HashMap, и мне это показалось немного нелогичным, ведь в мапу мы кладём пары значений, а в сэт – одиночные объекты. Но так и есть: так как ключи в мапе должны быть уникальными, для хранения значений множества используются именно они. В этих фиктивных парах в значения под капотом кидается объект-заглушка.
Так как хэш объекта используется в этих структурах для распределения по бакетам, то важно правильно описать расчёт для своего класса. Можно конечно просто возвращать одно и то же число – это не сломает ничего, но тогда все объекты всегда будут падать в один бакет, и мапу можно заменить списком.
Переопределение метода hashCode()
В методе hashCode() должен учитывать все те же поля, что учитываются в equals(), чтобы у равных объектов получалось равное число. Проще всего передавать все нужные поля в метод hash класса Objects:
Objects.hash(id, name);
Но лучшей практикой часто считают ручной «сбор» хэша. Для этого берут простое число (например, 31 часто встречается) и следуют алгоритму:
- Объявить целочисленную переменную для хранения результата и инициализировать её хэшем первого значимого поля.
- Для каждого следующего значимого поля рассчитывать его хэш и суммировать с базовым числом (31), умноженным на текущий результат (result).
- Полученное значение записывать в result, постепенно увеличивая result.
- Вернуть результат (result).
В коде всё это выглядит короче:
result = 31 * result + fieldObject.hashCode();
Пункт 2 не так прост, как кажется. Расчёт хэша для каждого поля может быть коварным. Но и тут есть правила:
- Если поле примитивного типа, то хэш считается с помощью метода hash из соответствующего этому типу класса. (Short для short, Integer для int и так далее).
- Если встречается объект, и в методе equals мы вызываем equals у объекта этого класса, то тут так же нужно просто вызвать hashCode. Если для сравнения используется сложная логика, то нужно привести значение к каноническому представлению перед расчётом его хэша.
- Если значения поля null, то используем 0.
- Если встречается массив, то все те же правила необходимо применять к каждому из его элементов, считая каждый элемент отдельным полем. Можно также использовать Arrays.hashCode.
Звучит немного запутанно, но смысл в том, чтобы складывать хэши всех значений в классе, даже если они лежат в структуре, или внутри другого объекта.
Единственное, что нужно добавить, это разъяснение про каноническое представление. Имеется в виду ситуация, в которой, например, разные объекты считаются равными, хотя выглядят по-разному. Например, в классе User мы будем сравнивать логин, игнорируя регистр.
@Overridepublic boolean equals(Object o) { <...> User u = (User) o; return login.equalsIgnoreCase(u.login);}
Тогда может случиться ситуация, в которой юзеры с логинами JOHN и john считаются равными, но строки JOHN и john имеют разные хэши. Поэтому в методе hashCode перед расчётом хэша для этих полей нужно привести их к каноническому представлению – сделать все в нижнем регистре (или в верхнем).
Рассмотрим расширенный класс User, где в проверке на равенство учитываем и id, и имя, и номер, и логин:
public class User { private long id; private String name; private PhoneNumber number; private String login; <...> @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; if (!(o instanceof User)) return false; User user = (User) o; return id == user.id && Objects.equals(name, user.name) && Objects.equals(number, user.number) && Objects.equals(login.toLowerCase(), user.login.toLowerCase()); }}
Опять же, можно вызвать простой вариант хэша:
@Override
public int hashCode() {
return Objects.hash(id, name, number, login.toLowerCase());
}А можно сделать всё по алгоритму. По нему мы последовательно суммируем все хэши и не забываем привести логин к нижнему регистру, как делаем это в equals:
@Override
public int hashCode() {
int result = Long.hashCode(id);
result = 31 * result + name.hashCode();
result = 31 * result + number.hashCode();
result = 31 * result + login.toLowerCase().hashCode();
return result;
}Не стоит отбрасывать какие-то поля, чтобы расчёты стали проще – это может незначительно ускорить работу программы, но при этом повлечь баги. Для оптимизации можно кэшировать хэш в приватное поле. При инициализации оно станет равным нулю, и в методе hashCode мы считаем хэш лишь раз, а при повторных вызовах возвращаем уже рассчитанное значение
private int hash;
@Override
public int hashCode() {
int result = hash;
if (result == 0) {
result = Long.hashCode(id);
<...>
hash = result;
}
return result;
}Это ленивое кэширование, которое полезно, если объект часто используется как ключ в хэшмапе, но объект должен быть неизменяемым после создания– immutable, по крайней мере по значимым полям, которые используются в наших двух важных методах.
Zimowski Journal 