Što je heš tablica i kako postižu O(1) pretragu?

Question

Accepted Answer

**Heš tablica** (heš mapa) sprema **ključ → vrijednost** parove i nudi **prosječno O(1)** umetanje, pretragu i brisanje. Funkcionira tako što svaki ključ prosljeđuje kroz **heš funkciju** koja ga preslikava na indeks u osnovnom nizu ("bucket").

## Kako funkcionira

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

## Primjer

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

## Vremenska složenost

| Operacija | Prosječno | Najgore |
|---|---|---|
| umetanje | O(1) | O(n) |
| pretraga | O(1) | O(n) |
| brisanje | O(1) | O(n) |

**Najgori slučaj** O(n) se javlja kada se mnogi ključevi sudare u istu grupu.

## Kompromisi

- **Prednosti:** ekstremno brz pristup baziran na ključu; fleksibilni ključevi.
- **Nedostaci:** nema redoslijeda ključeva; dodatna memorija; O(n) u najgorem slučaju; potrebna dobra heš funkcija.

## Zašto je važno

Heš tablice su vjerojatno najčešće korištena struktura u praksi — iza rječnika, skupova, međuspremnika, indeksa baza podataka i uklanjanja duplikata.

Zamjena linearne pretrage s heš pretraživanjem jedan je od najčešćih načina da se algoritam O(n²) pretvori u O(n).