Hızlı Arama Zamanlı Kaplar-2

Kaldığımız yerden devam ediyoruz. Dizimizin ikinci ve son yazısında, ilk yazıyı okuyanlara tanıdık gelecek aşağıdaki kısmi sıradüzenin eşlemler için dengeli ağaç temelli gerçekleştirim sağlayan kısmına değineceğiz. Buraya ilk yazıyı okumadan yolunuz düşüp de kavramsal olarak kendinizi hazır hissetmiyorsanız, size tavsiyem ilk yazıya bir göz atıp daha sonra buraya dönmeniz.🔎

• İlk yazı🔎
• TreeMap sınıfı
• SortedMap arayüzü
• NavigableMap arayüzü
• Uzmanlaşmış eşlemler

TreeMap Sınıfı

Eşlem yapısı, altyapıda anahtar bilgisine göre oluşturulan bir dengeli ağaç kullanılarak da gerçekleştirilebilir. Bu yol izlenecek olursa çözüm, eşleme gönderilen iletilerin dengeli ağaca yönlendirilmesiyle sağlanır. Bu tür ağaçların ekleme, silme ve sorgulama işlemlerini O(lgn) zamanda yapması nedeniyle, anılan işlemlerin eşlemde de O(lgn) performanslı gerçekleştirilmesi mümkün olacaktır. Bu noktadan hareketle, standart Java kitaplığındaki TreeMap sınıfı eşlem yapısını kırmızı-siyah ağaçlardan yararlanarak gerçekleştirmiştir.¹

Altyapıda dengeli ağaç kullanılıyor olması, TreeMap sınıfının pek çok ekstra iletiyi düşük maliyetli bir gerçekleştirimle desteklemesini olanaklı kılar. Bunun başlıca nedeni, kök-ortada (İng., inorder) dolaşmanın ağaç içindeki bilgileri anahtara göre sıralı vermesidir. Bu sayede eşlem içeriği anahtara göre sıralı bir şekilde oluşturulabilir; ayrıca sıralama aşamasına gerek yoktur. Bunun doğal bir sonucu olarak, TreeMap sınıfı SortedMap ve NavigableMap arayüzlerinde listelenen eşlem içeriğinin uç değerleri ve dilimlerine dair iletileri de destekler. Ayrıca, Map🔎 arayüzünde tanımlanmış olan entrySet, keySet ve values iletilerinin gerçekleştirimleri de sonuçlarını anahtara göre sıralı değerlerden oluşan birer kap içinde döndürürler.

Kök-ortada dolaşmanın düğümleri anahtara göre sıralı üretebilmesi, anahtar-tutanak çiftlerinin altyapıdaki dengeli ağacın anahtar değerine göre belirlenen uygun düğümlerine eklenmeleri ile mümkün olur. Bu ise, eklenmekte olan anahtar değerinin eşlemde var olanların bir kısmı ile karşılaştırılmasıyla olanaklıdır. Benzer şekilde, silme ve sorgulama işlemlerinde de söz konusu anahtara karşılık gelen düğümün karşılaştırma işlemleri yardımıyla saptanıp işlemin tamamlanması mümkün olacaktır. Bütün bunlar, anahtar türünün karşılaştırılabilir olması zorunluluğunu beraberinde getirir. Yani, anahtar türü ya Comparable kategorisinde olmalıdır ya da java.util.Comparator arayüzünü gerçekleştirilen bir sınıf anahtar türüne ait nesneleri karşılaştırma desteğini sağlamalıdır. Gelin bu konuyu TreeMap sınıfının yapıcılarına açıklık getirerek anlamaya çalışalım.

...
import java.util.TreeMap;

public class Eşlemler {
  public static void main(String[] ksa) {
    ...
    Map<String, String> sözlük3 = new TreeMap<>();
    sözlüğüDoldur(sözlük3);
    System.out.println("Sözlük içeriği: " + sözlük3);
    ...
  } // void main(String[]) sonu
  ...
} // Eşlemler sınıfının sonu

Yukarıdaki kod parçasının işaretli satırındaki yapıcı çağrısı sonucunda yaratılan eşlem, karşılaştırma amacıyla, herhangi bir bilgi verilmediği için, anahtar bilgilerinin üyesi olduğu String sınıfınca gerçekleştirilen Comparable arayüzündeki compareTo iletisini kullanacaktır. Bunun sonucunda, sözlük3 adlı eşlemi standart çıktıya basan komut, sözcükleri büyük harfler önce olmak üzere alfabetik sıraya göre dizecektir. Ayrıca, bu iş yapılırken Türkçe'ye özel harfler beklediğimiz sıranın aksine sona doğru yer alacaktır. Bu sorunun çözümü, Türkçe'ye özel bir sözcük karşılaştırma sınıfı gerçekleştirmektir.

...
import java.text.Collator;
import java.util.Comparator;
import java.util.Locale;

public class Eşlemler {
  public static void main(String[] ksa) {
    ...
    Map<String, String> trSözlük =
      new TreeMap<>(new TürkçeSözcükKarşılaştırıcı());
    sözlüğüDoldur(trSözlük);
    System.out.println("Sözlük içeriği: " + trSözlük);
    ...
  } // void main(String[]) sonu
  ...
} // Eşlemler sınıfının sonu

class TürkçeSözcükKarşılaştırıcı implements Comparator<String> {
  private final static Collator trKarşılaştırıcısı =
    Collator.getInstance(new Locale("tr"));

  public int compare(String s1, String s2) {
    return trKarşılaştırıcısı.compare(s1.toLowerCase(), s2.toLowerCase());
  }
} // TürkçeSözcükKarşılaştırıcı sınıfının sonu

Yukarıdaki kod parçasının işaretli satırları, dengeli ağaç altyapılı boş bir eşlem yaratırken ağacın, ve dolayısıyla eşlemin, oluşturulması amacıyla kullanılacak karşılaştırma ölçütünün argümanda geçirilen nesne tarafından belirlendiğini söylemektedir. Bu nesnenin sınıfına bakacak olursak, sözcüklerin büyük-küçük ayrımı yapılmaksızın Türkçe alfabeye göre karşılaştırılacağını ve sıranın Türkçe'den alıştığımız şekilde oluşacağını görürüz.

TreeMap sınıfının diğer yapıcıları kopyalayan yapıcı olarak çalışır. Bunlardan yegâne argümanında SortedMap arayüzünü gerçekleştiren bir eşlem alanı, yaratılmakta olan eşlemi argümanda geçirilenin içeriği ile dolduracaktır. Birbirinden bağımsız iki eşlem oluşmasına yol açan bu işlemin sonrasında yeni eşleme uygulanacak işlemler argümandaki eşlemin kullandığı karşılaştırma ölçütü ile aynı olacaktır. Sonuncu yapıcı da buna benzer bir mantıkla çalışır. Bu sefer, kopyalamanın kaynağı olan eşlem Map arayüzünü gerçekleştiren herhangi bir eşlem olabilir. Yani, argüman olarak TreeMap nesnesi geçirilebileceği gibi, diğer altbölümlerde göreceğimiz sınıfların nesneleri de geçirilebilir ki, bu yaratılmakta olan eşlemin taklit edeceği bir karşılaştırma ölçütünün olmayabileceği anlamına gelir. Dolayısıyla, bu yapıcı çağrısının kullanımı sonrasında yeni yaratılan eşlemin içeriğinin düzenlenmesinde ölçüt olarak anahtar sınıfının compareTo iletisi kullanılacaktır.

Yaratılan eşlemin içeriğini var olan bir eşlemden alırken farklı bir ölçüt kullanmak olanaklı değil mi, diye sorabilirsiniz. Hemen sorunuzun yanıtının olumlu olduğunu söyleyelim. Bunun için yapmanız gereken, eşlemi uygun bir karşılaştırma ölçütü ile boş yaratıp putAll iletisi ile doldurmaktan ibarettir.

...
public class Eşlemler {
  public static void main(String[] ksa) {
    ...
    Map<String, String> sözlük4 =
      new TreeMap<>(new TürkçeSözcükKarşılaştırıcı());
    sözlük4.putAll(sözlük3);
    System.out.println("Sözlük içeriği: " + sözlük4);
    ...
  } // void main(String[]) sonu
  ...
} // Eşlemler sınıfının sonu

SortedMap Arayüzü

Gelelim, SortedMap arayüzünde olup TreeMap sınıfınca gerçekleştirilen iletilere. Bunlardan comparator, hedef eşlemin hangi ölçüte göre düzenlendiğini döndürür. Ancak, aklınızda olsun: bu iletinin null döndürmesi herhangi bir ölçüt kullanılmadığı anlamına gelmez; sadece, Comparable arayüzünü destekleyen anahtar sınıfının compareTo gerçekleştiriminin kullanıldığı anlamına gelir.

SortedMap arayüzünde listelenen diğer iletiler uç değer ve eşlem dilimi döndürmek suretiyle görüntü sağlayanlar olmak üzere iki grupta toplanabilir. TreeMap türlü eşlemlerin dengeli ağaçlarla temsil edilmesi sayesinde ucuz maliyetlerle gerçekleştirilebilen bu iletilerden firstKey ve lastKey, sırasıyla, hedef eşlemin ilk ve son anahtar bilgisini döndürür. İkinci gruptaki iletiler, argüman veya argümanlarında belirtilen anahtar bilgileri ile belirlenen anahtar-tutanak çiftlerinden oluşan ve SortedMap tutacağı ile gösterilen eşlem görüntüleri döndürür. Bunlardan subMap, ilk argümanı ile başlayıp ikinci argümanının hemen öncesinde biten eşlem dilimini döndürürken, headMap başlangıçtan argümandaki anahtarın öncesine kadar olan dilimi, tailMap ise argümanındaki anahtar ile başlayıp eşlemin sonuna kadar giden dilimi döndürür.

SortedMap<String, String> adanbye = trSözlük.subMap("a", "b"); // "b" hariç!
SortedMap<String, String> jyeKadar = trSözlük.headMap("j");
SortedMap<String, String> jdenSonra = trSözlük.tailMap("j");

Her üç iletinin de, görüntüleme grubundaki diğer iletiler gibi, yeni bir eşlem yaratmaktansa ileti alıcının gösterdiği eşlemi paylaştırdığı unutulmamalıdır. Bundan dolayı, yukarıdaki kodun işlenmesi sonrasında trSözlük dört farklı tutacak yoluyla değiştirilebilecektir. Mesela, adanbye tutacağı ile gösterilen dilimin herhangi bir eşlemesinin değiştirilmesi trSözlük yoluyla gösterilen eşlemi de etkileyecektir. Ancak; trSözlük yoluyla sözlüğe "eşlem" anahtarı ve anlamının girilmesi sadece jyeKadar ile temsil edilen dilimi etkileyecektir, diğerlerini değil. Ayrıca, hiçbir eşlemin geçerli olduğu dilimin dışındaki herhangi bir anahtara dair bilgiyi eklemekte kullanılamayacağı da bilinmelidir. Örneğin, jdenSonra aracılığıyla "eşlem" anahtarı ve ilişkin anlamın girilmeye çalışılması IllegalArgumentException ayrıksı durumuna neden olacaktır.

NavigableMap Arayüzü

Java SE6 ile birlikte eklenen NavigableMap arayüzü, SortedMap'tekilere benzer iletiler sunar; tanımlanan işlevsellik uç değer işleme ve görüntüleme iletilerinden oluşur. Örneğin, SortedMap'ten kalıtlanan firstKey ve lastKey iletilerine ceilingKey, floorKey, higherKey ve lowerKey iletileri eklenmiştir. ceilingKey argümanındaki anahtara eşit veya ondan büyük ilk anahtar değerini döndürürken, floorKey argümanındaki anahtara eşit veya ondan küçük son anahtar değerini döndürür; higherKey ve lowerKey iletileri ise eşitlik denetimi yapmayan, sırasıyla, ceilingKey ve floorKey gibi çalışır.

String cVeyaSonrasındakiİlkSözcük = trSözlük.ceilingKey("c");
String cSonrasındakiİlkSözcük = trSözlük.higherKey("c");
String cVeyaÖncesindekiSonSözcük = trSözlük.floorKey("c");
String cÖncesindekiSonSözcük = trSözlük.lowerKey("c");

Bir diğer ileti grubu, yukarıda adını andığımız iletilerle aynı şekilde çalışmakla birlikte anahtarı döndürmektense Map.Entry türlü bir tutacak aracılığıyla gösterilen eşlemeyi sarmalayan nesneyi döndürür. Bu iletilerin adları, ilişkin iletinin adındaki Key kısmı yerine Entry koymakla elde edilebilir. İstenecek olursa, bu noktadan sonra sarmalanan nesne Map.Entry arayüzündeki iletilerle sorgulanabilir.

NavigableMap arayüzünce eklenen görüntüleme iletilerinden olan descendingKeySet, adının da haykırdığı gibi hedef eşlemdeki anahtarları bir küme içinde döndürür. Ancak, döndürülen kümenin dolaşılması anahtarları keySet'in döndürdüğünün tersi sırada verecektir. Anahtarlara dair görüntüyü döndüren bir diğer ileti olan navigableKeySet, keySet'e daha da çok benzer; iki iletinin döndürdükleri kümenin içeriği ve sırası tümüyle aynıdır. Ne var ki, keySet Set dönüş türüne sahipken, navigableKeySet NavigableSet döndürür.

Tanıdık gelecek bir diğer ileti grubu dilim döndüren görüntüleme iletileridir. NavigableMap arayüzü, SortedMap'ten kalıtladıklarına ek olarak, uç değerlerin dahil edilip edilmeyeceğini belirleyen ekstra parametrelere sahip headMap, subMap ve tailMap adlı üç ileti destekler. Söz konusu iletiler, her bir uç değeri takiben geçirilen boolean değerlerle döndürülecek dilimin uç noktalarının nasıl ele alınacağını belirler; true geçirilmesi uç noktayı sonuca katarken, false geçirilmesi dışlar. Bu iletilerin bir diğer farkı, SortedMap'ten kalıtlanan aynı adlı iletilerin SortedMap döndürmesine karşılık, NavigableMap döndürmeleridir.

Bir önceki paragrafta anılanlarla ele alınabilecek bir ileti de, hedef eşlemi döndürülen NavigableMap tutacağı vasıtasıyla ters sırada görüntülemeye yarayan descendingMap'tir. Yani, sözlüğümüzü ters sırada işlemek isteyecek olursak, yapmamız gereken aşağıdaki tanımlamadan ibarettir.

NavigableMap<String, String> trSözlük2 = trSözlük.descendingMap();

Değineceğimiz son iletiler, uç değerleri denetleyerek [var olmaları halinde] silen pollFirstEntry ve pollLastEntry iletileridir. pollFirstEntry, hedef eşlemde ilk sırada bulunan eşlemeyi yoklayıp silerken, pollLastEntry son eşlemeyi siler. Her iki ileti de sildikleri eşlemeye dair bilgiyi Map.Entry tutacağı ile döndürürken, eşlemin boş olması halinde null döndürülür.

Uzmanlaşmış Eşlemler

Veri Kapları Çerçevesi, yukarıda anlatılanlara ek olarak içerebileceği anahtarların niteliklerinden dolayı özel bir şekilde gerçekleştirilmek suretiyle daha yüksek performanslı kullanılabilecek iki eşlem sınıfı daha sunar: EnumMap ve WeakHashMap.

Anahtar türünün bir sabit listesi (İng,. enum) olması durumunda, eşlemdeki anahtar sayısı ilişkin sabit listesindeki simgesel sabitlerin sayısı ile sınırlanacaktır. Bu gibi bir durumda, anlattığımız eşlem sınıflarından birini kullanmaktansa, anahtarlarının sabit listesi değerleri olduğunu varsayarak eniyileme yapan EnumMap sınıfının kullanılması daha doğru olacaktır.

WeakHashMap sınıfı da, tıpkı HashMap gibi, kıyım tablosu temelli bir gerçekleştirim sağlar. Ancak; WeakHashMap içine konulabilecek anahtar değerleri WeakReference türünden olmak zorundadır.² Bu ise tutanakların, eşlem kullanıcısının göndereceği remove iletilerinin yanısıra, çöp toplayıcısının vereceği bir karar sonrasında [kullanıcı kontrolunun dışında] usulca silinebileceği anlamına gelir. Henüz silinmesi istenmeyen bir tutanağın bu sondan korunması kuvvetli bir tutacak ile gösterilmesi sayesinde sağlanabilir.

İlk Yazı
Doğrusal Veri Kapları
Değişken Uzunluklu Diziler: Vector

---

1. Kırmızı-siyah ağaçlar, B-tree ailesindeki dengeli ağaçlardan [azami] dört düğümlü olanların, ki bu ağaçlara tepeden aşağıya 2-3-4'lü ağaçlar da denir, ikili ağaç şeklinde gerçekleştirilmiş biçimleridir.↑
2. java.lang.ref paketinin Reference köklü sıradüzenindeki sınıfların tutacakları, bir nesne göstermektense bir başka nesnenin tutacağını sarmalayarak onu nesneye çevirir. JSM tarafından özel muameleye tabii tutulan bu nesnelerin kullanım amacı, çöp toplayıcı ile etkileşerek kaynak yönetim sürecine uygulama gereksinimlerine göre müdahele edilmesini olanaklı kılmaktır.↑