Преглеждам изходния код на 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?
От Effective Java
Също така е с едно по-малко от степен две, което позволява побитова оптимизация
Ето пълния цитат,
от елемент 9: Винаги заменяй hashCode, когато заменяш равно на:
Стойността 31 е избрана, защото е странно просто число. Ако беше четен и умножението беше препълнено, информацията щеше да бъде загубена, тъй като умножението по 2 е еквивалентно на преместване. Предимството от използването на просто е по-малко ясно, но е традиционно.
Хубаво свойство на 31 е, че умножението може да бъде заменено с отместване (§15.19) и изваждане за по-добра производителност:
31 * i == (i ‹‹ 5) - i Съвременните виртуални машини правят този вид оптимизация автоматично.
Въпреки че рецептата в този елемент дава сравнително добри хеш функции, тя не дава най-съвременните хеш функции, нито библиотеките на Java платформата предоставят такива хеш функции от версия 1.6. Писането на такива хеш функции е изследователска тема, която е най-добре оставена на математиците и теоретичните компютърни учени.
Може би по-късна версия на платформата ще предостави най-съвременните хеш функции за нейните класове и полезни методи, за да позволи на обикновените програмисти да конструират такива хеш функции. Междувременно техниките, описани в този елемент, трябва да са подходящи за повечето приложения.
Това е много Добър източник.
Стойността 31 е избрана, защото е странно просто число. Ако беше четен и умножението препълни, информацията щеше да бъде загубена, тъй като умножението по 2 е еквивалентно на преместване. Предимството от използването на просто е по-малко ясно, но е традиционно. Хубаво свойство на 31 е, че умножението може да бъде заменено с отместване и изваждане за по-добра производителност: 31 * i == (i ‹‹ 5) - i. Съвременните виртуални машини правят този вид оптимизация автоматично.
Вижте тази публикация: Защо hashCode() на Java в String да използвате 31 като множител?
Ето откъде идва отговорът на TheEwook.
Обикновено използвате прости числа, защото те нямат никакви множители и ще разпределят по-добре модул N, където N е размерът на диапазона, в който се събирате. 31 е малко, нечетно просто число, така че работи добре. Въпреки това, както показват различните източници, които ще намерите в интернет, малко просто число като 31 може да доведе до повече сблъсъци, отколкото по-голямо просто число (особено ако хешираните стойности не са добре разпределени в началото), така че можете да изберете по-голямо просто, ако установите, че производителността не е толкова добра, колкото бихте искали.
