Puteți explica structura internă și modul de funcționare al HashMap în limbajul Java?

HashMap în Java este o structură de date pentru stocarea perechilor cheie-valoare cu acces rapid pe baza cheii.

Structura internă:

• HashMap utilizează un array de containere (bucket array).
• Pentru cheie, se calculează un cod hash (hashCode), care apoi este transformat într-un index al array-ului.
• În fiecare container, se stochează elemente cu același index, de obicei sub formă de listă înlănțuită sau arbore (cu Java 8, dacă există multe coliziuni).

Funcționare:

• La inserarea unui obiect, se calculează indexul pe baza hash-ului cheii.
• Dacă containerul este gol, elementul este plasat acolo.
• Dacă containerul este ocupat, se verifică egalitatea cheilor (equals) pentru a actualiza valoarea sau a adăuga un element nou.
• La căutarea după cheie, se calculează de asemenea indexul și se parcurg elementele din container pentru a găsi potrivirea.

Exemplu:

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

Astfel, HashMap asigură un timp de acces amortizat O(1), dar în cazul multor coliziuni, poate degrada la O(n).