Hash tablosu nedir ve O(1) aramasını nasıl sağlar?

Question

Accepted Answer

Bir **hash tablosu** (hash map) **key → value** çiftlerini depolar ve ortalama olarak **O(1)** ekleme, arama ve silme işlemini sağlar. Her anahtarı, onu temel bir dizideki (bir "bucket") bir dizine eşleyen bir **hash işlevi** üzerinden çalıştırarak çalışır.

## Nasıl Çalışır

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## Örnek

```python
phone = {}
phone['alice'] = 555_1234   # insert -> hash 'alice' to a bucket
num = phone['alice']        # lookup -> hash again, jump to bucket
del phone['alice']          # delete
'bob' in phone              # membership -> O(1) average
```

## Zaman Karmaşıklığı

| İşlem | Ortalama | En Kötü |
|---|---|---|
| ekleme | O(1) | O(n) |
| arama | O(1) | O(n) |
| silme | O(1) | O(n) |

**En kötü durumda** O(n), birçok anahtarın aynı bucket'a çarpışması durumunda ortaya çıkar.

## Değişim

- **Güçlü Yönler:** anahtar tabanlı erişimde çok hızlı; esnek anahtarlar.
- **Zayıf Yönler:** anahtarların sırası yoktur; ek bellek; O(n) en kötü durum; iyi bir hash işlevi gerekir.

## Neden Önemli

Hash tabloları muhtemelen pratikte en çok kullanılan veri yapısı — sözlükler, kümeler, önbellekler, veritabanı indeksleri ve tekrar kaldırma işleminin arkasında yer alır.

Doğrusal taramayı hash aramasıyla değiştirmek, O(n²) algoritmasını O(n)'ye dönüştürmenin en yaygın yollarından biridir.