Kako razpredelne tabele (hash maps) optimizirajo algoritme?

Question

Accepted Answer

**Razpredelna tabela** (angl. hash map, slovar) daje **O(1) v povprečju** za iskanja, vstavljanja in brisanja. Z zamenjavo O(n) pomnilnika za hitrost se marsikateri O(n²) algoritem spremeni v O(n) z zamenjavo ponavljajočih pregledov z trenutnimi iskanjem.

## Osnovna ideja

Namesto pregleda seznama vsakič, shranjene vrednosti shranimo v razpredelno tabelo in preverimo pripadnost v konstantnem času.

## Primer: two-sum v 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)
```

Brez razpredelne tabele je to O(n²); z njo pa le en prehod.

## Pogoste uporabe

- **Deduplikacija / pripadnost** z množico.
- **Štetje frekvenc** (`Counter`).
- **Razvrščanje / indeksiranje** po ključu.
- **Predpomnenje / memoizacija** rezultatov.

## Časovna zahtevnost

- **Povprečje:** O(1) na operacijo. **Najslabši primer:** O(n) ob večjih trkih. **Prostor:** O(n).

## Pasti

Ključi morajo biti **hashabilni** in nespremenjivi. Najslabši primeri trkov poslabšajo zmogljivost. Razpredelne tabele so neurejenosortirane (uporabite urejene različice, če je vrstni red važen).

## Zakaj je to važno

Razpredelna funkcija je najbolj običajno izboljšanje pri intervjujih iz programiranja in v realnih sistemih — spremeni »iskalnik znova in znova« v »poglej samo enkrat«.

Trgovanje prostora za hitrost je ponavljajoča se inženirska tehnologija.

Štetje frekvenc, predpomnenje in indeksiranje se vsi slonijo na tej eni ideji.