Согласно документации Java, хеш-код для объекта String вычисляется как:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]используя
intарифметику, гдеs[i]- i- й символ строки,n- длина строки, а^возведение в степень.
Почему 31 используется в качестве множителя?
Я понимаю, что множитель должен быть относительно большим простым числом. Так почему бы не 29, или 37, или даже 97?
В соответствии с Joshua Bloch Effective Java (книга, которая не может быть рекомендована достаточно, и которую я купил благодаря постоянным упоминаниям о stackoverflow):
Значение 31 было выбрано потому, что это нечетное простое число. Если бы оно было четным и умножение было переполнено, информация была бы потеряна, так как умножение на 2 эквивалентно сдвигу. Преимущество использования прайма менее очевидно, но оно традиционно. Хорошим свойством 31 является то, что умножение может быть заменено сдвигом и вычитанием для лучшей производительности:
31 * я == (i << 5) - i. Современные виртуальные машины выполняют такую оптимизацию автоматически.
(из главы 3, пункт 9: всегда переопределять хэш-код при переопределении equals, стр. 48)
Как Goodrich и Tamassia указывают, если вы возьмете более 50 000 английских слов (сформированных как объединение списков слов, представленных в двух вариантах Unix), используя константы 31, 33, 37, 39 и 41, будет производить менее 7 столкновений в каждом случае. Зная это, неудивительно, что многие реализации Java выбирают одну из этих констант.
Кстати, я был в середине чтения раздела "полиномиальные хэш-коды", когда увидел этот вопрос.
РЕДАКТИРОВАТЬ: вот ссылка на книгу PDF-книги ~ 10mb, о которой я говорю выше. См. Раздел 10.2 Таблицы хэшей (страница 413) Структуры данных и алгоритмы в Java
В основном (в основном) старые процессоры, умножившись на 31, могут быть относительно дешевыми. Например, в ARM это только одна инструкция:
RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5)
Для большинства других процессоров потребуется отдельная команда смены и вычитания. Однако, если ваш множитель медленный, это все равно победа. Современные процессоры, как правило, имеют быстрые множители, поэтому это не имеет большого значения, если 32 идет по правильной стороне.
Это не большой алгоритм хэширования, но он достаточно хорош и лучше, чем код 1.0 (и намного лучше, чем 1.0 spec!).
При умножении биты сдвигаются влево. Это использует больше доступного пространства хеш-кодов, уменьшая коллизии.
Не используя силу два, также заполняются младшие и самые правые биты, которые должны смешиваться со следующей частью данных, поступающей в хэш.
Выражение n * 31 эквивалентно (n << 5) - n.
Вы можете прочитать оригинальные рассуждения Блоха в разделе "Комментарии" в 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 сложная, что немного нервничает.
Таким образом, рассуждение не было столь рациональным, как многие из приведенных здесь ответов, по-видимому, подразумевают. Но мы все хорошо придумываем рациональные причины после интуитивных решений (и даже Блох может быть склонен к этому).
На самом деле 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. Одно из возможных предупреждений состоит в том, что инструкции LEA с тремя аргументами, используемые здесь, стали медленнее в архитектуре Intel Sandy Bridge с увеличенной задержкой в 3 цикла.
Более того, 73 - любимый номер Шелдона Купера.
Neil Coffey объясняет, почему 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 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 Fn 1.2487 1.2471 1.2462 WAIS Fn 1.2497 1.2519 1.2452 Weinberger Fn(MatPak) 6.5169 7.2142 30.6864 Weinberger Fn(24) 1.3222 1.2791 1.9732 Weinberger Fn(28) 1.2530 1.2506 1.2439В этой таблице ясно, что все функции, кроме текущей функции Java и двух сломанных версий Weinberger's функция предлагает отличную, почти неотличимую производительность. я что гипотеза о том, что это "теоретический идеал", который вы получили бы, если бы использовали истинный случайный числовой генератор вместо хэш-функции.
Я бы исключил функцию WAIS, так как ее спецификация содержит страницы случайных чисел, а ее производительность не лучше, чем любая из гораздо более простые функции. Каждой из оставшихся шести функций кажется отличный выбор, но мы должны выбрать один. Полагаю, я бы исключал Вариант Vo и функция Вайнбергера из-за их добавления сложность, хотя и незначительная. Из оставшихся четырех я бы выбрал P (31), поскольку он самый дешевый для расчета на машине RISC (поскольку 31 является разностью двух степеней двух). P (33) также дешево вычислить, но его производительность незначительно хуже, а 33 составной, что заставляет меня немного нервничать.
Джош
Я не уверен, но я бы предположил, что они проверили некоторый образец простых чисел и обнаружили, что 31 дал наилучшее распределение по некоторому образцу возможных строк.
Блох не совсем вникает в это, но логическое обоснование, которое я всегда слышал/полагал, состоит в том, что это основная алгебра. Хэши сводятся к операциям умножения и модуляции, а это означает, что вы никогда не захотите использовать числа с общими факторами, если сможете это сделать. Другими словами, относительно простые числа обеспечивают равномерное распределение ответов.
Числа, которые составляют хэш, обычно:
Вы действительно можете контролировать только пару этих значений, поэтому немного больше внимания уделяется.
В последней версии JDK 31 все еще используется. https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode()
Назначение хеш-строки:
^ в документе вычисления хеш-кода, это поможет уникальный)31 - максимальное значение, которое можно поместить в 8-битный регистр (= 1 байт), наибольшее простое число, которое можно поместить в 1-байтовый регистр, - нечетное число.
Умножение 31 равно & lt; & lt; & lt; & lt; & lt; & lt; & lt; & lt; & lt; & lt; & lt; & lt; & lt; & lt; & lt; & lt; & le;
Это потому, что 31 обладает хорошим свойством - его умножение можно заменить битовым сдвигом, который быстрее стандартного умножения:
31 * i == (i << 5) - i