Tabelas de Dispersão (Hash Tables)
Definição
Uma tabela de dispersão (ou tabela hash) é uma estrutura de dados que associa chaves a valores por meio de uma função de dispersão (hash). Seu principal objetivo é permitir inserção, remoção e busca de elementos de forma eficiente, idealmente em tempo constante:
\[ \mathcal{O}(1) \]
Funções de Dispersão (Hash Functions)
A função de hash transforma a chave (que pode ser um número, string, etc.) em um índice dentro de um vetor fixo. A eficiência da tabela depende diretamente da qualidade da função hash, que deve:
- Distribuir uniformemente os dados;
- Ser rápida de calcular;
- Reduzir colisões.
Exemplo genérico:
\[ \text{índice} = h(\text{chave}) = \text{chave} \bmod N \]
Colisões
Uma colisão ocorre quando duas chaves diferentes geram o mesmo índice na tabela. Como isso é inevitável, a estrutura precisa de uma estratégia de tratamento, como:
- Encadeamento (chaining): cada posição da tabela contém uma lista encadeada de elementos com o mesmo índice.
- Sondagem linear (linear probing): busca sequencial por uma posição livre.
- Sondagem quadrática: similar à linear, mas com saltos crescentes.
- Endereçamento duplo (double hashing): usa uma segunda função hash para definir o salto.
Complexidade
- Melhor caso: \( \mathcal{O}(1) \)
- Pior caso: \( \mathcal{O}(n) \) (em caso de muitas colisões)
- Uso típico (com boa função hash e baixa carga): \( \mathcal{O}(1) \)
As tabelas de dispersão são amplamente utilizadas em bancos de dados, armazenamento de configurações, compiladores e qualquer aplicação que requeira acesso rápido a dados indexados por chave.