Javaда HashMap маалыматтардын түзүмү кандай түзүлгөн…

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) болушу мүмкүн.

Javaда HashMap маалыматтардын түзүмү кандай түзүлгөн жана уюштурулган?