Java-da HashMap məlumatlar strukturu necə qurulmuş və…

HashMap Java-da hash prinsiplərinə əsaslanır. O, "açar-dəyər" cütlüklərini saxlayır.

Daxili quruluş:

Baketlərin (qabların) massivləri. Hər bir baket əlaqəli siyahıdır (və ya Java 8-dən başlayaraq, çox sayda toqquşma olduqda, ağaca çevrilir).
Element əlavə edilərkən (put):
1. Açarın hash kodu hesablanır (key.hashCode()).
2. Hash kodu daha yaxşı paylanma üçün dəyişdirilir (hash).
3. Dəyişdirilmiş hash və baketin massiv ölçüsü istifadə edilərək, elementin yerləşdiriləcəyi baketin indeksi hesablanır (hash & (array_size - 1)).
4. Element ("açar-dəyər" cütlüyü obyekt kimi Node) həmin baketə yerləşdirilir. Əgər baket artıq elementlərə malikdirsə, yeni element əlaqəli siyahının və ya ağacın əvvəlinə əlavə olunur.
5. Açarın mövcudluğu yoxlanır: equals() metodu istifadə edilərək baketdə axtarış aparılır. Əgər açar tapılırsa, dəyər yenilənir.
Element alınarkən (get):
1. Açarın indeksi hesablanır.
2. Baket daxilində axtarış hashCode() və equals() metodları ilə aparılır.
3. Əlaqəli dəyər qaytarılır.

Təşkilatlanma:

Toqquşmalar: Əgər bir neçə açar eyni hash koduna malikdirsə və eyni baketə düşürsə, elementlər əlaqəli siyahı şəklində saxlanılır. Java 8-dən sonra, baketdəki elementlərin sayı müəyyən limiti aşdıqda (adətən 8), əlaqəli siyahı ağaca çevrilir ki, axtarış daha sürətli olsun (O(log n) əvəzinə O(n)).
Yenidən ölçmə: Elementlərin sayı load factor * capacity limitini aşdıqda, HashMap daxili massiv ölçüsünü artırır (adətən ikiqat) və bütün elementləri yenidən hash edir. Bu çox vaxt alan əməliyyatdır (O(n)).
Parametrlər:
- capacity: Başlanğıc massiv ölçüsü (standart 16).
- load factor: Yükləmə limiti (standart 0.75). Yenidən ölçmənin vaxtını müəyyən edir.

hashCode() və equals()-in əhəmiyyəti:

HashMap-in düzgün işləməsi üçün bu metodların düzgün tətbiqi vacibdir.
Əgər equals() iki obyekt üçün true qaytarırsa, hashCode() eyni dəyər qaytarmalıdır.
Yanlış tətbiq elementlərin tapılmamasına səbəb ola bilər (get null qaytarar), hətta onlar əlavə olunub.

Node strukturunun nümunəsi:

// Yalnız daxili istifadə üçün
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, ümumi halda, elementlərin əlavə olunması, alınması və silinməsi üçün sürətli (ortalama O(1)) əməliyyatlar təmin edir. Ən pis halda (güclü toqquşmalar) əməliyyat O(n) və ya ağaclarla O(log n) ola bilər.

İşə təhlükəsiz deyil. Təhlükəsiz istifadə üçün ConcurrentHashMap və ya Collections.synchronizedMap(new HashMap<...>(...)) istifadə olunmalıdır.

Java-da HashMap məlumatlar strukturu necə qurulmuş və təşkil olunmuşdur?