Sıralı ve Küme Yapıları

Koleksiyonlar dersi karma sözlüğü doğrudan yazdırmadı; anahtarları önce topladı, sıraladı, ancak öyle bastı. Bu adımın neden gerekli olduğu o derste askıda kaldı. Bu ders — beş veri modelleme dersinin sonuncusu — tam bu boşluğu dolduruyor: sıralı ve karma yapılar arasındaki güvence farkı nedir ve bu fark neden kaynakta bir sıralama adımını zorunlu kılıyor?

Şimdiye kadarki dört ders, sırasıyla bir değerin alanlarını, durumlarını, ayrıştırılma biçimini ve topluca tutulma yollarını ölçtü. Bu ders farklı bir eksende duruyor: iki yapı arasında bir seçim yapıldığında, bu seçimin gözlemlenebilir bir sonucu var mı? Yanıt evet — ama bu sonuç, iki yapının işlemlerinin çoğunda değil, yalnızca birinde, gezinmede, ortaya çıkıyor.

Rust’ın standart kitaplığı, hem sözlük hem küme için iki ayrı gerçekleştirim sunar: karma tabanlı (HashMap, HashSet) ve sıralı (BTreeMap, BTreeSet). İkisi de aynı temel işlemleri — ekleme, sorgulama, silme — destekler ve aynı temel adları taşır: insert, contains_key / contains, len. Bir kaynak, HashMap yerine BTreeMap yazarak da çoğu zaman değişmeden çalışmaya devam eder. Aralarındaki fark, işlemlerin sonucunda değil, yapının gezinme sırasında ortaya çıkar — ve bu ders tam olarak bu tek farkı ölçüyor.

Küme Eklemek: bool Dönüşü İki Yapıda da Aynıdır

Bir kümeye eleman eklemenin dönüş tipi booldur: eleman gerçekten yeni eklendiyse true, küme zaten o elemanı taşıyorduysa false. Bu davranış, sıralı kümede de karma kümede de aynıdır — sıra güvencesinden bağımsız bir ölçümdür.

// kume_ekleme_bool.rs — kume eklemek bool doner, sira guvencesinden bagimsiz
use std::collections::{BTreeSet, HashSet};

fn main() {
    let anahtarlar = ["ucgen", "cember", "dikdortgen", "kare"];

    let mut sirali_kume: BTreeSet<&str> = BTreeSet::new();
    for a in anahtarlar {
        let eklendi = sirali_kume.insert(a);
        println!("{:<30}: {}", format!("sirali_kume.insert({})", a), eklendi);
    }
    let tekrar_sirali = sirali_kume.insert("cember");
    println!("{:<30}: {}", "sirali_kume.insert(cember) 2.", tekrar_sirali);

    println!();
    let mut karma_kume: HashSet<&str> = HashSet::new();
    for a in anahtarlar {
        let eklendi = karma_kume.insert(a);
        println!("{:<30}: {}", format!("karma_kume.insert({})", a), eklendi);
    }
    let tekrar_karma = karma_kume.insert("cember");
    println!("{:<30}: {}", "karma_kume.insert(cember) 2.", tekrar_karma);
}

sirali_kume.insert(ucgen)     : true
sirali_kume.insert(cember)    : true
sirali_kume.insert(dikdortgen): true
sirali_kume.insert(kare)      : true
sirali_kume.insert(cember) 2. : false

karma_kume.insert(ucgen)      : true
karma_kume.insert(cember)     : true
karma_kume.insert(dikdortgen) : true
karma_kume.insert(kare)       : true
karma_kume.insert(cember) 2.  : false

Dört farklı anahtar hem sıralı kümeye hem karma kümeye eklendi; her iki yapıda da ilk dört ekleme true, "cember"in tekrar eklenmesi false verdi. Bu koşum, kümenin hangi sırayla dolaşılacağını hiç sormuyor — yalnızca “bu eleman zaten var mıydı” sorusuna yanıt arıyor ve bu soru bir kümenin iç sırasından tamamen bağımsız.

Bu, Numaralandırmalar dersinde ölçülen “varyant sayısı durum sayısı değildir” ayrımına benzer bir düzenektir: bool dönüşü, kümenin şu anda kaç eleman taşıdığına ya da onları nasıl sakladığına bakmadan, tek bir sorunun yanıtını taşıyor. sirali_kume ile karma_kume aynı dört anahtarı, aynı sırayla aldı ve ikisi de birbirinden bağımsız olarak aynı true, true, true, true, false dizisini üretti — biri sıralı tutuyor olmasına, öbürü sıralamıyor olmasına rağmen. Bu, kümeye eklemenin, kümenin gezinme düzeninden önce karar verilen bir soru olduğunu gösteriyor: eleman zaten var mı, yok mu.

RV16. — “Küme eklemenin bool dönüşünün sıra güvencesinden bağımsız olduğu” iddiası, aynı dört anahtarın hem BTreeSete hem HashSete eklenip ikisinin de birebir aynı true/false dizisini vermesiyle ölçülüyor. sirali_kume ile karma_kume, kaynak düzeyinde yalnızca tip adlarında farklı — kalan her satır aynı; buna rağmen sonuçlar satır satır örtüşüyor. Bu örtüşme beş ayrı koşumda da bozulmadı, çünkü insertin bool dönüşü elemanın kümede olup olmadığına bakar, kümenin bellekte nasıl dizildiğine değil.

Sıralı Sözlüğün Gezinmesi Her Koşumda Aynıdır

BTreeMap, anahtarları her zaman sıralı tutan bir sözlüktür. Bu sıra, ekleme sırasından değil anahtarların kendi değerlerinden gelir: hangi sırayla eklenirse eklensin, gezinme her zaman küçükten büyüğe doğru gerçekleşir.

// sirali_sozluk_gezinme.rs — sirali sozlugun gezinmesi her kosumda ayni
use std::collections::BTreeMap;

fn main() {
    let anahtarlar = ["ucgen", "cember", "dikdortgen", "kare"];
    let mut sirali_sozluk: BTreeMap<&str, i32> = BTreeMap::new();
    for (i, a) in anahtarlar.iter().enumerate() {
        sirali_sozluk.insert(a, i as i32);
    }
    for (anahtar, deger) in &sirali_sozluk {
        println!("{:<27}: {}", format!("sirali_sozluk[{}]", anahtar), deger);
    }
}

sirali_sozluk[cember]      : 1
sirali_sozluk[dikdortgen]  : 2
sirali_sozluk[kare]        : 3
sirali_sozluk[ucgen]       : 0

Anahtarlar kaynakta "ucgen", "cember", "dikdortgen", "kare" sırasıyla eklendi — ucgen ilk, kare son. Ama çıktıda görünen sıra bambaşka: cember, dikdortgen, kare, ucgen — alfabetik sıra. BTreeMap üzerinde dolaşan bir for döngüsü, ekleme sırasını değil, anahtarların kendi aralarındaki sırasını izliyor.

Bu, Vecin davranışından tamamen farklı bir garantidir. Koleksiyonlar dersinde ölçüldüğü gibi, bir büyüyen diziyi dolaşmak her zaman ekleme sırasını korur — üçüncü eklenen öğe üçüncü sırada kalır. BTreeMap bu garantiyi vermiyor; anahtarları ekleme sırasından tamamen koparıp kendi aralarındaki büyüklük ilişkisine göre yeniden diziyor. Bu yeniden dizilme, tek bir eklemede bile geçerlidir: sirali_sozluk içine beşinci bir anahtar, örneğin "elips", eklenseydi, bu anahtar listenin sonuna değil — alfabetik sıradaki yerine, "dikdortgen" ile "kare" arasına — yerleşirdi.

RV17. — “Sıralı sözlüğün gezinmesinin her koşumda aynı olduğu” iddiası burada ölçülmüyor değil, aksine bu dersin kod doğrulaması bu iddianın ta kendisine dayanıyor: yukarıdaki çıktı, bu dersin bir kez koşturulup kaydedilen sabit metniyle karşılaştırılıyor. Eğer BTreeMapin gezinmesi koşumdan koşuma değişseydi, bu karşılaştırma er ya da geç tutmazdı. Kaydedilen dört satırın sırası — cember, dikdortgen, kare, ucgen — anahtarların alfabetik sırasıyla birebir örtüşüyor; bu, BTreeMapin içindeki gerçek düzenin de bu sırayı izlediğinin dolaylı kanıtı.

Bu belirlenimcilik, kursun bütün derslerinde zaten örtük olarak varsayılan bir kuraldı: her koşumun, kaynağın bu dosyaya yazıldığı sırada üretilen çıktıyla birebir aynı sonucu vermesi gerekiyordu. BTreeMap bu kuralı kendiliğinden karşılıyor; ekleme sırası ne olursa olsun, aynı anahtar kümesi her zaman aynı gezinme sırasını üretiyor. Bu, BTreeMapi yalnızca “sıralı” değil, aynı zamanda bu kursun genel gereksinimini karşılayan tek sözlük gerçekleştirimi yapıyor.

Karma Sözlük Doğrudan Gezilmez — Kuralın Kendisi

HashMapin gezinme sırası, anahtarların değerinden değil, o çalışma anındaki karma işlevinin (hash function) başlangıç durumundan gelir; bu durum her program başlangıcında yeniden ve rastgele belirlenir. Bu rastgelelik bir eksiklik değil, bilinçli bir tasarım kararıdır: sabit bir karma işlevi kullanan bir sözlük, kötü niyetle seçilmiş girdilerle kasıtlı olarak yavaşlatılabilir — saldırgan, hangi anahtarların aynı iç kovaya düşeceğini önceden hesaplayabilir. Karma işlevin başlangıç durumunu her çalıştırmada yeniden ve rastgele seçmek, bu önceden hesaplamayı imkânsız kılar; bunun bedeli, aynı programın iki ayrı çalıştırmasının aynı anahtarlar için farklı bir gezinme sırası üretebilmesidir.

Aynı dört anahtar, aynı sırayla eklense bile, bir koşumda bir sırada, başka bir koşumda başka bir sırada dolaşılabilir. Kurs boyunca izlenen kural tam burada, kendi gerekçesiyle birlikte yazılabilir: bir karma sözlük ya da karma küme, hiçbir derste doğrudan yazdırılmaz ya da olduğu gibi dolaşılmaz — çünkü basılan çıktı bu derste doğrulanabilse bile, bir sonraki koşumda aynı kalacağının hiçbir garantisi yoktur.

Bu kural, karma sözlüğü kullanılamaz yapmıyor; yalnızca hangi işlemlerin güvenli olduğunu sınırlıyor. Belirli bir anahtarla değer okumak, bir anahtarın var olup olmadığını sormak, toplam eleman sayısını almak — bunların hiçbiri gezinme sırasına bağlı değildir ve her koşumda aynı sonucu verir. Koleksiyonlar dersinde karşılaşılan insertin dönüş değeri de bu güvenli kümeye girer: bir anahtarın önceki değerini Some/None olarak okumak, o anahtarın sözlükte kaçıncı sırada durduğuyla ilgilenmez.

Güvenli olmayan tek işlem, sözlüğün tamamının ham sırayla dolaşılıp bu sıranın bir sonuç olarak kullanılmasıdır — bir for döngüsüyle bütün çiftleri gezip bunları oldukları gibi yazdırmak, ya da ilk ya da son elemanı “gezinme sırasındaki konumuna” göre almak. Bu derste ve önceki derste her karma yapı, ya tek tek anahtarlarla sorgulandı ya da dolaşılmadan önce anahtarları ayrıca sıralandı; hiçbir yerde ham gezinme sırası bir sonuç olarak kullanılmadı.

// karma_sozluk_tek_anahtar.rs — karma sozluk dogrudan gezilmez, tek anahtar deterministiktir
use std::collections::HashMap;

fn main() {
    let anahtarlar = ["ucgen", "cember", "dikdortgen", "kare"];
    let mut karma_sozluk: HashMap<&str, i32> = HashMap::new();
    for (i, a) in anahtarlar.iter().enumerate() {
        karma_sozluk.insert(a, i as i32);
    }
    println!("{:<28}: {}", "karma_sozluk[cember]", karma_sozluk["cember"]);
    println!("{:<28}: {}", "icerir mi (kare)", karma_sozluk.contains_key("kare"));
    println!("{:<28}: {}", "uzunluk", karma_sozluk.len());
}

karma_sozluk[cember]        : 1
icerir mi (kare)            : true
uzunluk                     : 4

Bu koşumda karma_sozluk hiçbir yerde dolaşılmıyor; yalnızca tek bir anahtarla sorgulanıyor (karma_sozluk["cember"]), bir anahtarın varlığı soruluyor (contains_key) ve toplam uzunluk okunuyor (len()). Üçü de, sözlüğün içindeki elemanların hangi sırayla dizildiğinden tamamen bağımsız sonuçlar; "cember" her zaman 1 değerini taşır, sözlükte kaçıncı sırada durduğuna bakılmaksızın.

RV18. — “Karma sözlüğün tek anahtar sorgusunun deterministik olduğu” iddiası, bu koşumun beş ayrı çalıştırmada birebir aynı üç satırı vermesiyle ölçülüyor. Bu, BTreeMap örneğindeki gezinme testinden farklı bir ölçüm: orada bütün sözlük dolaşılıp sırası denetlendi, burada sözlük hiç dolaşılmadan yalnızca noktasal erişimler denetlendi. İki ölçüm birlikte, “hangi işlemler güvenli, hangileri değil” sınırını tam olarak çiziyor.

Bu sınırın pratik sonucu şudur: bir HashMap kullanan bir kaynağın, sözlüğü nasıl kullandığına bakılmadan “güvensiz” ilan edilmesi doğru olmaz. karma_sozluk_tek_anahtar.rs tam da HashMapin en yaygın kullanım biçimini gösteriyor — belirli bir anahtarla değere ulaşmak, bir anahtarın varlığını sormak — ve bu biçimin hiçbir yerinde gezinme sırasına ihtiyaç yok. Riskli olan, bir sözlüğün tamamının sırasını anlamlı sayan kodun yazılmasıdır; bu derste yazılan kodun hiçbiri bunu yapmıyor.

Sınırlayıcı Ölçüm: Sıra Güvencesi Ücretsiz Değildir

Bir sıralı sözlüğün ya da sıralı kümenin sırayı koruyabilmesi için, anahtar tipinin bir koşulu karşılaması gerekir: iki anahtar arasında her zaman “hangisi önce gelir” sorusuna bir yanıt verilebilmelidir. Bu koşula sıralanabilirlik koşulu denir ve her tip bunu karşılamaz.

Yapılar dersinde tanımlanan Nokta tipi (x: i32, y: i32) bu koşulu karşılamaz. İki Nokta değeri arasında “hangisi önce gelir” sorusunun tek bir yanıtı yoktur — xe göre mi sıralanmalı, yye göre mi, yoksa ikisinin bir bileşimine göre mi? Rust’ın standart kitaplığı bu kararı Nokta için otomatik vermez; Nokta değerlerini bir BTreeSete ya da bir BTreeMapin anahtarı olarak koymaya çalışan bir kaynak, sıralanabilirlik koşulu karşılanmadığı için derlenmez. Bu ders böyle bir kaynağı kod bloğuna koymuyor — derlenmeyen kaynak bloğa girmiyor — ama ret burada tarif edilebilir: derleyici, Nokta için iki değerin karşılaştırılma yolunu bilmediğini söyler.

RV19. — “Sıra güvencesinin ücretsiz olmadığı” iddiası burada olumlu yönden ölçülüyor: bu derste kullanılan bütün anahtarlar (&str) sıralanabilirlik koşulunu zaten karşılıyor — dizgiler alfabetik olarak karşılaştırılabilir, tam sayılar büyüklüklerine göre karşılaştırılabilir. sirali_sozluk_gezinme.rsin çalışıp beklenen çıktıyı vermesi, bu koşulun &str için sağlandığının dolaylı kanıtı; Nokta gibi bu koşulu karşılamayan bir tipin aynı yapıya girememesi ise koşulun isteğe bağlı değil zorunlu olduğunu gösteriyor.

Karma yapılar farklı bir koşul ister: anahtarın karşılaştırılabilir olması değil, bir karma değere dönüştürülebilir olması gerekir. Nokta için bu koşul da otomatik karşılanmaz. İki koşul birbirinin yerine geçmez — bir tip birini karşılayıp öbürünü karşılamayabilir — ama ikisinin de ortak noktası, “boş” bir tip üzerinde otomatik olarak sağlanmamalarıdır; standart kitaplığın kendi tipleri (i32, &str gibi) bu koşulları zaten taşır, kullanıcı tanımlı bir tip ise bunu ayrıca kazanmak zorundadır.

Bu, Yapılar dersinde ölçülen bir başka farkı da hatırlatıyor: Nokta { x: 3, y: 4 } ile Nokta { y: 4, x: 3 } alan alan eşit olsa da, Nokta tipinin kendisi henüz “iki değer birbirine eşit mi” sorusuna otomatik bir yanıt taşımıyordu — o derste bu karşılaştırma d.x == e.x && d.y == e.y yazılarak elle yapıldı, d == e yazılarak değil. Sıralanabilirlik ve karma alınabilirlik koşullarının ikisi de, önce böyle bir eşitlik koşulunu gerektirir: iki değerin ne zaman “aynı” sayılacağı bilinmeden, ne sıralama ne de karma değeri hesaplanabilir. Nokta bu eşitlik koşulunu bile henüz otomatik taşımadığından, sıralı ya da karma bir yapıya doğrudan giremiyor.

Bir tipin bu koşulları nasıl kazandığı — hangi anahtar sözcük ya da bildirim eklenerek — bu dersin kapsamı dışında kalıyor; burada yalnızca koşulun var olduğu ve her tipte otomatik sağlanmadığı ölçülüyor. Standart kitaplığın kendi tipleri bu koşulları baştan taşıdığı için, bu kursun bütün derslerinde kullanılan anahtarlar — tam sayılar, dizgiler — hiçbir yerde bu sınırla karşılaşmadı; sınır yalnızca Nokta gibi, alanları programcı tarafından tanımlanmış bir tip söz konusu olduğunda görünür hâle geliyor.

Beş dersin ortak sonucu şudur: Rust’ın veri modelleme araçları — yapı, numaralandırma, desen eşleme, koleksiyon, sıralı ve karma yapı — hepsi aynı iki soruya farklı açılardan yanıt verdi. Kaynakta yazılan bir şey bir değer mi üretiyor, yoksa yalnızca bir ad mı bildiriyor; ve bir işlemin sonucu, o işlemin dönüş tipinden mi okunuyor, yoksa işin “ne yaptığından” mı tahmin ediliyor. İkinci soru bu son derste özellikle belirginleşti: insertin bool dönmesi bir kümenin sıra güvencesiyle hiç ilgilenmiyor; bir sözlüğün gezinme sırası ise anahtarın kendi tipine bağlı bir koşulun ürünü.

Özet

• Küme eklemenin bool dönüşü, sıralı ve karma kümede aynı davranır; sıra güvencesinden bağımsız bir ölçümdür. Dönüş değeri taşıdığı için ekleme burada bir ifadedir.
• Sıralı sözlüğün (BTreeMap) gezinmesi anahtarların kendi sırasını izler ve her koşumda aynıdır.
• Karma sözlük (HashMap) hiçbir derste doğrudan yazdırılmaz ya da dolaşılmaz; yalnızca tek anahtar sorgusu, varlık denetimi ve uzunluk gibi sıradan bağımsız işlemler kullanılır.
• Sıra güvencesi bir koşula bağlıdır: anahtar tipinin sıralanabilirlik koşulunu karşılaması gerekir; her tip bunu otomatik karşılamaz.

Sonraki Adım

Beş veri modelleme dersi burada kapanıyor: yapılar, numaralandırmalar, desen eşleme, koleksiyonlar, sıralı ve küme yapıları — beş ders boyunca hep aynı soru soruldu, kaynakta yazılan bir şey bir değer mi üretiyor, yoksa yalnızca bir ad mı bildiriyor. Bu beş dersin hiçbiri, bu tiplerin ve fonksiyonların kaynağın neresinde görünebileceğini sormadı — bir yapı bildirimi, bir sözlük değişkeni, bir fonksiyon, hangi sınırın içinde tanımlı ve o sınırın dışından nasıl görülüyor? Kursun kapanış dersi bu soruyu açıyor: modüller ve kasalar, bütün bunların hangi sınırın içinde göründüğünü belirliyor.