Karma Tabloları

Ö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.

# 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:

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.