Как убедиться, что hashCode() согласуется с equals()?
https://stackoverflow.com/questions/410236
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
При переопределении функции equals() объекта java.lang.javadocs предполагают, что,
обычно необходимо переопределять метод hashCode всякий раз, когда этот метод переопределяется, чтобы поддерживать общий контракт для метода hashCode, в котором говорится, что равные объекты должны иметь равные хэш-коды.
Метод hashCode() должен возвращать уникальное целое число для каждого объекта (это легко сделать при сравнении объектов на основе расположения в памяти, просто верните уникальное целое число адрес объекта)
Как следует переопределить метод hashCode(), чтобы он возвращал уникальное целое число для каждого объекта, основанного только на свойствах этого объекта?
public class People{
public String name;
public int age;
public int hashCode(){
// How to get a unique integer based on name and age?
}
}
/*******************************/
public class App{
public static void main( String args[] ){
People mike = new People();
People melissa = new People();
mike.name = "mike";
mike.age = 23;
melissa.name = "melissa";
melissa.age = 24;
System.out.println( mike.hasCode() ); // output?
System.out.println( melissa.hashCode(); // output?
}
}
Решение
В нем не говорится, что хэш-код для объекта должен быть полностью уникальным, только то, что хэш-код для двух равных объектов возвращает один и тот же хэш-код.Совершенно законно, когда два неравных объекта возвращают один и тот же хэш-код.Однако, чем более уникальным будет распределение хэш-кода по набору объектов, тем более высокую производительность вы получите от хэш-карт и других операций, использующих хэш-код.
IDE, такие как IntelliJ Idea, имеют встроенные генераторы для equals и hashCode, которые обычно неплохо справляются с созданием "достаточно хорошего" кода для большинства объектов (и, вероятно, лучше, чем некоторые чрезмерно умные хэш-функции ручной работы).
Например, вот функция хэш-кода, которую Idea генерирует для вашего класса People:
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
Другие советы
Я не буду вдаваться в подробности уникальности хэш-кода, поскольку Марк уже обращался к этому вопросу.Для вашего People класс, сначала вам нужно решить, что означает равенство людей.Может быть, равенство основано исключительно на их имени, может быть, оно основано на имени и возрасте.Это будет зависеть от конкретного домена.Допустим, равенство основано на имени и возрасте.Ваш переопределенный equals было бы похоже
public boolean equals(Object obj) {
if (this==obj) return true;
if (obj==null) return false;
if (!(getClass().equals(obj.getClass())) return false;
Person other = (Person)obj;
return (name==null ? other.name==null : name.equals(other.name)) &&
age==other.age;
}
В любое время, когда вы переопределяете equals вы должны переопределить hashCode.Более того, hashCode не может использовать в своих вычислениях больше полей, чем equals сделал.Большую часть времени вы должны добавлять или исключать-или хэш-код различных полей (хэш-код должен быстро вычисляться).Таким образом, действительный hashCode метод может выглядеть следующим образом:
public int hashCode() {
return (name==null ? 17 : name.hashCode()) ^ age;
}
Обратите внимание, что ниже приведено недействительно поскольку он использует поле, которое equals не сделал (рост).В этом случае два "равных" объекта могут иметь разный хэш-код.
public int hashCode() {
return (name==null ? 17 : name.hashCode()) ^ age ^ height;
}
Кроме того, вполне допустимо, чтобы два не равных объекта имели один и тот же хэш-код:
public int hashCode() {
return age;
}
В этом случае возраст Джейн 30 лет не равен возрасту Боба 30 лет, но оба их хэш-кода равны 30.Хотя это допустимо, это нежелательно для производительности в коллекциях на основе хэша.
Другой вопрос заключается в том, есть ли какие-то базовые низкоуровневые вещи, которые должны знать все программисты, и я думаю, что поиск по хэшу является одним из них.Итак, поехали.
Хэш-таблица (обратите внимание, что я не использую фактическое имя класса) в основном представляет собой массив связанных списков.Чтобы найти что-то в таблице, вы сначала вычисляете хэш-код этого чего-то, затем изменяете его в соответствии с размером таблицы.Это индекс в массиве, и вы получаете связанный список по этому индексу.Затем вы просматриваете список до тех пор, пока не найдете свой объект.
Поскольку извлечение массива равно O (1), а обход связанного списка равен O (n), вам нужна хэш-функция, которая создает как можно более случайное распределение, чтобы объекты были хэшированы в разные списки.Каждый объект может возвращать значение 0 в качестве своего хэш-кода, и хэш-таблица все равно будет работать, но по сути это будет длинный связанный список в элементе 0 массива.
Вы также обычно хотите, чтобы массив был большим, что увеличивает вероятность того, что объект будет находиться в списке длиной 1.Java HashMap, например, увеличивает размер массива, когда количество записей в карте составляет > 75% от размера массива.Здесь есть компромисс:у вас может быть огромный массив с очень небольшим количеством записей и пустой тратой памяти, или массив меньшего размера, где каждый элемент массива представляет собой список с > 1 записью, и вы можете тратить время на обход.Идеальный хэш назначил бы каждому объекту уникальное местоположение в массиве, без потери места.
Термин "идеальный хэш" является реальным термином, и в некоторых случаях вы можете создать хэш-функцию, которая предоставляет уникальный номер для каждого объекта.Это возможно только тогда, когда вы знаете набор всех возможных значений.В общем случае вы не можете достичь этого, и будут некоторые значения, которые возвращают один и тот же хэш-код.Это простая математика:если у вас есть строка длиной более 4 байт, вы не сможете создать уникальный 4-байтовый хэш-код.
Один интересный лакомый кусочек:размер хэш-массивов обычно определяется на основе простых чисел, чтобы дать наилучшие шансы на случайное распределение при модификации результатов, независимо от того, насколько случайными на самом деле являются хэш-коды.
Редактировать на основе комментариев:
1) Связанный список - не единственный способ представления объектов, имеющих одинаковый хэш-код, хотя именно этот метод используется хэш-картой JDK 1.5.Несмотря на меньшую эффективность использования памяти, чем простой массив, он, возможно, создает меньший отток при повторном хэшировании (поскольку записи могут быть отсоединены из одной корзины и повторно привязаны к другой).
2) Начиная с JDK 1.4, класс HashMap использует массив размером в степени 2;до этого он использовал 2 ^ N + 1, что, я считаю, является простым для N <= 32.Это не ускоряет индексацию массива как таковую, но позволяет вычислять индекс массива побитово, а не с делением, как отметил Нил Коффи.Лично я бы усомнился в этом как в преждевременной оптимизации, но, учитывая список авторов в HashMap, я предполагаю, что есть какая-то реальная выгода.
В общем случае хэш-код не может быть уникальным, так как существует больше значений, чем возможных хэш-кодов (целых чисел).Хороший хэш-код хорошо распределяет значения по целым числам.Плохой всегда может давать одно и то же значение и при этом быть логически правильным, это просто привело бы к неприемлемо неэффективным хэш-таблицам.
Для корректной работы хэш-таблиц равные значения должны иметь одинаковое хэш-значение.В противном случае вы могли бы добавить ключ в хэш-таблицу, затем попытаться найти его через равное значение с другим хэш-кодом и не найти его.Или вы могли бы поместить равное значение с другим хэш-кодом и иметь два равных значения в разных местах хэш-таблицы.
На практике вы обычно выбираете подмножество полей, которые будут учитываться как в методе hashCode(), так и в методе equals().
Я думаю, вы это неправильно поняли.Хэш-код не обязательно должен быть уникальным для каждого объекта (в конце концов, это хэш-код), хотя вы, очевидно, не хотите, чтобы он был идентичным для всех объектов.Однако вам нужно, чтобы он был идентичен всем равным объектам, иначе такие вещи, как стандартные коллекции, не работали бы (например, вы бы посмотрели что-то в наборе хэшей, но не нашли бы это).
Для простых атрибутов в некоторых IDE есть конструкторы функций hashcode.
Если вы не используете IDE, рассмотрите возможность использования Apahce Commons и класса HashCodeBuilder
Единственное договорное обязательство для hashCode заключается в том, чтобы он был последовательный.Поля, используемые при создании значения хэш-кода, должны быть одинаковыми или являться подмножеством полей, используемых в методе equals.Это означает, что возврат 0 для всех значений допустим, хотя и неэффективен.
Можно проверить, является ли хэш-код согласованным, с помощью модульного теста.Я написал абстрактный класс под названием EqualityTestCase - тестовый случай, который выполняет несколько проверок хэш-кода.Нужно просто расширить тестовый пример и реализовать два или три заводских метода.Тест выполняет очень грубую работу по проверке эффективности хэш-кода.
Это то, что говорится нам в документации относительно метода хэш-кода
@ javadoc
Всякий раз, когда он вызывается для одного и того же объекта более одного раза во время выполнения приложения Java, метод hashCode должен последовательно возвращать одно и то же целое число при условии, что никакая информация, используемая в сравнениях equals для объекта, не изменена.Это целое число не обязательно должно оставаться согласованным от одного выполнения приложения до другого выполнения того же самого приложения.
Существует понятие бизнес-ключа, которое определяет уникальность отдельных экземпляров одного и того же типа.Каждый конкретный тип (класс), моделирующий отдельную сущность из целевого домена (например,транспортное средство в системе автопарка) должно иметь бизнес-ключ, который представлен одним или несколькими полями класса.Методы equals() и hasCode() должны быть реализованы с использованием полей, которые составляют бизнес-ключ.Это гарантирует, что оба метода согласуются друг с другом.
