Cum este structurată și organizată structura de date…

HashMap în Java se bazează pe principiile de hashing. Stochează perechi de "cheie-valoare".

Structura internă:

Array de bucket-uri (containere). Fiecare bucket este o listă înlănțuită (sau un copac, începând cu Java 8, când există multe coliziuni).
La adăugarea unui element (put):
1. Se calculează codul hash al cheii (key.hashCode()).
2. Codul hash este modificat pentru o distribuție mai bună (hash).
3. Folosind hash-ul modificat și dimensiunea array-ului de bucket-uri, se calculează indexul bucket-ului (hash & (dimensiune_array - 1)).
4. Elementul (perechea "cheie-valoare" ca obiect Node) este plasat în acel bucket. Dacă bucket-ul conține deja elemente, elementul nou se adaugă la începutul listei înlănțuite sau al copacului.
5. La adăugare, se verifică dacă cheia există deja: se folosește metoda equals() pentru compararea cheilor din interiorul bucket-ului. Dacă cheia este găsită, valoarea se actualizează.
La obținerea unui element (get):
1. Se calculează și indexul bucket-ului pe baza cheii.
2. În interiorul bucket-ului, se caută elementul după cheie, folosind metodele hashCode() și equals().
3. Se returnează valoarea asociată.

Organizare:

Coliziuni: Dacă mai multe chei au același cod hash și cad în același bucket, elementele sunt stocate sub formă de listă înlănțuită. Începând cu Java 8, când numărul de elemente dintr-un bucket depășește un prag (de obicei 8), lista înlănțuită se transformă într-un copac pentru căutări mai rapide (O(log n) în loc de O(n)).
Redimensionare: Când numărul de elemente depășește "factorul de încărcare" (load factor * capacity), HashMap mărește dimensiunea array-ului intern de bucket-uri (de obicei dublând) și recalculază toate hash-urile. Este o operație costisitoare (O(n)).
Parametri:
- capacity: dimensiunea inițială a array-ului de bucket-uri (implicit 16).
- load factor: pragul de încărcare (implicit 0.75). Determină când are loc redimensionarea.

De ce hashCode() și equals() sunt importante:

Funcționarea corectă a HashMap depinde de implementarea corectă a acestor metode.
Dacă equals() returnează true pentru două obiecte, atunci hashCode() trebuie să returneze aceeași valoare.
O implementare greșită poate duce la faptul că elementele nu vor fi găsite (get va returna null), chiar dacă au fost adăugate.

Exemplu de structură Node:

// Doar intern
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

HashMap asigură inserarea, obținerea și ștergerea rapidă (în medie O(1)) a elementelor, atunci când distribuția hash-urilor este uniformă. În cel mai rău caz (coliziuni puternice), operația poate deveni O(n) sau O(log n) cu arbori.

Nu este sigur pentru fire de execuție. Pentru utilizare în medii concurente, se recomandă ConcurrentHashMap sau Collections.synchronizedMap(new HashMap<...>(...)).

Cum este structurată și organizată structura de date HashMap în Java?