Лучший способ создания хеш-функции

Question

Я создаю составной ключ для хэш-карты в java и хочу определить собственный хэш-код для каждого из этих объектов. Мой вопрос в том, что является лучшей методологией двух ниже. Мой составной ключ имеет три атрибута String и один атрибут int.

public int hashCode(){ 
    return (className + methodName + uniqueNumber).hashCode(); 
} 

public int hashCode(){ 
    return (className + methodName + desc + uniqueNumber).hashCode(); 
} 

я должен иметь Classname, имяМетод и уникальный номер, чтобы гарантировать, что каждый ключ имеет уникальный хэш-код. Я хочу пойти с методом, который дает меньше шансов на столкновение. Моя интуиция заключается в том, что чем больше атрибутов, которые я «добавляю» к моей хэш-карте, тем меньше вероятность столкновения. Однако я не совсем уверен, что это правильно.

Answer 1

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

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

Предполагая, первый пример:

public int hashCode() { 
    int h = className.hashCode() * 23; 
    h += methodName.hashCode() * 17; 
    h += uniqueNumber; 
    return h; 
} 

Ото, если uniqueNumber на самом деле уникальный, можно упростить:

public int hashCode() {return uniqueNumber;} 

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

Теперь это очень важно: «Идентификация экземпляра» - это совсем другая вещь для хеша на & lookup, от «Value»! Вы не можете использовать тот же хэш-код & карты для обоих.

Например, если вам нужен ключ (ИмяКласс, MethodName) -> SomeValue поиск, что бы «значение» поиск & нужен будет хэширование по ИмяКлассу & значений имяМетода так, что он может быть повторен: то есть, так вы можете создать ключ для Map.get() для выполнения поиска.

«Идентификация экземпляра» на самом деле имеет встроенную поддержку для хэширования & карт на Java - это называется IdentityHashMap.

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

Когда вы переходите к поиску позже, как вы получите правильный uniqueNumber для извлечения данных? У меня такое ощущение, что:

1. Либо должен быть первый класс объект там вместо этого, который можно использовать в качестве ключа непосредственно (так не требуется класс CompositeKey больше), или что

2. Вы не может повторно получить uniqueNumber, и в этом случае он не работает/не требуется в любом случае.

Резюмируя: если uniqueNumber действительно необходимо или это применимо вообще, я бы ожидать, что она уже воплощен в первый класс объекта. Это не так. Похоже, вы, вероятно, должны использовать ключ на основе значений и сбросить бит uniqueNumber (отсюда как минимум).

Так что моя рекомендация:

public int hashCode() { 
    int h = className.hashCode() * 23; 
    h += methodName.hashCode() * 17; 
    h += desc.hashCode(); 
    return h; 
} 

Позвольте мне знать, если это помогает.

Answer 2

Несколько комментариев;

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

(2) Хэш-коды должны отражать состояние экземпляра объекта, а не класса объекта. Такие вещи, как имя класса, не будут входить в него. Если, конечно, это IS - данные экземпляра класса, например, в классе, который представляет собой один кадр трассировки стека.

(3) Хороший хеш-код будет иметь большое количество возможных значений, и эти значения будут распределены вероятностно таким образом, чтобы столкновения были НЕВЫПОЛНЕННЫ.

(4) В Java хэш-код должен соответствовать Object.equals(). См. Javadoc для java.lang.Object для справки.