Чӣ гуна сохтор ва ташкилоти структураи додаҳои…

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?