Kaip yra sukurta ir organizuota duomenų struktūra…

HashMap Java kalba yra pagrįsta maišos funkcijos principais. Ji saugo poras "raktas-reikšmė".

Vidinė struktūra:

Dėžučių masyvas. Kiekviena dėžutė yra susijusi sąrašas (arba medis nuo Java 8, kai kolizijos yra didelės).
Pridedant elementą (put):
1. Apskaičiuojamas rakto hash kodas (key.hashCode()).
2. Hash kodas modifikuojamas geresniam paskirstymui (hash).
3. Naudojant modifikuotą hash ir dėžučių masyvo dydį, apskaičiuojamas dėžutės indeksas (хеш & (masyvo_dydis - 1)).
4. Elementas (poros "raktas-reikšmė" objektas Node) įdedamas į šią dėžutę. Jei dėžutė jau turi elementų, naujas elementas pridedamas prie susietojo sąrašo arba medžio pradžios.
5. Pridedant tikrinama, ar yra raktas: naudojamas equals() metodas rakto palyginimui dėžutėje. Jei raktas rastas, reikšmė atnaujinama.
Gaunant elementą (get):
1. Taip pat apskaičiuojamas dėžutės indeksas pagal raktą.
2. Dėžutėje ieškoma elemento pagal raktą, naudojant hashCode() ir equals() metodus.
3. Grąžinama susieta reikšmė.

Organizacija:

Kolizijos: Jei keli raktai turi tą patį hash kodą ir patenka į tą patį dėžutę, elementai saugomi susietame sąraše. Nuo Java 8, kai dėžutės elementų skaičius viršija slenkstį (dažniausiai 8), susietas sąrašas paverčiamas medžiu greitesniam paieškai (O(log n) vietoj O(n)).
Perdarymas: Kai elementų skaičius viršija "įkrovimo lygį" (load factor * capacity), HashMap padidina vidinio masyvo dydį (dažniausiai dvigubai) ir perheshuoja visus elementus. Tai brangi operacija (O(n)).
Parametrai:
- capacity: Pradinis dėžučių masyvo dydis (numatytasis 16).
- load factor: Įkrovimo slenkstis (numatytasis 0.75). Nustato, kada įvyks perdarymas.

Kodėl svarbūs hashCode() ir equals():

Teisingas HashMap veikimas priklauso nuo šių metodų teisingos įgyvendinimo.
Jei equals() grąžina true dviems objektams, tada hashCode() turi grąžinti tą patį reikšmę.
Netinkama įgyvendinimas gali sukelti tai, kad elementai nebus rasti (get grąžins null), nors jie buvo pridėti.

Node struktūros pavyzdys:

// Tik vidiniam naudojimui
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 užtikrina greitą (vidutiniškai O(1)) elementų pridėjimą, gavimą ir ištrynimą, kai hash'ai paskirstyti tolygiai. Blogiausiu atveju (stiprios kolizijos) operacija gali tapti O(n) arba O(log n) su medžiais.

Kaip yra sukurta ir organizuota duomenų struktūra HashMap Java?