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

480

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?

jacobko
źródło
1
Porównaj także stackoverflow.com/questions/1835976/… - Myślę, że 31 to zły wybór, jeśli piszesz własne funkcje hashCode.
Hans-Peter Störr
6
Gdyby było 29, 37, a nawet 97, zapytałbyś „dlaczego nie 31?”
Markiz Lorne
2
@EJP ważne jest, aby znać powód wyboru nie. chyba że liczba jest wynikiem sztuczki czarnej magii.
Dushyant Sabharwal
Jest post na blogu autorstwa @ peter-lawrey na ten temat tutaj: vanilla-java.github.io/2018/08/12/… i tutaj: vanilla-java.github.io/2018/08/15/…
Christophe Roussy
@DushyantSabharwal Chodzi mi o to, że mogło to być 29 lub 37 lub 97 lub 41 lub wiele innych wartości, bez większego praktycznego znaczenia. Używaliśmy 37 w 1976 r.
Markiz Lorne

Odpowiedzi:

405

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)

matowy b
źródło
346
Cóż, wszystkie liczby pierwsze są nieparzyste, z wyjątkiem 2. Po prostu powiedz.
Kip
38
Nie sądzę, że Bloch twierdzi, że został wybrany, ponieważ był nieparzystą liczbą pierwszą, ale ponieważ był dziwny ORAZ dlatego, że był liczbą pierwszą (ORAZ dlatego, że można go łatwo zoptymalizować do zmiany / odjęcia).
matt b
50
31 został wybrany, ponieważ jest to dziwna liczba pierwsza ??? To nie ma żadnego sensu - mówię, że 31 zostało wybrane, ponieważ dało najlepszą dystrybucję - sprawdź computinglife.wordpress.com/2008/11/20/…
computinglife
65
Myślę, że wybór 31 jest raczej niefortunny. Jasne, może zaoszczędzić kilka cykli procesora na starych komputerach, ale masz już kolizje skrótu na krótkich ciągach ascii, takich jak „@ i #!, Lub Ca i DB. Nie dzieje się tak, jeśli wybierzesz na przykład 1327144003 lub w co najmniej 524287, który umożliwia także przesunięcie bitów: 524287 * i == i << 19 - i.
Hans-Peter Störr
15
@Jason Zobacz moją odpowiedź stackoverflow.com/questions/1835976/... . Chodzi mi o to: otrzymujesz znacznie mniej kolizji, jeśli użyjesz większej liczby pierwszej i nie stracisz nic w tych dniach. Problem jest gorszy, jeśli używasz języków innych niż angielski ze zwykłymi znakami innymi niż ascii. A 31 było złym przykładem dla wielu programistów podczas pisania własnych funkcji hashCode.
Hans-Peter Störr
80

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

JohnZaj
źródło
6
Pamiętaj jednak, że możesz uzyskać ZNACZNIE więcej kolizji, jeśli użyjesz dowolnego rodzaju międzynarodowego zestawu znaków ze zwykłymi znakami spoza zakresu ASCII. Przynajmniej sprawdziłem to dla 31 i niemieckiego. Myślę więc, że wybór 31 jest zepsuty.
Hans-Peter Störr
1
@ jJack, link podany w odpowiedzi jest uszkodzony.
SK Venkat
Oba linki w tej odpowiedzi są zepsute. Także argument z pierwszego akapitu jest w pewnym sensie niepełny; w jaki sposób inne liczby nieparzyste porównują się z pięcioma wymienionymi w tym teście?
Mark Amery
58

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

Tom Hawtin - tackline
źródło
7
Zabawne jest to, że mnożenie przez 31 jest na moim komputerze stacjonarnym w rzeczywistości trochę wolniejsze niż mnożenie przez, powiedzmy, 92821. Wydaje mi się, że kompilator próbuje „zoptymalizować” go do zmiany i dodać. :-)
Hans-Peter Störr
1
Nie sądzę, że kiedykolwiek użyłem ARM, który nie byłby równie szybki ze wszystkimi wartościami w zakresie +/- 255. Zastosowanie potęgi 2 minus jeden ma niefortunny efekt, że dopasowanie dopasowania do dwóch wartości zmienia kod skrótu o potęgę dwóch. Wartość -31 byłaby lepsza i sądzę, że coś w rodzaju -83 (64 + 16 + 2 + 1) mogłoby być jeszcze lepsze (blenderowanie bitów nieco lepiej).
supercat
@ supercat Nie przekonuje minus. Wygląda na to, że wrócisz do zera. / String.hashCodepoprzedza 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.
Tom Hawtin - tackline
1
@ TomHawtin-tackline: Przy użyciu 31 hasz czterech wartości wyniósłby 29791 * a + 961 * b + 31 * c + d; używając -31, byłoby -29791 * a + 961 * b - 31 * c + d. Nie sądzę, aby różnica była znacząca, gdyby cztery elementy były niezależne, ale jeśli pary sąsiednich elementów pasują, wynikowy kod skrótu będzie udziałem wszystkich niesparowanych elementów plus pewnej wielokrotności 32 (z par). W przypadku łańcuchów może to nie mieć większego znaczenia, ale jeśli pisze się metodę ogólnego przeznaczenia dla agregacji mieszających, sytuacja, w której pasujące elementy sąsiednie będzie nieproporcjonalnie powszechna.
supercat
3
@ fajny zabawny fakt, kod skrótu Map.Entryzostał naprawiony przez specyfikację, key.hashCode() ^ value.hashCode()mimo że nie jest nawet parą nieuporządkowaną keyi valuema zupełnie inne znaczenie. Tak, to oznacza, że Map.of(42, 42).hashCode()lub Map.of("foo", "foo", "bar", "bar").hashCode()itd. Są przewidywalnie zerowe. Więc nie używaj map jako kluczy do innych map…
Holger
33

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.

erickson
źródło
29

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

David Ongaro
źródło
2
Dokładne badania i obiektywna odpowiedź!
Vishal K,
22

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.

godz
źródło
5
Jesteś programistą pascal czy coś takiego? co jest z: = rzeczami?
Mainguy
11
@Mainguy W rzeczywistości jest to składnia ALGOL i jest dość często używana w pseudokodzie.
ApproachingDarknessFish
4
ale w zespole ARM mnożenie przez 31 można wykonać w jednej instrukcji
phuclv
W TPOP (1999) można przeczytać o wczesnej Javie ( str. 57 ): „... Problem został rozwiązany przez zastąpienie skrótu jednym równoważnikiem pokazanego przez nas (z mnożnikiem 37 ) ...”
miku
19

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.

Sok
źródło
12

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

Pływ
źródło
5

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

Jason
źródło
4

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.

Do Nhu Vy
źródło
3

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.

Dave L.
źródło
1

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