Ako je štruktúrovaná a organizovaná dátová štruktúra…

HashMap v Jave je založen na princípoch hašovania. Ukladá páry "kľúč-hodnota".

Vnútorná štruktúra:

Poľo košov (kontajnerov). Každý koš je spojený zoznam (alebo strom, od Java 8, keď je veľa kolízií).
Pri pridávaní prvku (put):
1. Vypočíta sa hash kód kľúča (key.hashCode()).
2. Hash kód sa upraví pre lepšie rozloženie (hash).
3. Použitím upraveného hashu a veľkosti poľa sa vypočíta index koša (hash & (array_size - 1)).
4. Prvok (pár "kľúč-hodnota" ako objekt Node) sa umiestni do tohto koša. Ak koš už obsahuje prvky, nový prvok sa pridá na začiatok spojového zoznamu alebo stromu.
5. Pri pridávaní sa kontroluje existencia kľúča: používa sa metóda equals() na porovnanie kľúčov v koši. Ak je kľúč nájdený, hodnota sa aktualizuje.
Pri získavaní prvku (get):
1. Index koša sa vypočíta podľa kľúča.
2. Vo vnútri koša sa hľadá prvok podľa kľúča pomocou metód hashCode() a equals().
3. Vráti sa spojená hodnota.

Organizácia:

Kolízie: Ak niekoľko kľúčov má rovnaký hash kód a spadnú do jedného koša, prvky sa ukladajú ako spojený zoznam. Od Java 8, ak počet prvkov v koši prekročí prah (zvyčajne 8), spojový zoznam sa premení na strom pre rýchlejšie vyhľadávanie (O(log n) namiesto O(n)).
Zmena veľkosti: Keď počet prvkov prekročí "práh načítania" (load factor * capacity), HashMap zväčší veľkosť vnútorného poľa (zvyčajne zdvojnásobí) a prehashuje všetky prvky. Táto operácia je náročná (O(n)).
Parametre:
- capacity: Počiatočná veľkosť poľa (predvolene 16).
- load factor: Práh načítania (predvolene 0.75). Určuje, kedy dôjde k zmenám veľkosti.

Prečo sú hashCode() a equals() dôležité:

Správne fungovanie HashMap závisí od správnej implementácie týchto metód.
Ak equals() vracia true pre dva objekty, hashCode() by mal vracať rovnakú hodnotu.
Nesprávna implementácia môže viesť k tomu, že prvky nebudú nájdené (get vráti null), aj keď boli pridané.

Príklad štruktúry Node:

// Iba pre vnútorné použitie
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 pri ravnomernom rasporedu haševa. U najgorem slučaju (jake kolizije), operacija može biti O(n) ili O(log n) sa stablima.

Ako je štruktúrovaná a organizovaná dátová štruktúra HashMap v Jave?