Como hash maps otimizam algoritmos?

Question

Accepted Answer

Um **hash map** (dicionário) oferece **O(1) em média** para buscas, inserções e exclusões. Trocando O(n) de memória por velocidade, muitos algoritmos O(n²) são transformados em O(n) substituindo varreduras repetidas por buscas instantâneas.

## A ideia

Em vez de pesquisar uma lista cada vez, armazene valores já vistos em um hash map e verifique a associação em tempo constante.

## Exemplo: two-sum em 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)
```

Sem o mapa é O(n²); com ele, uma passada.

## Usos comuns

- **Deduplicação / associação** com um conjunto.
- **Contagem de frequências** (`Counter`).
- **Agrupamento / indexação** por chave.
- **Caching / memoização** de resultados.

## Complexidade

- **Média:** O(1) por operação. **Pior caso:** O(n) em colisões pesadas. **Espaço:** O(n).

## Armadilhas

Chaves devem ser **hashable** e imutáveis. Colisões no pior caso degradam o desempenho. Hash maps são desordenados (use variantes ordenadas se a ordem importa).

## Por que isso importa

Hash é a otimização mais comum em entrevistas de codificação e sistemas reais — converte "busque novamente e novamente" em "procure uma vez".

A troca espaço-por-tempo é uma alavanca de engenharia recorrente.

Contagem de frequência, caching e indexação repousam todas nessa uma ideia.