Kako je strukturirana i organizovana struktura…

HashMap u Javi se zasniva na principima haširanja. Čuva parove "ključ-vrednost".

Unutrašnja struktura:

Niz koševa (kontejnera). Svaki koš je povezani spisak (ili drvo, od Java 8, kada je mnogo kolizija).
Prilikom dodavanja elementa (put):
1. Izračunava se hash kod ključa (key.hashCode()).
2. Hash kod se modifikuje za bolju raspodelu (hash).
3. Koristeći modifikovani hash i veličinu niza, računa se indeks koša (hash & (array_size - 1)).
4. Element (par "ključ-vrednost" kao objekat Node) se smešta u taj koš. Ako koš već sadrži elemente, novi element se dodaje na početak povezane liste ili stabla.
5. Pri dodavanju se proverava postojanje ključa: koristi se metoda equals() za poređenje ključeva u košu. Ako je ključ pronađen, vrednost se ažurira.
Pri dobijanju elementa (get):
1. Indeks koša se računa po ključu.
2. U košu se traži element po ključu koristeći metode hashCode() i equals().
3. Vraća se povezana vrednost.

Organizacija:

Kolizije: Ako više ključeva ima isti hash kod i padaju u isti koš, elementi se čuvaju kao povezani spisak. Od Java 8, ako broj elemenata u košu pređe prag (obično 8), povezani spisak se pretvara u stablo radi bržeg pretraživanja (O(log n) umesto O(n)).
Promena veličine: Kada broj elemenata pređe "prag opterećenja" (load factor * capacity), HashMap povećava veličinu unutrašnjeg niza (obično duplira) i ponovo hašira sve elemente. Ovo je skupa operacija (O(n)).
Parametri:
- capacity: Početna veličina niza (podrazumevano 16).
- load factor: Prag opterećenja (podrazumevano 0.75). Određuje kada će doći do promene veličine.

Zašto su hashCode() i equals() važni:

Ispravno funkcionisanje HashMap zavisi od ispravne implementacije ovih metoda.
Ako equals() vraća true za dva objekta, hashCode() mora vraćati istu vrednost.
Neispravna implementacija može dovesti do toga da elementi nisu pronađeni (get će vratiti null), čak i ako su dodani.

Primer strukture Node:

// Samo za unutrašnju upotrebu
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 obezbeđuje brzo (prosečno O(1)) dodavanje, dobijanje i brisanje elemenata uz ravnomerno raspoređivanje haševa. U najgorem slučaju (jake kolizije), operacija može biti O(n) ili O(log n) sa stablima.

Kako je strukturirana i organizovana struktura podataka HashMap u Javi?