Karma Tablolar ve Karma Fonksiyonları Nedir?
Karma tablolar (hash tables), anahtar-değer çiftlerini saklamak için kullanılan ve ortalama O(1) zaman karmaşıklığında erişim sağlayan dinamik veri yapılarıdır. Bu verimlilik, karma fonksiyonlarının (hash functions) doğru seçimine dayanır.
Karma tablolar, anahtar değerlerini önceden belirlenmiş bir dizi (array) içine dağıtmak için karma fonksiyonlarını kullanır. Karma fonksiyonu, bir anahtarı alır ve bu anahtarın tablo içindeki indeksini döndürür.
Adım adım çözümlü örnekler
Basit bir karma tabloya 'elma': 5, 'muz': 3, 'kiraz': 7 değerlerini ekleyelim. Modulo (kalan) alma yöntemiyle basit bir karma fonksiyonu kullanalım. Tablo boyutu 10 olsun.
1. 'elma' için karma(elma) = (e'nin ascii değeri + l'nin ascii değeri + ...) % 10 = indeks 2. 'muz' için karma(muz) = (m'nin ascii değeri + u'nun ascii değeri + ...) % 10 = indeks 3. 'kiraz' için karma(kiraz) = (k'nin ascii değeri + i'nin ascii değeri + ...) % 10 = indeks 4. Elde edilen indekslere karşılık gelen değerleri tabloya yerleştiririz.
Karma tabloya 'portakal': 9 değerini eklerken, karma fonksiyonunun 'elma' ile aynı indeksi döndürmesi durumunda ne olur? (Çarpışma/Collision)
1. Eğer karma('portakal') == karma('elma') ise bir çarpışma meydana gelir.
2. Çarpışmayı çözmek için 'ayrık zincirleme' (separate chaining) veya 'açık adresleme' (open addressing) gibi yöntemler kullanılır.
Ayrık zincirlemede, aynı indekse sahip elemanlar bir bağlı liste içinde saklanır.
Açık adreslemede ise, boş bir sonraki yuva aranır.Bilgi kartları
Mini test
S1.Karma tabloların en büyük avantajı aşağıdakilerden hangisidir?
S2.Bir karma fonksiyonunun görevi nedir?
S3.Aşağıdakilerden hangisi bir çarpışma çözüm tekniği DEĞİLDİR?
Sık yapılan hatalar
Karma fonksiyonu her zaman benzersiz indeksler üretir. — Doğrusu: Karma fonksiyonları farklı anahtarlar için aynı indeksi üretebilir; bu duruma çarpışma denir.
Karma tablolar, verileri her zaman sıralı bir şekilde saklar. — Doğrusu: Karma tablolar, verileri anahtarların karma değerlerine göre rastgele dağıtır ve sıralı saklama garantisi vermez.
Sıkça sorulan sorular
Karma tabloların en kötü durum performansı nedir?
Eğer tüm anahtarlar aynı indekse karma yaparsa (en kötü durum çarpışması), karma tablo bir bağlı liste gibi davranabilir ve erişim süresi O(n) olabilir. İyi bir karma fonksiyonu ve tablo boyutu seçimi bu durumu nadir hale getirir.
Hangi tür veriler anahtar olarak kullanılabilir?
Temel olarak, karma fonksiyonu uygulanabilen (yani sayısal veya metinsel temsili olan ve eşitlik karşılaştırması yapılabilen) herhangi bir veri türü anahtar olarak kullanılabilir. Genellikle tamsayılar, dizeler ve nesneler kullanılır.
Karma fonksiyonu seçimi neden önemlidir?
İyi bir karma fonksiyonu, anahtarları tabloya eşit olarak dağıtarak çarpışmaları en aza indirir ve böylece karma tablonun O(1) ortalama performansını korur. Kötü bir fonksiyon, performansı O(n)'ye düşürebilir.