Hogyan van felépítve és szervezve a HashMap…

A HashMap Java-ban a hashelés elvein alapul. Párokat tárol "kulcs-érték" formában.

Belső felépítés:

Kádak (tárolók) tömbje. Minden kád egy láncolt listát (vagy fát, Java 8-tól kezdve, ha sok ütközés van).
Elem hozzáadása (put):
1. A kulcs hash kódja számítódik (key.hashCode()).
2. A hash kód módosul a jobb eloszlás érdekében (hash).
3. A módosított hash és a tömb mérete alapján számítódik a kád indexe (hash & (array_size - 1)).
4. Az elem ("kulcs-érték" pár Node objektumként) ebbe a kádba kerül. Ha a kád már tartalmaz elemeket, az új elem a láncolt lista vagy fa elejére kerül.
5. Hozzáadáskor ellenőrzés történik a kulcs meglétére: az equals() metódus segítségével keresünk a kádon belül. Ha a kulcs megtalálható, az érték frissül.
Elem lekérése (get):
1. A kulcs alapján számítódik a kád indexe.
2. A kádon belül keresés történik az hashCode() és equals() metódusok segítségével.
3. Visszaadódik a kapcsolódó érték.

Szervezés:

Ütközések: Ha több kulcs ugyanazzal a hash kóddal rendelkezik és ugyanabba a kádba kerül, azok láncolt listaként tárolódnak. Java 8-tól, ha a kádon belüli elemek száma meghalad egy küszöböt (általában 8), a láncolt lista fává alakul a gyorsabb keresés érdekében (O(log n) helyett O(n)).
Méret növelése: Amikor az elemek száma meghaladja a load factor * capacity értéket, a HashMap megnöveli a belső tömb méretét (általában duplájára) és újra hash-eli az összes elemet. Ez erőforrás-igényes művelet (O(n)).
Paraméterek:
- capacity: Kezdeti tömbméret (alapértelmezett 16).
- load factor: Betöltési küszöb (alapértelmezett 0.75). Meghatározza, mikor történjen a méret növelése.

Miért fontosak a hashCode() és equals():

A HashMap helyes működése ezeknek a metódusoknak a helyes implementációjától függ.
Ha az equals() két objektum esetén true-t ad, akkor a hashCode() ugyanazt az értéket kell, hogy adja.
Hibás implementáció esetén az elemek nem találhatók meg (get null-t ad), még akkor sem, ha hozzáadtuk őket.

Node szerkezetének példája:

// Csak belső használatra
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;
    }
}

A HashMap gyors (átlagosan O(1)) hozzáférést, beszúrást és törlést biztosít, egyenletes eloszlás esetén. Legrosszabb esetben (erős ütközések) az idő O(n) vagy O(log n) lehet fákkal.

Hogyan van felépítve és szervezve a HashMap adatstruktúra Java-ban?