Verimli veri yapıları: Set'ler ve Map'ler

Java'da Kod Optimizasyonu

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Yer/zaman karmaşıklığını uygulama

Artık yer ve zaman karmaşıklığını biliyoruz!

Peki bu bilgiyi daha verimli kod yazmak için nasıl uygularız?

Doğru veri yapısını seçerek!

Bir kullanıcı yönetim sistemi

Bir kullanıcı yönetim sistemi kuruyoruz
Verilen bir kullanıcı adı için kullanıcının var olup olmadığını kontrol etmeliyiz
Liste kullanırsak: karmaşıklık $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}

Set'ler

Benzersiz öğelerden oluşan ve hızlı arama sunan bir koleksiyon
Öğeyi ekleme, kaldırma ve var mı kontrolünde ortalama $O(1)$ zaman

Geliştirilmiş kullanıcı yönetimi çözümü:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}

Map'ler

Sözlük gibi, kelime (anahtar) -> tanım (değer)
HashMap: işlemler için ortalama $O(1)$ zaman karmaşıklığı

public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) average time
    }
}

Hashcode yöntemi

Onları hızlı yapan şey -> hashCode()
ArrayList örneğimizde, bulmak için kullanıcı adının indeksini bilmiyorduk
hashcode() yöntemiyle bir nesneyi arayabileceğimiz bir indekse dönüştürebiliriz
Örneğin pavlos.2020 -> 35189

pavlos.2020 hashcode'dan geçirilip 35189 elde edilmesi

Öğeleri indeksleme

HashMap ve HashSet altında bir dizi barındırır
Bir öğe eklediğimizde:
- Java, tamsayı elde etmek için öğende hashCode() çağırır
- Yukarıdakine mod alır ve kova numarasını bulur

Örnek:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Java tarafından uygulanır
1406313774 % 16 = 14 <- kovamız bu!

Çakışmalar

Birden fazla öğe aynı kovaya düştüğünde
- Çakışma (collision) denir
Kova için LinkedList kullanılır
Bu yüzden ortalama $O(1)$ deriz

Aklında kalsın

Veri yapısı seçimi, işe uygun doğru aracı seçmek gibidir - bir çekiç (ArrayList) çiviler için harika ama vidalar için kötüdür (orada bir Set daha iyi olabilir).

Yan yana duran bir çekiç, tornavida, anahtar ve pense içeren açık alet kutusu

Hadi pratik yapalım!

Java'da Kod Optimizasyonu