Puteți explica structura internă și mecanismul de funcționare al tabelului hash în Java?

O tabelă hash în Java (de exemplu, HashMap) este o structură de date care stochează perechi cheie-valoare și asigură acces rapid pe baza cheii.

Structura internă:

• Baza este un array de coșuri (găleți).
• Fiecare găleată conține fie null, fie o listă legată (sau un copac, dacă sunt multe elemente) de elemente cu același cod hash modulo dimensiunea array-ului.

Mecanismul de funcționare:

1. La adăugarea unui element, se calculează codul hash al cheii și se determină indexul găleții.
2. Dacă găleata este goală, elementul se plasează acolo.
3. Dacă găleata este ocupată, se caută în lista legată (sau copac) dacă cheia există deja:
   • Dacă cheia este găsită, valoarea se actualizează.
   • Dacă nu, elementul se adaugă la listă.
4. Când se atinge un anumit prag de umplere, se extinde array-ul (rehash) pentru a menține performanța.

Această abordare asigură o complexitate medie a operațiilor de inserare, căutare și ștergere apropiată de O(1).

Exemplu de utilizare:

Map<String, Integer> map = new HashMap<>();
map.put("key1", 100);
Integer value = map.get("key1"); // acces rapid după cheie