Why does Java's hashCode() in String use 31 as a multiplier?
Почему хэш-код Java () в строке использует 31 в качестве множителя?
Согласно документации Java, хэш-код для String объекта вычисляется как:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
используя int арифметику, где s[i] - это i-й символ строки, n - длина строки, а ^ указывает на возведение в степень.
Почему 31 используется в качестве множителя?
Я понимаю, что множитель должен быть относительно большим простым числом. Так почему бы не 29, или 37, или даже 97?
Переведено автоматически
Ответ 1
Согласно книге Джошуа Блоха "Эффективная Java, второе издание" (книга, которую трудно рекомендовать, и которую я купил благодаря постоянным упоминаниям о Stack Overflow):
Значение 31 было выбрано потому, что это нечетное простое число. Если бы оно было четным и умножение было бы переполнено, информация была бы потеряна, поскольку умножение на 2 эквивалентно сдвигу. Преимущество использования простого числа менее очевидно, но оно традиционное. Приятным свойством 31 является то, что умножение может быть заменено сдвигом и вычитанием для повышения производительности: 31 * i == (i << 5) - i. Современные виртуальные машины выполняют такого рода оптимизацию автоматически.
(из главы 3, пункт 9: Всегда переопределять hashCode при переопределении equals, стр. 48)
Ответ 2
Гудрич и Тамассия вычислили из более чем 50 000 английских слов (сформированных как объединение списков слов, представленных в двух вариантах Unix), что использование констант 31, 33, 37, 39 и 41 приведет к менее чем 7 столкновениям в каждом случае. Это может быть причиной того, что так много реализаций Java выбирают такие константы.
На (в основном) старых процессорах умножение на 31 может быть относительно дешевым. Например, на ARM это всего лишь одна инструкция:
RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5)
Для большинства других процессоров потребовалась бы отдельная команда сдвига и вычитания. Однако, если ваш множитель медленный, это все равно выигрыш. Современные процессоры, как правило, имеют быстрые множители, поэтому это не имеет большого значения, пока 32 идет на правильной стороне.
Это не самый лучший хэш-алгоритм, но он достаточно хорош и лучше, чем код 1.0 (и намного лучше, чем спецификация 1.0!).
Ответ 4
При умножении биты сдвигаются влево. Это использует больше доступного пространства хэш-кодов, уменьшая коллизии.
Поскольку не используется степень двойки, заполняются также младшие, крайние правые биты, которые смешиваются со следующей частью данных, поступающих в хэш.