Java Academy · Ders

Ağaçlaştırma ve Performans

Java 8 ve sonrasında çakışmalar nasıl ele alınır

Ağaçlaştırma ve Performans, CoddyKit'te ücretsiz bir Java Academy dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Java Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Java Academy kursu toplamda 4 dersten oluşur.

Çakışma Sorunu

Java 8'den önce, çok sayıda çakışma içeren bir kova uzun bir bağlı listeye dönüşürdü. Bu kovadaki arama O(n) değerine kadar kötüleşirdi.

Bir saldırgan, tüm anahtarları tek kovaya hash'leyen özel hazırlanmış anahtarlarla bundan yararlanarak hizmet engellemeye neden olabilirdi.

public class Main {
    public static void main(String[] args) {
        // All these strings can be made to collide in one bucket
        System.out.println("FB".hashCode() == "Ea".hashCode());
    }
}

Java 8'de Ağaç Yapısına Dönüşüm

Java 8, ağaç yapısına dönüştürme özelliğini ekledi. Tek bir kovada çok fazla girdi bulunduğunda bağlı liste, dengeli bir kırmızı-siyah ağaca dönüştürülür.

Böylece bu kovadaki arama, O(n) yerine O(log n) olur.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < 1000; i++) m.put(i, i);
        System.out.println("Lookups stay fast: " + m.get(742));
    }
}

Eşik: TREEIFY_THRESHOLD

TREEIFY_THRESHOLD sabiti 8'dir. Bir kova 8 girdiye ulaştığında ağaca dönüştürülür.

Ancak ikinci bir koşul daha vardır: tablo en az MIN_TREEIFY_CAPACITY (64) boyutunda olmalıdır; aksi halde harita yeniden boyutlandırılır.

public class Main {
    public static void main(String[] args) {
        int TREEIFY_THRESHOLD = 8;
        int MIN_TREEIFY_CAPACITY = 64;
        System.out.println("Treeify when bucket size >= " + TREEIFY_THRESHOLD);
        System.out.println("...and table capacity >= " + MIN_TREEIFY_CAPACITY);
    }
}

Önce Yeniden Boyutlandırın, Sonra Ağaç Yapısına Dönüştürün

Bir kova taşarsa ancak tablo hâlâ küçükse (64'ten küçükse), HashMap önce tabloyu yeniden boyutlandırır.

Yeniden boyutlandırma genellikle girdileri yeniden dağıtır ve yoğun noktayı ortadan kaldırır; bu nedenle ağaç yapısına dönüştürme, gerçekten kötü hash dağılımları için yalnızca son çaredir.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16);
        for (int i = 0; i < 50; i++) m.put(i, i);
        // Many resizes happened before any treeify would
        System.out.println("size = " + m.size());
    }
}

Ağaç Yapısından Çıkarma

Ağaçlar kalıcı değildir. Silme işlemleri bir kovayı UNTREEIFY_THRESHOLD değerinin (6) altına küçültürse ağaç yeniden bağlı listeye dönüşür.

8 (ağaç yapısına dönüştürme) ile 6 (ağaç yapısından çıkarma) arasındaki fark, sınırda sürekli gidip gelmeyi önler.

public class Main {
    public static void main(String[] args) {
        System.out.println("TREEIFY_THRESHOLD   = 8");
        System.out.println("UNTREEIFY_THRESHOLD = 6");
        System.out.println("Gap prevents flip-flopping at the edge");
    }
}

Ağaçların Karşılaştırılabilirlik veya Kimlik Sıralamasına İhtiyacı Vardır

Kırmızı-siyah ağaç, girdilerini sıralamak zorundadır. HashMap önce hash kodlarını karşılaştırır; eşitlikler, anahtarlar karşılaştırılabilirliği uyguluyorsa buna göre, aksi halde sınıf adları ve kimlik temelinde kararlı bir eşitlik bozma kuralıyla çözülür.

Karşılaştırılabilir olan anahtarlar (örneğin String veya tamsayı), en düzenli ağaç sıralamasını sağlar.

public class Main {
    public static void main(String[] args) {
        System.out.println("String is Comparable: " + ("a" instanceof Comparable));
        System.out.println("Integer is Comparable: " + (Integer.valueOf(1) instanceof Comparable));
    }
}

Pratik Etki

Uygun hash kodlarına sahip gerçek programların çoğunda ağaç yapısına dönüşümü asla görmezsiniz. Kovalar kısa kalır.

Ağaç yapısına dönüştürme, hash'leme kötü veya kötü niyetli olsa bile en kötü durumdaki aramayı O(log n) ile sınırlayan bir güvenlik ağıdır.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("alpha", 1);
        m.put("beta", 2);
        m.put("gamma", 3);
        // Tiny buckets, plain linked lists, no trees needed
        System.out.println(m.get("beta"));
    }
}

Sabit hashCode Ağaç Yapılarını Zorunlu Kılar

Kasıtlı olarak sabit bir hashCode döndürürseniz her anahtar tek bir kovaya düşer. Kapasite 64 veya daha büyük olduğunda bu kova ağaç yapısına dönüşür.

Bu, güvenlik ağını gösterir; ancak bir tasarım kusurudur. Bunun yerine hashCode'u düzeltin.

import java.util.HashMap;
import java.util.Map;

public class Main {
    static class Bad implements Comparable<Bad> {
        final int v;
        Bad(int v) { this.v = v; }
        @Override public int hashCode() { return 1; } // forces collisions
        @Override public boolean equals(Object o) { return o instanceof Bad b && b.v == v; }
        @Override public int compareTo(Bad o) { return Integer.compare(v, o.v); }
    }
    public static void main(String[] args) {
        Map<Bad, Integer> m = new HashMap<>();
        for (int i = 0; i < 100; i++) m.put(new Bad(i), i);
        System.out.println("All in one bucket, still works: " + m.get(new Bad(50)));
    }
}

Ağaçların Bellek Maliyeti

Ağaç düğümleri, ebeveyn, sol, sağ ve renk başvurularını sakladıkları için sıradan bağlı liste düğümlerinden daha büyüktür.

Ağaç yapısına dönüşümün varsayılan seçenek değil, başka bir çözüm kalmadığında kullanılan bir yöntem olmasının bir nedeni de budur: ağaçlar en kötü durum hızını bellek karşılığında sunar.

public class Main {
    public static void main(String[] args) {
        System.out.println("Node: hash, key, value, next");
        System.out.println("TreeNode: + parent, left, right, prev, red flag");
        System.out.println("=> trees cost more memory per entry");
    }
}

Ağaç Yapısına Dönüşümden Nasıl Kaçınılır

Neredeyse hiçbir zaman ağaç yapısına dönüşüme güvenmek istemezsiniz. Bundan şu yollarla kaçının:

İyi dağıtılmış bir hashCode() yazın.
Anahtar olarak yerleşik türleri veya kayıtları kullanın.
Çakışmaları azaltmak için haritayı başlangıçta uygun boyutlandırın.

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class Main {
    record Key(int a, int b) {}
    public static void main(String[] args) {
        Map<Key, Integer> m = new HashMap<>(256);
        for (int i = 0; i < 200; i++) m.put(new Key(i, i * 31), i);
        System.out.println("Even distribution, fast lookups: " + m.get(new Key(10, 310)));
    }
}

Performans Özeti

HashMap işlemlerinin maliyeti:

İyi hash: ortalama O(1).
Bağlı kova: en kötü durumda kova başına O(n).
Ağaç yapısına dönüştürülmüş kova: kova başına O(log n).

Ağaç yapısına dönüşüm en kötü durumu sınırlar, ancak iyi bir hashCode sizi O(1) düzeyinde tutar.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(1 << 14);
        for (int i = 0; i < 10000; i++) m.put(i, i);
        System.out.println("10k entries, O(1) get: " + m.get(9999));
    }
}

Hızlı Kontrol

Ağaç yapısına dönüşüm bilginizi test edin.

Özet

Modern HashMap'in çakışmaları nasıl ele aldığını öğrendiniz:

Kovalar, kapasite en az 64 olduğunda 8 girdide ağaç yapısına dönüşür.
Ağaçlar en kötü durumda O(log n) arama süresi sağlar.
Kovalar 6 girdinin altında ağaç yapısından çıkar.
İyi bir hashCode, bu güvenlik ağını nadiren tetiklemeniz anlamına gelir.

HashMap iç yapısı kursunu tamamladınız.

public class Main {
    public static void main(String[] args) {
        System.out.println("Treeification course complete");
    }
}

Sıkça Sorulan Sorular

“Ağaçlaştırma ve Performans” dersi ücretsiz mi?

Evet — “Ağaçlaştırma ve Performans” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Java Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Java Academy kursu toplamda 4 dersten oluşur.

“Ağaçlaştırma ve Performans” dersinde ne öğreneceğim?

Java 8 ve sonrasında çakışmalar nasıl ele alınır Java Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

Java Academy öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Java Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.

“Ağaçlaştırma ve Performans” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Bu Java Academy dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Java Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Bu kursun tüm dersleri

← Java Academy Sayfasına Dön