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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вы можете прочитать оригинальные рассуждения Блоха в разделе «Комментарии» в http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 . Он исследовал работу различных hash-функций в отношении «среднего размера цепи» в хеш-таблице. P(31) была одной из общих функций за это время, которую он нашел в книге K & R (но даже Керниган и Ричи не могли вспомнить, откуда она взялась). В конце концов, он в основном должен был выбрать один, и поэтому он взял P(31) так как он, казалось, работал достаточно хорошо. Несмотря на то, что 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 y := x + 8 * x; z := x + 4 * y . Оба этапа соответствуют одной инструкции LEA x86, поэтому это очень быстро.

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

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

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

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

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

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

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

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

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

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

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

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

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

2) Все строки в / bin / , / usr / bin / , / usr / lib / , / usr / ucb / и / usr / openwin / bin / * (66,304 строки, средняя длина 21 символ).

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

Показатель производительности, показанный в таблице, представляет собой «средний размер цепи» по всем элементам hash-таблицы (т. Е. Ожидаемое значение числа ключей сравнивается с поиском элемента).

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

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

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

  • php mysqli_connect: метод проверки подлинности, неизвестный клиенту
  • Хранить и читать hash и массив в файлах в Perl
  • Что такое хеширование паролей?
  • Как я могу поддерживать порядок ключей, которые я добавляю к hashу Perl?
  • Что такое hash-функция по умолчанию, используемая в C ++ std :: unordered_map?
  • Могу ли я использовать список как hash в R? Если да, то почему это так медленно?
  • Выбор между std :: map и std :: unordered_map
  • Как создать hash-код из массива байтов в C #?
  • Можно ли получить идентичный hash SHA1?
  • Хеширование паролей с помощью MD5 или sha-256 C #
  • Хешируйте произвольное значение точности (boost :: multiprecision :: cpp_int)
  • Interesting Posts
    Давайте будем гением компьютера.