Как убедиться, что hashCode () соответствует equals ()? - PullRequest
Новая
       19

Как убедиться, что hashCode () соответствует equals ()?

21 голосов
/ 04 января 2009

При переопределении функции 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?
   }
}

Ответы [ 8 ]

28 голосов
/ 04 января 2009

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

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

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

public int hashCode() {
    int result = name != null ? name.hashCode() : 0;
    result = 31 * result + age;
    return result;
}
9 голосов
/ 04 января 2009

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

7 голосов
/ 04 января 2009

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

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

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

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

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

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

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

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

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

1 голос
/ 04 января 2009

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

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

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

0 голосов
/ 18 декабря 2010

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

0 голосов
/ 02 января 2010

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

@ javadoc

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

0 голосов
/ 19 октября 2009

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

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

0 голосов
/ 04 января 2009

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

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

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

...