Что такое разумное значение для вычисления хэш-кода? [Дубликат]

класс HashTest { int i ; int j ; public int hashCode () { final int prime = 31 ; int result = prime + i ; result = prime * result + j ; результат возврата ; } } v class = "question-status question-originalals-of-duplicate">

На этот вопрос уже есть ответ:

Eclipse 3.5 имеет очень приятную функцию для генерации функций Java hashCode (). Он будет генерировать, например (немного укорочен :)

i

(Если у вас больше атрибутов в классе, jповторяется для каждого дополнительного атрибута. Для ints .hashCode () можно опустить.)

Это кажется прекрасным, но для выбора 31 для простого. Вероятно, это взято из реализации hashCode Java String , которая использовалась по причинам производительности, которые давно прошли после внедрения аппаратных множителей. Здесь у вас много столкновений hashcode для небольших значений i и j: например (i = -1) и (-1,31) имеют одинаковое значение. Я думаю, что это Bad Thing (TM), так как небольшие значения происходят часто. Для String.hashCode вы также найдете много коротких строк с одним и тем же хэш-кодом, например «Ca» и «DB». Если вы возьмете большой премьер, эта проблема исчезнет, ??если вы выберете правое правое.

Итак, мой вопрос: что хорошего выбора? Какие критерии вы применяете для его поиска?

Это называется общим вопросом, поэтому я не хочу давать диапазон для i и j. Но я полагаю, что в большинстве приложений относительно небольшие значения встречаются чаще, чем большие. (Если у вас большие значения, выбор премьер-версии, вероятно, неважен.) Это может не сильно повлиять, но лучший выбор - простой и понятный способ улучшить это - так почему бы не сделать это? Commons lang HashCodeBuilder также предлагает любопытно небольшие значения.

( Уточнение : это не дубликат Почему хэш-код Java в String использует 31 как множитель? Поскольку мой вопрос не связан с историей 31 в JDK, а на том, что будет лучшим значением в новом коде используя тот же базовый шаблон. Ни один из ответов там не пытается ответить на этот вопрос.)

java,hashcode,primes,java,

49

Ответов: 6


67 ">голосов принято

Я рекомендую использовать 92821 . Вот почему.

Чтобы дать осмысленный ответ на этот вопрос, вы должны знать что-то о возможных значениях iи j. Единственное, о чем я могу думать в целом, это то, что во многих случаях небольшие значения будут более распространены, чем большие значения. (Шансы 15, показанные как ценность в вашей программе, намного лучше, чем, скажем, 438281923.) Таким образом, кажется хорошей идеей сделать наименьшее столкновение хэш-кодов как можно большим, выбирая подходящий премьер. Для 31 это довольно плохо - уже j=31и у i=0вас есть такое же значение хеш - функции , как и для j=0и Math.abs(i) + Math.abs(j).

Поскольку это интересно, я написал небольшую программу, которая искала весь диапазон int для лучшего простого в этом смысле. То есть для каждого штриха я искал минимальное значение i,jпо всем значениям, 0,0которые имеют один и тот же хэш-код 0,0, а затем заняли первое место, где это минимальное значение как можно больше.

Drumroll : лучший премьер в этом смысле - 486187739 (с наименьшим столкновением i=-25486, j=67194). Почти так же хорошо и намного легче запомнить 92821 с наименьшим столкновением i=-46272 and j=46016.

Если вы дадите «маленький» другой смысл и хотите быть как минимум минимальным Math.sqrt(i*i+j*j)для столкновения, результаты немного отличаются: лучше всего будет 1322837333 i=-6815 and j=70091, но мой любимый 92821 (наименьшее столкновение -46272,46016) снова почти так же хорош как лучшее значение.

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


5 ">голосов

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


5 ">голосов

Столкновения могут быть не такой большой проблемой ... Основная цель хэша - избегать использования равных для сравнений 1: 1. Если у вас есть реализация, где equals «вообще» чрезвычайно дешево для объектов, столкнувшихся с хэшем, то это не проблема (вообще).

В конце концов, лучший способ хеширования зависит от того, что вы сравниваете. В случае пары int (как в вашем примере) использование базовых побитовых операторов может быть достаточным (с использованием & или ^).


3

Вы должны определить свой диапазон для i и j. Вы можете использовать простое число для обоих.

public int hashCode() {
   http://primes.utm.edu/curios/ ;)
   return 97654321 * i ^ 12356789 * j;
}

3

Я бы выбрал 7243. Достаточно большой, чтобы избежать коллизий с небольшими числами. Не быстро переполняется на небольшие числа.

Java, хэш-код, простые числа, Java,