Dlaczego hashCode () Java w String używa 31 jako mnożnika?

Zgodnie z dokumentacją Java kod skrótu dla Stringobiektu jest obliczany jako:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

używając intarytmetyki, gdzie s[i]jest i tym znakiem łańcucha, njest 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?

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

Wybrano wartość 31, ponieważ jest to nieparzysta liczba pierwsza. Gdyby tak było, a mnożenie się przepełniłoby, informacja zostałaby utracona, ponieważ mnożenie przez 2 jest równoważne przesunięciu. Zaleta korzystania z liczby pierwszej jest mniej wyraźna, ale jest tradycyjna. Ładny obiekt z 31 jest to, że mnożenie można zastąpić przez przesunięcie i odejmowania dla lepszej wydajności: 31 * i == (i << 5) - i. Nowoczesne maszyny wirtualne wykonują tego rodzaju optymalizację automatycznie.

(z rozdziału 3, pozycja 9: Zawsze zastępuj kod skrótu, gdy zastępujesz wartość równą, strona 48)

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

Na (przeważnie) starych procesorach mnożenie przez 31 może być stosunkowo tanie. Na przykład na ARM jest to tylko jedna instrukcja:

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

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

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 * 31jest równoważne z (n << 5) - n.

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ą:

Z pozostałych czterech prawdopodobnie wybrałbym P (31), ponieważ jest to najtańszy kalkulator na maszynie RISC (ponieważ 31 jest różnicą dwóch potęg dwóch). P (33) jest podobnie tani do obliczenia, ale jego wydajność jest nieznacznie gorsza, a 33 jest złożony, co mnie trochę denerwuje.

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

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.

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.

Z JDK-4045622 , gdzie Joshua Bloch opisuje powody, dla których String.hashCode()wybrano tę konkretną (nową) implementację

Poniższa tabela podsumowuje działanie różnych funkcji skrótu opisanych powyżej dla trzech zestawów danych:

1) Wszystkie słowa i frazy z wpisami w 2. Int'l nienauczonym słowniku Merriam-Webster (311 141 ciągów, średnia długość 10 znaków).

2) Wszystkie ciągi znaków w / bin / , / usr / bin / , / usr / lib / , / usr / ucb / i / usr / openwin / bin / * (66 304 ciągów, średnia długość 21 znaków).

3) Lista adresów URL zebranych przez robota sieciowego, który działał przez kilka godzin zeszłej nocy (28 372 ciągów, średnia długość 49 znaków).

Metryka wydajności pokazana w tabeli jest „średnim rozmiarem łańcucha” dla wszystkich elementów w tablicy skrótów (tj. Oczekiwana wartość liczby kluczy w porównaniu do wyszukania elementu).

                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439

Patrząc na tę tabelę, jasne jest, że wszystkie funkcje oprócz bieżącej funkcji Java i dwóch uszkodzonych wersji funkcji Weinbergera oferują doskonałą, prawie nie do odróżnienia wydajność. Mocno przypuszczam, że ta wydajność jest w gruncie rzeczy „ideałem teoretycznym”, który uzyskałbyś, gdybyś użył prawdziwego generatora liczb losowych zamiast funkcji skrótu.

Wykluczę funkcję WAIS, ponieważ jej specyfikacja zawiera strony liczb losowych, a jej wydajność nie jest lepsza niż żadna z znacznie prostszych funkcji. Każda z pozostałych sześciu funkcji wydaje się być doskonałym wyborem, ale musimy wybrać jedną. Przypuszczam, że wykluczyłbym wariant Vo i funkcję Weinbergera ze względu na ich dodatkową złożoność, choć niewielką. Z pozostałych czterech prawdopodobnie wybrałbym P (31), ponieważ jest to najtańszy kalkulator na maszynie RISC (ponieważ 31 jest różnicą dwóch potęg dwóch). P (33) jest podobnie tani do obliczenia, ale jego wydajność jest nieznacznie gorsza, a 33 jest złożony, co mnie trochę denerwuje.

Josh

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:

• moduł typu danych, w który go wstawisz (2 ^ 32 lub 2 ^ 64)
• moduł liczby segmentów w twojej tablicy hasht (różni się. W java było kiedyś liczbą pierwszą, teraz 2 ^ n)
• pomnóż lub przesuń przez magiczną liczbę w funkcji miksowania
• Wartość wejściowa

Naprawdę możesz kontrolować tylko kilka z tych wartości, więc należy zachować szczególną ostrożność.

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

• unikalny (Zobacz operator ^ w dokumencie obliczania kodu skrótu, pomaga unikatowy)
• tani koszt obliczeń

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.

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.

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:

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