Почему Java hashCode () в String использует 31 в качестве множителя?

Я не уверен, но я предполагаю, что они протестировали некоторый образец простых чисел и обнаружили, что 31 дает наилучшее распределение по некоторому образцу возможных строк.

На (в основном) старых процессорах умножение на 31 может быть относительно дешевым. В ARM, например, есть только одна инструкция:

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

Для большинства других процессоров потребуется отдельная инструкция сдвига и вычитания. Однако, если ваш множитель медленный, это все равно выигрыш. Современные процессоры, как правило, имеют быстрые множители, поэтому это не имеет большого значения, если 32 идет на правильную сторону.

Это не лучший алгоритм хеширования, но он достаточно хорош и лучше, чем код 1.0 (и намного лучше, чем спецификация 1.0!).

Согласно Эффективная Java Джошуа Блоха (книга, которую нельзя рекомендовать достаточно, и которую я купил благодаря постоянным упоминаниям о stackoverflow):

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

(из главы 3, пункт 9: Всегда переопределять хэш-код при переопределении равенства, стр. 48)

Goodrich и Tamassia вычислили из более чем 50 000 английских слов (сформированных как объединение списков слов, представленных в двух вариантах Unix), что использование констант 31, 33, 37, 39 и 41 вызовет менее 7 коллизий в каждом случае. Это может быть причиной того, что многие реализации Java выбирают такие константы.

См. Раздел 9.2 Хеш-таблицы (стр. 522) в Структуры данных и алгоритмы в Java.

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

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

Выражение n * 31 эквивалентно (n << 5) - n.

Блох не совсем вникает в это, но я всегда слышал / верил в обоснование того, что это базовая алгебра. Хеши сводятся к операциям умножения и модуля, а это означает, что вы никогда не захотите использовать числа с общими множителями, если можете. Другими словами, относительно простые числа обеспечивают равномерное распределение ответов.

Числа, которые составляют с помощью хеша, обычно:

• модуль типа данных, в который вы его поместили (2 ^ 32 или 2 ^ 64)
• модуль счетчика ведра в вашей хэш-таблице (варьируется. В java раньше было простым, теперь 2 ^ n)
• умножьте или сдвиньте на магическое число в вашей функции смешивания
• Входное значение

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

На самом деле, 37 вполне подойдут! z: = 37 * x можно вычислить как y := x + 8 * x; z := x + 4 * y. Оба шага соответствуют одной инструкции LEA x86, так что это очень быстро.

Фактически, умножение на еще большее простое число 73 может быть выполнено с той же скоростью, установив y := x + 8 * x; z := x + 8 * y.

Использование 73 или 37 (вместо 31) может быть лучше, потому что это приводит к более плотный код: две инструкции LEA занимают только 6 байтов против 7 байтов для перемещения + сдвига + вычитания для умножения на 31. Одно из возможных предупреждений заключается в том, что Используемые здесь 3-аргументные инструкции LEA стали медленнее в архитектуре Intel Sandy bridge с увеличенной задержкой на 3 цикла.

Более того, 73 - любимое число Шелдона Купера.

Нил Коффи объясняет, почему 31 используется под Сглаживание предвзятости.

В основном использование 31 дает более равномерное распределение вероятностей для хеш-функции.

Вы можете прочитать исходную аргументацию Блоха в разделе «Комментарии» в http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622. Он исследовал производительность различных хэш-функций в отношении результирующего «среднего размера цепочки» в хеш-таблице. P(31) был одной из распространенных функций в то время, которую он нашел в книге K&R (но даже Керниган и Ричи не могли вспомнить, откуда она взялась). В конце концов, ему пришлось выбрать один, и поэтому он взял P(31), так как он, казалось, работал достаточно хорошо. Несмотря на то, что P(33) был не хуже, а умножение на 33 вычисляется одинаково быстро (просто сдвиг на 5 и сложение), он выбрал 31, поскольку 33 не является простым:

Of the remaining four, I'd probably select P(31), as it's the cheapest to calculate on a RISC machine (because 31 is the difference of two powers of two). P(33) is similarly cheap to calculate, but it's performance is marginally worse, and 33 is composite, which makes me a bit nervous.

Таким образом, рассуждение было не таким рациональным, как предполагают многие из приведенных здесь ответов. Но мы все умеем придумывать рациональные причины после интуитивных решений (и даже Блох может быть к этому склонен).

Из JDK-4045622, где Джошуа Блох описывает причины, по которым была выбрана именно эта (новая) реализация String.hashCode().

The table below summarizes the performance of the various hash functions described above, for three data sets:

1) All of the words and phrases with entries in Merriam-Webster's 2nd Int'l Unabridged Dictionary (311,141 strings, avg length 10 chars).

2) All of the strings in /bin/, /usr/bin/, /usr/lib/, /usr/ucb/ and /usr/openwin/bin/* (66,304 strings, avg length 21 characters).

3) A list of URLs gathered by a web-crawler that ran for several hours last night (28,372 strings, avg length 49 characters).

The performance metric shown in the table is the "average chain size" over all elements in the hash table (i.e., the expected value of the number of key compares to look up an element).

                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439

Looking at this table, it's clear that all of the functions except for the current Java function and the two broken versions of Weinberger's function offer excellent, nearly indistinguishable performance. I strongly conjecture that this performance is essentially the "theoretical ideal", which is what you'd get if you used a true random number generator in place of a hash function.

I'd rule out the WAIS function as its specification contains pages of random numbers, and its performance is no better than any of the far simpler functions. Any of the remaining six functions seem like excellent choices, but we have to pick one. I suppose I'd rule out Vo's variant and Weinberger's function because of their added complexity, albeit minor. Of the remaining four, I'd probably select P(31), as it's the cheapest to calculate on a RISC machine (because 31 is the difference of two powers of two). P(33) is similarly cheap to calculate, but it's performance is marginally worse, and 33 is composite, which makes me a bit nervous.

Josh

В последней версии JDK по-прежнему используется 31. https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode ()

Хеш-строка предназначена для

• уникальный (пусть в документе расчета хэш-кода см. оператор ^, помогает уникальный)
• дешевая стоимость для расчета

31 - максимальное значение, которое можно поместить в 8-битный (= 1 байт) регистр, наибольшее простое число, которое можно поместить в 1-байтовый регистр, - нечетное число.

Умножьте 31 на << 5, затем вычтите само себя, поэтому нужны дешевые ресурсы.

Это потому, что 31 имеет приятное свойство - его умножение можно заменить побитовым сдвигом, который быстрее стандартного умножения:

31 * i == (i << 5) - i

Большое ожидание от хэш-функций заключается в том, что равномерная случайность их результата выдерживает такую ​​операцию, как hash(x) % N, где N - произвольное число (и во многих случаях степень двойки), одна из причин заключается в том, что такие операции обычно используются в хеш-таблицах для определения слоты. Использование множителей простых чисел при вычислении хеша снижает вероятность того, что ваш множитель и N делят делители, что сделает результат операции менее случайным.

Другие указали на то замечательное свойство, что умножение на 31 может быть выполнено умножением и вычитанием. Я просто хочу указать, что для таких простых чисел существует математический термин: Мерсенн Прайм

Все простые числа Мерсенна на единицу меньше степени двойки, поэтому мы можем записать их как:

p = 2^n - 1

Умножая x на p:

x * p = x * (2^n - 1) = x * 2^n - x = (x << n) - x

Сдвиги (SAL / SHL) и вычитания (SUB) обычно выполняются быстрее, чем умножение (MUL) на многих машинах. См. таблицы инструкций от Agner Fog

Вот почему GCC, кажется, оптимизирует умножение на простые числа Мерсена, заменяя их сдвигами и подстановками, глянь сюда.

Однако, на мой взгляд, такое маленькое простое число - плохой выбор для хеш-функции. При относительно хорошей хеш-функции можно ожидать случайности в старших битах хеш-функции. Однако с хеш-функцией Java почти нет случайности в старших битах с более короткими строками (и все еще очень сомнительной случайности в младших битах). Это затрудняет создание эффективных хеш-таблиц. См. этот приятный трюк, который вы не смогли бы сделать с хеш-функцией Java.

В некоторых ответах упоминается, что, по их мнению, хорошо, что 31 помещается в байт. На самом деле это бесполезно, поскольку:

(1) Мы выполняем сдвиги вместо умножения, поэтому размер множителя не имеет значения.

(2) Насколько мне известно, нет специальной инструкции x86 для умножения 8-байтового значения на 1-байтовое значение, поэтому вам все равно пришлось бы преобразовать «31» в 8-байтовое значение, даже если вы умножали. Смотрите здесь, вы умножаете целые 64-битные регистры.

(А 127 на самом деле является самым большим простым числом Мерсенна, которое может уместиться в байте.)

Увеличивает ли меньшее значение случайность в средних и младших битах? Возможно, но это также, кажется, значительно увеличивает количество возможных столкновений :).

Можно перечислить много разных проблем, но обычно они сводятся к двум основным принципам, которые не выполняются должным образом: Путаница и Распространение

Но быстро ли это? Наверное, потому что мало что делает. Однако, если здесь в центре внимания производительность, один символ в цикле будет довольно неэффективным. Почему бы не делать 4 символа за раз (8 байтов) на итерацию цикла для более длинных строк, нравится? Что ж, это было бы сложно сделать с текущим определением хэша, где вам нужно умножать каждый символ индивидуально (пожалуйста, скажите мне, есть ли небольшой хак, чтобы решить эту проблему: D).