Jak działa HashMapa?

Pytania rekrutacyjne – Jak działa HashMapa w Javie?

Wśród wielu pytań zadawanych na rozmowach rekrutacyjnych są takie, które pojawiają się niezwykle często. Pytanie „Jak działa HashMapa?” to zdecydowanie najczęściej padające pytanie na rekrutacjach na stanowisko Java Developera. Ja osobiście odpowiadałem na nie co najmniej kilka razy. Dlatego odpowiedź na to pytanie powinien doskonale znać każdy developer Javy.

Jak działa HashMapa w Javie?

Żeby odpowiedzieć sensownie na to pytanie, trzeba zacząć od definicji HashMapy.

HashMapa to struktura danych, która pozwala przechowywać dane typu klucz-wartości. W większości przypadków pozwala pobierać i dodawać je w stałym czasie O(1) oraz działa ona na bazie hashowania.

Co to znaczy, że działa na bazie hashowania?

W mapie mamy dostępne metody put() i get(). Gdy wywołujemy metodę put(), musimy podać klucz i wartość. Mapa wywołuje metodę hashcode() na obiekcie klucza, a następnie używa własnej funkcji hashującej, by określić, w którym bucket (kubełku) zostanie umieszczona wartość reprezentowana przez Map.Entry. Co ważne, w Map.Entry mapa przechowuje zarówno klucz jak i wartość.

Gdy próbujemy odczytać z hashmapy wartość, odbywa się podobny process. Wywołujemy metodę get(), podając jako parametr klucz. Hashmapa wywołuje metodę hashcode dla klucza i używa funkcji hashującej, żeby określić, w którym buckecie znajduje się dana wartość. Jeśli odnajduje wartość w tym buckecie, to jest ona zwracana, jeśli nie zwracany jest null.

W tym momencie rekruterzy dopytują zwykle: „Co się dzieje, gdy dwa klucze mają ten sam hascode i czy jest to dopuszczalne?” lub „Co może być kluczem i jakie warunki musi spełniać klucz mapy?”. Oczywiście możesz też sam omówić wszystkie aspekty hashmapy, ale zwykle pojawiają się tego typu dodatkowe pytania.

Kolizje w hashmapie

Z odpowiedzią na pierwsze pytanie wiąże się zagadnienie kolizji w hashmapie i to jak hashmapa sobie z nimi radzi. Także bezpośrednio z tym związane jest to, że klasa klucza musi mieć zaimplementowaną metodę hascode() oraz equals().

W sytuacja, kiedy dla dwóch obiektów klucza przy wywołaniu metody hashcode() zwracana jest ta sama wartość, mamy do czynienia z kolizją. Hashmapa dodatkowo wywołuje dla takich kluczy metodę equals(). Jeśli metoda equals() dla dwóch kluczy zwróci false, to znaczy, że są to dwa różne klucze. Wtedy mapa umieszcza dwie wartości w tym samym buckecie. Kolejne obiekty dla tych samych kluczy są umieszczane w LinkedList, co może prowadzić do degradacji wydajności – dlatego ważne jest, by dobrze zaimplementować metody hashcode() i equals(). Natomiast, jeśli metoda equals() zwróci true, to oznacza, że są to te same klucze i stara wartość jest zastępowana nową.

Skąd możemy mieć taką pewność, że te klucze są takie same?

Wynika to z kontraktu pomiędzy metodami equals() i hashcode().

Kontrakt pomiędzy metodami equals(Object object) i hashcode():

  • Kiedykolwiek metoda hashcode() jest wywołana na tym samym obiekcie więcej niż raz, musi za każdym razem zwrócić tą samą wartość (int) hashcode niezależnie od metody equals(Object).
  • Jeśli dwa obiekty są równe zgodnie z metodą equals(Object), wtedy każde wywołanie metody hashcode() dla tych obiektów musi zwrócić tą samą wartość (hashcode’y są równe).
  • Jeśli dwa obiekty nie są równe zgodnie z metodą equals(Object), nie muszą zwracać różnych hashcodów. Mówiąc inaczej obiekty mogą mieć zgodny hascode i być nie równe zgodnie z metodą equals(Object) (equals zwróci false).

Kontrakt pomiędzy tymi metodami może także występować jako niezależne pytanie rekrutacyjne.

Powyższy kontrakt można znaleźć w oryginalnej formie w źródle klasy Object. Został zamieszczony w formie javadoca do metody hashCode() [Link]

Jak odczytujemy wartości w przypadku kolizji

Dzieje się to w analogiczny sposób, jak w przypadku niewystąpienie kolizji. W tym wypadku, dodatkowo po znalezieniu odpowiedniego bucketa, jest iterowana linked lista i na każdym elemencie (sprawdzany jest klucz w Map.Entry) jest wywoływana metoda equals(). Gdy metoda ta zwróci true, zwracana jest jest wartość.

Klucze HashMap

Kluczem hashmapy może być każdy obiekt, który ma odpowiednio zaimplementowane metody hascode() i equals(). Najlepiej, gdy obiekt klucza jest obiektem niezmiennym (immutable). W przypadku, gdy klucze mapy nie są niezmienne, może to prowadzić do nieprzewidywalnych rezultatów. Wyobraź sobie, że zapisujesz jakiś obiekt pod jakimś kluczem, nadal masz referencję do obiektu tego klucza, po chwili zmieniasz go i zmienia się też jego hashcode. W innym miejscu programu próbujesz pobrać z mapy pożądaną wartość. Już nie masz referencji do obiektu klucza, więc tworzysz go na nowo. I niestety, mapa zwraca Ci null, mimo że wartość, która cię interesuje jest ciągle w mapie (nie wiem, czy to jest do końca dla Ciebie jasne, jeśli nie – daj znać w komentarzu).

Dlatego obiekty takich klas jak String, czy Integer (i inne wrappery prymitywów) są najczęściej wykorzystywanymi kluczami w Hashmapach. Są niezmienne (immutable) i ich klasy są final co znaczy, że nie mogą być rozszerzane (nie można po nich dziedziczyć).

Oczywiście nie ma żadnego problemu, żeby stworzyć swoją własną klasę dla klucza. Wystarczy, że taka klasa będzie miała odpowiednio zaimplementowane metody equals() i hascode() oraz będzie niezmienna (nie jest to konieczne, ale jest to dobrą praktyką).

Poniżej przykładowa implementacja klasy, która może być wykorzystana jako klucz w hashmapie. Pola klasy są inicjalizowane przez konstruktor, nie mogą być w inny sposób zmienione, więc klasa spełnia warunki niezmienności. Zostały także zaimplementowane metody equals() i hascode() (Tutaj implementacja została wygenerowana za pomocą środowiska Intellij Idea):

import java.util.Objects;

public final class MyKey {
    private final String myName;
    private final int myAge;

    public MyKey(String myName, int myAge) {
        this.myName = myName;
        this.myAge = myAge;
    }

    public String getMyName() {
        return myName;
    }

    public int getMyAge() {
        return myAge;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        MyKey myKey = (MyKey) o;
        return myAge == myKey.myAge &&
                Objects.equals(myName, myKey.myName);
    }

    @Override
    public int hashCode() {
        return Objects.hash(myName, myAge);
    }
}

użycie:

Map<MyKey, String> map = new HashMap<>();
map.put(new MyKey("Jan Kowalski", 22), "Jakaś wartość");

 

Optymalizacja w Javie 8

Warto także wspomnieć o jednej optymalizacji, która została wprowadzona w Javie 8 i dotyczy ona kolizji. Normalnie w przypadku kolizji tworzona jest LinkedLista, co w najgorszym przypadku może degradować wydajność pobierania elementów z HashMapy do O(n) (gdzie normalnie jest to O(1)). Żeby poprawić tę sytuację, architekci Javy postanowili zamienić LinkedListę na drzewo binarne. Dzieje się to przy odpowiedniej wielkości listy (TREEIFY_THRESHOLD = 8).  Wtedy wydajność pobierania elementu w najgorszym wypadku będzie O(log n).

 

Podsumowanie

Postanowiłem raz na jakiś czas wrzucać takie opracowanie pytań rekrutacyjnych. Mam nadzieję, że Wam się przyda. Wiem, że jest wiele dostępnych opracowań z pytaniami rekrutacyjnymi, ale często są to tylko podstawowe regułki, które nie zawsze są wystarczające. Poza tym zawsze staram się dokładać 3 grosze od siebie 😉

Źródła:

https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java

 

Mateusz Dąbrowski

Cześć jestem Mateusz, zajmuję się programowaniem już ponad 12 lat z czego ponad 8 programuję w Javie. Zapraszam Cię do lektury mojego bloga. Możesz przeczytać więcej o mnie >>TUTAJ<<

11 thoughts to “Pytania rekrutacyjne – Jak działa HashMapa w Javie?”

  1. Bardzo fajne opracowanie, chyba wyczerpujace temat. Ostatni punkt kontraktu możesz ubrać w inne słowa żeby latwiej było zrozumieć.

    Dzięki za lekcję 🙂

    1. Dzięki za komentarz. Poprawiłem trochę, dodałem też linka do dokumentacji z oryginalnym kontraktem 😉

  2. Cześć. Fajny tekst, jedna rzecz mi tylko przeszkadza. Definicja HashMapy może wprowadzać w błąd. Jak sam podajesz w przypadku kolizji zwiększa się zlożoność z O(1) do max O(log n). Czytając artykuł od początku, po definicji miałem takie „oj oj nie do końca się z nią zgadzam”. Oczywiście dalej tłumaczysz przypadek kolizji, ale może możnaby dodać jakiś mały komentarz w stylu „najczęściej O(1)” albo „w ogólnym przypadku” żeby zasygnalizować wyjątki.
    Pozdrawiam!

    1. Dzięki za komentarz Jedrzej. Ok, poprawiłem trochę definicję. Z samego artykułu wynika, że nie zawsze jest O(1), więc założyłem (błędnie), że dla wszystkich będzie to jasne.

  3. Hej Mateusz! Och, ile razy już słyszałem to pytanie:) Także zgadzam się, że warto jeszcze raz sobie przypomnieć odpowiedź:) Tekst bardzo dobry. IMHO, dobrze byłoby wspomnieć jeszcze o drzewie czerwono-czarnym w optymalizacji JDK8 i dlaczego warto, by obiekty implementowały Comparable (co by rzeczywiście było log(n)). Pozdro!

    1. Dawid, dzięki za komentarz. Masz racje warto o tym wspomnieć. W wolnym czasie zaktualizuję artykuł.

  4. Cześć,

    fajny artykuł w większości wyczerpuję temat.
    „Tutaj implementacja została wygenerowana za pomocą środowiska Intellij Idea”
    Czy nie masz zastrzeżeń do tego kodu?
    Czy pola myAge, myName nie mogłyby być final? Czy klasa musi być publiczna?

    Dodam, że jak ktoś stosuje lomboka to jest tam adnotacja @EqualsAndHashCode
    która wygeneruje taki kod:

    public boolean equals(final Object o) {
            if (o == this) return true;
            if (!(o instanceof MyKey)) return false;
            final MyKey other = (MyKey) o;
            final Object this$myName = this.getMyName();
            final Object other$myName = other.getMyName();
            if (this$myName == null ? other$myName != null : !this$myName.equals(other$myName)) return false;
            if (this.getMyAge() != other.getMyAge()) return false;
            return true;
        }
    
        public int hashCode() {
            final int PRIME = 59;
            int result = 1;
            final Object $myName = this.getMyName();
            result = result * PRIME + ($myName == null ? 43 : $myName.hashCode());
            result = result * PRIME + this.getMyAge();
            return result;
        }
    

    Być może przydałoby się zastanowić jakie są korzyści ze stosowania lomboka zamiast tamtego kodu? Czym te fragmenty kody się różnią? Taki pomysł – być może na Twój następny artykuł ?

    1. Dzięki za komentarz Kamil. Oczywiście można mieć zastrzeżenia co do wygenerowanego kodu. Idea daje kilka możliwości jego generacji i żadna nie jest idealna. Ale tak to już jest z generowanym kodem, że generujesz by zaoszczędzić czas. I oczywiście można go poprawiać, ale wtedy trochę przestaje mieć sens jego generacja. Wszystko zależy od ciebie. Jak ci się nie podoba (albo w twoim zespole nie jest akceptowalny taki kod), to możesz pisać ręcznie. Wiele razy właśnie tak musiałem robić.

      „Czy pola myAge, myName nie mogłyby być final? Czy klasa musi być publiczna?”
      Tak mogłyby być, a nawet powinny.

      Co do Lomboka to napisałem kiedyś art. Lombok dobre i słabe strony
      Tak @EqualsAndHashCode generuje taki kod, ale go nie widać, więc oczy nie bolą. W tym przykładzie wygenerowałem kod z Ideii, tak by to było zrozumiałe dla wszystkich.

Komentarze są zamknięte.