Kā ir uzbūvēta un organizēta HashMap datu struktūra…

HashMap Java valodā balstās uz hašēšanas principiem. Tā glabā "atslēgas-vērtības" pārus.

Iekšējā struktūra:

Baku masīvs. Katrs bakets ir saistīts saraksts (vai koks, sākot no Java 8, kad kolīcijas ir lielas).
Pievienojot elementu (put):
1. Tiek aprēķināts atslēgas haškods (key.hashCode()).
2. Haškods tiek modificēts labākai sadalīšanai (hash).
3. Izmantojot modificēto haš kodu un baketu masīva izmēru, tiek aprēķināts baketa indekss (хеш & (masīva_izmērs - 1)).
4. Elements (atslēgas-vērtības pāris Node objektā) tiek ievietots šajā baketā. Ja bakets jau satur elementus, jauns elements tiek pievienots saistītā saraksta vai koka sākumā.
5. Pievienojot, tiek pārbaudīts, vai ir atslēga: tiek izmantota equals() metode atslēgu salīdzināšanai baketā. Ja atslēga ir atrasta, vērtība tiek atjaunināta.
Saņemot elementu (get):
1. Tiek aprēķināts baketa indekss pēc atslēgas.
2. Baketā tiek meklēts elements pēc atslēgas, izmantojot hashCode() un equals() metodes.
3. Atgriežas saistītā vērtība.

Organizācija:

Kolīcijas: Ja vairāki atslēgas ir ar vienādu haš kodu un nonāk tajā pašā baketā, elementi tiek glabāti saistītā sarakstā. No Java 8, kad baketa elementu skaits pārsniedz slieksni (parasti 8), saistītais saraksts tiek pārveidots par koku ātrākai meklēšanai (O(log n) vietā, kur n ir elementi).
Pārformatēšana: Kad elementu skaits pārsniedz "ielādes līmeni" (load factor * capacity), HashMap palielina iekšējā masīva izmēru (parasti divkārši) un pārreģistrē visus elementus. Šī ir dārga operācija (O(n)).
Parametri:
- capacity: Sākotnējais baketu masīva izmērs (noklusējuma 16).
- load factor: Ielādes slieksnis (noklusējuma 0.75). Nosaka, kad notiks pārformatēšana.

Kāpēc ir svarīgi hashCode() un equals():

Pareiza HashMap darbība ir atkarīga no šo metožu pareizas realizācijas.
Ja equals() atgriež true diviem objektiem, tad hashCode() jāatgriež tas pats vērtību.
Nepareiza realizācija var novest pie tā, ka elementi netiks atrasti (get atgriezīs null), lai gan tie ir pievienoti.

Node struktūras piemērs:

// Tikai iekšējai lietošanai
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 nodrošina ātru (vidēji O(1)) pievienošanu, saņemšanu un dzēšanu, ja haši ir vienmērīgi sadalīti. Sliktākajā gadījumā (stipras kolīcijas) operācija var kļūt par O(n) vai O(log n) ar kokiem.

Kā ir uzbūvēta un organizēta HashMap datu struktūra Java?