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

Question

В Java, то hash code для String объекта вычисляется как

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

использования int арифметика, где s[i] является i^я символа строки, n длина строки, и ^ указывает на возведение в степень.

Почему 31 используется как множитель?

Я понимаю, что множитель должен быть относительно большим простым числом. Так почему же 29, или 37, или даже 97?

Answer 1

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

Значение 31 было выбрано потому, что это нечетное простое число. Если бы он был четным и переполнение было переполнено, информация была бы потеряна, поскольку умножение на 2 эквивалентно сдвигу. Преимущество использования прогона менее понятно, но оно традиционно. Хорошим свойством 31 является то, что умножение может быть заменено сдвигом и вычитанием для лучшей производительности: 31 * i == (i << 5) - i. Современные виртуальные машины делают такую ​​оптимизацию автоматически.

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

Answer 2

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

Answer 3

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

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

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

Это не большой алгоритм хэширования, но он достаточно хорош и лучше, чем код 1.0 (и намного лучше, чем 1.0 spec!).

Answer 4

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

Кстати, я был в середине чтения раздела «полиномиальные хэш-коды», когда увидел этот вопрос.

EDIT: здесь ссылка на ~ 10mb PDF-книгу, о которой я говорю выше. См. Раздел 10.2 Таблицы хеша (стр. 413) Data Structures and Algorithms in Java

Answer 5

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

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

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

Answer 6

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

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

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

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

Answer 7

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

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

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

Кроме того, 73 является любимым номером Шелдона Купера.

Answer 8

Neil Coffey explains Почему 31 используется под Сглаживание смещения.

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

Answer 9

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

Из оставшихся четыре, Я бы выбрал P (31), так как самый дешевый для расчета на машине RISC (потому что 31 - разница двух степеней по два). P (33) равен Аналогично дешево для расчета, но его производительность незначительно хуже, и 33 является составным, что заставляет меня немного нервничать.

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

Answer 10

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

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

1) Все слова и фразы с записями в Merriam-Webster's 2-й международный словарь без словаря (311,141 строки, средняя длина 10 символов).

2) Все строки в/bin/,/USR/бен/,/USR/Lib/,/USR/UCB/ и/USR/openwin/bin/* (66,304 строк, avg длиной 21 символ).

3) Список URL-адресов, собранных веб-гусеничным аппаратом, который выполнялся в течение нескольких дней часов прошлой ночью (28 372 строки, средняя длина 49 символов).

Метрика производительности показано в таблице, представляет собой «средний размер цепь» по всем элементам в хэш-таблице (т.е., ожидаемое значение числа ключа сравнивает смотреть вверх элемент).

      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 

Глядя на эту таблицу, то становится ясно, что все функции для текущей функции Java и две сломанные версии функции предложения Вайнбергера отлично, почти неотличимы производительности за исключением. I настоятельно полагают, что эта работа по существу является «теоретическим идеалом» , что и было бы тем, что вы получили бы, если бы вместо хэш-функции использовался случайный генератор чисел .

Я бы исключил функцию WAIS, так как ее спецификация содержит страницы случайных чисел, а ее производительность не лучше, чем любая из гораздо более простых функций. Любая из оставшихся шести функций выглядит как отличный выбор, но мы должны выбрать один. Полагаю, я бы исключил вариант Vo и функцию Вайнбергера из-за их сложности , хотя и незначительной. Из оставшихся четырех я бы выбрал P (31), так как он самый дешевый для расчета на машине RISC (потому что 31 - это разница двух степеней двух). P (33) так же дешев до , но его производительность незначительно хуже, а 33 - , что делает меня немного нервным.

Джош