Как е структурирана и организирана структурата на…

HashMap в Java се основава на принципите на хеширането. Той съхранява двойки "ключ-стойност".

Вътрешна структура:

Масиви от кофи (контейнери). Всяка кофичка е свързан списък (или дърво, от Java 8 нататък, при голям брой колизии).
При добавяне на елемент (put):
1. Изчислява се хеш кодът на ключа (key.hashCode()).
2. Хеш кодът се модифицира за по-добро разпределение (hash).
3. Използвайки модифицирания хеш и размера на масива, се изчислява индексът на кофата (hash & (array_size - 1)).
4. Елементът (двойката "ключ-стойност" като обект Node) се поставя в тази кофа. Ако кофата вече съдържа елементи, новият елемент се добавя в началото на свързания списък или дървото.
5. При добавяне се проверява наличието на ключа: използва се методът equals() за сравнение на ключовете в кофата. Ако ключът е намерен, стойността се актуализира.
При получаване на елемент (get):
1. Индексът на кофата се изчислява по ключа.
2. В кофата се търси елемент по ключ, използвайки методите hashCode() и equals().
3. Връща се свързаната стойност.

Организация:

Колизии: Ако няколко ключа имат еднакъв хеш код и попадат в една и съща кофа, елементите се съхраняват като свързан списък. От Java 8 нататък, ако броят на елементите в кофата надвиши прага (обикновено 8), свързаният списък се преобразува в дърво за по-бързо търсене (O(log n) вместо O(n)).
Преоразмеряване: Когато броят на елементите надвиши "порога на зареждане" (load factor * capacity), HashMap увеличава размера на вътрешния масив (обикновено двойно) и пре-хешира всички елементи. Това е скъпа операция (O(n)).
Параметри:
- capacity: Начален размер на масива (по подразбиране 16).
- load factor: Порога на зареждане (по подразбиране 0.75). Определя кога ще се извърши преоразмеряване.

Защо hashCode() и equals() са важни:

Правилната работа на HashMap зависи от правилната реализация на тези методи.
Ако equals() връща true за два обекта, hashCode() трябва да връща същата стойност.
Неправилната реализация може да доведе до това, че елементите няма да бъдат намерени (get ще върне null), дори ако са добавени.

Пример за структура Node:

// Само за вътрешна употреба
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 осигурява бързо (средно O(1)) добавяне, получаване и изтриване на елементи при равномерно разпределение на хешовете. В най-лошия случай (силни колизии) операцията може да стане O(n) или O(log n) с дървета.

Как е структурирана и организирана структурата на данните HashMap в Java?