--- title: 'Karma Tabloları' source: 'https://academia.sh/tr/kurslar/veri-yapilari/karma-tablolari' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:07:51+00:00' license: 'CC BY-SA 4.0' --- # Karma Tabloları Anahtardan konum hesaplama, karma fonksiyonunun nitelikleri, yük çarpanı ve ortalama sabit maliyetin koşulları. Önceki konu, aramayı en iyi durumda logaritmik maliyete indirdi. Daha aşağısı mümkün müdür? Sıralama ve karşılaştırma temelli her yapı için değildir; karşılaştırmayla arama yapan yapılar bu sınıra takılır. Farklı bir fikir gerekir: **elemanın nerede saklandığını, elemanın kendisinden hesaplamak.** Aranan değer verildiğinde konumu hesaplanabiliyorsa, arama tek adıma iner. ## Doğrudan Adresleme Fikrin en yalın hâli şudur: anahtar bir tam sayıysa ve aralığı küçükse, anahtarın kendisi dizin olarak kullanılabilir. ```python # Anahtarlar 0-9 aralığında olsun; anahtar doğrudan dizindir. tablo = [None] * 10 tablo[3] = "üç" tablo[7] = "yedi" print(tablo[3], tablo[7]) # üç yedi ``` Erişim sabit zamanlıdır ve hiçbir arama yapılmaz. Sorun, anahtar uzayının büyüklüğüdür: anahtarlar dokuz haneli kimlik numaralarıysa, doğrudan adresleme bir milyar gözlü bir dizi ister. Anahtarlar dizgi ise dizin olarak hiç kullanılamaz. ## Karma Fonksiyonu **Karma fonksiyonu (hash function)**, herhangi bir anahtarı sabit bir aralıktaki tam sayıya eşler. Bu sayı, tablodaki konumu (kovayı) belirler: $$ \text{konum} = h(\text{anahtar}) \bmod m $$ Burada $m$ tablo boyutudur. Anahtar uzayı ne kadar büyük olursa olsun, konum $0$ ile $m-1$ arasına iner. Bu, doğrudan adreslemenin bellek sorununu çözer — ancak yeni bir sorun getirir: iki farklı anahtar aynı konuma düşebilir. Bu duruma **çakışma (collision)** denir ve kaçınılmazdır. Anahtar uzayı tablo boyutundan büyük olduğu sürece, en az iki anahtarın aynı konuma eşleneceği kesindir. Bu, güvercin yuvası ilkesinin doğrudan sonucudur: $n$ nesne $m < n$ kutuya dağıtıldığında en az bir kutuya birden çok nesne düşer. Çakışmalarla nasıl başa çıkılacağı sonraki dersin konusudur. Bu ders, çakışmaların **nadir** olmasını sağlayan koşullarla ilgilenir. ## İyi Bir Karma Fonksiyonu Üç nitelik aranır. **Belirlilik.** Aynı anahtar her zaman aynı değeri vermelidir. Program çalıştığı sürece değişmeyen bir eşleme olmalıdır; aksi hâlde saklanan veri bulunamaz. **Düzgün dağılım.** Anahtarlar kovalara mümkün olduğunca eşit dağılmalıdır. Bir kovaya yığılma, o kovadaki aramayı doğrusala çevirir. İyi bir fonksiyonda, anahtarın tek bir bitinin değişmesi çıktının yaklaşık yarısını değiştirir; bu özellik **çığ etkisi** olarak adlandırılır. **Hız.** Karma hesabı, aramanın kendisinden pahalı olmamalıdır. Kriptografik karma fonksiyonları çığ etkisini güçlü biçimde sağlar ancak veri yapısı için gereğinden yavaştır; tablo için hafif fonksiyonlar kullanılır. Dizgiler için yaygın bir yöntem, karakterleri bir taban üzerinden polinom gibi değerlendirmektir: ```python def dizgi_karma(metin: str, taban: int = 31, mod: int = 1_000_003) -> int: """Karakterleri polinom biçiminde değerlendirir.""" deger = 0 for karakter in metin: deger = (deger * taban + ord(karakter)) % mod return deger print(dizgi_karma("olcum")) # 826819 print(dizgi_karma("olcun")) # 826820 — tek harf farkı print(dizgi_karma("mucol")) # 247712 — aynı harfler, farklı sıra ``` Tabanın çarpan olarak kullanılması, karakter sırasının sonuca yansımasını sağlar: aynı harflerden oluşan farklı dizgiler farklı değer üretir. Sıra dikkate alınmasaydı, harflerin toplamı kullanılan bir fonksiyonda tüm harf permütasyonları çakışırdı. ## Yük Çarpanı Tablonun doluluk oranı, başarımın belirleyicisidir: $$ \alpha = \frac{n}{m} $$ $n$ eleman sayısı, $m$ kova sayısıdır. Yük çarpanı büyüdükçe çakışma olasılığı artar; küçüldükçe bellek boşa harcanır. Gerçekleştirimler bir eşik belirler (yaygın olarak $0{,}7$ dolayında) ve eşik aşıldığında tabloyu büyütür. Büyütme, dinamik dizideki gibi kapasiteyi katlamak ve **tüm elemanları yeniden yerleştirmektir** — çünkü konum, tablo boyutuna bağlıdır. Bu işleme **yeniden karma (rehash)** denir ve maliyeti $O(n)$'dir; amortize edildiğinde ekleme başına sabit kalır. ## Karma Değeri ile Konum Ayrı Şeylerdir İki kavramın karıştırılması yaygındır. **Karma değeri**, anahtardan hesaplanan sayıdır ve tablo boyutundan bağımsızdır. **Konum**, o değerin tablo boyutuna indirgenmiş hâlidir. Ayrımın pratik sonucu, karma değerinin saklanabilmesidir. Gerçekleştirimler her göze, anahtarın yanında karma değerini de yazar. İki kazanç sağlar: yeniden karma sırasında değerler yeniden hesaplanmaz, yalnızca yeni tablo boyutuna göre indirgenir; ve arama sırasında anahtarlar karşılaştırılmadan önce karma değerleri karşılaştırılır — farklıysa pahalı eşitlik sınamasına hiç girilmez. İkinci kazanç, anahtarların uzun dizgiler olduğu durumlarda belirgindir: iki tam sayıyı karşılaştırmak, iki dizgiyi karakter karakter karşılaştırmaktan çok daha ucuzdur. ## Ortalama ve En Kötü Durum Karma tablosunun maliyet vaadi koşulludur: | Durum | Arama, ekleme, silme | |---|---| | Ortalama (düzgün dağılım, sınırlı yük çarpanı) | $O(1)$ | | En kötü durum (tüm anahtarlar aynı kovada) | $O(n)$ | En kötü durum yalnızca kuramsal değildir. Karma fonksiyonu biliniyorsa, aynı kovaya düşen anahtarlar kasıtlı olarak üretilebilir; bu, sunucuyu doğrusal maliyete zorlayan bir saldırı biçimidir. Savunma, karma fonksiyonuna çalışma anında belirlenen bir tohum eklemektir — böylece kovaların dağılımı dışarıdan öngörülemez. Bu konu, uygulama güvenliği müfredatında ayrıca ele alınır. ## Anahtarın Değişmezliği Bir anahtar tabloya konduktan sonra değiştirilirse, karma değeri de değişir; eleman artık bulunduğu kovada aranmaz ve erişilemez hâle gelir. Bu nedenle anahtar olarak **değiştirilemez** değerler kullanılır. Programlama Temelleri kursunda tanıtılan değiştirilemez–değiştirilebilir ayrımının pratik sonuçlarından biri budur: diller çoğu zaman değiştirilebilir nesnelerin anahtar olmasını doğrudan yasaklar. İkinci kural, eşitlik ile karma tutarlılığıdır: eşit sayılan iki anahtar aynı karma değerini üretmelidir. Eşitlik davranışı özelleştirilirken karma hesabının güncellenmemesi, sessizce bozulan tablolara yol açar. ## Maliyet Tablosu | Yapı | Arama | Ekleme | Silme | Sıra korunur mu | |---|---|---|---|---| | Sıralı dizi | $O(\log n)$ | $O(n)$ | $O(n)$ | Evet | | Atlama listesi | $O(\log n)$ beklenen | $O(\log n)$ | $O(\log n)$ | Evet | | Karma tablosu | $O(1)$ ortalama | $O(1)$ ortalama | $O(1)$ ortalama | Hayır | Bazı gerçekleştirimler, kova düzeninden bağımsız olarak **ekleme sırasını** ayrıca korur; bu, sıralama değil ekleme sırasıdır ve anahtarların büyüklüğüyle ilgisi yoktur. Aralık sorgusu yine yapılamaz. Son sütun, karma tablosunun ödediği bedeldir: elemanlar kova sırasına göre dağıldığı için anahtar sırası korunmaz. Sıralı gezinme veya aralık sorgusu gerekiyorsa, ağaç tabanlı yapılar seçilir. Son bir uyarı: karma değeri bir kimlik değildir. İki farklı anahtarın aynı karma değerini üretmesi olağandır; bu nedenle karma eşleşmesi bulunduğunda anahtarların kendisi de karşılaştırılır. Bu adımın atlanması, sessizce yanlış değer döndüren bir tabloya yol açar. ## Özet - Karma tablosu, konumu anahtardan hesaplayarak aramayı ortalama sabit zamana indirir. - Doğrudan adresleme yalnızca küçük ve tam sayı anahtar uzaylarında uygulanabilir; karma fonksiyonu bu kısıtı kaldırır. - İyi bir karma fonksiyonu belirli, düzgün dağıtan ve hızlıdır; çığ etkisi düzgün dağılımın göstergesidir. - Çakışma kaçınılmazdır; yük çarpanı doluluk oranıdır ve eşik aşıldığında tablo büyütülerek tüm elemanlar yeniden yerleştirilir. - En kötü durum doğrusaldır ve kasıtlı olarak tetiklenebilir; tohumlu karma bu riski azaltır. - Anahtarlar değiştirilemez olmalı, eşitlik ile karma tutarlı kalmalıdır. ## Sonraki Adım Çakışmanın kaçınılmaz olduğu kuruldu ama ne yapılacağı söylenmedi. Aynı kovaya düşen iki eleman nereye konur ve bu karar arama maliyetini nasıl etkiler? Sonraki ders iki ana çözüm ailesini — zincirleme ve açık adreslemeyi — karşılaştıracak.