mariakomar-blog - Tumblr blog

mariakomar-blog · 10 years ago

Text

Популярная тема для собеседований: equals() и hashCode()

Статья основана на переводе нескольких источников, постаралась осветить все основные тонкости при использовании этих методов.

У класса Object есть два метода для определения идентичности обьектов: equals() и hashCode().

Если вы переопределяете один из этих методов необходимо также переопределить второй.

Если два объекта идентичны согласно методу equals(), их hashCode() также должен совпадать.

Нужно помнить, что обратное утверждение не всегда верно. Если у двух разных объектов одинаковый hashCode() это может говорить о том, что хэшкоды в этом классе высчитываются не достаточно хорошо, или у вас коллекция из большого колличества (несколько миллионов или миллиардов) объектов.

Впрочем HashMap будет работать даже, если все ключи будут возвращать одинаковый хэш (конечно это скажется на производительности).

Для того чтобы объекты можно было корректно сравнивать с помощью метода equals(), необходимо его переопределить, так как базовая реализация в классе Object сравнивает только ссылки на объекты:

public boolean equals(Object obj){ return (this ==obj); }

Это значит, что если мы не переопределим этот метод, две ссылки будут признаны одинаковыми, только если они ссылаются на один и тот же оъект.

��азовая реализация метода hashCode() в классе Object заключается в маппинге адреса объекта в памяти в значение типа int. Так как колличество адресов в памяти больше, чем диапазон значений для int, возможна ситуация, когда дава различных объекта будут име��ь одинаковый hashCode(). Если вы переопределите метод hashCode(), у вас все равно будет возможность использовать использовать System.identityHashCode() чтобы вызвать дефолтный метод.

Простой пример переопределенеия equals() в классе Integer:

public boolean equals(Object obj){ return(obj unstanceof Integer && intValue() == ((Integer)obj).intValue()); }

Согласно этому методу, два интежера равны только когда они содержат одинаковые целочисленные значения. Это, а также, то что объекты класса Integer являются иммутабельными, делает их удобными для использования в качестве ключа для HashMap. Это же касается таких классов, как Float, Character, Boolean и String(два объекта класса String равны, если они содержат одинаковую последовательность символов). Так как все эти классы иммутабельны и разумно переопределяют hashCode и equals(), они дают хорошие хэш ключи.

Зачем переопределять equals() и hashCode()? Что случилось бы, если бы Integer не переопределял equals() и hashCode()? Ничего, если бы мы никогда не использовали такой объект в качестве ключа для HashMap или любой другой основанной на хэше коллекции. Если бы мы все же использовали такой объект в качестве ключа для HashMap, у нас бы не было возможности надежно извлекать связанное с ним значение. Если бы только мы не использовали тот же экземпляр класса Integer при вызове get(), что и при вызове put(), и так на протяжении работы всей программы. А это весьма неудобный и ведущий к ошибкам подход.

Контракт относительно класса Object говорит о том, что если два объекта являются одинаковыми согласно методу equals(), они должны иметь одинаковое значение hashCode(). Зачем же нужен hashCode(), если он так похож на equals()? Существование hashCode() оправданно соображениями эффективности. Сравнение большого колличества объектов с помощью equals() может быть нерациональным с точки зрения использования вычислительных ресурсов. Поддержка каждым объектом hashCode() позволяет эффективно сохранять и извлекать объекты в коллекциях использующих хэш.

Требования к переопределению equals() и hashCode()

Симметричность - для дувух ссылок, а и b, a.equals(b) тогда и только тогда, когда b.equals(a) Рефлексивность - для любого ненулевого a, a.equals(a) Транзитивность - если a.equals(b) и b.equals(c) то a.equals(c) Согласованность с hashCode() - два одинаковых объекта согласно equals() должны иметь одинаковый hashCode()

Если hashCode() объекта может измениться в зависимости от его состояния, мы должны быть осторожными используя такой объект в качестве ключа в базирующихся на хэше коллекциях и быть уверенными, что мы не позволим состоянию объекта измениться, пока он используется в такой коллекции.

Если хеш код объекта изменится, пока он используется в качестве ключа в коллекции, это может привести к непредсказуемым и сбивающим с толку последствиям.

Например к таким (цитата с хабра): В каком случае может быть потерян элемент в HashMap? Этот интересный вопрос мне прислал LeoCcoder, у меня подобного не спрашивали и честно признаюсь, после прочтения сходу не смог придумать сценарий для потери элемента. Все опять же оказалось довольно просто, хоть и не так явно: допустим в качестве ключа используется не примитив, а объект с несколькими полями. После добавления элемента в HashMap у объекта, который выступает в качестве ключа, изменяют одно поле, которое участвует в вычислении хеш-кода. В результате при попытке найти данный элемент по исходному ключу, будет происходить обращение к правильной корзине, а вот equals (ведь equals и hashCode должны работать с одним и тем же набором полей) уже не найдет указанный ключ в списке элементов. Тем не менее, даже если equals реализован таким образом, что изменение данного поля объекта не влияет на результат, то после увеличения размера корзин и пересчета хеш-кодов элементов, указанный элемент, с измененным значением поля, с большой долей вероятности попадет совсем в другую корзину и тогда он уже совсем потеряется.

Не трогайте поля объекта-ключа ответственные за хэш-код, после того как поместили его в хэшированную коллекцию.

Пример переопределения методов equals() и hashCode()

class A{ final B someNonNullField; C someOtherField; int someNonStateField; }

Этот метод переопределения equals() и hashCode() подходит для большинства ситуаций:

public boolean equals(Object other){ //Не строго необходимо, но всегда хорошая оптимизация. if(this == other) {return true; } if(other == null) {return false; } if (getClass() != obj.getClass()) { return false; } A otherA = (A) other; return (someNonNullField.equals(otherA.someNonNullField)) && ((someOtherField == null) ? otherA.someOtherField == null : someOtherFiled.equals(otherA.someOtherField))); }

В процессе написания статьи нашелся один интересный вопрос с собеседований: "В чем отличие в использовании instanceof и getClass() для проверки типа внутри equals()?". Основное отличие заключается в том, что оператор instanceof возвращает true при сравнение с классом наследником, getClass() в этом случе возвращает false. Используя getClass() вы будете уверенными, что при сравнениии с классом-наследником, ваша реализация equals() не вернет true. Использование же оператора instanceof, может привести к нарушению правила симметричности.

Похожим образом разумно переопределять и hashCode(), используя произвольное заданное вручную простое число, желательно, чтобы для разных классов оно отличалось:

public int hashCode(){ int hash = 1; //Еще один вариант, присв��ить результирующей переменной также простое число, например int hash = 17; hash = hash*37 + someNonNullField.hashCode(); hash = hash* 37 + (someOtherField == null ? 0 : someOtherField.hashCode()); return hash; }

Для примитивных типов в соответствующих клссах-обертках есть вспомогательные функции, которые могут помочь в получении их хэш значений:

Для типа boolen: result = 37 * result + (boolenValue ? 1 : 0);

Для типов byte, char, short или int, нужно вычислите (int)value: result = 37 * result + (int)charValue;

Для типа String: result = 37 * result + (stringValue == null ? 0 : stringValue.hashCode());

Для типа long: result = 37 * result + (int)(longValue - (longValue >>> 32));

Для типа float: result = 37 * result + Float.floatToOntBits(floatValue);

Для типа double: long longBits = Double.doubleToLongBits(doubleValue); result = 37 * result + (int)(longBits - (longBits >>> 32));

Для массивов: for (byte b : arrayValue) result = 37 * result + (int)b;

Немного сложнее обстоит ситуация с переопределением equals() и hashCode() если у класса есть суперкласс отличный от Object. Вот пример самого простого решения, без вмешательства в private поля суперкласса:

@Override public boolean equals(Object obj) { if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } if (! super.equals(obj)) return false; else { // compare subclass fields }

@Override public int hashCode() { int hash = super.hashCode(); hash = 89 * hash + (this.name != null ? this.name.hashCode() : 0); hash = 89 * hash + (this.faceBookNickname != null ? this.faceBookNickname.hashCode() : 0); return hash; }

Использованные материалы:

http://www.ibm.com/developerworks/java/library/j-jtp05273/index.html http://www.seostella.com/ru/article/2012/10/04/kak-sgenerirovat-hashcode-v-java.html http://javatalks.ru/topics/38165 http://stackoverflow.com/questions/2066917/overriding-equals-hashcode-in-sub-classes-considering-super-fields http://www.angelikalanger.com/Articles/JavaSolutions/SecretsOfEquals/Equals.html http://javarevisited.blogspot.com/2013/08/10-equals-and-hashcode-interview.html

#java #hashcode

1 note · View note