Karma Tabloları
Bir karma tablo, anahtarları dizi konumlarına eşlemek için bir karma fonksiyonu kullanarak bir sözlüğü uygulamaktadır; bu yapı, çarpışmalar iyi yönetildiğinde beklenen sabit süreli ekleme, silme ve arama işlemlerini desteklemektedir.
Tanım
Karma tablo, anahtar-değer çiftlerini bir dizide depolayan, her anahtardan diziye bir indeks hesaplamak için bir karma fonksiyonu kullanan ve aynı indekse karma işlemi uygulanan farklı anahtarları yönetmek için bir çarpışma çözme şemasına sahip bir veri yapısıdır.
Kapsam
Bu konu, karma tabanlı sözlükleri; karma fonksiyonlarını ve bunların arzu edilen özelliklerini, çarpışma çözme stratejilerini (ayrı zincirleme ve açık adresleme), yük faktörünü ve yeniden boyutlandırmayı, kanıtlanabilir garantiler sağlayan evrensel ve mükemmel karma çerçevelerini ve Bloom filtreleri gibi ilgili olasılıksal yapıları kapsamaktadır. Sıralı sözlük yapıları bu kapsamın dışındadır; bunlar arama ağaçları başlığı altında incelenmektedir.
Temel sorular
- Bir karma fonksiyonunu iyi yapan nedir ve anahtarları tekdüze dağıtmak için nasıl seçilmektedir?
- Çarpışmalar zincirleme veya açık adresleme ile nasıl çözülmektedir ve maliyeti nasıl etkilemektedir?
- Yük faktörü, beklenen işlem süresini nasıl yönetmekte ve yeniden boyutlandırmayı nasıl tetiklemektedir?
- Evrensel ve mükemmel karma, kanıtlanabilir performans garantilerini nasıl sağlamaktadır?
- Bir Bloom filtresi gibi alan açısından verimli olasılıksal bir yapı, kesin bir tabloya ne zaman tercih edilmektedir?
Anahtar kavramlar
- karma fonksiyonu
- ayrı zincirleme
- açık adresleme
- yük faktörü
- yeniden karma ve yeniden boyutlandırma
- evrensel karma
- mükemmel karma
- Bloom filtresi
Temel kuramlar
- Evrensel karma
- Karma fonksiyonunu dikkatlice tasarlanmış (evrensel) bir aileden rastgele seçerek, herhangi bir sabit anahtar kümesi için düşük beklenen çarpışma sayısını garanti etmek mümkün olmakta, böylece en kötü durumdaki düşmanca girdilerin olasılığı azalmaktadır.
- Çarpışma çözme ve yük faktörü
- Ayrı zincirleme, çarpışan anahtarları her yuva için listelerde depolarken, açık adresleme alternatif yuvaları araştırmaktadır; beklenen işlem süresi yük faktörü (yuva başına giriş sayısı) tarafından yönetilmekte ve tablolar, bu faktörü sınırlı tutmak için yeniden boyutlandırılmaktadır.
Klinik önem
Karma tablolar, bilişimde en çok kullanılan veri yapılarından biridir: standart kütüphanelerde sözlükleri ve kümeleri uygulamakta, veritabanı indekslemeyi ve bellek içi önbellekleri desteklemekte, derleyicilerdeki sembol tablolarına yardımcı olmakta ve tekilleştirme ile üyelik testlerinin temelini oluşturmaktadır. Bloom filtreleri ise, kesin depolamanın mümkün olmadığı veritabanları ve ağ sistemlerinde üyelik sorgularını ölçeklendirmektedir.
Tarihçe
Karma işlemi (hashing), 1950'lerde IBM'den Hans Peter Luhn'a atfedilen çalışmalarla ortaya çıkmıştır. Burton Bloom, 1970 yılında alan açısından verimli Bloom filtresini tanıtmıştır. Carter ve Wegman, 1970'lerin sonları ve 1980'lerin başlarında evrensel ve daha sonra güçlü evrensel karma işlemini resmileştirerek, karma işlemine titiz bir teorik temel sağlamışlardır.
Öne çıkan isimler
- Hans Peter Luhn
- J. Lawrence Carter
- Mark Wegman
- Burton H. Bloom
İlgili konular
Temel eserler
- bloom1970
- carter1981
- cormen2009
Sıkça sorulan sorular
- Karma tablo işlemleri neden garantili O(1) yerine beklenen O(1) olarak tanımlanmaktadır?
- Çok sayıda anahtar çarpıştığında, işlemler O(n) seviyesine düşebilmektedir. Sabit zaman, iyi bir karma fonksiyonu ve sınırlı bir yük faktörü altında beklenen bir durumdur; evrensel karma, kötü bir durumu olası olmaktan çıkarmakla birlikte, en kötü durum garantileri mükemmel karma veya başka teknikler gerektirmektedir.
- Bloom filtresi nedir ve bir karma tablodan farkı nedir?
- Bloom filtresi, bir bit dizisi üzerinde birden fazla karma fonksiyonu kullanarak küme üyeliğini test eden kompakt bir olasılıksal yapıdır. Yanlış pozitifler verebilmekte ancak asla yanlış negatifler vermemektedir ve hiçbir anahtar depolamamaktadır; bir karma tabloya kıyasla kesinliği büyük alan tasarrufuyla takas etmektedir.