Java HashMap

Co to jest Hashmap w Javie?

HashMap Java jest częścią frameworka kolekcji Java i implementuje interfejs Map, zapewniając strukturę danych, która umożliwia przechowywanie par klucz-wartość. Jest to kluczowy komponent, którego programiści używają do wydajnego przechowywania, pobierania i manipulowania danymi.

HashMap działa na zasadzie haszowania. Hashowanie polega na pobraniu danych wejściowych lub “wiadomości” i zwróceniu ciągu bajtów o stałym rozmiarze, zazwyczaj w postaci kodu skrótu. Ten kod skrótu jest następnie używany jako indeks, w którym odpowiednia wartość jest przechowywana w tablicy. Gdy wartość musi zostać pobrana, klucz jest ponownie hashowany w celu wygenerowania kodu hash, który może być następnie użyty do przeszukania tablicy w celu znalezienia odpowiedniej wartości.

Każdy wpis w HashMap jest w rzeczywistości obiektem prostej klasy “Map.Entry“, która zawiera parę klucz-wartość. Klucze są unikalne, a mapa przechowuje tylko jedną wartość dla każdego klucza. Oznacza to, że dodanie elementu z kluczem, który już istnieje w mapie, spowoduje, że nowa wartość zastąpi starą.

HashMap używa tablicy i struktury danych LinkedList do przechowywania klucza i wartości. Każda para klucz-wartość jest przechowywana w lokalizacji “bucket” w podstawowej tablicy. W przypadku kolizji (gdy dwa różne klucze mają ten sam kod skrótu), te pary klucz-wartość są przechowywane jako węzeł w LinkedList w tej lokalizacji wiadra. Każdy węzeł przechowuje swój kod skrótu, klucz, wartość i wskaźnik do następnego węzła.

Podczas pobierania wartości na podstawie klucza, HashMap oblicza kod skrótu klucza i używa go do znalezienia lokalizacji kubełka, w którym jest przechowywany. Jeśli wiele kluczy zostało zaszyfrowanych w tym samym kubełku (sytuacja znana jako “kolizja”), HashMap używa metody equals(), aby upewnić się, że znalazł właściwy klucz.

Podsumowując, HashMap w Javie zapewnia wydajne rozwiązanie struktury danych do przechowywania par klucz-wartość. Efektywność wynika z użycia haszowania do konwersji kluczy na indeksy tablicowe, co pozwala na stałą wydajność operacji get() i put() w idealnych warunkach. Jeśli jednak zbyt wiele elementów znajdzie się w tym samym kubełku, wydajność może spaść do O(n), gdzie n to liczba elementów w kubełku, ponieważ trzeba przejść przez każdy węzeł, aby znaleźć żądaną wartość.