Co je hashovací tabulka a jak dosahuje vyhledávání O(1)?

Question

Accepted Answer

**Hashovací tabulka** (hash map) ukládá páry **key → value** a nabízí průměrné vložení, vyhledávání a smazání v čase **O(1)**. Funguje tím, že každý klíč projde **hashovací funkcí**, která jej mapuje na index v podkladovém poli ("zásobníku").

## Jak to funguje

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

## Příklad

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

## Složitost

| Operace | Průměr | Nejhorší případ |
|---|---|---|
| vložení | O(1) | O(n) |
| vyhledávání | O(1) | O(n) |
| smazání | O(1) | O(n) |

**Nejhorší případ** O(n) nastane, když se mnoho klíčů srazí do stejného zásobníku.

## Kompromisy

- **Silné stránky:** extrémně rychlý přístup založený na klíči; flexibilní klíče.
- **Slabé stránky:** žádné řazení klíčů; dodatečná paměť; O(n) v nejhorším případě; potřeba dobré hashovací funkce.

## Proč je to důležité

Hashovací tabulky jsou v praxi pravděpodobně nejpoužívanější strukturou — jsou základem slovníků, množin, cache pamětí, indexů databází a deduplikace.

Nahrazení lineárního prohledávání hashovacím vyhledáváním je jedním z nejčastějších způsobů, jak přeměnit algoritmus O(n²) na O(n).