Jak je strukturována a organizována datová struktura…

HashMap v Javě je založen na principech hašování. Ukládá páry "klíč-hodnota".

Vnitřní struktura:

Pole košů (kontejnerů). Každý koš je spojový seznam (nebo strom, od Java 8, pokud je mnoho kolizí).
Při přidání prvku (put):
1. Vypočítá se hash kód klíče (key.hashCode()).
2. Hash kód je upraven pro lepší rozložení (hash).
3. Pomocí upraveného hashe a velikosti pole se vypočítá index koše (hash & (array_size - 1)).
4. Prvek (pár "klíč-hodnota" jako objekt Node) je umístěn do tohoto koše. Pokud koš již obsahuje prvky, nový prvek se přidá na začátek spojového seznamu nebo stromu.
5. Při přidání se kontroluje existence klíče: používá se metoda equals() pro porovnání klíčů v koši. Pokud je klíč nalezen, hodnota je aktualizována.
Při získání prvku (get):
1. Index koše se vypočítá podle klíče.
2. Uvnitř koše se hledá prvek podle klíče pomocí metod hashCode() a equals().
3. Vrací se spojená hodnota.

Organizace:

Kolize: Pokud několik klíčů má stejný hash kód a spadnou do jednoho koše, jsou uloženy jako spojový seznam. Od Java 8, pokud počet prvků v koši přesáhne práh (obvykle 8), spojový seznam se převede na strom pro rychlejší hledání (O(log n) místo O(n)).
Změna velikosti: Když počet prvků přesáhne "práh načtení" (load factor * capacity), HashMap zvětší velikost vnitřního pole (obvykle zdvojnásobí) a přehashuje všechny prvky. Tato operace je nákladná (O(n)).
Parametry:
- capacity: Počáteční velikost pole (výchozí 16).
- load factor: Práh načtení (výchozí 0.75). Určuje, kdy dojde ke změně velikosti.

Proč jsou důležité hashCode() a equals():

Správná funkce HashMap závisí na správné implementaci těchto metod.
Pokud equals() vrací true pro dva objekty, hashCode() by měl vracet stejnou hodnotu.
Nesprávná implementace může vést k tomu, že prvky nebudou nalezeny (get vrátí null), i když byly přidány.

Příklad struktury Node:

// Pouze 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 zajišťuje rychlé (průměrně O(1)) přidávání, získávání a mazání prvků při rovnoměrném rozložení hashů. V nejhorším případě (silné kolize) může být operace O(n) nebo O(log n) s použitím stromů.

Jak je strukturována a organizována datová struktura HashMap v Javě?