Zgodnie z dokumentacją Java kod skrótu dla String
obiektu jest obliczany jako:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
używając
int
arytmetyki, gdzies[i]
jest i tym znakiem łańcucha,n
jest długością łańcucha i^
wskazuje na potęgowanie.
Dlaczego 31 jest używany jako mnożnik?
Rozumiem, że mnożnik powinien być stosunkowo dużą liczbą pierwszą. Dlaczego więc nie 29, 37, a nawet 97?
Odpowiedzi:
Według Effective Java Joshua Blocha (książki, której nie można wystarczająco polecić i którą kupiłem dzięki ciągłym wzmiankom o przepełnieniu stosu):
(z rozdziału 3, pozycja 9: Zawsze zastępuj kod skrótu, gdy zastępujesz wartość równą, strona 48)
źródło
Jak wskazują Goodrich i Tamassia , jeśli weźmiesz ponad 50 000 angielskich słów (utworzonych jako połączenie list słów zawartych w dwóch wariantach Uniksa), użycie stałych 31, 33, 37, 39 i 41 spowoduje mniej niż 7 kolizji w każdej sprawie. Wiedząc o tym, nie powinno dziwić, że wiele implementacji Java wybiera jedną z tych stałych.
Przypadkowo byłem w trakcie czytania sekcji „wielomianowe kody skrótu”, kiedy zobaczyłem to pytanie.
EDYCJA: tutaj jest link do książki PDF ~ 10mb, o której mowa powyżej. Zobacz rozdział 10.2 Tabele skrótów (strona 413) Struktur danych i algorytmów w Javie
źródło
Na (przeważnie) starych procesorach mnożenie przez 31 może być stosunkowo tanie. Na przykład na ARM jest to tylko jedna instrukcja:
Większość innych procesorów wymagałaby osobnej instrukcji przesunięcia i odjęcia. Jeśli jednak twój mnożnik jest wolny, nadal jest to wygrana. Współczesne procesory mają zwykle szybkie mnożniki, więc nie ma to większego znaczenia, o ile 32 idzie po właściwej stronie.
Nie jest to świetny algorytm mieszania, ale jest wystarczająco dobry i lepszy niż kod 1.0 (i znacznie lepszy niż specyfikacja 1.0!).
źródło
String.hashCode
poprzedza StrongARM, który IIRC wprowadził 8-bitowy multiplikator i prawdopodobnie zwiększył się do dwóch cykli dla połączonej arytmetyki / logiki z operacjami przesunięcia.Map.Entry
został naprawiony przez specyfikację,key.hashCode() ^ value.hashCode()
mimo że nie jest nawet parą nieuporządkowanąkey
ivalue
ma zupełnie inne znaczenie. Tak, to oznacza, żeMap.of(42, 42).hashCode()
lubMap.of("foo", "foo", "bar", "bar").hashCode()
itd. Są przewidywalnie zerowe. Więc nie używaj map jako kluczy do innych map…Po pomnożeniu bity są przesuwane w lewo. Wykorzystuje to więcej dostępnej przestrzeni kodów skrótu, redukując kolizje.
Nie wykorzystując potęgi dwóch, bity skrajnie prawe niższego rzędu również są zapełniane, aby zmieszać je z kolejną częścią danych przechodzących do skrótu.
Wyrażenie
n * 31
jest równoważne z(n << 5) - n
.źródło
Możesz przeczytać oryginalne uzasadnienie Blocha w sekcji „Komentarze” w http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 . Zbadał wydajność różnych funkcji skrótu w odniesieniu do wynikowej „średniej wielkości łańcucha” w tabeli skrótów.
P(31)
był jedną z powszechnych funkcji w tym czasie, którą znalazł w książce K&R (ale nawet Kernighan i Ritchie nie pamiętali, skąd się wziął). W końcu musiał zasadniczo wybrać jeden, więc wziął,P(31)
ponieważ wydawało się, że działa wystarczająco dobrze. ChociażP(33)
nie było tak naprawdę gorzej, a mnożenie przez 33 jest równie szybkie do obliczenia (tylko przesunięcie o 5 i dodanie), wybrał 31, ponieważ 33 nie jest liczbą pierwszą:Tak więc rozumowanie nie było tak racjonalne, jak sugeruje wiele odpowiedzi tutaj. Ale wszyscy dobrze wymyślamy racjonalne powody po decyzjach jelitowych (i nawet Bloch może być na to podatny).
źródło
Właściwie 37 działałoby całkiem dobrze! z: = 37 * x można obliczyć jako
y := x + 8 * x; z := x + 4 * y
. Oba kroki odpowiadają jednej instrukcji LEA x86, więc jest to niezwykle szybkie.W rzeczywistości mnożenie z jeszcze większą liczbą pierwszą 73 można wykonać z tą samą prędkością przez ustawienie
y := x + 8 * x; z := x + 8 * y
.Zastosowanie 73 lub 37 (zamiast 31) może być lepsze, ponieważ prowadzi do gęstszego kodu : dwie instrukcje LEA zajmują tylko 6 bajtów w porównaniu z 7 bajtami dla ruchu + shift + odejmowania dla pomnożenia przez 31. Jednym z możliwych zastrzeżeń jest to, że zastosowane tutaj 3-argumentowe instrukcje LEA stały się wolniejsze w architekturze Sandy Bridge Intela, ze zwiększonym opóźnieniem o 3 cykle.
Co więcej, 73 to ulubiony numer Sheldona Coopera.
źródło
Neil Coffey wyjaśnia, dlaczego 31 jest używane w ramach wyprasowywania stronniczości .
Zasadniczo użycie 31 daje bardziej równomierny rozkład prawdopodobieństwa dla funkcji skrótu.
źródło
Z JDK-4045622 , gdzie Joshua Bloch opisuje powody, dla których
String.hashCode()
wybrano tę konkretną (nową) implementacjęźródło
Bloch nie do końca się tym zajmuje, ale uzasadnieniem, które zawsze słyszałem / wierzyłem, jest to, że jest to podstawowa algebra. Skróty sprowadzają się do mnożenia i operacji modułu, co oznacza, że nigdy nie chcesz używać liczb ze wspólnymi czynnikami, jeśli możesz im pomóc. Innymi słowy, względnie pierwsze liczby zapewniają równomierny rozkład odpowiedzi.
Liczby, które składają się za pomocą skrótu, to zazwyczaj:
Naprawdę możesz kontrolować tylko kilka z tych wartości, więc należy zachować szczególną ostrożność.
źródło
W najnowszej wersji JDK 31 jest nadal używane. https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode ()
Celem ciągu mieszającego jest
^
w dokumencie obliczania kodu skrótu, pomaga unikatowy)31 to maksymalna wartość, którą można umieścić w rejestrze 8-bitowym (= 1 bajt), jest to największa liczba pierwsza w rejestrze 1-bajtowym, jest liczbą nieparzystą.
Pomnóż 31 to << 5, a następnie odejmij się, dlatego potrzebujesz tanich zasobów.
źródło
Nie jestem pewien, ale zgaduję, że przetestowali próbkę liczb pierwszych i stwierdzili, że 31 dało najlepszy rozkład na próbkę możliwych ciągów.
źródło
Wynika to z faktu, że 31 ma niezłą właściwość - jej mnożenie można zastąpić przesunięciem bitowym, które jest szybsze niż standardowe mnożenie:
źródło