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

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

  •  08-07-2019
  •  | 
  •  

Вопрос

Согласно документации Java, хэш-код для String объект вычисляется как:

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

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

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

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

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

Решение

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

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

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

Другие советы

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

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

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

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

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

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

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

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

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

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

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

  

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

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

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

Более того, 73 это любимый номер Шелдона Купера.

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

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

От 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-функции и двух сломанных версий функции Вайнбергера обеспечивают отличную, почти неотличимую производительность.Я Я полагаю, что это выступление по существу является "теоретический идеал", который вы бы получили, если бы использовали истинный случайный генератор чисел вместо хеш-функции.

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

Джош

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

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

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

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

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

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

Целью хеш-строки является

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

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

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

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