Temeller
Olasılık ve beklenen değer
Hash map ortalaması neden O(1); rastgele algoritmalar ve beklenen sayılar.
Soru: 1000 anahtarı 24 kovaya rastgele dağıtırsan en uzun zincir ne kadar olur?
Beklenen ortalama zincir uzunluğu λ = n/m ≈ 42. Ama en uzun zincir≈ λ + √(2λ ln m) ≈ 56. Hash map’te tek bir get yine ortalama O(1). Bu sayfa, neden “hash map ortalama O(1)” ifadesinin altındaki olasılık matematiğini açar.
Sayılarla: yük faktörü
| n anahtar / m kova | λ = n/m | Beklenen zincir | En kötü beklenen |
|---|---|---|---|
| 24 / 24 | 1.0 | O(1) | ~4 |
| 1000 / 24 | 41.7 | O(λ) | ~56 |
| 10⁶ / 1.3M | 0.75 | O(1) | ~5 |
Tek satırda: λ sabitse (load factor ≤ ~0.75) hem beklenen zincir hem en kötü beklenen zincir O(1). Rehash bu factorü korur; bu yüzden hash map ortalama O(1) derkenfactor sabit varsayımı vardır.
Nereden gelir?
Beklenen değer: E[X] = Σ xᵢ · P(xᵢ). n get, her biri ortalamaE[tek get] maliyet, toplam beklenen n · E[tek get].
Çarpışma analizi: m kova, n anahtar, uniform hash. Her kovaya ortalamaλ = n/m anahtar düşer (Poisson). Bir get, hedef kovadaki zinciri taramak zorunda; beklenen zincir uzunluğu λ + 1. λ sabitse (rehash bunu garantiler) → O(1).
En kötü durum: tüm anahtarlar bir kovaya çakışırsa O(n). Uniform hash altında olasılığı çok düşüktür ama attacker-controlled key’lerde (ör. web framework hash map) gerçek bir saldırıdır; bu yüzden modern diller keyed hash (SipHash) kullanır.
Tuzak: “hash map her zaman O(1)”
Yanlış. Ortalama O(1), varsayım: uniform hash ve load factor sabit. En kötü durum O(n): kötü hash fonksiyonu (tüm anahtarlar bir kovaya) veya load factor kontrolden çıkarsa. Python dict ve Java HashMap rehash eder, ama yine de amortized O(1), worst case O(n). Mülakatta “amortized average O(1), worst O(n)” diye cevapla.
Sıradaki adım
- hashing kalıbı - hash map’in kullanıldığı DSA yerleri.
- LC 217 Contains Duplicate - hash set ile O(n) ortalama.
- LC 1 Two Sum - hash map ile complement arama, O(n) ortalama.
- Toplamlar - beklenen değer toplamları.
Alıştırma
Aşağıdaki simülasyonda +100’e birkaç kez bas. Ortalama zincir ~1 civarında kalır. Şimdi+1000’e defalarca bas: λ yükselir ve bazı kovalar belirgin şekilde dolmaya başlar. Bu, yük faktörünün neden çarpışmayı belirlediğini ve rehash’ın neden gerekli olduğunu gösterir.
kova doluluğu (m = 24) · load factor λ ≈ 0.00