... bütün sözlük

• Kitaplar
• Forum


• Tanıtım
• Makaleler
• Sunumlar
• Kurulum

• Digital Mars
• Newsgroups
• Programming in D
• Books

• RSS Beslemesi
• İletişim
• Hakları

Eşleme Tabloları

Eşleme tabloları üst düzey dillerin hepsinde bulunan veri yapılarıdır. Onları program içine gömülen minik veri tabanları olarak düşünülebilirsiniz. Programlarda çok kullanılan ve çok hızlı veri yapılarıdır.

Dizileri "elemanları yan yana duran topluluk" olarak tanımlamış ve elemanlarına indeksle erişildiğini görmüştük. Örneğin haftanın günlerinin isimlerini tutan bir dizi şöyle tanımlanabilir:

    string[] günİsimleri =
        [ "Pazartesi", "Salı", "Çarşamba", "Perşembe",
          "Cuma", "Cumartesi", "Pazar" ];

Belirli bir günün ismi o diziyi kullanarak şöyle yazdırılabilir:

    writeln(günİsimleri[1]);   // "Salı" yazar

Dizilerin elemanları sıra numarasıyla (indeksle) eriştiriyor olmaları, onların indekslerle elemanları eşleştirdikleri olarak açıklanabilir.

Ancak, diziler indeks türü olarak yalnızca tamsayı türler kullanabilirler. Örneğin "Salı" dizgisi bulunduğunda onun haftanın 1 numaralı günü olduğunu söyleyemezler çünkü "Salı" gibi bir dizgiyi indeks olarak kullanamazlar.

Eşleme tablolarının kullanışlılığı işte bu gibi durumlarda ortaya çıkar. Eşleme tabloları elemanlara yalnızca numara ile değil, herhangi bir türle erişilen veri yapılarıdır. Görevleri, herhangi bir indeks türündeki bir değeri herhangi başka bir türdeki değer ile eşlemektir. Eşleme tabloları elemanlarını indeks-değer çiftleri olarak tutarlar. Aşağıda eleman yazdığım her yerde bir indeks-değer çiftini kastedeceğim.

Eşleme tabloları arka planda hash table veri yapısını kullandıkları için algoritma karmaşıklığı açısından dizilerden geri kalmazlar: son derece hızlı topluluklardır. Bunun anlamı, içlerindeki eleman sayısından bağımsız olarak, hemen her zaman için sabit zamanda erişim sağlamalarıdır.

Bu kadar hızlı çalışmalarının bedeli, içlerindeki elemanların sıraları konusunda bir şey bilinemiyor olmasıdır. Elemanların ne dizilerdeki gibi yan yana olduklarını, ne de örneğin küçükten büyüğe doğru sıralandıklarını söyleyebiliriz.

Diziler indeks değerleri için yer harcamazlar. Dizi elemanları bellekte yan yana durduklarından her elemanın indeks değeri onun başlangıçtan kaç eleman ötede olduğudur.

Öte yandan, eşleme tabloları hem indeksleri hem de değerleri saklamak zorundadırlar. Bu fark eşleme tablolarının bellekte daha fazla yer tutmalarına neden olsa da, onların seyrek indeks değerleri kullanabilmelerini de sağlar. Örneğin, 0 ve 999 gibi iki değer için diziler 1000 eleman saklamak zorunda oldukları halde eşleme tabloları yalnızca iki eleman saklarlar.

Tanımlama

Eşleme tablosu tanımı dizi tanımına çok benzer. Tek farkı, köşeli parantezler içine dizinin uzunluğu yerine dizinin indeks türünün gelmesidir. Söz dizimi aşağıdaki gibidir:

    değer_türü[indeks_türü] tablo_ismi;

Örneğin türü string olan gün isminden türü int olan gün sıra numarasına eşleyen bir eşleme tablosu şöyle tanımlanır:

    int[string] günSıraları;

O tanım gün ismine karşılık olarak gün numarasını veren, yani yukarıdaki günİsimleri dizisinin tersi olarak işleyen bir tablo olarak kullanılabilir. Bunu aşağıdaki kod örneklerinde göreceğiz.

Eşleme tablolarının en kullanışlı taraflarından birisi, indeks ve değer türü olarak daha sonra öğreneceğimiz yapı ve sınıf türleri de dahil olmak üzere her türün kullanılabilmesidir.

Dinamik dizilerde olduğu gibi, eşleme tablolarının uzunlukları da tanımlandıkları zaman belirlenmez. Tablo otomatik olarak büyür.

Not: Baştan elemansız olarak tanımlanan bir eşleme tablosu boş değil, null'dır. Bu ayrımın işlevlere parametre olarak geçirilen eşleme tabloları açısından büyük önemi vardır. Bu kavramları ilerideki bölümlerde göreceğiz.

Tabloya eleman ekleme

Belirli bir indeks değerine karşılık gelen değer atama işleci ile belirlenir:

    günSıraları["Pazartesi"] = 0;  // "Pazartesi"yi 0 ile eşler
    günSıraları["Salı"] = 1;       // "Salı"yı 1 ile eşler

Eşleme ilişkisi tablonun otomatik olarak büyümesi için de yeterlidir. Yukarıdaki işlemler sonucunda tabloda artık iki eleman vardır. Bunu bütün tabloyu yazdırarak görebiliriz:

    writeln(günSıraları);

Çıktısı, "Pazartesi" ve "Salı" indekslerine karşılık 0 ve 1 değerlerinin bulunduğunu gösterir:

["Pazartesi":0, "Salı":1]

Her indeks değerine karşılık tek değer bulunabilir. Bu yüzden, var olan bir indekse karşılık yeni bir değer atandığında tablo büyümez, var olan elemanın değeri değişir:

    günSıraları["Salı"] = 222;
    writeln(günSıraları);

Çıktısı:

["Pazartesi":0, "Salı":222]

İlkleme

Gün sıraları kavramında olduğu gibi, eşleme bilgisi bazen tablo kurulduğu sırada bilinir. Eşlemeleri teker teker atayarak kurmak yerine bu bilgiyi tabloyu tanımladığımız zaman da verebiliriz. Eşleme tabloları da dizi söz diziminde olduğu gibi ilklenir. Farklı olarak, indeks ile değeri arasına : karakteri yazılır:

    int[string] günSıraları =
        [ "Pazartesi" : 0, "Salı" : 1, "Çarşamba" : 2,
          "Perşembe"  : 3, "Cuma" : 4, "Cumartesi": 5,
          "Pazar"     : 6 ];

    writeln(günSıraları["Salı"]);    // "1" yazar

Tablodan eleman çıkartma

Elemanlar, buradaki kullanımında "çıkart, at" anlamına gelen .remove ile çıkartılırlar:

    günSıraları.remove("Salı");
    writeln(günSıraları["Salı"]);  // ← çalışma zamanı HATASI

Son satır, tabloda artık bulunmayan bir elemana erişmeye çalıştığı için çalışma zamanında bir hata atılmasına ve o hatanın yakalanmaması durumunda da programın sonlanmasına neden olur. Hata düzeneğini ilerideki bir bölümde göreceğiz.

Elemanların hepsini birden çıkartmak gerektiğinde .clear kullanılır:

    günSıraları.clear;    // Tablo boşalır

Eleman sorgulama

Tabloda bulunmayan bir elemana erişmek bir hata atılmasına neden olduğundan, sorgulamak için in işleci kullanılır. Bu kullanım "içinde var mı?" sorusunu yanıtlar:

    if ("mor" in renkKodları) {
        // evet, renkKodları'nda "mor" indeksli değer var

    } else {
        // hayır, yok
    }

Bazen elemanın bulunup bulunmadığını açıkça sorgulamak yerine eleman bulunmadığı durumda standart bir değer kullanmak istenebilir. Örneğin, renkKodları tablosunda bulunmayan renklere karşılık -1 gibi bir değer kabul edilmiş olabilir. Bu gibi durumlarda .get() kullanılır. Tabloda varsa mevcut değeri, yoksa .get()'e verilen ikinci parametrenin değerini döndürür:

    int[string] renkKodları = [ "mavi" : 10, "yeşil" : 20 ];
    writeln(renkKodları.get("mor", -1));

Tabloda "mor" indeksli eleman bulunmadığından .get() ikinci parametresinin değeri olan -1'i döndürür:

-1

Nitelikler

• .length eleman sayısını verir.
• .keys bütün indeksleri dinamik dizi olarak verir.
• .byKey bütün indeksleri bir aralık olarak sunar; bunun kullanımını bir sonraki bölümde göreceğiz.
• .values bütün eleman değerlerini dinamik dizi olarak verir.
• .byValue bütün eleman değerlerini bir aralık olarak sunar; bunun kullanımını bir sonraki bölümde göreceğiz.
• .byKeyValue bütün indeksleri ve değerleri bir aralık olarak sunar.
• .rehash ancak gerçekten gereken durumlarda tablonun daha etkin çalışmasını sağlayabilir. Örneğin, tabloya çok sayıda eleman eklendikten sonra ve daha tablonun asıl kullanımı başlamadan önce bu nitelik çağrılırsa tablonun erişim işlemleri bazı programlarda daha hızlı olabilir.
• .sizeof tablonun referansının büyüklüğüdür (tablodaki eleman adediyle ilgisi yoktur ve her tablo için aynıdır).
• .get varsa elemanın değerini, yoksa ikinci parametresinin değerini döndürür.
• .remove belirtilen indeksli elemanı tablodan çıkartır.
• .clear tabloyu boşaltır.

Örnek

Girilen rengin İngilizcesini veren bir program şöyle yazılabilir:

import std.stdio;
import std.string;

void main() {
    string[string] renkler = [ "siyah"   : "black",
                               "beyaz"   : "white",
                               "kırmızı" : "red",
                               "yeşil"   : "green",
                               "mavi"    : "blue" ];

    writeln("Ben bu ", renkler.length,
            " rengin İngilizcelerini öğrendim: ",
            renkler.keys);

    write("Haydi sorun: ");
    string türkçesi = strip(readln());

    if (türkçesi in renkler) {
        writefln("İngilizcesi \"%s\"", renkler[türkçesi]);

    } else {
        writeln("Onu bilmiyorum.");
    }
}

Problemler

1. Bir eşleme tablosunu bütünüyle boşaltmak için .clear'den başka ne yöntemler düşünülebilir? (Bunun en doğal yolu .clear'dir.) En az üç yöntem düşünülebilir:
   • Elemanları bir döngü içinde teker teker tablodan çıkartmak
   • Boş bir eşleme tablosu atamak
   • Bir öncekine benzer şekilde, tablonun .init niteliğini atamak

     Not: Her türün .init niteliği, o türün ilk değeri olarak kullanılan değerdir:

         sayı = int.init;    // int için 0 olur
     

2. Dizilerde olduğu gibi, eşleme tablolarında da her indekse karşılık tek değer bulunabilir. Bu, bazı durumlarda kısıtlayıcıdır.

   Her öğrenci için birden fazla not tutmak istiyor olalım. Örneğin "emre" için 90, 85, 95, vs. notlarını barındırmak isteyelim.

   Bir eşleme tablosu kullanmak, notlara notlar["emre"] şeklinde öğrencinin ismiyle erişme konusunda yardımcı olur. Ancak, notları tabloya aşağıdaki şekilde yerleştirmek işe yaramaz:

       int[string] notlar;
       notlar["emre"] = 90;
       notlar["emre"] = 85;   // ← Olmaz: öncekinin üstüne yazar
   

   Ne yapabilirsiniz? Her öğrenci için birden fazla not tutabilen bir eşleme tablosu tanımlayın.