Hoe is de gegevensstructuur HashMap in Java opgebouwd…

HashMap in Java is gebaseerd op hashing principes. Het slaat "sleutel-waarde" paren op.

Interne structuur:

Array van buckets (containers). Elke bucket is een gekoppelde lijst (of een boom, vanaf Java 8, bij veel collisions).
Bij het toevoegen van een element (put):
1. Wordt de hash-code van de sleutel berekend (key.hashCode()).
2. De hash-code wordt aangepast voor een betere verdeling (hash).
3. Met de aangepaste hash en de grootte van de bucket-array wordt de index van de bucket berekend (hash & (array_grootte - 1)).
4. Het element (paar "sleutel-waarde" als object Node) wordt in die bucket geplaatst. Als de bucket al elementen bevat, wordt het nieuwe element aan het begin van de gekoppelde lijst of boom toegevoegd.
5. Bij het toevoegen wordt gecontroleerd of de sleutel al bestaat: de methode equals() wordt gebruikt om de sleutels binnen de bucket te vergelijken. Als de sleutel wordt gevonden, wordt de waarde bijgewerkt.
Bij het ophalen van een element (get):
1. Wordt ook de bucket index berekend op basis van de sleutel.
2. Binnen de bucket wordt gezocht naar het element met behulp van hashCode() en equals().
3. De gekoppelde waarde wordt geretourneerd.

Organisatie:

Collisions: Als meerdere sleutels dezelfde hash-code hebben en in dezelfde bucket terechtkomen, worden de elementen opgeslagen als een gekoppelde lijst. Vanaf Java 8, wanneer het aantal elementen in een bucket de drempel overschrijdt (meestal 8), wordt de lijst omgezet in een boom voor snellere zoekopdrachten (O(log n) in plaats van O(n)).
Resizing: Wanneer het aantal elementen de "load factor" (load factor * capacity) overschrijdt, vergroot HashMap de interne array van buckets (meestal verdubbelen) en herberekent alle hashes. Dit is een dure operatie (O(n)).
Parameters:
- capacity: initiële grootte van de bucket array (standaard 16).
- load factor: drempelwaarde voor belasting (standaard 0.75). Bepaalt wanneer resizing plaatsvindt.

Waarom hashCode() en equals() belangrijk zijn:

Het correct functioneren van HashMap hangt af van de juiste implementatie van deze methoden.
Als equals() true retourneert voor twee objecten, moet hashCode() hetzelfde waarde retourneren.
Een verkeerde implementatie kan ertoe leiden dat elementen niet gevonden worden (get retourneert null), zelfs als ze toegevoegd zijn.

Voorbeeld van Node-structuur:

// Alleen intern
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 biedt snelle (gemiddeld O(1)) toevoegen, ophalen en verwijderen van elementen bij een gelijkmatige verdeling van hashes. In het slechtste geval (sterke collisions) kan de operatie O(n) of O(log n) worden met bomen.

Niet thread-safe. Voor gebruik in multi-threaded omgevingen, gebruik ConcurrentHashMap of Collections.synchronizedMap(new HashMap<...>(...)).

Hoe is de gegevensstructuur HashMap in Java opgebouwd en georganiseerd?