Hash maplar algoritmaları nasıl optimize eder?

Question

Accepted Answer

Bir **hash map** (sözlük), **O(1) ortalama** arama, ekleme ve silme işlemleri sağlar. O(n) belleği hız için değiştirerek, birçok O(n²) algoritmayı O(n) olarak dönüştürür; bunu tekrarlanan taramaları anlık aramalarla değiştirerek yapar.

## Temel fikir

Her seferinde bir listeyi aramanın yerine, gördüğünüz değerleri bir hash map'de saklayın ve üyeliği sabit zamanda kontrol edin.

## Örnek: O(n) içinde iki-toplam

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

Harita olmadan bu O(n²); onunla, tek bir geçiş.

## Yaygın kullanımlar

- **Çoğaltmadan kurtulma / üyelik** bir set ile.
- **Frekans sayımı** (`Counter`).
- **Gruplandırma / indeksleme** anahtar'a göre.
- **Belleğe alma / hafıza** sonuçları.

## Karmaşıklık

- **Ortalama:** Operasyon başına O(1). **En kötü:** Ağır çarpışmalar halinde O(n). **Alan:** O(n).

## Tuzaklar

Anahtarlar **hashable** ve değişmez olmalıdır. En kötü durum çarpışmaları performansı azaltır. Hash maplar sırasızdır (sıra önemliyse sıralı varyantları kullanın).

## ## Neden önemli

Haşlama, kodlama mülakatlari ve gerçek sistemlerdeki en yaygın optimizasyondur — "tekrar tekrar ara" öğesini "bir kez ara" öğesine dönüştürür.

Alan-zaman dengesi, tekrarlanan bir mühendislik kaldıracıdır.

Frekans sayımı, belleğe alma ve indeksleme hepsi bu tek fikre dayanır.