Oprócz oczywistej wartości praktycznej, znajomość odpowiedzi na to pytanie często przydaje się na rozmowach rekrutacyjnych na Java Developera. Jak działa HashMap w Java? Aby w pełni odpowiedzieć na to pytanie, omówmy sobie HashMap na trzech „poziomach wtajemniczenia”. Najczęściej poziom pierwszy będzie wystarczył do „zaliczenia” rozmowy na poziomie juniora natomiast poziomy drugi i trzeci to już raczej poziom regular (i może jakaś rozgrzewka dla seniora).
Poziom 1 – główne założenia HashMap
Wkraczamy w pierwszy poziom wtajemniczenia, co to jest ogólnie HashMap? W skrócie jest to kolekcja, do której wkładamy pary klucz-wartość, a potem, mając klucz, możemy wyjąć konkretną wartość.
Jak działa insert do HashMap
Kiedy „wkładamy” do HashMap parę klucz-wartość metodą put(), para jest dodawana do kolekcji. Jeżeli dodamy inną wartość z identycznym kluczem, nadpisze ona wartość poprzednią. Natomiast jeśli dodamy parę z kluczem null – para również zostanie dodana. Oczywiście, możemy ją potem „wyjąć” podając jako klucz null. HashMap nie zachowuje jednak kolejności dodawanych par.
Jak działa szukanie w HashMap
Gdy chcemy wyciągnąć jakąś wartość z HashMap, używamy metody get(). Mapa porównuje wartość klucza z już posiadanymi kluczami, i w zależności, czy znajdzie, zwraca wartość lub null. Więc jak mapa określa, czy klucze są równe? No właśnie – używając metod hashCode() i equals().
Bardzo podobny zestaw czynności wystąpi przy każdej metodzie wymagającej wyszukania elementu, jak remove() czy containsKey().
Poziom 2 – wewnętrzne mechanizmy i Big O notation
Schodzimy poziom niżej, zobaczmy więc jak HashMap w Java zachowuje się „pod maską”. Otóż pary klucz-wartość mapa przechowuje razem, w obiekcie Node<K, V>, który implementuje interfejs Map.Entry<K, V>. Obiekty te są zorientowane w kolekcję, która odpowiada jednokierunkowej LinkedList – każde Entry ma referencję do następnego.
Insert pod maską i buckety
HashMap to tak naprawdę tablica java o stałej długości składająca się umownie z tzw. bucketów. Każdy bucket to właśnie LinkedList złożony z obiektów Entry. Gdy wywołujemy metodę put() na mapie, HashMap z tablicą o długości n w pierwszej kolejności wylicza indeks bucketu, do którego trafi nowe Entry. A robi to, używając bitowej operacji AND na hashu klucza.
index = key.hashCode() & (n - 1)
Gdy już określi index bucketu, dodaje do niego parę. Warto tutaj zauważyć, że jeśli w buckecie już coś jest, mapa będzie porównywać metodą equals() klucze, które już buckecie są, z nowym kluczem. Jeśli któryś z nich okaże się równy to zamiast dodawać nową parę, podmieni wartość w tej z identycznym kluczem. Natomiast jeśli klucz jest null – cały algorytm przebiega tak samo, tyle że wartość trafia zawsze do bucketu z indeksem 0.
Złożoność dodawania nowej pary do HashMap jest taka sama, jak do LinkedList, czyli O(1).
Lookup pod maską – uważaj na hashCode() i equals()
Gdy wywołujemy metodę wymagającą wyszukania po kluczu, HashMap wykonuje to samo wyliczenie, co przy put(), obliczając indeks bucketu odpowiadającego kluczowi. Jeśli jest tam tylko jedno Entry – nie ma problemu, mapa od razu zwraca wartość. Jednak jeśli będzie tam więcej obiektów, mapa porówna klucz z każdym w buckecie operacją equals(). Dopiero, jeśli dla któregoś z nich equals() zwróci true, mapa zwróci odpowiadającą mu wartość.
Złożoność wyciągania obiektów z HashMap to również 0(1). Załóżmy jednak, że źle zdefiniowaliśmy metodę hashCode(). Na przykład, jakiś niedoświadczony developer uznał że może tam zawsze zwracać taką samą wartość. Wtedy złożoność szukania osiągniemy taką samą, jak w LinkedList – O(n). A to dlatego, że wszystkie Entry będą trafiać do jednego bucketu.
Synchronizacja
HashMapa nie jest bezpieczna dla równoległego przetwarzania przez wiele wątków – używając jej, musimy więc zapewnić synchronizację jakimś innym mechanizmem. Alternatywnie możemy użyć ConcurrentHashMap. Więcej o użyciu kolekcji w środowisku wielowątkowym możesz poczytać tutaj
Poziom 3 – optymalizacja
Gdyby HashMap utworzone z ośmioma bucketami miało ich już na zawsze 8, to w miarę dodawania kolejnych obiektów złożoność szukania w niej dążyłaby szybko do O(n). Dlatego aby pozostać przy pożądanym O(1) potrzebujemy pewnych optymalizacji.
Pojemność
Startową liczbę bucketów możemy określić, kiedy tworzymy HashMap – parametrem initialCapacity. Jeśli go nie podamy, otrzyma on domyślna wartość, czyli 16. Możemy też zdefiniować dodatkowy parametr loadFactor typu float w zakresie od 0 do 1. Parametr ten odpowiada za moment, w którym mapa podwoi liczbę swoich bucketów, wywołująć metodę resize(). Dokładniej, mając loadFactor równy 0.75 (wartość domyślna), HashMap wywoła resize() w momencie, gdy ponad 75% bucketów będzie miała co najmniej jedno Entry. Podczas powiększania jest tworzona nowa tablica bucketów, dwukrotnie większa, a indeks dla każdego Entry jest wyliczany ponownie.
Złożoność operacji dodawania, przy której HashMap będzie się powiększać, to już nie O(1), a O(n). Dlatego, jeśli znamy przybliżoną liczbę obiektów, jakie będziemy obsługiwać – warto od razu zainicjalizować większą mapę.
treeify/untreeify
Jest jeszcze jedna optymalizacja działania HashMap w Java – jeśli dany bucket „urośnie” i będzie miał 8 Entry – zostaje na nim wywołana metoda treeifyBin() i wszystkie instancje Node<K, V> w tym buckecie zostaną zamienione na TreeNode<K, V>, efektywnie tworząc drzewo binarne. Dodatkowym warunkiem, jaki musi być spełniony jest osiągnięcie liczby bucketów większej od 64. Jeśli jest ich mniej, mapa wywołuje metodę resize(). Natomiast jeśli liczba Entry w buckecie zmniejszy się do 6 – zostanie wywołana metoda untreeify() i bucket znowu będzie listą.
Optymalizacja ta ma konkretną korzyść – złożoność wyszukiwania elementów w danym buckecie z O(n) zmienia się na O(log(n)), jeśli ma on wiele elementów.
Podsumowanie
Mam nadzieję, że we w miarę przystępny sposób przybliżyłem zasadę działania HashMap w Java. Prawdopodobnie z wiedzą z tego artykułu nawet pytania najdociekliwszego rekrutera nie powinny stanowić problemu. 🙂
