Co powinieneś wiedzieć o HashMap

Ten kto programuje już jakiś czas wie, iż HashMapa to kolekcja danych przechowująca unikalny zestaw kluczy pod które podpięta jest jakaś wartość. Struktura ta pozwala na dodanie jednego klucza nullowego oraz wiele takich wartości. Kilka osób doda, iż aby HashMapa działała prawidłowo, w kluczu powinien być poprawnie spełniony kontrakt hash code and equals. Na początku swojej przygody z programowaniem przez długi czas też tak myślałem, wtedy w zupełności wystarczało to do pracy jako programista. Aż pewnego dnia na rozmowie kwalifikacyjnej zapytano mnie jak działa HashMap? Co dzieje się pod spodem gdy wkładamy lub pobieramy elementy? Odpowiedziałem dokładnie tak jak to opisałem powyżej. Poczułem jednak, iż moją wypowiedź mógłbym rozwinąć, iż nie wszystko przedstawiłem, iż rekrutrer liczył na rozwinięcie tematu, zahaczenie o implementację jak i mechanizmy, które w niej zachodzą.

Od tamtej pory zacząłem się zastanawiać co mogłem powiedzieć inaczej lub lepiej, może czegoś nie wiedziałem? Zacząłem grzebać w różnych źródłach jak i kodzie źródłowym implementacji HashMap. Dzisiaj chciałbym wam przybliżyć czego się dowiedziałem. Jak wyczerpać temat do końca na rozmowie rekrutacyjnej? Jakie interesujące mechanizmy stosuje jedna z implementacji Mapy w Javie, mianowicie HashMapa?

A więc jak działa Hash Mapa w Javie ?

HashMapa swoje działanie opiera na tablicy obiektów klasy statycznej HashMap.Node ,która implementuje interfejs Map.ENTRY oraz mechanizmie haszowania klucza wykorzystywanego do odnajdywania indeksu tablicy. Dzięki temu rozwiązaniu zapewnione jest przechowywanie i wyciąganie obiektów (jeśli znamy klucz) ze złożonością O(1). Wizualizacja HashMap wyglądała następująco:

Hash – liczba całkowita, obliczona w prosty sposób w momencie dodawania elementu do mapy dzięki metody HashMap.hash(key), metoda ta oblicza hash(ang skrót) obiektu i przyporządkowuje mu, krótką deterministyczną wartość posiadającą zawsze stały rozmiar, tzw. skrót nieodwracalny. W tej konkretnej implementacji wykorzystywane jest do tego logiczne przesunięcie bitowe w prawo. Dla osób zainteresowanych szczegółami na koniec artykułu postaram się dokładnie wyjaśnić jak przebiega ten proces.

key – Obiekt (Implementacja pozwala na przechowywanie jednego klucza nullowego) dobrymi kandydatami na klucze na pewno będą obiekty niezmienne, spełniające kontrakt hashCode i equal . w uproszczeniu jeżeli dwa różne obiekty zwrócą ten sam HashCode to obiekty te mogą być równoznaczne, wtedy equals może zwrócić true lub false. o ile jednak HashCode obydwu obiektów jest różny, wtedy equals zawsze zwróci false. Dobrymi kandydatami na klucze są String, Integer oraz inne Wrappery typów prymitywnych. String jest prawdopodobnie najczęściej używanym typem klucza w mapie, dlatego iż jest niezmienny i ma poprawnie zaimplementowane metody equals i hashCode oraz jest czytelny. Niezmienność obiektów jest kluczowa aby zapobiec zmianie pól używanych do obliczania hashCode w trakcie trwania programu, ponieważ kody wyliczane są podczas wkładania i pobierania elementów z mapy. jeżeli pomiędzy tymi operacjami pola w kluczu się zmienią nie będziemy w stanie znaleźć żądanego obiektu, gdyż hashCode wyliczone przed i i po będą się różnić.

value – dowolny obiekt lub null

next – referencja na następny node (wyjaśnię to pole w dalszej części artykułu przy omawianiu kolizji)

Tworzenie HashMapy i optymalizacja w różnych wersjach Javy

Na początek warto wspomnieć o tym, iż wielkość wewnętrznej tablicy jest zawsze potęgą dwójki (jeśli w konstruktorze podamy np.. Liczbę 18 wewnętrzna tablica za alokuje pamięć na 32 elementy ponieważ jest to najbliższa potęga dwójki większa od podanej liczby 18), dzięki temu HashMapa jest w stanie zapewnić nam złożoność na poziomie O(1).

Warto też zauważyć iż niektóre zmienne w klasie HashMap ustawiane są defaultowo np.:

DEFAULT_INITIAL_CAPACITY – jest to początkowa wielkość naszej wewnętrznej tablicy ustawione na 16 elementów, co ważne jest to potęga dwójki , jeżeli przy tworzeniu mapy podamy wielkość w konstruktorze wartość ta jest pomijana.

DEFAULT_LOAD_FACTOR – współczynnik obciążenia ustawiony na poziomie 0.75 jest to dozwolony procent załadowania elementami naszej mapy.

Int threshold – zmienna wyliczana z dwóch powyższych wartości oznacza próg ilości elementów w mapie po przekroczeniu którego zostanie ona rozszerzona.

We wcześniejszych wersjach Javy przed wersja 1.7 przy tworzeniu pustej mapy bez podania jej wielkości automatycznie pod spodem alokowała się tablica o wielkości 16 elementów

W Javie w wersji 1.7 oraz 1.8 zostało to zoptymalizowane aby ją przyspieszyć i zredukować zajmowaną pamięć, wprowadzono tzw. lazy initialization, oznacza to, iż przy tworzeniu mapy nie alokujemy tak jak wcześniej 16 elementowej tablicy, zamiast tego tablica tworzona jest dopiero przy wykonaniu metody Put . Widocznie zrozumiano iż często mapy są tymczasowe i nie potrzebują tak wielkiej wewnętrznej struktury inicjalizowanej od razu po stworzeniu, która marnuje pamięć.

Powyższy kod dobrze obrazuje czemu komentarze w kodzie są słabe. 🙂 Zmieniając implementację HashMapy zmieniono działanie konstruktora ale nie zaktualizowano komentarza.

Dodawanie elementów do mapy metoda put(key,value)

Dodawanie elementów do mapy odbywa się dzięki metody put, przyjmuje ona dwa parametry klucz i wartość. Podczas wykonywania tej operacji, jeżeli wersja używanej javy jest wyższa niż 1.6 sprawdzany jest aktualny rozmiar tablicy. jeżeli nie została ona stworzona wcześniej, wówczas wykorzystywany zostaje Lazy Loading, o którym wspominałem kilka akapitów wyżej. Następstwem tego jest stworzenie tablicy o defaultowym rozmiarze i obliczenie rozmiaru threshold. Po sprawdzeniu i ewentualnym stworzeniu tablicy, obliczony zostaje Hash podanego klucza wykorzystany do znalezienia miejsca w tablicy aby zapisać obiekt Entry zawierający hash, klucz i wartość.

Wyliczanie indexu w tablicy

Jak już wspominałem wcześniej HashMapa dba o to aby rozmiar wewnętrznej tablicy był potęgą dwójki. Dzieje się tak, ponieważ wielkość ta wykorzystywana jest wraz z wartością hash do wyznaczania indexu dla dodawanych obiektów Entry. Aby indeks nie wychodził poza zakres tablicy nie możemy użyć bezpośrednio wartości Hash, zamiast tego wykonywane jest dzielenie modulo, którego wynik zawsze będzie mieścił się w podanym zakresie n( rozmiar tablicy) wzór tab[i=hash % n]. Jednak taki zabieg jest zasobożerny, dlatego wymuszono rozmiar tablicy odpowiadający wielkości potęgi dwójki, aby można było zastosować szybsze dzielenie modulo binarne. Jest to bardziej optymalne rozwiązanie. Wzór wygląda następująco tab[i=(n-1)&hash]. Liczby zamienione są na postać binarną po czym zastosowany jest operator AND wynik operacji to dziesiętna reprezentacja indexu w tablicy, przykład poniżej powinien rozwiać wątpliwości:

hash = 123 n = 16 hash % n = 123 % 16 = 11 (modulo) (n - 1) & hash = 15 & 123 = 11 (modulo binarne) ‭1 1 1 1‬ (15)‬ &(AND) ‭ 0 1 1 1 1 0 1 1‬ (123) (przykład operacji modulo binarne) = 1 0 1 1 (11)

Dzięki takiemu zabiegowi index wyliczany jest gwałtownie i nie wychodzi poza rozmiar tablicy a także wstawianie i wyciąganie elementów odbywa się ze złożonością O(1). Nie jest to jednak idealne rozwiązanie i czasami powoduje kolizje.

Kolizje obiektów o tej samej wartości Hash

Wyliczanie indeksów opierając się na metodzie hashCode danego klucza nie jest idealnym rozwiązaniem, czasami powoduje kolizje kluczy . Dzieje się tak gdy hash dodawanego obiektu jest taki sam jak hash już istniejącego obiektu w tablicy. Prowadzi to do kolizji, która w zależności od sytuacji może być obsłużona na 2 sposoby:

1. W tablicy przechowywany jest obiekt Entry zawierający hash, klucz i wartość. jeżeli klucz przekazany do metody put jest równy kluczowi przechowywanemu w obiekcie Entry, pod indexem wyliczonym dzięki metody hash, wtedy wiemy, iż klucz jest taki sam i wartość zostaje podmieniana na nową.
2. Jeżeli jednak klucze mają taki sam Hash ale metoda equals zwraca false, oznacza to iż te dwa klucze różnią się od siebie co za tym idzie wstawiany obiekt musi znaleźć się w podanym indeksie w tablicy, bez nadpisywania już istniejącego. Z pomocą przychodzi zmienna next, gdy wystąpi kolizja kluczy, wewnątrz tablicy o wyliczonym indeksie obiekt Entry traktowany jest jako lista, a nowy obiekt dodawany jest w miejsce next !
   
   Jako iż jest to lista obiektów, w najgorszym przypadku złożoność wyszukiwania wynosi O(n). Zostało to zoptymalizowane w wersji javy 1.8. Kiedy rozmiar listy przekroczy określony threshold, dokonywana jest zamiana listy na drzewo binarne, dzięki czemu wyszukiwanie w wyżej podanym przypadku ma złożoność na poziomie O(log N ). Threshold – określa ilość elementów po której przekroczeniu lista zostaje przetransformowana w drzewo binarne, jest ustawiony w stałej o nazwie. TREEIFY_THRESHOLD aktualnie wartość ta wynosi 8, co oznacza iż po przekroczeniu tej ilości elementów zamiast listy do przechowywania elementów zostanie użyte zrównoważone drzewo binarne o złożoności O(log N ) .

Wyciąganie obiektów z Mapy metoda get(key)

W przeciwieństwie do metody put( klucz , wartość ) metoda get jest dużo prostsza i łatwiejsza w wyjaśnieniu. W momencie wywołania tej metody na obiekcie kluczu wykonana zostaje metoda hashCode(), która jak sama nazwa wskazuje zwraca HashCode obiektu. Index tablicy obliczany jest dzięki binarnego dzielenia modulo tak jak w przypadku metody put, dlatego obliczony hashcode klucza przekazywany jest do funkcji HashMap.hash. Ponieważ Hashcode dla różnych obiektów może zwracać tą samą wartość funkcja hash zapewnia większą unikalność poprzez zastosowanie przesunięcia bitowego w prawo na wartości hashcode (funkcja hash dodatkowo ignoruje znak liczby ujemnej i traktuje ją jak dodatnią) , aczkolwiek nie eliminuje to kolizji w 100 procentach. Wynik przeprowadzonych działań wskazuje na indeks tablicy pod którym należy szukać wartości dla podanego klucza.

Teraz nie pozostaje nic innego jak sięgnąć pod podany indeks tablicy i spróbować wyciągnąć wartość powiązaną z przekazywanym kluczem. O ile w tablicy nie jest przechowywana lista/drzewo obiektów, metoda kończy swoje działanie i zwraca wartość dla podanego klucza.
Aktualizacja: przy wyciąganiu elementu sprawdzana jest referencja klucza w wyliczonym indeksie i referencja przekazywanego klucza gdy się nie zgadzają wykonywana jest metoda equals żeby sprawdzić czy to te same klucze.

Ale co w przypadku jeżeli w tablicy znajduje się lista obiektów Entry ? Skąd wiemy która wartość pasuje do klucza skoro tylko hash wskazuje nam szukany obiekt a wszystkie wartości hash obiektów w liście są równe wyliczonej wartości? Tutaj warto pamiętać o tym, iż Obiekty Entry przechowują zarówno hash, klucz, wartość oraz wskazanie na następny element o ile istnieje.

W wyżej podanym przypadku przechodzimy po kolei po liście elementów i dla wszystkich obiektu oprócz porównywania Hash klucza porównywany zostaje też klucz dzięki metody equals , jeżeli hash wyliczony w metodzie get i klucz przekazany do tej metody zgadzają się z tymi samymi wartościami w iterowanym aktualnie obiekcie, iteracja zostaje przerwana i wartość jest zwracana.

Dlatego ważne jest aby obiekt klucz w mapie był Immutable i nie zmieniał swoich pól pomiędzy wywołaniem metody put oraz get.

Dynamiczne powiększanie HashMapy oraz Race Condition

Co dzieje się z naszą mapą, jeżeli przekroczymy próg elementów zdefiniowany przez zmienną Int threshold?

W takim przypadku tworzona jest nowa mapa o rozmiarze dwa razy większym niż poprzednia. Elementy ze starej mapy zostają przepisane do nowej z przeliczeniem indeksów wykorzystując do tego hash zapisany w obiekcie i nowy rozmiar tablicy tab[i=(n-1)&hash].

Teoretycznie wydaje się to dobrym rozwiązaniem, ale jeżeli odbywa się to w środowisku wielowątkowym operacja ta narażona jest na poważne konsekwencje potencjalnego race condition tzw. wyścigu wątków. Występuje on np. w sytuacji kiedy dwa wątki w tym samym czasie zorientują się iż mapa osiągnęła swój threshold i należy ją rozszerzyć. Każdy z wątków tworzy nową tablicę dwa razy większą od pierwotnej i zaczyna alokować zawartość starej tablicy w dopiero co utworzonej. Następstwem tych działań mogą być utracone dane. W starszych wersjach Javy przy rozszerzaniu tablicy przez 2 wątki jeden z nich mógł wpaść w pętlę nieskończoną. Dla osób które chcą bardziej zgłębić temat pętli nieskończonej, obszerniej jest to opisane pod tym linkiem

Innym przykładem jest dodawanie przez 2 wątki po 1000 elementów każdy, do mapy. Wielkość mapy przy każdym odpaleniu programu może się różnić, elementy mogą zostać zgubione.

Generalnie korzystanie z HashMap nie jest dobrym pomysłem jeżeli chodzi o środowisko wielowątkowe. Dużo lepszym rozwiązaniem jest użycie implementacji ConcurrentHashMap, która jest bezpieczna wielowątkowo. Różnice pomiędzy obiema implementacjami opisze w przyszłości w osobnym poście.

Podsumowując

Stopień skomplikowania i ilość operacji zaszytych w Implementacji HashMap czyni ją idealnym pytaniem podczas rozmowy rekrutacyjnej na stanowisko mid lub senior. Przy pytaniach o kolekcje prawie zawsze pada pytanie odnośnie działania HashMapy, aby zobaczyć czy osoba zna podstawy jej działania, a także bardziej złożone aspekty tej implementacji. Sądzę, iż napisany artykuł dość mocno wyczerpał temat działania HashMapy. A wy co myślicie ? Może warto by było coś dodać lub macie jakieś pytania? Chętnie odpowiem na wszystkie wątpliwości w komentarzach pod artykułem. 🙂