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

Он не говорит, что хэш-код для объекта должен быть полностью уникальным, только то, что хэш-код для двух одинаковых объектов возвращает один и тот же хэш-код. Совершенно законно, чтобы два неравных объекта возвращали один и тот же хэш-код. Однако чем более уникальным является распределение хэш-кода по набору объектов, тем выше производительность, которую вы получите от 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;
}

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

Для простых атрибутов в некоторых IDE есть построители функций хэш-кода.

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

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

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

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

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

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

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

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

Редактировать на основе комментариев:

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

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

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

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

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

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

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

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

@ javadoc

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

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