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

Question

Согласно документации Java, хеш-код для объекта 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 Джошуа Блоха (книга, которую нельзя рекомендовать достаточно, и которую я купил благодаря постоянным упоминаниям о переполнении стека):

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

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

Answer 2

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

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

РЕДАКТИРОВАТЬ: здесь ссылка на PDF-книгу ~ 10 МБ, на которую я ссылаюсь выше. См. Раздел 10.2 Хеш-таблицы (стр. 413) из Структуры данных и алгоритмы в Java

Answer 3

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

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

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

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

Answer 4

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

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

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

Answer 5

Вы можете прочитать исходные рассуждения Блоха в разделе «Комментарии» в 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 6

На самом деле 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 байтов для move + shift + вычитания умножение на 31. Одно возможное предостережение состоит в том, что используемые здесь инструкции LEA с тремя аргументами стали медленнее в архитектуре Intel Sandy Bridge с увеличенной задержкой в ​​3 цикла.

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

Answer 7

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

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

Answer 8

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

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

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

2) Все строки в / bin / , / usr / bin / , / usr / lib / , / usr / ucb / и / usr / openwin / bin / * (66 304 строки, средняя длина 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 и две сломанные версии Weinberger's Функция предлагает отличную, почти неотличимую производительность. я твердо предположить, что это представление по сути «теоретический идеал», который вы получили бы, если бы использовали реальный случайный генератор чисел вместо хеш-функции.

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

Josh

Answer 9

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

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

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

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

Answer 10

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