Java'da HashMap ma'lumotlar tuzilmasi qanday tuzilgan…

Java'da HashMap hashing prinsiplari asosida ishlaydi. U "kalit-qiymat" juftliklarini saqlaydi.

Ichki tuzilishi:

Bucket (qoplar) massivlari. Har bir bucket bog'langan ro'yxat (yoki Java 8 dan boshlab, ko'p koliziyalar bo'lsa, daraxt).
Element qo'shishda (put):
1. Kalitning hash kodi hisoblanadi (key.hashCode()).
2. Hash kodi yaxshiroq taqsimot uchun o'zgartiriladi (hash).
3. O'zgartirilgan hash va bucket massivining o'lchami yordamida, element joylashadigan bucket indeksi hisoblanadi (hash & (array_size - 1)).
4. Element ("kalit-qiymat" juftligi Node obyekti sifatida) shu bucketga joylashtiriladi. Agar bucketda allaqachon elementlar bo'lsa, yangi element bog'langan ro'yxat yoki daraxtning boshiga qo'shiladi.
5. Qo'shishda, kalit oldindan mavjudligini tekshirish uchun equals() metodi ishlatiladi. Agar kalit topilsa, qiymat yangilanadi.
Elementni olishda (get):
1. Shuningdek, kalitga asoslangan bucket indeksi hisoblanadi.
2. Bucket ichida, kalit yordamida element qidiriladi, hashCode() va equals() metodlari yordamida.
3. Bog'langan qiymat qaytariladi.

Tashkiliy tuzilma:

Kollisionlar: Agar bir nechta kalitlar bir xil hash kodiga ega bo'lsa va bir bucketga tushsa, elementlar bog'langan ro'yxat sifatida saqlanadi. Java 8 dan boshlab, bucketdagi elementlar soni belgilangan chegaradan oshsa (odatda 8), ro'yxat daraxtga aylantiriladi, bu esa qidiruvni tezlashtiradi (O(log n) o'rniga O(n)).
Yangi o'lchamga o'tish: Elementlar soni "yuklama koeffitsienti" (load factor * capacity) dan oshsa, HashMap ichki bucket massivining o'lchamini (odatda ikki barobar) oshiradi va barcha elementlarni qayta hashlaydi. Bu juda qimmatli operatsiya (O(n)).
Parametrlar:
- capacity: boshlang'ich massiv o'lchami (standart 16).
- load factor: yuklama chegarasi (standart 0.75). Qachon o'lcham o'zgartirilishini belgilaydi.

Nima uchun hashCode() va equals() muhim:

HashMap to'g'ri ishlashi uchun bu metodlarning to'g'ri implementatsiyasi muhim.
Agar equals() true qaytaradigan ikki ob'ekt uchun, hashCode() ham bir xil qiymat qaytarishi kerak.
Noto'g'ri implementatsiya, elementlar topilmasligiga olib kelishi mumkin (get null qaytaradi), hatto ular qo'shilgan bo'lsa ham.

Node strukturasining misoli:

// Faqat ichki
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, hashlarning taqsimoti teng bo'lsa, elementlarni qo'shish, olish va o'chirish operatsiyalari o'rtacha O(1) vaqt oladi. Kuchli koliziyalar bo'lsa, bu operatsiyalar O(n) yoki daraxtlar bilan O(log n) bo'lishi mumkin.

Ushbu class thread-safety emas. Ko'p ipli muhitlarda foydalanish uchun ConcurrentHashMap yoki Collections.synchronizedMap(new HashMap<...>(...)) tavsiya etiladi.

Java'da HashMap ma'lumotlar tuzilmasi qanday tuzilgan va tashkil etilgan?