Çakışma Çözümleme

Önceki ders çakışmanın kaçınılmaz olduğunu gösterdi: anahtar uzayı tablodan büyükse, en az iki anahtar aynı kovaya düşer. Bu ders, düştüklerinde ne yapılacağını ele alır.

İki çözüm ailesi vardır ve ikisi de yaygın kullanılır. Ayrım tek bir soruda toplanır: çakışan eleman kovanın içinde mi yoksa tablonun başka bir konumunda mı saklanır?

Zincirleme

Zincirlemede (chaining) her kova, o kovaya düşen elemanların listesini tutar. Tablo bir dizi listedir; ekleme, ilgili listeye eklemektir.

class ZincirliTablo:
    def __init__(self, kova_sayisi: int = 8) -> None:
        self._kovalar: list[list] = [[] for _ in range(kova_sayisi)]
        self.karsilastirma = 0                 # ölçüm için

    def _konum(self, anahtar) -> int:
        return hash(anahtar) % len(self._kovalar)

    def koy(self, anahtar, deger) -> None:
        kova = self._kovalar[self._konum(anahtar)]
        for i, (mevcut, _) in enumerate(kova):
            if mevcut == anahtar:
                kova[i] = (anahtar, deger)     # var olan anahtar güncellenir
                return
        kova.append((anahtar, deger))

    def al(self, anahtar):
        kova = self._kovalar[self._konum(anahtar)]
        for mevcut, deger in kova:
            self.karsilastirma += 1
            if mevcut == anahtar:
                return deger
        raise KeyError(anahtar)

    def sil(self, anahtar) -> None:
        kova = self._kovalar[self._konum(anahtar)]
        for i, (mevcut, _) in enumerate(kova):
            if mevcut == anahtar:
                kova.pop(i)                     # listeden çıkarmak yeterli
                return
        raise KeyError(anahtar)


tablo = ZincirliTablo()
for ad, olcum in [("kuzey", 12), ("guney", 18), ("dogu", 7), ("bati", 25)]:
    tablo.koy(ad, olcum)

print(tablo.al("dogu"))        # 7
tablo.sil("dogu")
print(tablo.al("bati"))        # 25

Silmenin sade olduğuna dikkat edin: eleman listeden çıkarılır, başka hiçbir şey etkilenmez.

Zincirlemenin maliyeti, kova başına düşen ortalama eleman sayısıdır — yani yük çarpanı. Arama, kovayı bulmak (sabit) artı kovadaki listeyi taramaktır ($O(\alpha)$). Yük çarpanı sabit tutulduğu sürece ortalama maliyet sabittir.

Yük çarpanı zincirlemede $1$’i aşabilir: kovalar liste tuttuğu için tablo “dolmaz”. Bu esneklik, yeniden boyutlandırmayı geciktirmeye izin verir.

Açık Adresleme

Açık adreslemede (open addressing) tüm elemanlar tablonun kendi gözlerinde durur. Çakışma olduğunda, belirli bir kurala göre başka bir göz denenir; bu denemelere yoklama (probing) denir.

En yalın kural doğrusal yoklamadır: bir sonraki göze bak, dolu ise bir sonrakine, tablonun sonuna gelince başa dön.

BOS = object()        # hiç kullanılmamış göz
SILINDI = object()    # silinmiş göz (mezar taşı)

class AcikTablo:
    def __init__(self, kapasite: int = 8) -> None:
        self._gozler: list = [BOS] * kapasite
        self.yoklama = 0

    def _konum(self, anahtar) -> int:
        return hash(anahtar) % len(self._gozler)

    def koy(self, anahtar, deger) -> None:
        i = self._konum(anahtar)
        while self._gozler[i] is not BOS and self._gozler[i] is not SILINDI:
            if self._gozler[i][0] == anahtar:
                break                                   # güncelleme
            i = (i + 1) % len(self._gozler)             # doğrusal yoklama
            self.yoklama += 1
        self._gozler[i] = (anahtar, deger)

    def al(self, anahtar):
        i = self._konum(anahtar)
        while self._gozler[i] is not BOS:                # BOS görülünce arama biter
            self.yoklama += 1
            if self._gozler[i] is not SILINDI and self._gozler[i][0] == anahtar:
                return self._gozler[i][1]
            i = (i + 1) % len(self._gozler)
        raise KeyError(anahtar)

    def sil(self, anahtar) -> None:
        i = self._konum(anahtar)
        while self._gozler[i] is not BOS:
            if self._gozler[i] is not SILINDI and self._gozler[i][0] == anahtar:
                self._gozler[i] = SILINDI                # mezar taşı bırakılır
                return
            i = (i + 1) % len(self._gozler)
        raise KeyError(anahtar)


tablo = AcikTablo()
for ad, olcum in [("kuzey", 12), ("guney", 18), ("dogu", 7)]:
    tablo.koy(ad, olcum)
print(tablo.al("guney"))       # 18
tablo.sil("guney")
print(tablo.al("dogu"))        # 7

Silmenin Sorunu

Açık adreslemede silme, göze yalnızca “boş” yazarak yapılamaz. Arama, ilk boş gözü görünce durduğu için, silinen göz aramanın yolunu keser: aynı zincirin ilerisindeki elemanlar bulunamaz hâle gelir.

Çözüm, silinen gözü ayrı bir işaretle — mezar taşıyla — doldurmaktır. Arama mezar taşını görünce devam eder, ekleme ise oraya yazabilir.

Bedeli birikimdir: çok sayıda silme sonrası tablo mezar taşlarıyla dolar ve aramalar uzar. Gerçekleştirimler, mezar taşı oranı bir eşiği aştığında tabloyu yeniden düzenler.

Kümelenme

Doğrusal yoklamanın bilinen zayıflığı birincil kümelenmedir: dolu gözlerin ardışık blokları oluşur ve her yeni çakışma bloğu uzatır. Blok uzadıkça, o bölgeye düşen her anahtarın yoklama sayısı artar; büyüme kendi kendini besler.

İki alternatif kural bunu azaltır:

• Karesel yoklama: Adım aralığı sabit değil, artan bir kare dizisidir. Ardışık bloklar oluşmaz; ancak aynı konumdan başlayan anahtarlar aynı sırayı izler (ikincil kümelenme).
• Çift karma: Adım aralığı, ikinci bir karma fonksiyonundan hesaplanır. Her anahtar farklı bir sıra izler; kümelenme en aza iner, karşılığında ikinci karma hesabı gerekir.

Doğrusal yoklamanın bir üstünlüğü vardır ve önemsiz değildir: ardışık gözlere bakması, önbellek satırı içinde kalmak anlamına gelir. Bilgisayarlar Nasıl Çalışır kursundaki yerellik gözlemi burada doğrusal yoklamayı, kuramsal olarak daha iyi olan alternatiflere karşı rekabetçi kılar.

İki Ailenin Karşılaştırması

Ölçüt	Zincirleme	Açık adresleme
Yük çarpanı sınırı	$1$’i aşabilir	$1$’i aşamaz; eşik daha düşük tutulur
Bellek	Düğüm/liste ek yükü	Ek yapı yok, boş gözler var
Önbellek davranışı	Zayıf (dağınık liste)	İyi (bitişik gözler)
Silme	Doğrudan	Mezar taşı gerekir
En kötü durum	Tek kovada uzun liste	Tabloyu dolaşan uzun yoklama
Kovadaki yapı değiştirilebilir	Evet (liste yerine ağaç)	Hayır

Son satır, pratik bir güvenlik önlemine kapı açar: kova uzunluğu bir eşiği aşarsa liste yerine dengeli bir ağaç kullanılır ve en kötü durum $O(n)$ yerine $O(\log n)$ olur. Bu tasarım, kasıtlı çakışma saldırılarına karşı savunma olarak yaygınlaşmıştır.

Maliyet Tablosu

Yapı	Ortalama arama	En kötü arama	Silme
Zincirleme	$O(1 + \alpha)$	$O(n)$	$O(1 + \alpha)$
Zincirleme (ağaçlı kova)	$O(1 + \alpha)$	$O(\log n)$	$O(\log n)$
Açık adresleme	$O\left(\frac{1}{1-\alpha}\right)$	$O(n)$	Mezar taşıyla $O(1)$*

* Mezar taşı birikimi arttıkça bozulur.

Üçüncü satırdaki ifade, yük çarpanı $1$’e yaklaştıkça maliyetin neden hızla arttığını gösterir: $\alpha = 0{,}9$ için ortalama on yoklama gerekir. Açık adreslemede eşik bu nedenle daha düşük tutulur.

Özet

• Zincirlemede çakışan elemanlar kovadaki bir listede, açık adreslemede tablonun başka gözlerinde saklanır.
• Zincirlemede ortalama maliyet yük çarpanına bağlıdır ve yük çarpanı $1$’i aşabilir.
• Açık adreslemede silme, mezar taşı gerektirir; aksi hâlde arama yolu kesilir.
• Doğrusal yoklama birincil kümelenme üretir; karesel yoklama ve çift karma bunu azaltır.
• Doğrusal yoklamanın önbellek davranışı, kuramsal dezavantajını pratikte telafi eder.
• Kova içi yapının ağaca dönüştürülmesi, en kötü durumu logaritmik yapar ve çakışma saldırılarına karşı savunma sağlar.

Sonraki Adım

Karma tablosu anahtar–değer eşlemesi kurar. Bazı problemlerde değer gerekmez; yalnızca “bu eleman var mı” sorusu sorulur. Sonraki ders, bu soruya odaklanan küme yapılarını ve küçük evrenlerde bit düzeyi işlemlerle kurulan çok verimli bir gerçekleştirimi ele alacak.