Dlaczego warto używać liczby pierwszej w hashCode?

Liczby pierwsze są wybierane tak, aby najlepiej rozdzielać dane między hash buckets. Jeśli rozkład wejść jest losowy i równomiernie rozłożony, to wybór kodu/modułu nie ma znaczenia. Ma wpływ tylko wtedy, gdy istnieje pewien wzór na wejściach.

Jest to często przypadek, gdy mamy do czynienia z lokalizacjami pamięci. Na przykład wszystkie 32-bitowe liczby całkowite są wyrównane do adresów podzielnych przez 4. W poniższej tabeli przedstawiono efekty używania prime vs. non-prime Moduł:

Input       Modulo 8    Modulo 7
0           0           0
4           4           4
8           0           1
12          4           5
16          0           2
20          4           6
24          0           3
28          4           0

Zwróć uwagę na rozkład prawie doskonały przy użyciu modułu prime vs. modułu non-prime.

Jednakże, chociaż powyższy przykład jest w dużej mierze wymyślony, ogólna zasada jest taka, że gdy mamy do czynienia z wzorem wejść , użycie modułu liczby pierwszej da najlepszy rozkład.

Jeśli to coś warte, Effective Java 2nd Edition odręcznie pomija zagadnienie matematyki i po prostu mówi, że powodem wyboru 31 jest:

• ponieważ jest to dziwna liczba pierwsza, a używanie liczb pierwszych jest "tradycyjne"
• jest to również jedna moc mniejsza od dwóch, co pozwala na optymalizację bitową

Oto pełny cytat z pozycji 9: zawsze nadpisuj hashCode Kiedy nadpisujesz equals:

Wartość 31 została wybrana, ponieważ jest dziwna prime. Gdyby było równe i mnożenie przepełnione, informacja zostałaby utracona, ponieważ mnożenie przez 2 jest równoznaczne z przesunięciem. Zaleta stosowania prime jest mniej wyraźna, ale jest tradycyjna.

Ładną właściwością 31 jest to, że mnożenie można zastąpić przesunięciem (§15.19) i odejmowanie dla lepszej wydajności:

 31 * i == (i << 5) - i

Nowoczesne maszyny wirtualne wykonują tego rodzaju optymalizację automatycznie.

---

Podczas gdy przepis w tym punkcie daje rozsądnie dobre funkcje hashowe, nie dają najnowocześniejszych funkcji hashowych, ani biblioteki platformy Java nie dostarczają takich funkcji hashowych od wydania 1.6. Pisanie takich funkcji hashowych jest tematem badawczym, najlepiej pozostawionym matematykom i informatykom teoretycznym.

Być może późniejsze wydanie platformy dostarczy najnowocześniejszych funkcji hashowych dla swoich klas i metod użytkowych, aby umożliwić przeciętnym programistom konstruowanie takich funkcji hashowych. W międzyczasie techniki opisane w tej pozycji powinny być odpowiednie dla większości zastosowań.

W uproszczeniu można powiedzieć, że użycie mnożnika z licznymi dzielnikami spowoduje więcej kolizji hashowych. Ponieważ dla efektywnego hashowania chcemy zminimalizować liczbę kolizji, staramy się użyć mnożnika, który ma mniej dzielników. Liczba pierwsza z definicji ma dokładnie dwa odrębne, dodatnie dzielniki.

Podobne pytania

• Java hashCode from one pole - przepis, Plus przykład użycia Apache Commons Lang ' s builders
• czy błędne jest definiowanie hashcode obiektu jako sumy, mnożenia, cokolwiek, wszystkich zmiennych klasowych hashcodes?
• Absolute Beginner ' s Guide To Bit Shifting?

Słyszałem, że 31 zostało wybrane tak, że kompilator może zoptymalizować mnożenie do lewego przesunięcia 5 bitów, a następnie odjąć wartość.

Oto cytat trochę bliżej źródła.

Sprowadza się do:

• 31 jest liczbą pierwszą, która zmniejsza kolizje
• 31]}
• rozsądny kompromis w prędkości

Najpierw obliczysz wartość hash modulo 2^32 (wielkość int), więc chcesz coś względnie prime do 2^32 (względnie prime oznacza, że nie ma wspólnych dzielników). Każdy nieparzysty numer by do tego pasował.

Wtedy dla danej tabeli hash indeks jest zwykle obliczany z wartości hash modulo wielkości tabeli hash, więc chcesz coś, co jest względnie pierwsze do wielkości tabeli hash. Często rozmiary tabel skrótów są wybierane jako liczby pierwsze z tego powodu. W w przypadku Javy implementacja Sun upewnia się, że rozmiar jest zawsze potęgą dwóch, więc tutaj też wystarczy Nieparzysta liczba. Istnieje również dodatkowe masowanie klawiszy skrótu w celu dalszego ograniczenia kolizji.

Złym skutkiem, jeśli tabela hash i mnożnik mają wspólny czynnik n, może być to, że w pewnych okolicznościach zostaną użyte tylko 1/N wpisów w tabeli hash.

Ogólnie pomaga osiągnąć bardziej równomierne rozprzestrzenianie się danych między zasobnikami hash, szczególnie w przypadku kluczy o niskiej entropii.

31 jest również specyficzna dla Java HashMap, która używa int jako typu danych hash. Tak więc maksymalna pojemność 2^32. Nie ma sensu używać większych liczb pierwszych Fermata lub Mersenne ' a.