Bagaimanakah peta hash mengoptimalkan algoritma?

Question

IT Interview Practice · Accepted Answer

**Peta hash** (kamus) memberikan pencarian, penyisipan, dan penghapusan **O(1) purata**. Menukar memori O(n) untuk kecepatan mengubah banyak algoritma O(n²) menjadi O(n) dengan menggantikan pemindaian berulang dengan pencarian instan.

## Idea

Daripada mencari daftar setiap kali, simpan nilai yang terlihat di peta hash dan periksa keanggotaan dalam waktu tetap.

## Contoh: dua-jumlah 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 lintasan.

## Kegunaan umum

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

## Kerumitan

- **Purata:** O(1) setiap operasi. **Terburuk:** O(n) pada perlanggaran berat. **Ruang:** O(n).

## Jebakan

Kunci mesti **dapat dicincang** dan tidak berubah. Perlanggaran kasus terburuk merendahkan prestasi. Peta hash tidak teratur (gunakan varian teratur jika urutan penting).

## Mengapa ini penting

Hash adalah pengoptimalan tunggal yang paling biasa dalam temu duga kodifikasi dan sistem sebenar — ia menukar "cari lagi dan lagi" menjadi "cari ia sekali".

Pertukaran ruang-untuk-masa adalah tuas kejuruteraan yang berulang.

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

Idea

Contoh: dua-jumlah dalam O(n)

Kegunaan umum

Kerumitan

Jebakan

Mengapa ini penting

Soalan berkaitan