Po co używać liczby pierwszej w hashCode?

Zastanawiałem się tylko, dlaczego w klasach używa się liczb pierwszych hashCode() metodzie ? Na przykład, gdy używam Eclipse do generowania mojej hashCode()metody, zawsze 31używana jest liczba pierwsza :

public int hashCode() {
     final int prime = 31;
     //...
}

Bibliografia:

Oto dobry podkład na temat Hashcode i artykuł o tym, jak działa haszowanie, który znalazłem (C #, ale koncepcje są przenoszone): Eric Lippert's Guidelines and rules for GetHashCode ()

Ponieważ chcesz, aby liczba, przez którą mnożysz, i liczba segmentów, do których wstawiasz, miały ortogonalne czynniki pierwsze.

Załóżmy, że jest 8 pojemników do włożenia. Jeśli liczba, której używasz do pomnożenia, jest wielokrotnością 8, to przedział wstawiony do zostanie określony tylko przez najmniej znaczący wpis (ten w ogóle nie został pomnożony). Podobne wpisy będą się zderzać. Nie nadaje się do funkcji skrótu.

31 jest na tyle dużą liczbą pierwszą, że jest mało prawdopodobne, aby liczba zasobników była przez nią podzielna (a w rzeczywistości nowoczesne implementacje HashMap w języku Java utrzymują liczbę zasobników do potęgi 2).

Liczby pierwsze są wybierane tak, aby jak najlepiej rozdzielać dane między zasobniki mieszania. Jeśli rozkład danych wejściowych jest losowy i równomiernie rozłożony, wówczas wybór kodu skrótu / modułu nie ma znaczenia. Ma to wpływ tylko wtedy, gdy na danych wejściowych występuje określony wzorzec.

Dzieje się tak często w przypadku lokalizacji pamięci. Na przykład wszystkie 32-bitowe liczby całkowite są wyrównane do adresów podzielnych przez 4. Zapoznaj się z poniższą tabelą, aby zwizualizować skutki zastosowania modułu pierwszego względem modułu innego niż pierwszy:

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 prawie idealny rozkład, gdy używasz modułu podstawowego w porównaniu z modułem innym niż pierwotny.

Jednakże, chociaż powyższy przykład jest w dużej mierze zmyślony, ogólną zasadą jest, że gdy mamy do czynienia z układem danych wejściowych , użycie modułu liczb pierwszych da najlepszy rozkład.

Co jest warte, Effective Java 2nd Edition rezygnuje z matematyki i po prostu powiedz, że powodem wyboru 31 jest:

• Ponieważ jest to dziwna liczba pierwsza i „tradycyjne” jest używanie liczb pierwszych
• Jest to również o jeden mniej niż potęga dwóch, co pozwala na optymalizację bitową

Oto pełny cytat z punktu 9: Zawsze zastępuj, hashCodegdy zastępujeszequals :

Wartość 31 została wybrana, ponieważ jest to nieparzysta liczba pierwsza. Gdyby była parzysta, a mnożenie się przepełniało, informacja zostałaby utracona, ponieważ mnożenie przez 2 jest równoważne przesunięciu. Zaleta stosowania liczby pierwszej jest mniej wyraźna, ale jest tradycyjna.

Fajną własnością 31 jest to, że mnożenie można zastąpić przesunięciem ( §15.19 ) i odejmowaniem dla lepszej wydajności:

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

Nowoczesne maszyny wirtualne wykonują ten rodzaj optymalizacji automatycznie.

---

Chociaż przepis w tym elemencie zapewnia dość dobre funkcje skrótu, nie zapewnia najnowocześniejszych funkcji skrótu, a biblioteki platform Java nie zapewniają takich funkcji skrótu od wersji 1.6. Pisanie takich funkcji skrótu jest tematem badawczym, najlepiej pozostawionym matematykom i teoretycznym informatykom.

Być może późniejsze wydanie platformy zapewni najnowocześniejsze funkcje skrótu dla swoich klas i metod narzędziowych, aby umożliwić przeciętnym programistom tworzenie takich funkcji. W międzyczasie techniki opisane w tym punkcie powinny być odpowiednie dla większości zastosowań.

Raczej w uproszczeniu można powiedzieć, że użycie mnożnika z licznymi dzielnikami spowoduje więcej zderzeń z mieszaniem . Ponieważ w celu efektywnego haszowania chcemy zminimalizować liczbę kolizji, staramy się używać mnożnika, który ma mniej dzielników. Liczba pierwsza z definicji ma dokładnie dwa odrębne, dodatnie dzielniki.

Powiązane pytania

• Java hashCode z jednego pola - przepis oraz przykład użycia konstruktorów Apache Commons Lang
• czy niewłaściwe jest definiowanie hashcode obiektu jako sumy, mnożenia itp. wszystkich hashcodes zmiennych klas?
• Przewodnik dla początkujących na temat przesuwania końcówek?

Słyszałem, że wybrano 31 tak, aby kompilator mógł zoptymalizować mnożenie do 5 bitów z przesunięciem w lewo, a następnie odjąć wartość.

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

Sprowadza się do:

• 31 jest liczbą pierwszą, co zmniejsza liczbę kolizji
• 31 tworzy dobrą dystrybucję z
• rozsądny kompromis w szybkości

Najpierw obliczasz wartość skrótu modulo 2 ^ 32 (rozmiar an int), więc chcesz, aby coś było względnie pierwsze na 2 ^ 32 (względnie pierwsze oznacza, że ​​nie ma wspólnych dzielników). Każda nieparzysta liczba wystarczyłaby do tego.

Następnie dla danej tablicy skrótów indeks jest zwykle obliczany z wartości skrótu modulo rozmiar tablicy mieszającej, więc potrzebujesz czegoś, co jest względnie pierwsze w stosunku do rozmiaru tablicy skrótów. Z tego powodu często rozmiary tabel skrótów są wybierane jako liczby pierwsze. W przypadku Javy implementacja Sun zapewnia, że ​​rozmiar jest zawsze potęgą dwójki, więc i tutaj wystarczyłaby liczba nieparzysta. Istnieje również dodatkowe masowanie kluczy mieszających, aby jeszcze bardziej ograniczyć kolizje.

Zły efekt, jeśli tablica skrótów i mnożnik miały wspólny czynnik, nmoże polegać na tym, że w pewnych okolicznościach zostanie użyty tylko 1 / n wpisów w tablicy skrótów.

Powodem, dla którego używane są liczby pierwsze, jest zminimalizowanie kolizji, gdy dane wykazują określone wzorce.

Po pierwsze: jeśli dane są losowe, nie ma potrzeby stosowania liczby pierwszej, możesz wykonać operację modowania na dowolnej liczbie i będziesz mieć taką samą liczbę kolizji dla każdej możliwej wartości modułu.

Ale kiedy dane nie są przypadkowe, dzieją się dziwne rzeczy. Na przykład rozważ dane liczbowe, które zawsze są wielokrotnością 10.

Jeśli użyjemy mod 4, znajdziemy:

10 mod 4 = 2

20 mod 4 = 0

30 mod 4 = 2

40 mod 4 = 0

50 mod 4 = 2

Zatem z 3 możliwych wartości modułu (0,1,2,3) tylko 0 i 2 będą miały kolizje, czyli źle.

Jeśli użyjemy liczby pierwszej takiej jak 7:

10 mod 7 = 3

20 mod 7 = 6

30 mod 7 = 2

40 mod 7 = 4

50 mod 7 = 1

itp

Zwracamy również uwagę, że 5 nie jest dobrym wyborem, ale 5 jest liczbą pierwszą, ponieważ wszystkie nasze klucze są wielokrotnością 5. Oznacza to, że musimy wybrać liczbę pierwszą, która nie dzieli naszych kluczy, wybór dużej liczby pierwszej to zwykle wystarczy.

Zatem błędem jest powtarzalność, powodem używania liczb pierwszych jest zneutralizowanie wpływu wzorców w kluczach na rozkład kolizji funkcji skrótu.

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

Generalnie pomaga to osiągnąć bardziej równomierne rozłożenie danych między zasobnikami mieszania, szczególnie w przypadku kluczy o niskiej entropii.