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

StackOverflow https://stackoverflow.com/questions/1835976

  •  11-09-2019
  •  | 
  •  

Вопрос

В 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(); повторяется для каждого дополнительного атрибута.Для целых чисел .hashCode() можно опустить.)

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

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

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

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

Это было полезно?

Решение

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

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

Поскольку это интересно, я написал небольшую программу, которая искала лучшее простое число в этом смысле по всему диапазону чисел.То есть для каждого простого числа я искал минимальное значение 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.Если у вас есть реализация, в которой метод «равно» «обычно» чрезвычайно дешев для объектов, у которых есть конфликтующие хеши, то это не проблема (вообще).

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top