Dlaczego metoda hashCode() w łańcuchu znaków używa 31 jako mnożnika?

Goodrich i Tamassia obliczyli z ponad 50 000 angielskich słów (utworzonych jako związek list słów dostarczanych w dwóch wariantach Uniksa), że użycie stałych 31, 33, 37, 39 i 41 spowoduje mniej niż 7 kolizji w każdym przypadku. Może to być powodem, dla którego tak wiele implementacji Javy wybiera takie stałe.

Patrz sekcja 9.2 tabele skrótów (strona 522) struktur danych i algorytmów w Javie .

Na (głównie) starych procesorach mnożenie przez 31 może być stosunkowo tanie. Na przykład na ramieniu jest to tylko jedna instrukcja:

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

Większość innych procesorów wymagałaby oddzielnej instrukcji przesunięcia i odjęcia. Jeśli jednak twój mnożnik jest powolny, to nadal jest to wygrana. Nowoczesne procesory mają zwykle szybkie mnożniki, więc nie robi to wielkiej różnicy, tak długo, jak 32 idzie po właściwej stronie.

Nie jest to świetny algorytm haszujący, ale jest wystarczająco dobry i lepszy niż 1.0 kod (i bardzo dużo lepszy niż 1.0 spec!).

Mnożąc, bity są przesuwane w lewo. Wykorzystuje to więcej dostępnej przestrzeni kodów skrótu, redukując kolizje.

Nie używając potęgi dwóch, wypełniane są również bity niższego rzędu, prawe, które można mieszać z następnym fragmentem danych wchodzącym do skrótu.

Wyrażenie n * 31 jest równoważne (n << 5) - n.

Możesz przeczytać oryginalne rozumowanie Blocha pod "komentarzami" w http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 . badał wydajność różnych funkcji hash w odniesieniu do wynikowej "średniej wielkości łańcucha" w tabeli hash. P(31) był jedną z powszechnych funkcji w tym czasie, które znalazł w książce K&R (ale nawet Kernighan i Ritchie nie pamiętali, skąd pochodzi). W końcu w zasadzie musiał wybrać jeden i tak wziął P(31) ponieważ wydawało aby wykonać wystarczająco dobrze. Mimo że P(33) nie było tak naprawdę gorsze i 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 cztery, pewnie wybrałbym P (31), bo najtaniej obliczyć na RISC maszyna (bo 31 jest różnicą dwóch potęg z dwóch). P (33) jest podobnie tani w obliczeniach, ale jego wydajność jest nieznacznie gorsza, a 33 jest złożony, co czyni mnie trochę zdenerwowany.

Właściwie, 37 byłoby całkiem niezłe! 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 przez jeszcze większą liczbę pierwszą 73 można to zrobić z tą samą prędkością przez ustawienie y := x + 8 * x; z := x + 8 * y.

Użycie 73 lub 37 (zamiast 31) może być lepsze, ponieważ prowadzi to do gęstszego kodu : dwie instrukcje LEA zajmują tylko 6 bajtów vs. 7 bajtów dla move+shift+odejmowanie dla mnożenia do 31. Jednym z możliwych zastrzeżeń jest to, że 3-argumentowe instrukcje LEA użyte tutaj stały się wolniejsze w architekturze Sandy bridge Intela, ze zwiększonym opóźnieniem 3 cykli.

Ponadto, 73 to ulubiony numer Sheldona Coopera.

Neil Coffey wyjaśnia Dlaczego 31 jest używany pod .

Zasadniczo użycie 31 daje bardziej równomierny rozkład prawdopodobieństwa dla funkcji hash.

Z JDK-4045622, gdzie Joshua Bloch opisuje powody, dla których ta konkretna (Nowa) String.hashCode() implementacja została wybrana

Poniższa tabela podsumowuje wydajność różnych skrótów funkcje opisane powyżej, dla trzech zbiorów danych:

1) wszystkie słowa i zwroty z wpisami w Merriam-Webster ' s 2. Int ' l Unabridged Dictionary (311 141 ciągów, avg length 10 chars).

2) wszystkie łańcuchy w /bin/, / usr / bin / , /usr / lib / , / usr / ucb / i/usr/openwin/ bin / * (66 304 ciągów, długość avg 21 znaków).

3) Lista adresów URL zebranych przez web-crawler, który działał przez kilka godziny ostatniej nocy (28 372 ciągów, długość avg 49 znaków).

Metryka wydajności pokazana w tabeli to " średni rozmiar łańcucha" nad wszystkimi elementami w tabeli hash (tj. wartością oczekiwaną Liczba klawiszy 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 tej tabeli, jest jasne, że wszystkie funkcje oprócz aktualną funkcję Javy oraz dwie zepsute wersje Weinbergera funkcja oferuje doskonałą, prawie nie do odróżnienia wydajność. I mocno przypuszczać, że ten występ jest zasadniczo "ideał teoretyczny", czyli to, co dostałbyś, gdybyś użył prawdziwego losowego generator liczb w miejsce funkcji hash.

Wykluczyłbym funkcję WAIS, ponieważ jej Specyfikacja zawiera strony liczb losowych, a jej wydajność nie jest lepsza niż którykolwiek z znacznie prostsze funkcje. Każda z pozostałych sześciu funkcji wygląda jak doskonały wybór, ale musimy wybrać jeden. Chyba wykluczyłbym Wariant Vo I funkcja Weinbergera ze względu na dodane złożoność, choć niewielka. Z pozostałych czterech wybrałbym P (31), ponieważ jest najtańszy do obliczenia na maszynie RISC (bo 31 jest różnicą dwóch potęg z dwóch). P (33) jest podobnie Tani do obliczyć, ale to wydajność jest nieznacznie gorsza, a 33 jest composite, co mnie trochę denerwuje.

Josh

Bloch nie do końca się w to angażuje, ale zawsze słyszałem/wierzyłem, że jest to podstawowa algebra. Hasze sprowadzają się do operacji mnożenia i modułu, co oznacza, że nigdy nie chcesz używać liczb ze wspólnymi czynnikami, jeśli możesz mu pomóc. Innymi słowy, względnie pierwsze liczby zapewniają równomierny rozkład odpowiedzi.

Liczby tworzące hash to zazwyczaj:

• moduł typu danych, do którego go wstawiasz (2^32 lub 2^64)
• Moduł liczby kubełków w Twoim hashtable (waha się. W Javie kiedyś prime, teraz 2^n)
• mnożenie lub przesunięcie przez liczbę magiczną w funkcji mieszania
• wartość wejściowa

Naprawdę można kontrolować tylko kilka z tych wartości, więc należy się trochę dodatkowej troski.

W najnowszej wersji JDK, 31 jest nadal używany. https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode()

Celem łańcucha hashowego jest

• unique (Let see operator ^ in hashcode calculation document, it help unique)
• tani koszt do obliczenia

31 to maksymalna wartość, którą można umieścić w rejestrze 8-bitowym (= 1 bajt), największa liczba pierwsza może umieścić w rejestrze 1-bajtowym, jest liczbą nieparzystą.

Mnożenie 31 jest

Nie jestem pewien, ale zgaduję, że przetestowali próbkę liczb pierwszych i odkryli, że 31 daje najlepszy rozkład na próbkę możliwych ciągów.

Dzieje się tak dlatego, że 31 ma ładną 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

Dużym oczekiwaniem od funkcji hash jest to, że ich jednorodna przypadkowość wyniku przetrwa operację, taką jak hash(x) % N gdzie N jest dowolną liczbą (i w wielu przypadkach potęgą dwóch), jednym z powodów jest to, że takie operacje są powszechnie używane w tabelach hash do określania szczelin. Użycie mnożników liczb pierwszych przy obliczaniu skrótu zmniejsza prawdopodobieństwo, że mnożnik i dzielniki N dzielą się, co sprawi, że wynik operacji będzie mniej równomiernie losowy.

Inni zwrócili uwagę na właściwość nice, że mnożenie przez 31 można wykonać przez mnożenie i odejmowanie. Chcę tylko zaznaczyć, że istnieje matematyczne określenie dla takich liczb pierwszych: Mersenne Prime

Wszystkie liczby pierwsze mersenne ' a są o jedną mniejszą od potęgi dwóch, więc możemy je zapisać jako:

p = 2^n - 1

Mnożenie x przez p:

x * p = x * (2^n - 1) = x * 2^n - x = (x << n) - x

Przesunięcia (SAL / SHL) i odejmowania (SUB) są na ogół szybsze niż mnożenie (MUL) na wielu maszynach. Zobacz tabele instrukcji od Agner Mgła

Dlatego GCC wydaje się optymalizować mnożenie przez liczby pierwsze mersenne ' a, zastępując je przesunięciami i podst. zobacz tutaj.

Jednak, moim zdaniem, taki mały prime jest złym wyborem dla funkcji hash. Przy stosunkowo dobrej funkcji skrótu można oczekiwać losowości na wyższych bitach skrótu. Jednak w przypadku funkcji hash Javy prawie nie ma losowości na wyższych bitach z krótszymi łańcuchami (i nadal wysoce wątpliwa losowość na dolnych bitów). Utrudnia to tworzenie efektywnych tabel hashowych. Zobacz tę fajną sztuczkę, której nie mogłeś zrobić za pomocą funkcji hash w Javie .

Niektóre odpowiedzi wspominają, że uważają, że to dobrze, że 31 pasuje do bajtu. Jest to w rzeczywistości bezużyteczne od:

(1) wykonujemy przesunięcia zamiast mnożenia, więc wielkość mnożnika nie ma znaczenia.

(2) z tego co wiem, nie ma konkretnej instrukcji x86, aby pomnożyć wartość 8 bajtów z wartością 1 bajtu, więc i tak musiałbyś przekonwertować "31" na wartość 8 bajtów, nawet jeśli mnożyłeś. Zobacz tutaj , mnożysz całe 64-bitowe rejestry.

Czy mniejsza wartość zwiększa losowość w środkowych-dolnych bitach? Może, ale wydaje się też, że znacznie zwiększa to możliwe kolizje :).

Można wymienić wiele różnych kwestii, ale generalnie sprowadzają się do dwóch podstawowych zasad, które nie są zamieszanie i dyfuzja