Hash Tabloları

📌 Neden Hash Tabloları?

Binary Search’ün Özellikleri:

• Worst-case: O(log n) - çok verimli
• Gereksinimler: Sıralı veri + Doğrudan erişim
• Sıralı ekleme: O(n) - pratik olarak yavaş

Hash Tabloları ile İyileştirme:

• Ekleme: Genelde O(1), worst-case O(n)
• Arama: Genelde O(1), worst-case O(n)

🔑 Hash Fonksiyonu

Hash fonksiyonu, bir anahtarı (key) tablo indeksine dönüştürür.

String için Örnek Hash Fonksiyonu

public static int hash(String wort) {
    int m = 13;  // Tablo boyutu (asal sayı olmalı)
    int k = 0;
    
    for (int i = 0; i < wort.length(); i++) {
        k += (int) wort.charAt(i);  // ASCII/Unicode değerlerinin toplamı
    }
    
    return k % m;  // Modulo ile indeks hesaplama
}

Hash Fonksiyonunun Özellikleri

Uzay U (Sonsuz anahtar uzayı)
        ↓
   Hash Fonksiyonu h(k)
        ↓
Hash Tablosu T [0...m-1] (Sonlu alan)

• Evrensel küme (U): Tüm olası anahtarlar
• Anahtar kümesi (S): Gerçekte kullanılan anahtarlar
• Hash tablosu (T): Sabit boyutlu m elemanlı dizi
• Önemli: Hash fonksiyonları genelde injektif değildir (farklı anahtarlar aynı indeksi verebilir)

⚠️ Önemli Not

Tablo boyutu asal sayı olmalı! Bu, daha iyi dağılım sağlar.

💥 Kollizyon (Çakışma) Problemi

İki farklı anahtar aynı hash değerine sahip olabilir:

hash("Ali") = 5
hash("Veli") = 5  ← Kollizyon!

🔍 Sondaj Stratejileri (Collision Resolution)

1. Lineer Sondaj (Linear Probing)

Boş yer bulunana kadar sırayla ilerle:

Adım 0: hash(key) = i
Adım 1: (i + 1) % m
Adım 2: (i + 2) % m
Adım 3: (i + 3) % m
...

Örnek:

Tablo: [_, _, X, X, _, _, _]
         0  1  2  3  4  5  6

hash(key) = 2 (dolu)
→ index 3'e bak (dolu)
→ index 4'e bak (boş) ✓ Buraya yerleştir!

❌ Problem: Kümelenme (Clustering)

• Aynı hash değerine sahip elemanlar yan yana birikir
• Arama performansı düşer

2. Karesel Sondaj (Quadratic Probing)

Kare sayılarla atlayarak ilerle:

Adım 0: hash(key) = i
Adım 1: (i + 1²) % m
Adım 2: (i + 2²) % m
Adım 3: (i + 3²) % m
...

⚠️ Potansiyel Problem:

• Tüm boş yerleri bulamayabilir
• Kümelenmeyi azaltır ama tam çözüm değil

3. Zincirleme (Chaining) - En Yaygın Yöntem

Her indekste bağlı liste kullan:

Hash Tablosu:
[0] → [Ali] → [Mehmet] → NULL
[1] → NULL
[2] → [Ayşe] → [Fatma] → [Zeynep] → NULL
[3] → [Veli] → NULL
[4] → NULL
...

✅ Avantajlar:

• Tüm elemanlar muhakkak saklanır
• Tablo doluluk oranı %100’ü aşabilir
• Ekleme her zaman mümkün

📊 Performans:

• Ortalama liste uzunluğu: α = n/m (yük faktörü)
• İdeal: α < 1 (az kollizyon)

🔎 Arama İşlemi

// Pseudo-kod
search(key) {
    index = hash(key)
    
    // Zincirleme yöntemi için
    list = table[index]
    for (element in list) {
        if (element.key == key)
            return element
    }
    
    return null  // Bulunamadı
}

Adımlar:

1. Hash değerini hesapla: index = hash(key)
2. İlgili indeksteki listeyi tara
3. Anahtar eşleşirse döndür
4. Yoksa null döndür

📈 Performans Analizi

Worst-case ne zaman olur?

• Tüm elemanlar aynı indekse düşerse
• Tek bir uzun liste oluşur
• Binary Search Tree’ye benzer durum

💡 Pratik Öneriler

1. Tablo boyutu asal sayı olsun

İyi: 13, 31, 97, 199
Kötü: 10, 16, 100

2. Yük faktörünü kontrol et

α = n/m
α < 0.7 ise performans iyi
α > 0.9 ise tablo büyütülmeli

3. İyi hash fonksiyonu seç

• Anahtarları düzgün dağıtsın
• Hızlı hesaplansın
• Deterministik olsun

🎯 Özet

Hash Tabloları = Hız + Pratiklik

✅ Avantajlar

• Ortalamada çok hızlı: O(1)
• Basit implementasyon
• Dinamik boyutlandırma mümkün

⚠️ Dikkat Edilmesi Gerekenler

• İyi hash fonksiyonu kritik
• Kollizyon yönetimi önemli
• Worst-case O(n) unutulmamalı

📚 Karşılaştırma Tablosu