Jak hash mapy optimalizují algoritmy?

Question

Accepted Answer

**Hash mapa** (slovník) poskytuje **O(1) průměr** pro vyhledávání, vkládání a mazání. Nahrazením opakovaných vyhledávání okamžitým vyhledáváním se převádí mnoho O(n²) algoritmů na O(n) za cenu O(n) paměti.

## Hlavní myšlenka

Místo hledání v seznamu pokaždé uložte viděné hodnoty do hash mapy a zkontrolujte příslušnost v konstantním čase.

## Příklad: 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)
```

Bez mapy je to O(n²); s ní pouze jeden průchod.

## Běžné použití

- **Deduplikace / příslušnost** se sadou.
- **Počítání frekvencí** (`Counter`).
- **Seskupování / indexování** podle klíče.
- **Cachování / memoizace** výsledků.

## Složitost

- **Průměr:** O(1) na operaci. **Nejhorší:** O(n) při těžkých kolizích. **Prostor:** O(n).

## Úskalí

Klíče musí být **hashable** a neměnné. Kolize v nejhorším případě zhoršují výkon. Hash mapy jsou neuspořádané (používejte seřazené varianty, pokud záleží na pořadí).

## Proč na tom záleží

Hashování je jediným nejčastějším optimalizačním postupem v kódovacích pohovorech a skutečných systémech — převádí "hledání znovu a znovu" na "podívej se na to jednou".

Výměna prostoru za čas je opakující se inženýrský nástroj.

Počítání frekvencí, cachování a indexování vše závisí na jedné myšlence.