Nasza strona używa cookies. Dowiedz się więcej o celu ich używania i zmianie ustawień w przeglądarce. Korzystając ze strony, wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki. Rozumiem

Ciekawy przypadek ciągu HashCode w Javie

Animesh Gaitonde Senior Software Engineer / Directi
Jak sposób wyliczania hashCode wpływa na pobieranie danych z HashSet.
 Ciekawy przypadek ciągu HashCode w Javie

Programuję w Javie od 1,5 roku. Ostatnio eksperymentowałem z analizą wydajności struktur danych Javy. Ale żeby nie było zbyt łatwo, postanowiłem wybrać moją ulubioną strukturę danych, czyli HashSet. HashSet pozwala na sprawdzenie obecności elementu i zapis ze  złożonością czasową na poziomie O(1). Zmierzyłem i porównałem czas wyszukiwania losowych ciągów o różnych długościach w HashSet.

Poniżej znajduje się napisany przeze mnie fragment kodu:

package performance;

import com.google.common.base.Stopwatch;

import java.util.*;

public class HashCodePerformance {
    public static void main(String[] args) {
        Set<String> stringHashSet = new HashSet<>();
        stringHashSet.add("London");
        stringHashSet.add("Mumbai");
        stringHashSet.add("NewYork");
        List<String> stringsToSearch = Arrays.asList("f5a5a608", "48abre7a6 i8a5r507",
                "7e50bc488 pl43fvf1p 65", "e843r6f1p vfvdfv vdvdg vgbgd ", "38aeaf9a6");
        for (String string : stringsToSearch) {
            Stopwatch timer = Stopwatch.createStarted();
            for (int index=0; index < 10000000; ++index) {
                stringHashSet.contains(string);
            }
            System.out.println("Search String \"" + string + "\" time taken " + timer.stop());
        }
    }
}


Rzućmy okiem na wydajność wyszukiwania losowych ciągów znaków:


Wydajność wyszukiwania ciągu

Zaobserwowałem coś ciekawego. Pierwsze i ostatnie wyszukiwanie ciągu (podświetlone na czerwono) zajmuje prawie 3 do 4 razy więcej czasu niż środkowe ciągi. Mimo że długość środkowych trzech ciągów znaków jest większa, wyszukiwanie jest o wiele bardziej wydajne. Oznacza to, że wyszukiwanie HashSet jest niezależne od długości ciągu.

Aby zrozumieć to zachowanie HashSet, wróćmy do podstaw.


Jak pod spodem działa HashSet

Java HashSet wewnętrznie wykorzystuje tablicę list do wstawiania, wyszukiwania i usuwania ze złożonością O(1). HashSet najpierw oblicza hash obiektu, aby określić indeks tablicy, pod którym obiekt będzie przechowywany. Później obiekt jest przechowywany pod obliczonym indeksem. Ta sama zasada obowiązuje podczas wyszukiwania i usuwania.

Jak HashSet/HashMap przechowuje obiekty

Uzyskiwanie dostępu do elementu tablicy jest operacją O(1), więc jedynym narzutem jest obliczanie skrótu obiektu. Dlatego funkcja haszująca musi być optymalna, aby nie wpływała w żaden sposób na wydajność.

Ponadto wynik tej funkcji powinien mieć równomierną dystrybucję. W przypadku kolizji, długość listy przy danym indeksie będzie rosła, a w najgorszym przypadku powikłaniem będzie O(n).

Kolizje HashSet/HashMap w wyniku nierównomiernego hashowania


Konstrukcja HashCode 

W Javie każdy obiekt ma metodę hashCode(). HashSet wywołuje tę metodę w celu określenia indeksu obiektu. Powróćmy do przykładu, w którym analizowaliśmy wydajność wyszukiwania łańcucha i sprawdźmy wartość hashCode dla losowych ciągów.


HashCode losowych ciągów w przykładzie

Widzimy, że pierwszy i ostatni ciąg znaków mają hashCode równy 0. Teraz czas zagłębić się w kod i rzucić okiem na implementację.

W starszych wersjach JDK 1.0+ i 1.1+, metoda hashCode dla ciągów zapętlała się co n-ty znak. Minusem tego podejścia było wiele ciągów znaków mapowanych na ten sam skrót, a to powodowało kolizje.

W Javie 1.2 stosuje się poniższy algorytm. Jest to dość powolny sposób, ale pomaga uniknąć kolizji.

Obliczanie HashCode Stringa

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }


Z powyższego kodu wynika, że przy pierwszym wywołaniu hashCode domyślna wartość zmiennej hash będzie wynosić 0 i wykonane zostaną linie 3–9. Kolejne wywołania funkcji hashCode() nie wykonają linii 3–9, jeśli wartość skrótu nie będzie równa zero.

Można wywnioskować, że funkcja hashCode() wykorzystuje cache'owanie, w którym skrót jest obliczany tylko przy pierwszym wywołaniu, a późniejsze wywołania otrzymają już obliczoną wartość.

public int hashCode() {
        int h = hash;
        if (!computed && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
            computed = true;
        }
        return h;
    }


Jeśli skrót ciągu wynosi 0, to obliczenie skrótu będzie wykonywane za każdym razem, gdy metoda zostanie wywołana. Teraz wiadomo, dlaczego wyszukiwanie niektórych ciągów zajmuje tyle czasu.


Obejście problemu wydajności

Powyższe obliczenia HashCode działają słabo w przypadku ciągów, które mają skrót 0. Jak możemy to zoptymalizować?

Każdy uczestnik kursu CS101 poleciłby użycie flagi, która zostanie ustawiona po pierwszym obliczeniu i pominie obliczenia w kolejnych wywołaniach.

Być może zastanawiasz się teraz, dlaczego twórcy Javy nie pomyśleli o tej optymalizacji w pierwszej kolejności lub dlaczego nie została ona załatana w późniejszych wersjach Javy?


Dlaczego nie naprawić HashCode?

Zgodnie z implementacją, poniżej znajduje się formuła skrótu dowolnego ciągu znaków o długości n.

hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] (tutaj s [n] jest n-tym znakiem w ciągu)

Taka funkcja hash zapewnia równomierny rozkład wartości w całym zakresie liczb całkowitych. Oznacza to prawdopodobieństwo, że ciąg znaków zostanie skrócony do 0, to 1 do 2³².

Pomyślmy o przypadkach, w których hash ciągu znaków wyniesie 0:

  1. Ciąg zawiera tylko 0 (znak Unicode)
  2. Pusty ciąg
  3. Nastąpiło przekroczenie zakresu liczb całkowitych


W rzeczywistych aplikacjach prawdopodobieństwo uzyskania takich ciągów jest niewielkie. Naprawienie implementacji hashCode jest banalne i deweloperzy Java mogli o tym pomyśleć. Jednak nie ma super korzyści wynikającej z takiego podejścia.

Obecnie dotyczy to tylko ciągów, których hash wynosi 0. Załóżmy, że naprawiamy hashCode przez dodanie flagi, o której wspominałem. Ogólnie rzecz biorąc, nie zauważymy większego wpływu na wydajność systemu w świecie rzeczywistym. Może to spowodować poprawę prędkości o 0,000010%. To analogiczne do stwierdzenia, że zoptymalizowaliśmy zadanie, które można wykonać w ciągu 1 godziny do 59 minut 59 sekund 7 milisekund.

Lepiej więc nie wprowadzać żadnych zmian w hashCode() poprzez wprowadzenie nowej zmiennej, ponieważ nie wpłynie to znacząco na wzrost wydajności.


Niektóre ciągi znaków, które mają hash 0

Wziąłem listę 20 000 słów ze słownika angielskiego i spróbowałem połączyć je tak, aby sprawdzić, czy mają one wartość zero. Kiedy rozważałem pojedyncze znaczenie tych słów, żadne z nich nie zmieniło się na zero. Kombinacja dwóch lub więcej słów dawała natomiast taki wynik.

Kilka przykładów zdań (znaczących słów), których skrót wynosi zero:

  • carcinomas motorists high
  • zipped daydreams thunderflashes
  • where inattentive agronomy
  • drumwood boulderhead


HashSet i HashMap są świetnie zoptymalizowane do sprawdzania, wstawiania i usuwania wartości. Istnieją jednak przypadki, w których wydajność może zostać obniżona z powodu nietypowego zachowania.


Oryginał tekstu w języku angielskim przeczytasz tutaj.

Lubisz dzielić się wiedzą i chcesz zostać autorem?

Podziel się wiedzą z 130 tysiącami naszych czytelników

Dowiedz się więcej