Подтвердить что ты не робот

Как обеспечить соответствие hashCode() с equals()?

При переопределении функции equals() объекта java.lang.Object 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?
   }
}
4b9b3361

ОТВЕТЫ

Ответ 1

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

В средах IDE, таких как IntelliJ Idea, есть встроенные генераторы для equals и hashCode, которые обычно выполняют довольно хорошую работу при разработке кода "достаточно хорошо" для большинства объектов (и, вероятно, лучше, чем некоторые чрезмерно умные хеш-функции с ручной обработкой).

Например, здесь функция hashCode, которую Idea генерирует для вашего класса People:

public int hashCode() {
    int result = name != null ? name.hashCode() : 0;
    result = 31 * result + age;
    return result;
}

Ответ 2

Я не буду вдаваться в подробности уникальности hashCode, поскольку Марк уже обратился к ней. Для вашего класса 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 должен быстро вычисляться). Таким образом, действительный метод 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. Хотя это допустимо, это нежелательно для производительности в коллекциях на основе хэшей.

Ответ 3

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

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

Так как поиск массива - O (1), а связанный обход списка - O (n), вы хотите, чтобы хеш-функция создавала как можно более случайное распределение, чтобы объекты были хэшированы в разные списки. Каждый объект может вернуть значение 0 в качестве своего хэш-кода, а хэш-таблица все равно будет работать, но по существу это будет длинный связанный список в элементе 0 массива.

Вы также обычно хотите, чтобы массив был большим, что увеличивает вероятность того, что объект будет в списке длины 1. Например, Java HashMap увеличивает размер массива, когда количество записей на карте > 75% от размера массива. Здесь есть компромисс: у вас может быть огромный массив с очень маленькими записями и ненужной памятью или меньший массив, где каждый элемент в массиве - это список s > 1 записями и тратится время на перемещение. Идеальный хэш присваивает каждому объекту уникальное местоположение в массиве без пробелов.

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

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

Изменить на основе комментариев:

1) Связанный список не является единственным способом представления объектов, имеющих один и тот же хэш-код, хотя это метод, используемый JDK 1.5 HashMap. Хотя он менее эффективен в памяти, чем простой массив, он, возможно, создает меньше отскока при повторной посылке (поскольку записи могут быть отсоединены от одного ведра и перенаправлены на другой).

2) Начиная с JDK 1.4, класс HashMap использует массив размером от 2; до этого он использовал 2 ^ N + 1, который, по моему мнению, является простым для N <= 32. Это не ускоряет индексирование массива как таковое, но позволяет вычислять индекс массива с побитовым И, а не делением, как отметил Нил Коффи. Лично я бы поставил под сомнение это как преждевременную оптимизацию, но, учитывая список авторов на HashMap, я предполагаю, что есть реальная польза.

Ответ 4

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

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

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

Ответ 5

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

Для простых атрибутов некоторые IDE имеют встроенные функции hashcode.

Если вы не используете IDE, рассмотрите возможность использования Apahce Commons и класса HashCodeBuilder

Ответ 6

Единственное контрактное обязательство для hashCode заключается в том, что оно согласовано. Поля, используемые при создании значения hashCode, должны быть одинаковыми или подмножеством полей, используемых в методе equals. Это означает, что возврат 0 для всех значений действителен, хотя и неэффективен.

Можно проверить, совместим ли hashCode с помощью unit test. Я написал абстрактный класс под названием EqualityTestCase, который выполняет несколько проверок hashCode. Просто нужно расширить тестовый пример и реализовать два или три метода factory. Тест выполняет очень грубую работу по тестированию, если hashCode эффективен.

Ответ 7

Это то, что документация говорит нам о методе хэш-кода

@javadoc

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

Ответ 8

Существует понятие бизнес-ключа, которое определяет уникальность отдельных экземпляров того же типа. Каждый конкретный тип (класс), который моделирует отдельный объект из целевого домена (например, транспортное средство в системе флота), должен иметь бизнес-ключ, который представлен одним или несколькими полями классов. Методы equals() и hasCode() должны быть реализованы с использованием полей, составляющих бизнес-ключ. Это гарантирует, что оба метода согласуются друг с другом.