Java'da HashMap veri yapısı nasıl yapılandırılmış ve…

Java'da HashMap, hashing ilkelerine dayanır. "Anahtar-değer" çiftlerini depolar.

İç yapı:

Buckets (kova) dizisi. Her bucket bağlı liste (veya Java 8'den itibaren, çok sayıda çakışma varsa ağaç).
Bir öğe eklerken (put):
1. Anahtarın hash kodu hesaplanır (key.hashCode()).
2. Hash kodu daha iyi dağılım için değiştirilir (hash).
3. Değiştirilmiş hash ve bucket dizisinin boyutu kullanılarak, öğenin yerleştirileceği bucket indeksi hesaplanır (hash & (dizi_boyu - 1)).
4. Öğe ("anahtar-değer" çifti Node nesnesi olarak) bu bucketa yerleştirilir. Eğer bucket zaten öğeler içeriyorsa, yeni öğe listenin veya ağacın başına eklenir.
5. Eklerken, anahtarın zaten var olup olmadığı kontrol edilir: equals() metodu kullanılır, bucket içindeki anahtarlar karşılaştırılır. Anahtar bulunursa, değer güncellenir.
Bir öğe alınırken (get):
1. Aynı şekilde, anahtara göre bucket indeksi hesaplanır.
2. Bucket içinde, anahtar kullanılarak öğe aranır, hashCode() ve equals() metodlarıyla.
3. Bağlantılı değer döndürülür.

Organizasyon:

Çakışmalar: Birden fazla anahtar aynı hash koduna sahipse ve aynı bucketa düşerse, öğeler bağlı liste şeklinde saklanır. Java 8'den itibaren, bucket'taki öğe sayısı eşikten (genellikle 8) fazla olursa, liste ağaç haline getirilir, böylece arama daha hızlı olur (O(log n) yerine O(n)).
Yeniden boyutlandırma: Öğelerin sayısı, "yükleme faktörü" (load factor * capacity) aşarsa, HashMap iç dizisi (genellikle iki katına çıkarılır) büyütülür ve tüm öğeler yeniden hashlenir. Bu maliyetli bir işlemdir (O(n)).
Parametreler:
- capacity: başlangıç dizisi boyutu (varsayılan 16).
- load factor: yükleme eşiği (varsayılan 0.75). Yeniden boyutlandırmanın ne zaman olacağını belirler.

Neden hashCode() ve equals() önemli:

HashMap'in doğru çalışması, bu metodların doğru uygulanmasına bağlıdır.
Eğer equals() iki nesne için true dönerse, hashCode() aynı değeri döndürmelidir.
Yanlış uygulama, öğelerin bulunmamasına neden olabilir (get null döner), eklenmiş olsalar bile.

Node yapısına örnek:

// Sadece iç
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, dağılımı düzgün olduğunda, ekleme, alma ve silme işlemlerini ortalama O(1) sürede yapar. Çok sayıda çakışma olursa, bu işlemler O(n) veya ağaçlar kullanıldığında O(log n) olabilir.

İş parçacığı güvenli değildir. Çok iş parçacıklı ortamlar için ConcurrentHashMap veya Collections.synchronizedMap(new HashMap<...>(...)) kullanılmalıdır.

Java'da HashMap veri yapısı nasıl yapılandırılmış ve organize edilmiştir?