Cum optimizează hash maps algoritmii?

Question

Accepted Answer

O **hash map** (dicționar) oferă **O(1) în medie** pentru căutări, inserări și ștergeri. Tranzacționând memoria O(n) pentru viteză, mulți algoritmi O(n²) se transformă în O(n) prin înlocuirea scanărilor repetate cu căutări instantanee.

## Ideea

În loc să cauți o listă de fiecare dată, stochează valorile pe care le-ai văzut într-o hash map și verifică apartenența în timp constant.

## Exemplu: two-sum în 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)
```

Fără harta este O(n²); cu ea, o trecere.

## Utilizări comune

- **Deduplicare / apartenență** cu un set.
- **Numărarea frecvențelor** (`Counter`).
- **Grupare / indexare** după cheie.
- **Caching / memoizare** de rezultate.

## Complexitate

- **Medie:** O(1) pe operație. **Cel mai rău:** O(n) la coliziuni grele. **Spațiu:** O(n).

## Capcane

Chei trebuie să fie **hashable** și imutabile. Coliziunile în cel mai rău caz degradează performanța. Hash maps sunt neordonate (utilizează variante ordonate dacă ordinea contează).

## De ce este important

Hash-ul este cea mai comună optimizare în interviurile de codificare și sistemele reale — convertește "cauta din nou și din nou" în "cauta o dată".

Tranzacția spațiu-pentru-timp este o pârghie recurentă de inginerie.

Numărarea frecvențelor, caching-ul și indexarea se bazează pe această singură idee.