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

Question

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

import java.util.*;

class MapEQ {

  public static void main(String[] args) {
   Map<ToDos, String> m = new HashMap<ToDos, String>();
   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; } не комментируется m.size() возвращает 2, когда его оставляют закомментированным, он возвращает три. Зачем?

Answer 1

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

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

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

class AmbiguousInteger {
    private final int value;

    AmbiguousInteger(int value) {
        this.value = value;
    }
}

HashMap<AmbiguousInteger, Integer> 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

Override hashCode() только: HashMap карты key1 а также key2 в одно и то же ведро, но они остаются разными записями из-за обоих key1 == key2 а также key1.equals(key2) проверки не выполняются, как по умолчанию equals() использования == проверьте, и они относятся к разным случаям. 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

Override 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 в том же ведре. == проверки не проходят при сравнении разных экземпляров, но 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

Answer 2

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

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

Answer 3

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

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

-Том

Answer 4

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

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

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

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

Answer 5

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

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

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

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

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

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

Answer 6

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

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

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

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

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

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

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

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

Answer 7

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

Здесь есть несколько важных вещей, о которых стоит подумать:

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

Answer 8

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

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

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

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

Answer 9

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

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

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