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

Ответ 1

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

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

Ответ 2

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

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

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

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

-Tom

Ответ 4

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

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

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

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

Ответ 5

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

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

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

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

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(). Это гарантирует, что если два объекта равны, они всегда будут иметь одинаковые хэш-коды. hashCodes не следует воспринимать как псевдослучайные числа, поскольку они должны быть согласованы с equals()

Ответ 6

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

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

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

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

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

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

Ответ 7

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

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

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

Ответ 8

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

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

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

Ответ 9

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

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

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

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