Kuidas on üles ehitatud ja organiseeritud HashMap…

HashMap Java keeles põhineb hajutamise põhimõtetel. See salvestab "võtme-väärtuse" paare.

Sisemine struktuur:

Kasti massiiv. Iga kasti on seotud nimekiri (või puu, alates Java 8-st, kui kolisioonid on suured).
Elementi lisamisel (put):
1. Arvutatakse võtme hash-kood (key.hashCode()).
2. Hash-kood muudetakse parema jaotumise jaoks (hash).
3. Kasutades muudetud hash-i ja kasti massiivi suurust, arvutatakse kasti indeks (хеш & (massivi_suurus - 1)).
4. Element (võti-väärtuse paar Node objekti kujul) paigutatakse sellesse kasti. Kui kastis on juba elemente, lisatakse uus element seotud nimekirja või puu algusesse.
5. Lisamisel kontrollitakse, kas võti on olemas: kasutatakse equals() meetodit võtmete võrdlemiseks kastis. Kui võti leitakse, uuendatakse väärtust.
Elementi saamisel (get):
1. Arvutatakse samuti kasti indeks võtme põhjal.
2. Kastis otsitakse elementi võtme järgi, kasutades hashCode() ja equals() meetodeid.
3. Tagastatakse seotud väärtus.

Organisatsioon:

Kolisioonid: Kui mitu võtit omavad sama hash-koodi ja satuvad samasse kasti, salvestatakse elemendid seotud nimekirja. Alates Java 8-st, kui kasti elementide arv ületab lävendi (tavaliselt 8), muudetakse seotud nimekiri puuks kiirema otsingu jaoks (O(log n) asemel).
Uuesti suurendamine: Kui elementide arv ületab "laadimistaseme" (load factor * capacity), suurendab HashMap sisemise massiivi suurust (tavaliselt kahekordistub) ja ümberhüppab kõik elemendid. See on kallis operatsioon (O(n)).
Parameetrid:
- capacity: Algne kasti massiivi suurus (vaikimisi 16).
- load factor: Laadimistasemelõik (vaikimisi 0.75). Määrab, millal toimub uuesti suurendamine.

Miks on olulised hashCode() ja equals():

Õige HashMap-i toimimine sõltub nende meetodite õigest implementeerimisest.
Kui equals() tagastab true kahe objekti jaoks, peab hashCode() tagastama sama väärtuse.
Vale implementeerimine võib põhjustada selle, et elemendid ei leita (get tagastab null), kuigi need on lisatud.

Node struktuuri näide:

// Ainult sisekasutuseks
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 tagab kiire (keskmiselt O(1)) elementide lisamise, saamise ja kustutamise, kui hajutused on ühtlaselt jaotunud. Halvimal juhul (tõsised kolisioonid) võib operatsioon muutuda O(n) või O(log n) puude abil.

Kuidas on üles ehitatud ja organiseeritud HashMap andmestruktuur Java-s