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

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

class HashTest {
    int i;
    int j;        
    public int hashCode() {
        final int prime = 31;
        int result = prime + i;
        result = prime * result + j;
        return result;
    }
}

(Если у вас есть больше атрибутов в классе, result = prime * result + attribute.hashCode(); повторяется для каждого дополнительного атрибута. Для ints.hashCode() может быть опущен.)

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

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

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

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

Ответ 1

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

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

Поскольку это интересно, я написал небольшую программу, которая искала весь диапазон int для лучшего простого в этом смысле. То есть для каждого штриха я искал минимальное значение Math.abs(i) + Math.abs(j) по всем значениям i,j, которые имеют тот же хэш-код, что и 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, если у вас нет веских причин не делать этого.

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

Я просто хочу указать, что hashcode не имеет ничего общего с простым. В реализации JDK

for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }

Я нашел, если вы замените 31 на 27, результат очень схож.