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

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

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

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

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

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

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

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

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

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

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

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