Czy możesz wyjaśnić wewnętrzną strukturę i mechanizm działania tablicy haszującej w Java?

Tablica haszowa w Java (np. HashMap) to struktura danych, która przechowuje pary klucz-wartość i zapewnia szybki dostęp po kluczu.

Struktura wewnętrzna:

• Podstawą jest tablica kubełków (koszyków).
• Każdy kubełek zawiera albo null, albo powiązaną listę (lub drzewo, jeśli jest dużo elementów) elementów z tym samym kodem hash modulo rozmiaru tablicy.

Mechanizm działania:

1. Przy dodawaniu elementu oblicza się kod hash klucza i na jego podstawie określa indeks kubełka.
2. Jeśli kubełek jest pusty, element jest tam umieszczany.
3. Jeśli kubełek jest zajęty, przeszukuje się powiązaną listę (lub drzewo) w celu sprawdzenia, czy klucz już istnieje:
   • Jeśli klucz zostanie znaleziony, wartość jest aktualizowana.
   • Jeśli nie, element jest dodawany do listy.
4. Po osiągnięciu określonego progu wypełnienia, następuje rozszerzenie tablicy (rehash), aby utrzymać wydajność.

Takie podejście zapewnia średnią złożoność operacji wstawiania, wyszukiwania i usuwania bliską O(1).

Przykład użycia:

Map<String, Integer> map = new HashMap<>();
map.put("key1", 100);
Integer value = map.get("key1"); // szybki dostęp po kluczu