Bagaimana hash map mengoptimalkan algoritma?

Question

Accepted Answer

Sebuah **hash map** (dictionary) memberikan **O(1) rata-rata** untuk pencarian, penyisipan, dan penghapusan. Menukar memori O(n) untuk kecepatan mengubah banyak algoritma O(n²) menjadi O(n) dengan mengganti pemindaian berulang dengan pencarian instan.

## Idenya

Alih-alih mencari daftar setiap kali, simpan nilai yang sudah dilihat dalam hash map dan periksa keanggotaan dalam waktu konstan.

## Contoh: two-sum dalam O(n)

```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)
```

Tanpa peta ini adalah O(n²); dengannya, satu kali lewatan.

## Penggunaan umum

- **Deduplikasi / keanggotaan** dengan set.
- **Menghitung frekuensi** (`Counter`).
- **Pengelompokan / pengindeksan** berdasarkan kunci.
- **Caching / memoization** hasil.

## Kompleksitas

- **Rata-rata:** O(1) per operasi. **Terburuk:** O(n) pada tabrakan berat. **Ruang:** O(n).

## Jebakan

Kunci harus **hashable** dan tidak dapat diubah. Tabrakan terburuk menurunkan kinerja. Hash map tidak terurut (gunakan varian terurut jika urutan penting).

## Mengapa ini penting

Hashing adalah optimisasi paling umum dalam wawancara coding dan sistem nyata — ini mengubah "cari lagi dan lagi" menjadi "lihat sekali saja."

Tukar ruang dengan waktu adalah lever engineering yang berulang.

Penghitungan frekuensi, caching, dan pengindeksan semuanya bergantung pada satu ide ini.