O que é uma tabela de espalhamento e como ela consegue busca O(1)?

Question

Accepted Answer

Uma **tabela de espalhamento** (hash map) armazena pares **key → value** e oferece insert, lookup e delete com **O(1)** em média. Funciona passando cada chave por uma **função de espalhamento** que a mapeia para um índice em um array subjacente (um "bucket").

## Como funciona

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

## Exemplo

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

## Complexidade

| Operação | Média | Pior caso |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

O **pior caso** O(n) acontece quando muitas chaves colidem no mesmo bucket.

## Trade-offs

- **Vantagens:** acesso extremamente rápido baseado em chaves; chaves flexíveis.
- **Desvantagens:** nenhuma ordenação de chaves; memória extra; O(n) no pior caso; requer uma boa função de espalhamento.

## Por que isso importa

Tabelas de espalhamento são provavelmente a estrutura mais usada na prática — por trás de dicionários, conjuntos, caches, índices de banco de dados e deduplicação.

Substituir uma varredura linear por uma busca de espalhamento é uma das maneiras mais comuns de transformar um algoritmo O(n²) em O(n).