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

Question

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 , которая использовалась по соображениям производительности, которые давно исчезли после введения аппаратных множителей. Здесь у вас есть много коллизий хеш-кода для небольших значений i и j: например, (0,0) и (-1,31) имеют одинаковое значение. Я думаю, что это плохо, так как небольшие значения встречаются часто. Для String.hashCode вы также найдете много коротких строк с одинаковым хеш-кодом, например, «Ca» и «DB». Если вы берете большое простое число, эта проблема исчезнет, ​​если вы выберете простое право.

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

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

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

Answer 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, если только у вас нет веских причин не делать этого.

Answer 2

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

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