Переопределяя метод equals, всегда переопределяйте hashCode

Распространенным источником ошибок является отсутствие переопределения метода hashCode. Вы должны переопределять метод hashCode в каждом классе, где переопределен метод equals. Невыполнение этого условия приведет к наруше­нию общих соглашений для метода Object.hashCode, а это не позволит вашему классу правильно работать в сочетании с любыми коллекциями, построенными на использовании хэш-таблиц, в том числе с HashMap, HashSet и HashTable.

Приведем текст соглашений, представленных в спецификации jауа.lang.Object:

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

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

· Если метод equals(Object) показывает, что два объекта не равны

друг другу, вовсе не обязательно, что метод hashCode возвратит для них разные числа. Между тем программист должен понимать, что генерация разных чисел для неравных объектов может повысить эффективность хэш-таблиц.

 

Главным является второе условие: равные объекты должны иметь одиноко - вый хаш·код. Если вы не переопределите метод hashCode, оно будет нарушено: два различных экземпляра с точки зрения метода equals могут быть логически равны, Однако для метода hashCode из класса Object это всего лишь два объекта, не имеющих между собой ничего общего. Поэтому метод hashCode скорее всего возвратит для этих объектов два случайных числа. а не одинаковых, как того требует соглашение.

 

35

 

 

В качестве примера рассмотрим следующий упрощенный класс PhoneNumber, в котором метод equals построен по рецепту из статьи 7:

import java.util.*;

public final class PhoneNumber {

private final short areaCode;

private final short exchange;

private final short extension;

  public PhoneNumber(int areaCode, int exchange,

                  int extension) {

   rangeCheck(areaCode, 999, "area code");

   rangeCheck(exchange, 999, "exchange");

   rangeCheck(extension, 9999, "extension");

   this.areaCode = (short) areaCode;

   this.exchange = (short) exchange;

   this.extension = (short) extension;

}

private static void rangeCheck(int arg, int max,

                              String name) {

   if (arg < 0 || arg > max)

      throw new IllegalArgumentException(name +": " + arg);

}

public boolean equals(Object o) {

   if (o == this)

       return true;

   if (!(o instanceof PhoneNumber))

       return false;

   PhoneNumber pn = (PhoneNumber)o;

   return pn.extension == extension &&

             pn.exchange == exchange &&

          pn.areaCode == areaCode;

}

 // Нет метода hashCode!

        // Остальное опущено

     }

 

Предположим, что вы попытались использовать этот класс с HashMap:

Мар m = new HashMap();

m. put (new PhbneNumber( 408, 867, 5309), "Jenny");

 

Вы вправе ожидать, что m.get(new PhoneNumber(408, 867, 5309)) возвратит строку "Jenny", однако он выдает null. Заметим, что здесь задействованы два экземпляра класса PhoneNumber: один используется для вставки в таблицу HashMap, а другой,

 

36

равный ему экземпляр,- для поиска. Отсутствие в классе PhoneNumber переопре­деленного метода hashCode приводит к тому, что двум равным экземплярам соот­ветствует разный хэш-код, т. е. имеем нарушение соглашений для этого метода. Как следствие, метод get ищет указанный телефонный номер в другом сегменте хэш-таблицы, а не там, где была сделана запись с помощью метода put. Разрешить эту проблему можно, поместив в класс PhoneNumber правильный метод hashCode.

Как же должен выглядеть метод hashCode? Написать действующий, но не слиш­ком хороший метод нетрудно. Например, следующий метод всегда приемлем, но поль­зоваться им не надо никогда:

 

 // Самая плохая из допуотимых хэш-функций – никогда

// не пользуйтеоь ею l

public int hashCode() { return 42; }

 

Данный метод приемлем, поскольку для равных объектов он гарантирует возврат одного и того же хэш-кода. Плохо то, что он гарантирует получение одного и того же хэш-кода для любого объекта. Соответственно, любой объект будет привязан к одно­му и тому же сегменту хэш-таблииы, а сами хэш-таблииы вырождаются в связные списки, для программ, время работы которых с ростом хэш-таблии должно увеличи­ваться линейно, имеет место квадратичная зависимость. Для больших хэш-таблии это равносильно переходу от работоспособного к неработоспособному варианту.

Хорошая хэш-функция стремится генерировать для неравных объектов различные хэш-коды. И это именно то, что подразумевает третье условие в соглашениях для hashCode. В идеале хэш-функция должна равномерно распределять любое возможное множество неравных экземпляров класса по всем возможным значениям хэш-кода. Достичь этого может быть чрезвычайно сложно. К счастью, не так трудно получить хорошее приближение. Приведем простой рецепт:

1. Присвойте переменной result (тип int) некоторое ненулевое число, скажем, 17.

2. Для каждого значимого поля f в вашем объекте (т. е. поля, значение которого принимается в расчет методом equals), выполните следующее:

а. Вычислите для поля хэш-код с (тип int):а

1. Если поле имеет тип boolean, вычислите (f ? О : 1).

2. Если поле имеет тип byte, char, short или int, вычислите (int)f.

3. Если поле имеет тип long, вычислите (int)(f - (f >>> 32)).

4. Если поле имеет тип float, вычислите Float. floatтoIntBits(f).

5. Если - тип double, вычислите Double. doubleToLongBits(f), а затем преобразуйте полученное значение, как указано в п. 2.a.3.

 

 

37

 

 

6. Если поле является ссылкой на объект, а метод equals

данного класса сравнивает это поле, рекурсивно вызывая другие методы equals, так же рекурсивно вызывайте для этого поля метод hashCode. Если требуется более сложное сравнение, вычислите для данного поля каноническое представление (canonical representation), а затем вызовите для него

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

7. Если поле является массивом, обрабатываете его так, как если бы каждый его элемент был отдельным полем. Иными словами, вычислите хэш-код для каждого значимого элемента, рекурсивно применяя данные правила, а затем объедините полученные значения так, как описано в п. 2.Ь.

b. Объедините хэш-код с, вычисленный на этапе а, с текущим значением поля resul t следующим образом:

result = 37*result + с;

3. Верните значение resul t.

4. Закончив писать метод hashCode, спросите себя, имеют ли равные экземпляры одинаковый хэш-код. Если нет, выясните, в чем причина, и устраните проблему.

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

На этапе 1 используется ненулевое начальное значение. Благодаря этому не будут игнорироваться те обрабатываемые в первую очередь поля, у которых значение хэш-­кода, полученное на этапе 2.а, оказалось нулевым. Если же на этапе 1 в качестве начального значения использовать нуль, то ни одно из этих обрабатываемых в первую очередь полей не сможет повлиять на общее значение хэш-кода, что способно привес­ти к увеличению числа коллизий. Число 17 выбрано произвольно.

Умножение на шаге 2.Ь создает зависимость значения хэш-кода от очередности обработки полей, а это обеспечивает гораздо лучшую хэш-функцию в случае, когда в классе много одинаковых полей. Например, если из хэш-функции для класса String, построенной по этому рецепту, исключить умножение, то все анаграммы (слова, полученные от некоего исходного слова путем перестановки букв) будут иметь один и тот же хэш-код. Множитель 37 выбран потому, что является простым нечетным числом. Если бы это было четное число и при умножении произошло переполнение,

 

 

38

 

информация была бы потеряна, поскольку умножение числа на 2 равнозначно его , арифметическому сдвигу. Хотя преимущества от применения простых чисел не столь очевидны, именно их принято использовать для этой цели.

Используем описанный рецепт для класса PhoneNumber. В нем есть три значимых поля, все имеют тип short. Прямое применение рецепта дает следующую хэш-функцию

public int hashCode() {

int result = 17;

result = 37*result + areaCode;

result = 37*result + exchange;

               result = 37*result + extension;                  \

return result;

}

Поскольку этот метод возвращает результат простого детерминированного вычисления, исходными данными для которого являются три значащих поля в эк­земпляре PhoneNumber, очевидно, что равные экземпляры PhoneNumber будут иметь равный хэш-код. Фактически этот метод является абсолютно правильной реализа­цией hashCode для класса PhoneNumber наряду с методами из библиотек Java версии 1.4. Он прост, довольно быстр и правильно разносит неравные телефонные номера по разным сегментам хэш-таблицы.

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

// Отложенная инициализация, кэшируемый hashCode

        private volatile int hashCode = о;        // (см. статью 48)

public int hashCode() {

if (hashCode == о) {

int result = 17;

result = 37*result + areaCode;

result = 37*result + exchange;

result = 37*result + extension;

hashCode = result;

}

return hashCode;

}

 

39

 

 

Рецепт, изложенный в этой статье, позволяет создавать довольно хорошие хэш-функции, однако он не соответствует ни современным хэш-функциям, ни хэш­-функциям из библиотек для платформы Java, которые реализованы в версии 1.4. Раз­работка подобных хэш-функций является предметом активных исследований, которые лучше оставить математикам и ученым, работающим в области теории вычислительных машин. Возможно, в последней версии платформы Java для библиотечных классов будут представлены современные хэш-функции, а также методы-утилиты, которые позволят рядовым программистам самостоятельно создавать такие хэш-функции. Пока же описанные в этой статье приемы применяются для большинства приложений.

Повышение производительности не стоит того, чтобы при вычислении хэш-кода игнорировать значимые части объекта. Хотя хэш-функция способна работать быстрее, ее качество может ухудшиться до такой степени, что обработка хэш-таБлицы будет производиться слишком медленно. В частности, не исключено, что фэш-функция столкнется с большим количеством экземпляров, которые существенно разнятся как раз в тех частях, которые вы решили игнорировать. В этом случае хэш-функция сопоставит всем этим экземплярам всего лишь несколько значений хэш-кода. Соответственно, коллекция, основанная на хэш-функциях, будет вызывать падение производительности в квадратичной зависимости от числа элементов. Это не просто теоретическая проблема. Хэш-функция класса String, реализованная во всех версиях платформы Java до номера 1,2, проверялась самое большее для строк с 16 сим­волами и равномерным распределением пробелов по всей строке, начиная с первого символа. для больших коллекций иерархических имен, таких как URL, эта хэш­фую(ция демонстрировала то патологическое поведение, о котором здесь говорилось.

у многих классов в библиотеках для платформы Java, таких как Str1ng, Integer и Date, конкретное значение, возвращаемое методом hashCode, определяется как функ­ция от значения экземпляра. Вообще говоря, это не слишком хорошая идея, поскольку она серьезно ограничивает возможности по улучшению хэш-функций в будущих вер­сиях. Если бы вы оставили детали реализации фэш-йункции не конкретизированными и в ней обнаружился бы изъян, вы бы могли исправить эту хэш-функцию в следующей версии, не опасаясь утратить совместимость с теми клиентами, работа которых зависит от того, какое конкретное значение возвращает хэш-функция.

 

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: