Po co używać liczby pierwszej w hashCode?

174

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 ()

Ian Dallas
źródło
To jest mniej więcej duplikat pytania stackoverflow.com/questions/1145217/… .
Hans-Peter Störr
1
Proszę sprawdzić moją odpowiedź na stackoverflow.com/questions/1145217/… Jest to związane z właściwościami wielomianów nad polem (nie pierścieniem!), Stąd liczbami pierwszymi.
TT_

Odpowiedzi:

104

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).

ILMTitan
źródło
9
Wtedy funkcja skrótu pomnożona przez 31 nie będzie działać optymalnie. Jednak uznałbym taką implementację tablicy mieszającej za źle zaprojektowaną, biorąc pod uwagę, jak powszechna jest 31 jako mnożnik.
ILMTitan
11
Więc 31 jest wybierane na podstawie założenia, że ​​implementatorzy tablic mieszających wiedzą, że 31 jest powszechnie używane w kodach skrótu?
Steve Kuo
3
31 jest wybierany w oparciu o założenie, że większość implementacji ma faktoryzacje o stosunkowo małych liczbach pierwszych. Zwykle 2s, 3s i 5s. Może zaczynać się od 10 i rosnąć 3X, gdy się zapełni. Rozmiar rzadko jest całkowicie losowy. A nawet gdyby tak było, 30/31 to niezłe szanse na posiadanie dobrze zsynchronizowanych algorytmów mieszania. Obliczenie może być również łatwe, jak stwierdzili inni.
ILMTitan
8
Innymi słowy ... musimy wiedzieć coś o zbiorze wartości wejściowych i prawidłowościach zbioru, aby napisać funkcję, która ma na celu pozbawienie ich tych prawidłowości, aby wartości w zestawie nie kolidowały w tym samym wiadra do mieszania. Mnożenie / dzielenie / modulowanie przez liczbę pierwszą daje taki efekt, ponieważ jeśli masz LOOP z elementami X i przeskoczysz spacje Y w pętli, nigdy nie wrócisz do tego samego miejsca, dopóki X nie stanie się czynnikiem Y Ponieważ X jest często liczbą parzystą lub potęgą 2, to Y musi być liczbą pierwszą, więc X + X + X ... nie jest dzielnikiem Y, więc 31 yay! : /
Triynko,
3
@FrankQ. Taka jest natura arytmetyki modularnej. (x*8 + y) % 8 = (x*8) % 8 + y % 8 = 0 + y % 8 = y % 8
ILMTitan
135

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.

advait
źródło
17
Czy nie mówimy o mnożniku używanym do generowania kodu skrótu, a nie o modulo używanym do sortowania tych kodów skrótu w zasobniki?
ILMTitan
3
Ta sama zasada. Jeśli chodzi o I / O, hash zasila operację modulo tablicy skrótów. Myślę, że chodziło o to, że jeśli pomnożymy przez liczby pierwsze, uzyskamy bardziej losowo rozłożone dane wejściowe do punktu, w którym modulo nawet nie będzie miało znaczenia. Ponieważ funkcja skrótu lepiej wykorzystuje luzy w dystrybucji danych wejściowych, czyniąc je mniej regularnymi, jest mniej prawdopodobne, że zderzają się, niezależnie od modułu użytego do umieszczenia ich w wiadrze.
Triynko
9
Ten rodzaj odpowiedzi jest bardzo przydatny, ponieważ przypomina raczej naukę łowienia ryb niż łowienie dla niego. Pomaga ludziom zobaczyć i zrozumieć zasadę leżącą u podstaw używania liczb pierwszych do haszowania ... która polega na nieregularnym rozkładaniu danych wejściowych, aby po modulo wpadały one równomiernie do wiader :).
Triynko,
29

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

smary wielogenowe
źródło
4
Prawda, ale nie są wiele odpowiednich liczb pierwszych , które są albo 2 ^ n + 1 (tak zwane bodźce Fermat ), tj 3, 5, 17, 257, 65537lub 2 ^ N - 1 ( liczb pierwszych Mersenne ) 3, 7, 31, 127, 8191, 131071, 524287, 2147483647. Jednak 31(a nie, powiedzmy, 127) jest wybrany.
Dmitry Bychenko
4
"ponieważ to dziwna liczba pierwsza" ... jest tylko jedna parzysta liczba pierwsza: P
Martin Schneider
Nie podoba mi się sformułowanie „jest mniej jasne, ale jest tradycyjne” w „Efektywnej Javie”. Jeśli nie chce wchodzić w szczegóły matematyczne, powinien zamiast tego napisać coś w rodzaju „ma [podobne] matematyczne powody”. Sposób, w jaki pisze, brzmi, jakby miał tylko tło historyczne :(
Qw3ry,
5

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ść.

Steve Kuo
źródło
jak kompilator mógłby zoptymalizować ten sposób? x * 31 == x * 32-1 nie jest prawdą dla wszystkich x ostatecznie. Miałeś na myśli przesunięcie w lewo 5 (równe pomnożeniu przez 32), a następnie odjęcie pierwotnej wartości (x w moim przykładzie). Chociaż może to być szybsze niż mnożenie (nawiasem mówiąc, prawdopodobnie nie jest to dla nowoczesnych procesorów cpu), są ważniejsze czynniki do rozważenia przy wyborze mnożenia dla haschcode (przychodzi na myśl równy rozkład wartości wejściowych do koszyków)
Grizzly
Poszukaj trochę, to dość powszechna opinia.
Steve Kuo
4
Powszechna opinia nie ma znaczenia.
fractor
1
@Grizzly, to jest szybsze niż mnożenie. IMul ​​ma minimalne opóźnienie wynoszące 3 cykle na każdym nowoczesnym procesorze. (patrz instrukcje Agner Fog) mov reg1, reg2-shl reg1,5-sub reg1,reg2można wykonać w 2 cyklach. (mov to tylko zmiana nazwy i trwa 0 cykli).
Johan
3

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
Jan
źródło
3

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.

starblue
źródło
2

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.

Amar Magar
źródło
1

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.

DED
źródło
0

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


źródło