Anahtar-değer çiftlerini depolamak için hash fonksiyonu kullanan veri yapısı.
Temel Bileşenler
- Hash Fonksiyonu: Anahtarı dizi indeksine dönüştürür
- Bucket Array: Veri depolanan dizi
- Çarpışma Çözümleme: Aynı indekse eşlenen anahtarları yönetir
Çarpışma Çözümleme Yöntemleri
1. Zincirleme (Chaining)
- Aynı indeksteki elemanları bağlı listede saklar
- Ekleme: O(1)
- Arama: O(1) ortalama, O(n) en kötü
- Ek bellek gerektirir
2. Açık Adresleme (Open Addressing)
- Doğrusal Sondalama: i+1, i+2, ...
- Karesel Sondalama: i+1², i+2², ...
- Çift Hashleme: İkinci hash fonksiyonu kullanır
Performans
| İşlem | Ortalama Durum | En Kötü Durum |
|---|---|---|
| Arama | O(1) | O(n) |
| Ekleme | O(1) | O(n) |
| Silme | O(1) | O(n) |
Yük Faktörü (Load Factor)
α = n / m (n: eleman sayısı, m: tablo boyutu)
- Düşük α: Az çarpışma, fazla bellek
- Yüksek α: Çok çarpışma, az bellek
- Optimal α ≈ 0.7-0.8
Kullanım Alanları
- Veritabanı indeksleme
- Önbellekleme (caching)
- Sembol tabloları
- Sözlükler/Haritalar
- Benzersiz eleman kontrolü