Kaj je zgoščena tabela in kako doseže O(1) iskanje?

Question

Accepted Answer

**Zgoščena tabela** (hash map) shranjuje pare **key → value** in ponuja **povprečno O(1)** vstavljanje, iskanje in brisanje. Deluje tako, da vsak ključ preslika skozi **zgoščevalno funkcijo**, ki ga preslikuje na indeks v osnovnem polju ("bucket").

## Kako deluje

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

## Primer

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

## Časovna zahtevnost

| Operacija | Povprečje | Najslabši primer |
|---|---|---|
| vstavljanje | O(1) | O(n) |
| iskanje | O(1) | O(n) |
| brisanje | O(1) | O(n) |

**Najslabši primer** O(n) se pojavi, ko se mnogo ključev trči v isti bucket.

## Kompromisi

- **Prednosti:** ekstremno hitro dostopanje na osnovi ključa; fleksibilni ključi.
- **Slabosti:** brez urejanja ključev; dodatna pomnilnik; O(n) v najslabšem primeru; potrebna je dobra zgoščevalna funkcija.

## Zakaj je to pomembno

Zgoščene tabele so verjetno najbolj uporabljena struktura v praksi — za slovarje, množice, predpomnilnike, indekse baz podatkov in dedupliciranje.

Zamenjava linearnega pregleda z zgoščevalno iskalnim je eden izmed najbolj pogostih načinov za spremembo algoritma O(n²) v O(n).