То, как удостовериться, что хэш-код () согласовывается с, равняется ()?

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

В этом случае возраст Jane 30 не равен возрасту Bob 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; до этого это использовало 2^N+1, которому я верю, является главным для N < = 32. Это не ускоряет индексацию массива по сути, но действительно позволяет индексу массива быть вычисленным с поразрядным И а не подразделение, как отмечено Neil Coffey. Лично, я подверг бы сомнению это как преждевременную оптимизацию, но, учитывая список авторов на HashMap, я предположу, что существует некоторая реальная выгода.

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

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

На практике Вы обычно выбираете подмножество полей, которые будут приняты во внимание в обоих хэш-код () и равняние () метод.

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

Для простых атрибутов, некоторые IDE имеют разработчиков функции хэш-кода.

, Если Вы не используете IDE, рассмотрите использование палаты общин Apahce и класса HashCodeBuilder

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

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

Об этом говорится в документации как о методе хэш-кода

@ javadoc

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