В Java, почему equals() и hashCode() должны быть последовательными?

Question

Если я переопределяю любой метод класса, он должен убедиться, что если A.equals(B) = true, то (A.hashCode() == B.hashCode) также должен быть правдой.

Может ли кто-нибудь показать мне простой пример, где, если это нарушено, это вызовет проблему? Я думаю, что это имеет какое-то отношение, если вы используете этот класс как тип ключей для Hashmap?

Answer 1

Sure:

public class Test { 
    private final int m, n; 

    public Test(int m, int n) { 
    this.m = m; 
    this.n = n; 
    } 

    public int hashCode() { return n * m; } 

    public boolean equals(Object ob) { 
    if (ob.getClass() != Test.class) return false; 
    Test other = (Test)ob; 
    return m == other.m; 
    } 
} 

с:

Set<Test> set = new HashSet<Test>(); 
set.put(new Test(3,4)); 
boolean b = set.contains(new Test(3, 10)); // false 

Технически это должно быть правдой, потому что м == 3 в обоих случаях.

В общем, HashMap работает следующим образом: он имеет переменное число, которое обычно называют «ведрами». Количество ведер может меняться со временем (при добавлении и удалении записей), но оно всегда равно 2.

Предположим, что данный HashMap имеет 16 ковшей. Когда вы вызываете put() для добавления записи, вычисляется hashCode() ключа, а затем берется маска в зависимости от размера ведер. Если вы (побитовое) и хэш-код() с 15 (0x0F) вы получите последние 4 бита, сравнявшись число от 0 до 15 включительно:

int factor = 4; 
int buckets = 1 << (factor-1) - 1; // 16 
int mask = buckets - 1; // 15 
int code = key.hashCode(); 
int dest = code & mask; // a number from 0 to 15 inclusive 

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

Так, чтобы найти, если данный ключ в карте уже:

1. Вычислить замаскированный хэш-код;
2. Найти подходящее ведро;
3. Если он пуст, ключ не найден;
4. Если значение не пустое, пропустите все записи в ведре, проверяя равен().

Просматривая ведро - это линейная операция (O (n)), но она находится на небольшом подмножестве. Определение ковша hashcode по существу постоянное (O (1)). Если ведра достаточно малы, то доступ к HashMap обычно описывается как «около O (1)».

Вы можете сделать пару замечаний об этом.

Во-первых, если у вас есть куча объектов, которые все возвращают 42 в качестве своего хеш-кода, то HashMap все равно будет работать, но он будет работать как дорогой список. Доступ будет O (n) (поскольку все будет в одном ковше независимо от количества ведер). На самом деле меня спрашивали в интервью.

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

Answer 2

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

Answer 3

Вот небольшой пример:

Set<Foo> myFoos = new HashSet<Foo>(); 
Foo firstFoo = new Foo(123,"Alpha"); 
myFoos.add(firstFoo); 

// later in the processing you get another Foo from somewhere 
Foo someFoo = //use imagination here...; 
// maybe you get it from a database... and it's equal to Foo(123,"Alpha) 

if (myFoos.contains(someFoo)) { 
    // maybe you win a million bucks. 
} 

Итак, представьте себе, что хэш-код, который будет создаваться для firstFoo является 99999 и ветры в определенном месте в myFoos HashSet. Позже, когда вы получите someFoo, и вы ищете его в myFoos HashSet, ему необходимо сгенерировать тот же хэш-код, чтобы его можно было найти.

Answer 4

Контейнеры, такие как HashSet, полагаются на функцию хэша, чтобы определить, куда ее поместить, и откуда ее получить, когда ее попросят. Если A.equals(B), то HashSet ожидает, что A будет в том же месте, что и B. Если вы положите A в со значением V, и найдите B, вы должны ожидать получить V назад (так как вы сказали A.equals(B)). Но если A.hashcode()! = B.hashcode(), то hashset может не найти, куда вы его положили.

Answer 5

Это обсуждается в Пункт 8: Всегда переопределить хэш-код при переопределении равно Джошуа Блоха Эффективное Java:

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

Вот контракт, скопированный из спецификации java.lang.Object:

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

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

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

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

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

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; 
    } 

    // No hashCode method! 
    ... // Remainder omitted 
} 

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

Map m = new HashMap(); 
m.put(new PhoneNumber(408, 867, 5309), "Jenny"); 

на данный момент, вы могли бы ожидать m.get(new PhoneNumber(408 , 867, 5309)) вернуться "Jenny", но возвращает null. Обратите внимание, что два экземпляра PhoneNumber: : Один используется для вставки в HashMap, а второй, равный, экземпляр используется для (попытки) . Ошибка класса PhoneNumber для переопределения hashCode вызывает два равных экземпляра, чтобы иметь неравные хеш-коды, в нарушение контракта hashCode. Поэтому метод get ищет номер телефона в другом хеш-ведре от , в котором он хранился по методу . Исправление этой проблемы равно простым, как предоставление правильного метода hashCode для класса PhoneNumber. [...]

Полный текст см. На Chapter 3.

Answer 6

Это точно из-за хеш-таблиц.

Из-за возможности коллизий хеш-кода хэш-таблицы также должны проверять идентификационную информацию, иначе таблица не может определить, нашел ли он объект, который он искал, или один с тем же хэш-кодом. Поэтому каждый get() в хеш-таблице вызывает key.equals(potentialMatch) перед возвратом значения.

Если equals() и hashCode() противоречат друг другу, вы можете получить очень непоследовательное поведение. Скажем, для двух объектов, a и b, a.equals(b) возвращает true, но a.hashCode() != b.hashCode(). Вставьте a и HashSet вернет false для .contains(b), но список, созданный из этого набора, вернет true (потому что список не использует хэш-коды).

HashSet set = new HashSet(); 
set.add(a); 
set.contains(b); // false 
new ArrayList(set).contains(b); // true 

Очевидно, что это может быть плохо.