Jak jest zbudowana i zorganizowana struktura danych…

HashMap w Javie opiera się na zasadach haszowania. Przechowuje pary "klucz-wartość".

Wewnętrzna struktura:

Tablica kubełków (kontenerów). Każdy kubełek to lista powiązana (lub drzewo, od Java 8, przy dużej liczbie kolizji).
Przy dodawaniu elementu (put):
1. Oblicza się kod hash klucza (key.hashCode()).
2. Kod hash jest modyfikowany dla lepszego rozkładu (hash).
3. Używając zmodyfikowanego hash i rozmiaru tablicy kubełków, oblicza się indeks kubełka (hash & (rozmiar_tablicy - 1)).
4. Element (para "klucz-wartość" jako obiekt Node) jest umieszczany w tym kubełku. Jeśli kubełek już zawiera elementy, nowy element jest dodawany na początku listy powiązanej lub drzewa.
5. Przy dodawaniu sprawdza się, czy klucz już istnieje: używa się metody equals() do porównania kluczy w kubełku. Jeśli klucz zostanie znaleziony, wartość jest aktualizowana.
Przy pobieraniu elementu (get):
1. Również oblicza się indeks kubełka na podstawie klucza.
2. Wewnątrz kubełka szuka się elementu po kluczu, używając metod hashCode() i equals().
3. Zwracana jest powiązana wartość.

Organizacja:

Kolizje: Jeśli kilka kluczy ma ten sam kod hash i trafia do tego samego kubełka, elementy są przechowywane jako lista powiązana. Od Java 8, gdy liczba elementów w kubełku przekracza próg (zazwyczaj 8), lista jest przekształcana w drzewo dla szybszych wyszukiwań (O(log n) zamiast O(n)).
Resizing: Gdy liczba elementów przekracza "współczynnik ładowania" (load factor * capacity), HashMap zwiększa rozmiar wewnętrznej tablicy kubełków (zazwyczaj podwaja) i ponownie hashuje wszystkie elementy. To kosztowna operacja (O(n)).
Parametry:
- capacity: początkowy rozmiar tablicy kubełków (domyślnie 16).
- load factor: próg ładowania (domyślnie 0.75). Określa, kiedy następuje resize.

Dlaczego hashCode() i equals() są ważne:

Prawidłowe działanie HashMap zależy od poprawnej implementacji tych metod.
Jeśli equals() zwraca true dla dwóch obiektów, to hashCode() musi zwracać tę samą wartość.
Niepoprawna implementacja może spowodować, że elementy nie zostaną odnalezione (get zwróci null), nawet jeśli zostały dodane.

Przykład struktury Node:

// Tylko wewnętrznie
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 zapewnia szybkie (średnio O(1)) dodawanie, pobieranie i usuwanie elementów przy równomiernym rozkładzie hashy. W najgorszym przypadku (silne kolizje) operacja może mieć złożoność O(n) lub O(log n) z drzewami.

Nie jest bezpieczny wątkowo. Do użycia w środowiskach wielowątkowych należy używać ConcurrentHashMap lub Collections.synchronizedMap(new HashMap<...>(...)).

Jak jest zbudowana i zorganizowana struktura danych HashMap w Java?