Kako hash mape optimiziraju algoritme?

Question

Accepted Answer

**Hash mapa** (rječnik) omogućava **O(1) prosječne** lookup-e, umetanja i brisanja. Zamjena O(n) memorije za brzinu pretvara mnoge O(n²) algoritme u O(n) zamjenom ponovljenih pretraga s trenutnim lookup-ima.

## Ideja

Umjesto pretraživanja liste svaki put, pohranite viđene vrijednosti u hash mapu i provjerite članstvo u konstantnom vremenu.

## Primjer: two-sum u 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)
```

Bez mape ovo je O(n²); s njom, jedan prolazak.

## Česta uporaba

- **Deduplikacija / članstvo** sa skupom.
- **Brojanje frekvencija** (`Counter`).
- **Grupiranje / indeksiranje** po ključu.
- **Cachiranje / memoizacija** rezultata.

## Složenost

- **Prosječno:** O(1) po operaciji. **Najgore:** O(n) pri teškim sudarima. **Prostor:** O(n).

## Zamke

Ključevi moraju biti **hashabilni** i nepromjenjivi. Sudaranja u najgorem slučaju degradiraju performanse. Hash mape su neuređene (koristite uređene varijante ako redoslijed važi).

## Zašto je važno

Hashiranje je najčešća optimizacija u intervjuima iz kodiranja i stvarnim sustavima — pretvara "pretraži ponovno i ponovno" u "pronađi to jednom".

Trgovinski odnos prostor-za-vrijeme je ponavljajuća poluga inženjerstva.

Brojanje frekvencija, cachiranje i indeksiranje svi počivaju na toj jednoj ideji.