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

481

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

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

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

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

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

jacobko
источник
1
Сравните также stackoverflow.com/questions/1835976/… - Я думаю, что 31 - плохой выбор, если вы пишете свои собственные функции hashCode.
Ганс-Петер Стёрр
6
Если бы было 29, или 37, или даже 97, вы бы спросили: «Почему бы не 31?»
маркиз Лорн
2
@ EJP важно знать причину выбора «нет». если число не является результатом уловки черной магии.
Dushyant Сабхарвал
Об этом есть сообщение в блоге @ peter-lawrey: vanilla-java.github.io/2018/08/12/… и здесь: vanilla-java.github.io/2018/08/15/…
Кристоф Русси
@DushyantSabharwal Я хочу сказать, что это могло быть 29, 37, 97 или 41, или много других значений, без особой практической разницы. Мы использовали 37 в 1976 году.
Маркиз Лорн

Ответы:

406

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

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

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

Мэтт Б
источник
346
Ну, все простые числа, кроме 2. Просто скажите.
Кип
38
Я не думаю, что Блох говорит, что он был выбран, потому что это было нечетное простое число, а потому, что оно было нечетным И, потому что оно было простым (И потому, что его можно легко оптимизировать в сдвиг / вычитание).
Мэтт б
50
31 был выбран, потому что это нечетное простое число ??? Это не имеет никакого смысла - я говорю, что 31 был выбран, потому что это дало лучший дистрибутив - проверьте computinglife.wordpress.com/2008/11/20/…
computinglife
65
Я думаю, что выбор 31 довольно неудачный. Конечно, это может сэкономить несколько циклов ЦП на старых машинах, но у вас уже есть коллизии хеша в коротких строках ascii, таких как "@ и #!" Или Ca и DB. Этого не произойдет, если вы выберете, например, 1327144003 или в минимум 524287, который также допускает битовое смещение: 524287 * i == i << 19 - i.
Hans-Peter Störr
15
@ Джейсон Смотрите мой ответ stackoverflow.com/questions/1835976/… . Моя точка зрения такова: вы получаете гораздо меньше столкновений, если используете более простое число, и ничего не теряете в наши дни. Проблема усугубляется, если вы используете неанглийские языки с обычными не-ascii символами. И 31 послужил плохим примером для многих программистов при написании собственных функций hashCode.
Ганс-Петер Стёрр,
80

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

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

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

JohnZaj
источник
6
Тем не менее, обратите внимание, что вы можете получить намного больше коллизий, если вы используете какой-либо международный набор символов с общими символами вне диапазона ASCII. По крайней мере, я проверил это на 31 и немецкий. Поэтому я думаю, что выбор из 31 нарушен.
Ганс-Петер Стёрр,
1
@jJack, ссылка в вашем ответе не работает.
СК Венкат
Обе ссылки в этом ответе не работают. Кроме того, аргумент в первом абзаце является своего рода неполным; Как другие нечетные числа сравниваются с пятью, которые вы перечислили в этом тесте?
Марк Эмери
58

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

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

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

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

Том Хотин - Tackline
источник
7
Как ни странно, умножение с 31 на моем настольном компьютере на самом деле немного медленнее, чем умножение с, скажем, 92821. Я думаю, компилятор пытается «оптимизировать» его до сдвига и добавления. :-)
Ханс-Петер Стёрр
1
Я не думаю, что когда-либо использовал ARM, который не был одинаково быстрым со всеми значениями в диапазоне +/- 255. Использование степени 2 минус один приводит к нежелательному эффекту, так как соответствующее изменение двух значений меняет хэш-код на степень двух. Значение -31 было бы лучше, и я бы подумал, что что-то вроде -83 (64 + 16 + 2 + 1) могло бы быть еще лучше (немного лучше смешать).
суперкат
@supercat Не уверен минусом. Кажется, ты возвращаешься к нулям. / String.hashCodeпредшествует StrongARM, который, IIRC, ввел 8-битный множитель и, возможно, увеличил до двух циклов для комбинированной арифметической / логической операции со сдвигом.
Том Хотин - tackline
1
@ TomHawtin-tackline: при использовании 31 хеш из четырех значений будет 29791 * a + 961 * b + 31 * c + d; при использовании -31 это будет -29791 * a + 961 * b - 31 * c + d. Я не думаю, что разница будет существенной, если четыре элемента независимы, но если пары соседних элементов совпадают, результирующий хэш-код будет вкладом всех непарных элементов плюс кратное 32 (из парных). Для строк это может не иметь большого значения, но если вы пишете универсальный метод для агрегации хэширования, ситуация, когда соседние элементы совпадают, будет непропорционально распространена.
суперкат
3
@Supercat забавный факт, хеш-код Map.Entryбыл исправлен спецификацией, чтобы быть, key.hashCode() ^ value.hashCode()несмотря на то, что это даже не неупорядоченная пара, keyи valueимеют совершенно другое значение. Да, это подразумевает, что Map.of(42, 42).hashCode()или Map.of("foo", "foo", "bar", "bar").hashCode()и т. Д. Предсказуемо равны нулю. Так что не используйте карты в качестве ключей для других карт ...
Хольгер
33

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

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

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

Эриксон
источник
29

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

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

Дэвид Онгаро
источник
2
Тщательное исследование и непредвзятый ответ!
Вишал К
22

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

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

ПЧР
источник
5
Вы паскаль программист или что-то? что с: = вещи?
Mainguy
11
@Mainguy На самом деле это синтаксис ALGOL и довольно часто используется в псевдокоде.
Приближается к
4
но в сборке ARM умножение на 31 можно выполнить в одной инструкции
phuclv
В TPOP (1999) можно прочитать о ранней Java (стр.57): «... Проблема была решена путем замены хеша одним эквивалентом показанному нами (с множителем 37 ) ...»
Мику
19

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

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

Сок
источник
12

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

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

1) Все слова и фразы с записями во 2-м международном словаре Merriam-Webster без ограничений (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 сложная, что немного нервничает.

мистифицировать

поток
источник
5

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

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

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

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

Джейсон
источник
4

В последней версии 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, затем вычтите себя, поэтому нужны дешевые ресурсы.

До Нху Вы
источник
3

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

Дэйв Л.
источник
1

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

31 * i == (i << 5) - i
yoAlex5
источник