Понимание работы equals и hashCode в HashMap

У меня есть этот тестовый код:

import java.util.*; class MapEQ { public static void main(String[] args) { Map m = new HashMap(); ToDos t1 = new ToDos("Monday"); ToDos t2 = new ToDos("Monday"); ToDos t3 = new ToDos("Tuesday"); m.put(t1, "doLaundry"); m.put(t2, "payBills"); m.put(t3, "cleanAttic"); System.out.println(m.size()); } } class ToDos{ String day; ToDos(String d) { day = d; } public boolean equals(Object o) { return ((ToDos)o).day == this.day; } // public int hashCode() { return 9; } } 

Когда // public int hashCode() { return 9; } // public int hashCode() { return 9; } m.size() возвращает 2, когда он оставлен прокомментированным, он возвращает три. Зачем?

У вас есть лишние equals без переопределения hashCode . Вы должны убедиться, что для всех случаев, когда equals возвращает true для двух объектов, hashCode возвращает одно и то же значение. Хэш-код – это код, который должен быть равен, если два объекта равны (обращение не обязательно должно быть истинным). Когда вы помещаете свое жестко закодированное значение в 9, вы снова удовлетворяете контракт.

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

HashMap использует hashCode() , == и equals() для поиска входа. Последовательность поиска для заданного ключа k выглядит следующим образом:

  • Используйте k.hashCode() чтобы определить, в каком ведре запись хранится, если есть
  • Если найдено, для ключа k1 каждой записи в этом ковше, если k == k1 || k.equals(k1) k == k1 || k.equals(k1) , затем верните запись k1
  • Любые другие результаты, без соответствующей записи

Чтобы продемонстрировать использование примера, предположим, что мы хотим создать HashMap где ключи являются «логически эквивалентными», если они имеют одинаковое целочисленное значение, представленное classом AmbiguousInteger . Затем мы создаем HashMap , помещаем одну запись, затем пытаемся переопределить ее значение и получить значение по ключу.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } } HashMap map = new HashMap<>(); // logically equivalent keys AmbiguousInteger key1 = new AmbiguousInteger(1), key2 = new AmbiguousInteger(1), key3 = new AmbiguousInteger(1); map.put(key1, 1); // put in value for entry '1' map.put(key2, 2); // attempt to override value for entry '1' System.out.println(map.get(key1)); System.out.println(map.get(key2)); System.out.println(map.get(key3)); Expected: 2, 2, 2 

Не переопределяйте hashCode() и equals() : по умолчанию Java генерирует разные значения hashCode() для разных объектов, поэтому HashMap использует эти значения для сопоставления key1 и key2 в разных ведрах. key3 не имеет соответствующего ведра, поэтому он не имеет значения.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 2, set as entry 2[1] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 2, get as entry 2[1] map.get(key3); // map to no bucket Expected: 2, 2, 2 Output: 1, 2, null 

Только переопределить hashCode() : HashMap отображает key1 и key2 в одно и то же ведро, но они остаются разными записями из-за того, что оба key1 == key2 и key1.equals(key2) сбой, поскольку по умолчанию equals() использует == check и они ссылаются на разные случаи. key3 не работает как == и equals() проверяет key1 и key2 и, следовательно, не имеет соответствующего значения.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[2] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[2] map.get(key3); // map to bucket 1, no corresponding entry Expected: 2, 2, 2 Output: 1, 2, null 

Только переопределить equals() : HashMap отображает все ключи в разные ведра из-за разного hashCode() . == или equals() здесь не имеет значения, так как HashMap никогда не достигает точки, в которой он должен их использовать.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 2, set as entry 2[1] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 2, get as entry 2[1] map.get(key3); // map to no bucket Expected: 2, 2, 2 Actual: 1, 2, null 

Переопределите как hashCode() и equals() : HashMap отображает key1 , key2 и key3 в одно и то же ведро. == check fail при сравнении разных экземпляров, но equals() проверяет проход, поскольку все они имеют одинаковое значение и считаются логически эквивалентными нашей логикой.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return value; } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[1], override value map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[1] map.get(key3); // map to bucket 1, get as entry 1[1] Expected: 2, 2, 2 Actual: 2, 2, 2 

Что делать, если hashCode() является случайным? : HashMap назначит другое ведро для каждой операции, и поэтому вы никогда не найдете ту же запись, которую вы положили раньше.

 class AmbiguousInteger { private static int staticInt; private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return ++staticInt; // every subsequent call gets different value } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 2, set as entry 2[1] map.get(key1); // map to no bucket, no corresponding value map.get(key2); // map to no bucket, no corresponding value map.get(key3); // map to no bucket, no corresponding value Expected: 2, 2, 2 Actual: null, null, null 

Что, если hashCode() всегда одно и то же? : HashMap отображает все ключи в одно большое ведро. В этом случае ваш код функционально корректен, но использование HashMap практически избыточно, так как для любого извлечения потребуется перебрать все записи в этом одиночном ведре в O (N) время ( или O (logN) для Java 8 ), что эквивалентно использованию List .

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return 0; } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[1] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[1] map.get(key3); // map to bucket 1, get as entry 1[1] Expected: 2, 2, 2 Actual: 2, 2, 2 

А что, если equals всегда ложные? : == проверять проходы, когда мы сравниваем один и тот же экземпляр с самим собой, но в противном случае не выполняем иначе, equals проверки всегда терпят неудачу, поэтому key1 , key2 и key3 считаются «логически разными» и сопоставляются с разными записями, хотя они все еще находятся в одном и том же из-за того же hashCode() .

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return 0; } @Override public boolean equals(Object obj) { return false; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[2] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[2] map.get(key3); // map to bucket 1, no corresponding entry Expected: 2, 2, 2 Actual: 1, 2, null 

Хорошо, что, если equals всегда истинны сейчас? : вы в основном говорите, что все объекты считаются «логически эквивалентными» для другого, поэтому все они сопоставляются с одним и тем же ведром (из-за того же hashCode() ), той же записи.

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return 0; } @Override public boolean equals(Object obj) { return true; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[1], override value map.put(new AmbiguousInteger(100), 100); // map to bucket 1, set as entry1[1], override value map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[1] map.get(key3); // map to bucket 1, get as entry 1[1] Expected: 2, 2, 2 Actual: 100, 100, 100 

Я не могу подчеркнуть, что вы должны прочитать главу 3 в « Эффективной Java» (предупреждение: pdf-ссылка). В этой главе вы узнаете все, что вам нужно знать об основных методах в Object , и, в частности, о equals контракте. У Джоша Блоха есть отличный рецепт для переопределения метода equals которым вы должны следовать. И это поможет вам понять, почему вы должны использовать equals и not == в вашей конкретной реализации метода equals .

Надеюсь это поможет. ПОЖАЛУЙСТА ПРОЧИТАЙТЕ ЭТО. (По крайней мере, первые пара предметов … и тогда вам захочется прочитать остальное :-).

-Том

Если вы не переопределите метод hashCode (), ваш class ToDos наследует метод hashCode () по умолчанию от Object, который дает каждому объекту отдельный хеш-код. Это означает, что t1 и t2 имеют два разных хеш-кода, даже если бы вы их сравнивали, они были бы равны. В зависимости от конкретной реализации hashmap карта может свободно хранить их отдельно (и это на самом деле происходит).

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

Лучшая реализация даст объекты, не равные различным хеш-кодам, например:

 public int hashCode() { return (day != null) ? day.hashCode() : 0; } 

когда вы комментируете, он возвращает 3;

потому что hashCode (), унаследованный от объекта, ТОЛЬКО называется, который возвращает 3 разных hash-кода для 3 объектов ToDos. Неравные hash-коды означают, что 3 объекта предназначены для разных ведер и равно () возвращают false, поскольку они являются первыми участниками в своих соответствующих ковши. Если hash-коды различны, то заранее понятно, что объекты неравны. Они поедут в разные ведра.

когда вы раскомментируете, он возвращает 2;

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

hashCode () для t3 равен 9 и, поскольку он является первым участником, equals () является ложным и t3 вставлен в bucket-say bucket0.

Тогда t2, получая тот же hashCode (), что 9 предназначен для одного и того же bucket0, следующий equals () на уже проживающем t3 в bucket0 возвращает false по определению overridden equal ().

Теперь t1 с hashCode () как 9 также предназначен для bucket0, а последующий вызов equals () возвращает true по сравнению с ранее существовавшим t2 в том же ведро. t1 не может войти в карту. Таким образом, размер сети составляет 2 -> {ToDos @ 9 = cleanAttic, ToDos @ 9 = payBills}

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

Согласно эффективной Java,

Всегда переопределяйте hashCode (), когда вы переопределяете equals ()

Ну зачем? Простой, потому что разные объекты (контент, а не ссылки) должны иметь разные hash-коды; с другой стороны, равные объекты должны получать одинаковый hash-код.

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

В конкретном случае (т. Е. Тот, который был представлен выше), когда hashCode () комментируется , для каждого экземпляра генерируется случайное число (поведение, унаследованное Object) как hash, equals () проверяет ссылки String (помните Java String Pool), поэтому equals () должен возвращать true, но hashCode () нет, в результате сохраняется 3 разных объекта . Давайте посмотрим, что произойдет, если hashCode () соблюдает контракт, но всегда возвращается 9 без раскопок . Ну, hashCode () постоянно то же самое, equals () возвращает true для двух строк в пуле (т.е. «понедельник»), и для них ведро будет таким же, что и в сохранении всего лишь 2 элементов .

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

Когда hashCode раскоментирован, HashMap видит t1 и t2 как одно и то же; таким образом, значение t2 сгибает значение t1. Чтобы понять, как это работает, обратите внимание, что когда hashCode возвращает одно и то же для двух экземпляров, они попадают в одно и то же ведро HashMap. Когда вы пытаетесь вставить вторую вещь в одно и то же ведро (в этом случае t2 вставляется, когда t1 уже присутствует), HashMap сканирует ведро для другого ключа, равного. В вашем случае t1 и t2 равны, потому что они имеют один и тот же день. В этот момент «payBills» clobbers «doLaundry». Что касается t2 clobbers t1 как ключа, я считаю, что это не определено; таким образом, допускается либо поведение.

Здесь есть несколько важных вещей:

  1. Действительно ли два экземпляра ToDos равны только потому, что они имеют тот же день недели?
  2. Всякий раз, когда вы реализуете equals, вы должны реализовать hashCode, чтобы любые два объекта, которые равны, также имеют одинаковые значения hash-кода. Это фундаментальное предположение, которое делает HashMap. Это, вероятно, также относится ко всему, что полагается на метод hashCode.
  3. Создайте свой метод hashCode, чтобы hash-коды были равномерно распределены; в противном случае вы не получите преимущества hashирования. С этой точки зрения возrotation 9 – одна из худших вещей, которые вы можете сделать.

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

Хэш-таблицы обычно работают, определяя семейство признаков, причем один из них будет применим к хеш-коду каждого объекта (например, «соответствует конгруэнту 0 mod 47», «соответствует 1 mod 47» и т. Д.), А затем имея набор объектов с каждой чертой. Если кому-то дается объект и он может определить, какая черта относится к нему, можно знать, что он должен быть в коллекции вещей с этой чертой.

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

Всякий раз, когда вы создаете новый объект в Java, ему будет присвоен уникальный hash-код JVM. Если бы вы не переопределили метод hashcode, тогда объект получит уникальный hascode и, следовательно, уникальное ведро (Imagine bucket – это не что иное, как место в памяти, где JVM отправится на поиск объекта).

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

В вашем случае, когда вы не комментируете метод hashcode, hashmap сначала ищет ведро с тем же hash-кодом, который возвращает метод. И каждый раз вы возвращаете один и тот же hash-код. Теперь, когда hashmap находит это ведро, он будет сравнивать текущий объект с объектом, находящимся в ведре, используя метод euqals. Здесь он находит «понедельник», и поэтому реализация hashmap не позволяет добавить его снова, потому что уже есть объект, имеющий один и тот же hash-код и ту же реализацию euqality.

Когда вы комментируете метод hashcode, JVM просто возвращает другой hash-код для всех трех объектов, и, следовательно, он даже не беспокоится о компарационных объектах с использованием метода equals. И поэтому в Map добавлено три разных объекта с помощью реализации hashmap.

  • Hashcode и Equals для Hashset
  • Какова лучшая страtagsя для Equals и GetHashCode?
  • Почему нам нужно переопределить метод equals () в Java?
  • Разница между пустой и пустой ("") строкой Java
  • Как проверить, равна ли моя строка нулевой?
  • Как следует использовать равенства и hash-код при использовании JPA и Hibernate
  • Есть ли утилита отражения Java для глубокого сравнения двух объектов?
  • почему equals () метод, когда у нас есть оператор?
  • Разность C # между == и Equals ()
  • Метод Java - equals в базовом classе и в подclassах
  • Почему эти ==, но не `equals ()`?
  • Давайте будем гением компьютера.