Karma Tabloları

Önceki iki ders bir değerin ya paylaşılan bir nesne üzerinden kalıcı biçimde göründüğünü (ortak) ya da bir aracıdan tam bir kez geçip kaybolduğunu (aktarım) ölçtü. Bu ders üçüncü bir sınıfı, kopya’yı ölçüyor: bir karma tablosundan bir kaydı okumak, o kaydı tablodan çıkarmıyor ve tablodaki kayıtla paylaşılan bir nesne de üretmiyor — çağırana kaydın kendi kopyasını veriyor. Bu kopya üzerinde yapılan bir değişiklik tabloya hiç yansımıyor, çünkü ikisi arasında ortak hiçbir bellek bloğu yok.

Karma Tablo: Ayrık Zincirleme ile Ekleme ve Bulma

Tablo sabit sayıda kovadan oluşuyor; her kova bir bağlı liste (zincir). karma_indeks bir anahtarı kova sayısına göre bir indekse eşliyor. karma_ekle anahtar zincirde varsa kaydı güncelliyor, yoksa zincirin başına yeni bir düğüm ekliyor. karma_bul kaydı bulursa kopyasını hedef’e yazıyor ve 1 döndürüyor; bulamazsa 0 döndürüyor.

// karma.h — ayrik zincirlemeli karma tablo
#ifndef KARMA_H
#define KARMA_H

#define KARMA_KAPASITE 8

struct Kayit {
    int miktar;
    int sayac;
};

struct KarmaDugumu {
    int anahtar;
    struct Kayit deger;
    struct KarmaDugumu *sonraki;
};

struct KarmaTablo {
    struct KarmaDugumu *kovalar[KARMA_KAPASITE];
};

void karma_hazirla(struct KarmaTablo *t);
void karma_ekle(struct KarmaTablo *t, int anahtar, struct Kayit deger);
int karma_bul(const struct KarmaTablo *t, int anahtar, struct Kayit *hedef);
void karma_serbest(struct KarmaTablo *t);

#endif

// karma.c — karma tablo islemlerinin gerceklemesi
#include <stdlib.h>
#include "karma.h"

static int karma_indeks(int anahtar) {
    return (anahtar % KARMA_KAPASITE + KARMA_KAPASITE) % KARMA_KAPASITE;
}

void karma_hazirla(struct KarmaTablo *t) {
    for (int i = 0; i < KARMA_KAPASITE; i++) {
        t->kovalar[i] = NULL;
    }
}

void karma_ekle(struct KarmaTablo *t, int anahtar, struct Kayit deger) {
    int i = karma_indeks(anahtar);
    for (struct KarmaDugumu *d = t->kovalar[i]; d != NULL; d = d->sonraki) {
        if (d->anahtar == anahtar) {
            d->deger = deger;
            return;
        }
    }
    struct KarmaDugumu *yeni = malloc(sizeof *yeni);
    if (yeni == NULL) {
        return;
    }
    yeni->anahtar = anahtar;
    yeni->deger = deger;
    yeni->sonraki = t->kovalar[i];
    t->kovalar[i] = yeni;
}

int karma_bul(const struct KarmaTablo *t, int anahtar, struct Kayit *hedef) {
    int i = karma_indeks(anahtar);
    for (struct KarmaDugumu *d = t->kovalar[i]; d != NULL; d = d->sonraki) {
        if (d->anahtar == anahtar) {
            *hedef = d->deger;
            return 1;
        }
    }
    return 0;
}

void karma_serbest(struct KarmaTablo *t) {
    for (int i = 0; i < KARMA_KAPASITE; i++) {
        struct KarmaDugumu *d = t->kovalar[i];
        while (d != NULL) {
            struct KarmaDugumu *sonraki = d->sonraki;
            free(d);
            d = sonraki;
        }
    }
}

Okunan Kaydın Kendi Kopyası Olması

Bir kayıt eklenip okunuyor, sonra okunan kopya değiştiriliyor. Asıl ölçüm, bu değişiklikten sonra tablodan tekrar okunan değerin ilk hâlini korumasında.

// bulunan_kopya.c — okunan kayit degistiriliyor, tablo etkilenmiyor mu
#include <stdio.h>
#include "karma.h"

int main(void) {
    struct KarmaTablo t;
    karma_hazirla(&t);

    struct Kayit ilk = {100, 1};
    karma_ekle(&t, 3, ilk);

    struct Kayit okunan;
    karma_bul(&t, 3, &okunan);
    printf("%s %d\n", "ilk okunan miktar", okunan.miktar);

    okunan.miktar = 900;
    printf("%s %d\n", "kopya degistirildikten sonra kopyanin miktari", okunan.miktar);

    struct Kayit tekrar_okunan;
    karma_bul(&t, 3, &tekrar_okunan);
    printf("%s %d\n", "tablodan tekrar okunan miktar", tekrar_okunan.miktar);

    karma_serbest(&t);
    return 0;
}

ilk okunan miktar 100
kopya degistirildikten sonra kopyanin miktari 900
tablodan tekrar okunan miktar 100

VY7. karma_bul’un imzası (int karma_bul(const struct KarmaTablo *t, int anahtar, struct Kayit *hedef)) hedef’e yazılan struct Kayit‘in tablonun kendi kaydı mı yoksa bağımsız bir kopyası mı olduğunu söylemiyor — bunu belirleyen *hedef = d->deger satırı, yani bir yapı ataması. C’de bir yapıyı bir başka yapıya atamak, alanlarını tek tek kopyalıyor; okunan bu atamadan sonra d->deger ile aynı bellek bloğunu göstermiyor, kendi bağımsız bloğunda duruyor. okunan.miktar = 900 ataması bu yüzden yalnız okunan’ı değiştiriyor; tablo parametresi karma_bul‘a zaten const struct KarmaTablo * olarak geçiyor ve işlev onu hiç değiştirmiyor. İkinci karma_bul çağrısı tablodan yeniden okuyor ve ilk değeri (100) veriyor — 900’ü değil. Sınıf kopya: okunan kayıt üzerinde yapılan bir değişiklik ikinci bir okuyucuya (burada tablonun kendisi) hiç ulaşmıyor, çünkü aralarında paylaşılan bir nesne yok.

Aynı Anahtarla Yeniden Ekleme

karma_ekle aynı anahtarla ikinci kez çağrıldığında yeni bir düğüm eklemiyor, var olan düğümün deger alanını güncelliyor. Bu, önceden okunmuş bir kopyayı etkilemiyor — kopya zaten ayrı bir bellek bloğunda.

// yeniden_ekleme.c — ayni anahtarla guncelleme, onceki kopyayi etkilemiyor
#include <stdio.h>
#include "karma.h"

int main(void) {
    struct KarmaTablo t;
    karma_hazirla(&t);

    struct Kayit ilk = {5, 1};
    karma_ekle(&t, 7, ilk);

    struct Kayit once_okunan;
    karma_bul(&t, 7, &once_okunan);
    printf("%s %d\n", "guncellemeden once okunan miktar", once_okunan.miktar);

    struct Kayit guncel = {50, 2};
    karma_ekle(&t, 7, guncel);

    printf("%s %d\n", "guncellemeden sonra eski kopyanin miktari", once_okunan.miktar);

    struct Kayit sonra_okunan;
    karma_bul(&t, 7, &sonra_okunan);
    printf("%s %d\n", "guncellemeden sonra tablodan okunan miktar", sonra_okunan.miktar);

    karma_serbest(&t);
    return 0;
}

guncellemeden once okunan miktar 5
guncellemeden sonra eski kopyanin miktari 5
guncellemeden sonra tablodan okunan miktar 50

VY8. once_okunan, karma_ekle(&t, 7, guncel) çağrısından önce alınmış bir kopya — tabloyla hiçbir bağı kalmadığı için tablo güncellendiğinde değişmiyor, 5’te kalıyor. Tablodan yeniden okunan sonra_okunan ise güncel değeri (50) görüyor, çünkü bu kez karma_bul güncellemeden sonra çağrıldı ve tablonun o andaki hâlinden yeni bir kopya aldı. Bu iki satır birlikte kopya sınıfının sınırını gösteriyor: bir kopya, alındığı andaki değeri sonsuza dek taşıyor; kaynağı sonradan değişse bile kopya bunu hiç görmüyor, çünkü görmesi için kaynakla aralarında paylaşılan bir bağ gerekirdi.

Çakışan Anahtarların Aynı Kovada Zincirlenmesi

Kapasite sekiz olduğu için 3 ve 11 anahtarları aynı kovaya (3 % 8 = 3, 11 % 8 = 3) düşüyor. karma_ekle bu durumda ikinci düğümü zincirin başına ekliyor; karma_bul doğru anahtarı zincirde arayarak buluyor.

// cakisan_anahtarlar.c — ayni kovaya dusen iki farkli anahtar
#include <stdio.h>
#include "karma.h"

int main(void) {
    struct KarmaTablo t;
    karma_hazirla(&t);

    struct Kayit birinci = {11, 0};
    struct Kayit ikinci = {22, 0};
    karma_ekle(&t, 3, birinci);
    karma_ekle(&t, 11, ikinci);

    struct Kayit sonuc;
    karma_bul(&t, 3, &sonuc);
    printf("%s %d\n", "anahtar 3 icin bulunan miktar", sonuc.miktar);
    karma_bul(&t, 11, &sonuc);
    printf("%s %d\n", "anahtar 11 icin bulunan miktar", sonuc.miktar);

    karma_serbest(&t);
    return 0;
}

anahtar 3 icin bulunan miktar 11
anahtar 11 icin bulunan miktar 22

VY9. İki anahtar aynı kovaya düştüğü hâlde karma_bul doğru kaydı buluyor, çünkü arama yalnız kovanın indeksine değil, zincirdeki her düğümün anahtar alanına da bakıyor (d->anahtar == anahtar). Bu, karma tablonun neden bir dizi değil bir dizi listeler olduğunu gösteriyor: bir kovaya birden fazla anahtar düşebiliyor ve zincir bu çakışmayı çözüyor. Çakışmanın kendisi bu dersin ölçtüğü sınıfı değiştirmiyor — her iki karma_bul çağrısı da yine kendi kopyasını üretiyor.

Anahtarı İşaretçiyle Tutan Sürüm

Şimdiye kadarki tablo anahtarı bir int olarak değerle tutuyordu — karma_ekle’ye geçen anahtar kopyalanıyor, düğüm kendi bağımsız kopyasını saklıyor. Anahtarı bunun yerine bir işaretçiyle tutan bir sürüm de yazılabilir; bu, anahtarın ölçtüğü sınıfı kopya’dan ortak’a çeviriyor ve farklı bir tehlike doğuruyor.

// karma_ptr.h — anahtari isaretciyle tutan karma tablo surumunun bildirimi
#ifndef KARMA_PTR_H
#define KARMA_PTR_H

#include "karma.h"

struct KarmaDugumuPtr {
    const int *anahtar;
    struct Kayit deger;
    struct KarmaDugumuPtr *sonraki;
};

struct KarmaTabloPtr {
    struct KarmaDugumuPtr *kovalar[KARMA_KAPASITE];
};

void karma_ptr_hazirla(struct KarmaTabloPtr *t);
void karma_ptr_ekle(struct KarmaTabloPtr *t, const int *anahtar, struct Kayit deger);
int karma_ptr_bul(const struct KarmaTabloPtr *t, int anahtar_degeri, struct Kayit *hedef);
void karma_ptr_serbest(struct KarmaTabloPtr *t);

#endif

// karma_ptr.c — anahtari isaretciyle tutan karma tablo surumunun gerceklemesi
#include <stdlib.h>
#include "karma_ptr.h"

static int karma_ptr_indeks(int anahtar_degeri) {
    return (anahtar_degeri % KARMA_KAPASITE + KARMA_KAPASITE) % KARMA_KAPASITE;
}

void karma_ptr_hazirla(struct KarmaTabloPtr *t) {
    for (int i = 0; i < KARMA_KAPASITE; i++) {
        t->kovalar[i] = NULL;
    }
}

void karma_ptr_ekle(struct KarmaTabloPtr *t, const int *anahtar, struct Kayit deger) {
    int i = karma_ptr_indeks(*anahtar);
    struct KarmaDugumuPtr *yeni = malloc(sizeof *yeni);
    if (yeni == NULL) {
        return;
    }
    yeni->anahtar = anahtar;
    yeni->deger = deger;
    yeni->sonraki = t->kovalar[i];
    t->kovalar[i] = yeni;
}

int karma_ptr_bul(const struct KarmaTabloPtr *t, int anahtar_degeri, struct Kayit *hedef) {
    int i = karma_ptr_indeks(anahtar_degeri);
    for (struct KarmaDugumuPtr *d = t->kovalar[i]; d != NULL; d = d->sonraki) {
        if (*(d->anahtar) == anahtar_degeri) {
            *hedef = d->deger;
            return 1;
        }
    }
    return 0;
}

void karma_ptr_serbest(struct KarmaTabloPtr *t) {
    for (int i = 0; i < KARMA_KAPASITE; i++) {
        struct KarmaDugumuPtr *d = t->kovalar[i];
        while (d != NULL) {
            struct KarmaDugumuPtr *sonraki = d->sonraki;
            free(d);
            d = sonraki;
        }
    }
}

// anahtar_isaretci.c — anahtari tutan degisken sonradan degisince arama bozuluyor mu
#include <stdio.h>
#include "karma_ptr.h"

int main(void) {
    struct KarmaTabloPtr t;
    karma_ptr_hazirla(&t);

    int anahtar_degiskeni = 5;
    struct Kayit deger = {42, 1};
    karma_ptr_ekle(&t, &anahtar_degiskeni, deger);

    struct Kayit bulunan;
    int bulundu_mu = karma_ptr_bul(&t, 5, &bulunan);
    printf("%s %d\n", "degisiklikten once anahtar 5 ile bulundu mu", bulundu_mu);

    anahtar_degiskeni = 99;

    int eski_deger_ile_bulundu_mu = karma_ptr_bul(&t, 5, &bulunan);
    printf("%s %d\n", "degiskeni 99 yaptiktan sonra eski deger 5 ile bulundu mu", eski_deger_ile_bulundu_mu);

    int yeni_deger_ile_bulundu_mu = karma_ptr_bul(&t, 99, &bulunan);
    printf("%s %d\n", "degiskeni 99 yaptiktan sonra yeni deger 99 ile bulundu mu", yeni_deger_ile_bulundu_mu);

    karma_ptr_serbest(&t);
    return 0;
}

degisiklikten once anahtar 5 ile bulundu mu 1
degiskeni 99 yaptiktan sonra eski deger 5 ile bulundu mu 0
degiskeni 99 yaptiktan sonra yeni deger 99 ile bulundu mu 0

VY16. karma_ptr_ekle düğümün kovasını *anahtar — yani anahtar_degiskeni’nin o andaki değeri — üzerinden hesaplıyor ve bu kova bir daha değişmiyor. Ama düğüm anahtarı kopyalamıyor, anahtar_degiskeni’nin adresini tutuyor; bu yüzden anahtar alanı ile çağıranın değişkeni arasında bir ortak ilişkisi var. anahtar_degiskeni 99’a değiştiğinde d->anahtar’ın gösterdiği bellek de 99 oluyor, ama düğüm hâlâ 5’in kovasında duruyor. Sonuç: 5 ile arandığında kovadaki düğümün anahtarı artık 5 değil (bulunamıyor); 99 ile arandığında doğru kova (99’un kovası) boş (yine bulunamıyor). Kayıt hiçbir anahtarla erişilemez hâle geliyor — kovaya yerleştirme bir kerelik bir karardı, ama karşılaştırma canlı belleği okumaya devam ediyor. karma_ekle bu tehlikeden bağışık, çünkü anahtarı değerle kopyalıyor; anahtarı işaretçiyle tutmak bu korumayı kaybediyor.

Sınırlayıcı Ölçüm

Bir bulma işlevinin dönüş tipi, döndürdüğü kaydın tablonun kendi belleğiyle paylaşılıp paylaşılmadığını söylemiyor. struct Kayit *hedef parametresi bir işaretçi taşıyor, ama işaretçinin gösterdiği yer çağıranın kendi yerel değişkeni — tablo bu değişkenden habersiz. Bu dersteki karma_bul her zaman bir yapı ataması (*hedef = d->deger) yaptığı için sınıf hep kopya; aynı imzayla yazılmış bir işlev, eğer hedef’e tablo içindeki düğümün adresini yazsaydı (hedef bir struct Kayit ** olsaydı), sonuç ortak olurdu. Bu fark yalnız gövde okunarak ya da (bu derste yapıldığı gibi) kaynağı sonradan değiştirip kopyanın bunu görüp görmediği ölçülerek anlaşılabiliyor.

Özet

• Karma tablo sabit sayıda kovaya dağılıyor; her kova bir zincir, çakışan anahtarlar aynı zincirde anahtar alanına bakılarak ayırt ediliyor.
• karma_bul bir yapı ataması (*hedef = d->deger) ile kaydın kopyasını üretiyor; kopya üzerindeki değişiklik tabloya hiç yansımıyor — sınıf kopya.
• Bir kopya, alındığı andaki değeri taşımaya devam ediyor; kaynak sonradan değişse bile önceden alınmış bir kopya bunu görmüyor.
• Kopya’nın ortak’tan farkı: ortakta paylaşılan nesne tek, kopyada iki bağımsız nesne var; aktarım’dan farkı: aktarımda okunan yer boşalıyor, kopyada tablo aynı kaydı tekrar tekrar (güncel hâliyle) verebiliyor.
• Bir bulma işlevinin döndürdüğü değerin kopya mı paylaşılan bir nesne mi olduğu imzada görünmüyor; yalnız gövde ya da ölçümle anlaşılıyor.
• Anahtarı değerle değil işaretçiyle tutmak sınıfı ortak’a çeviriyor: kova yerleşimi ekleme anındaki değere göre sabitleniyor ama karşılaştırma canlı belleği okuyor — dışarıdaki değişken değişirse kayıt hiçbir anahtarla erişilemez hâle gelebiliyor.

Sonraki Adım

Bu üç ders bağlı yapı, arabellek ve tablo üzerinden üç ayrı sınıfı (ortak, aktarım, kopya) ölçtü. Bir sonraki ders, Nesne Benzeri Tasarım, C’nin sınıfı olmayan bir dilde bir “nesne” izlenimini nasıl kurduğunu — işlev işaretçileri ve opak yapılarla — ele alıyor ve bu üç sınıfın aynı nesne arayüzü içinde nasıl bir arada bulunabildiğini gösteriyor.