Я просматриваю исходный код Arrays.hashCode(char[] c)
Я не очень подтверждаю, что применяемый алгоритм хорошо работает во всех случаях.
public static int hashCode(int a[]) {
if (a == null)
return 0;
int result = 1;
for (int element : a)
result = 31 * result + element;
return result;
}
Действительно ли реализованная здесь хэш-функция равномерно распределяет все входные массивы. И почему мы используем здесь простое число 31.
Зачем использовать простое число 31?
Это можно разделить на две части?
- Почему простое число?
Здесь нам нужно понять, что наша цель — получить уникальный HashCode для объекта, который поможет нам найти этот объект за время O(1).
Ключевое слово здесь — уникальный.
Простые числа
Простые числа — это уникальные числа. Они уникальны тем, что произведение простого числа на любое другое число имеет наилучшие шансы быть уникальным (конечно, не таким уникальным, как само простое число) из-за того, что для его составления используется простое число. Это свойство используется в функциях хеширования.
.
Почему номер 31?
Из Эффективная Java
Это также на единицу меньше, чем степень двойки, что позволяет выполнять побитовую оптимизацию.
Вот полная цитата,
из пункта 9: Всегда переопределяйте hashCode при переопределении equals:
Значение 31 было выбрано потому, что это нечетное простое число. Если бы оно было четным, а умножение переполнилось бы, информация была бы потеряна, так как умножение на 2 эквивалентно сдвигу. Преимущество использования прайма менее очевидно, но оно традиционно.
Замечательным свойством числа 31 является то, что умножение можно заменить сдвигом (§15.19) и вычитанием для повышения производительности:
31 * i == (i ‹‹ 5) - i Современные виртуальные машины выполняют такую оптимизацию автоматически.
Хотя рецепт в этом пункте дает достаточно хорошие хеш-функции, он не дает современных хеш-функций, и библиотеки платформы Java не предоставляют такие хэш-функции по состоянию на выпуск 1.6. Написание таких хэш-функций — тема исследований, которую лучше оставить математикам и теоретикам-компьютерщикам.
Возможно, более поздняя версия платформы предоставит современные хеш-функции для своих классов и служебных методов, чтобы обычные программисты могли создавать такие хеш-функции. Между тем, методы, описанные в этом пункте, должны подойти для большинства приложений.
Это очень хороший источник.< /а>
Значение 31 было выбрано потому, что это нечетное простое число. Если бы оно было четным и умножение переполнилось бы, информация была бы потеряна, так как умножение на 2 эквивалентно сдвигу. Преимущество использования прайма менее очевидно, но оно традиционно. Замечательным свойством числа 31 является то, что умножение можно заменить сдвигом и вычитанием для лучшей производительности: 31 * i == (i ‹‹ 5) - i. Современные виртуальные машины выполняют такую оптимизацию автоматически.
См. этот пост: Почему Java hashCode() в String использовать 31 в качестве множителя?
Вот откуда ответ TheEwook.
Как правило, вы используете простые числа, потому что они не имеют множителей и будут лучше распределяться по модулю N, где N — размер диапазона, в который вы входите. 31 — маленькое нечетное простое число, поэтому оно работает хорошо. Однако, как указывают различные источники, которые вы найдете в Интернете, маленькое простое число, такое как 31, может привести к большему количеству конфликтов, чем большее простое число (особенно если хешируемые значения изначально неравномерно распределены), поэтому вы можете выбрать большее простое число, если вы обнаружили, что производительность не так хороша, как хотелось бы.
