Czy możesz wyjaśnić wewnętrzną strukturę i działanie HashMap w języku Java?

HashMap w Java to struktura danych do przechowywania par klucz-wartość z szybkim dostępem po kluczu.

Wewnętrzna struktura:

• HashMap używa tablicy kubełków (bucket array).
• Dla klucza obliczany jest kod hash (hashCode), który następnie jest przekształcany na indeks tablicy.
• W każdym kubełku przechowywane są elementy z tym samym indeksem, zazwyczaj w postaci listy powiązanej lub drzewa (w Java 8, przy dużej liczbie kolizji).

Działanie:

• Przy wstawianiu obiektu obliczany jest indeks na podstawie hasha klucza.
• Jeśli kubełek jest pusty, element jest tam umieszczany.
• Jeśli kubełek jest zajęty, sprawdzana jest równość kluczy (equals), aby zaktualizować wartość lub dodać nowy element.
• Przy wyszukiwaniu po kluczu również oblicza się indeks, a następnie przeszukuje elementy w kubełku w celu znalezienia dopasowania.

Przykład:

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 5);
int value = map.get("apple"); // 5

W ten sposób HashMap zapewnia amortyzowany czas dostępu O(1), ale przy dużej liczbie kolizji może się degradować do O(n).