--- title: 'Çakışma Çözümleme' source: 'https://academia.sh/tr/kurslar/veri-yapilari/cakisma-cozumleme' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:07:50+00:00' license: 'CC BY-SA 4.0' --- # Çakışma Çözümleme Zincirleme ve açık adresleme, yoklama stratejileri, kümelenme, silme sorunu ve iki ailenin karşılaştırması. Ö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. ```python 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. ```python 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.