Согласно документации Java, хеш-код для String
объекта вычисляется как:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
с использованием
int
арифметических операций, гдеs[i]
это я й символ строки,n
длина строки, и^
указывает , возведение в степень.
Почему 31 используется как множитель?
Я понимаю, что множитель должен быть относительно большим простым числом. Так почему бы не 29, или 37, или даже 97?
Ответы:
Согласно книге « Эффективная Java» Джошуа Блоха (книга, которую нельзя рекомендовать достаточно, и которую я купил благодаря постоянным упоминаниям о стековом потоке):
(из главы 3, пункт 9: всегда переопределять хэш-код при переопределении equals, стр. 48)
источник
Как указывают Гудрич и Тамассия , если вы берете более 50 000 английских слов (сформированных как объединение списков слов, представленных в двух вариантах Unix), использование констант 31, 33, 37, 39 и 41 вызовет менее 7 коллизий в каждом случае. Зная это, неудивительно, что многие реализации Java выбирают одну из этих констант.
По совпадению, я был в середине чтения раздела "полиномиальные хэш-коды", когда я увидел этот вопрос.
РЕДАКТИРОВАТЬ: здесь ссылка на книгу ~ 10 МБ PDF, я имею в виду выше. См. Раздел 10.2 Хеш-таблицы (стр. 413) структур данных и алгоритмов в Java.
источник
На (в основном) старых процессорах умножение на 31 может быть относительно дешевым. На ARM, например, это только одна инструкция:
Большинство других процессоров потребует отдельной инструкции сдвига и вычитания. Однако, если ваш множитель медленный, это все равно победа. Современные процессоры, как правило, имеют быстрые множители, поэтому это не имеет большого значения, если 32 идет на правильную сторону.
Это не отличный алгоритм хеширования, но он достаточно хорош и лучше, чем код 1.0 (и намного лучше, чем спецификация 1.0!).
источник
String.hashCode
предшествует StrongARM, который, IIRC, ввел 8-битный множитель и, возможно, увеличил до двух циклов для комбинированной арифметической / логической операции со сдвигом.Map.Entry
был исправлен спецификацией, чтобы быть,key.hashCode() ^ value.hashCode()
несмотря на то, что это даже не неупорядоченная пара,key
иvalue
имеют совершенно другое значение. Да, это подразумевает, чтоMap.of(42, 42).hashCode()
илиMap.of("foo", "foo", "bar", "bar").hashCode()
и т. Д. Предсказуемо равны нулю. Так что не используйте карты в качестве ключей для других карт ...При умножении биты сдвигаются влево. Это использует больше доступного пространства хэш-кодов, уменьшая коллизии.
Если не использовать степень двойки, младшие биты младшего разряда также заполняются, чтобы быть смешанными со следующим фрагментом данных, поступающим в хеш.
Выражение
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 не простое число:Таким образом, рассуждение не было столь рациональным, как, кажется, подразумевают многие ответы здесь. Но мы все хорошо придумываем рациональные причины после интуитивных решений (и даже Блох может быть склонен к этому).
источник
На самом деле 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 - любимый номер Шелдона Купера.
источник
Нил Коффи объясняет, почему 31 используется при сглаживании предвзятости .
В основном использование 31 дает вам более равномерное распределение битовых вероятностей для хэш-функции.
источник
Из JDK-4045622 , где Джошуа Блох описывает причины, по которым
String.hashCode()
была выбрана эта конкретная (новая) реализацияисточник
Блох не совсем в этом разбирается, но обоснование, которое я всегда слышал / верил, состоит в том, что это базовая алгебра. Хэши сводятся к операциям умножения и модуля, что означает, что вы никогда не захотите использовать числа с общими факторами, если сможете помочь. Другими словами, относительно простые числа обеспечивают равномерное распределение ответов.
Числа, которые составляют использование хэша, как правило:
Вы действительно можете контролировать только пару из этих значений, так что требуется немного больше внимания.
источник
В последней версии 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, затем вычтите себя, поэтому нужны дешевые ресурсы.
источник
Я не уверен, но я предполагаю, что они проверили некоторую выборку простых чисел и обнаружили, что 31 дал лучшее распределение по некоторой выборке возможных строк.
источник
Это потому, что 31 обладает хорошим свойством - его умножение можно заменить битовым сдвигом, который быстрее стандартного умножения:
источник