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

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

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

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

Это не большой хеш-алгоритм, но это достаточно хорошо и лучше, чем 1,0 кода (и намного лучше, чем 1,0 спецификации!).

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

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

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

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

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

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

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

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

Обычно используются следующие числа:

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

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