Hashing
Hashing em Algoritmos e Estruturas de Dados
Hashing é uma técnica eficiente para armazenar e recuperar dados em tempo constante (O(1) no caso médio. Utiliza uma função hash para mapear chaves a posições em uma tabela (array).
Componentes Principais
- Função Hash: Converte uma chave em um índice da tabela (ex: módulo, multiplicação).
- Tabela Hash: Estrutura (array) que armazena os dados.
- Colisões: Ocorrem quando duas chaves distintas são mapeadas para o mesmo índice.
Tratamento de Colisões
- Encadeamento: Armazena itens colididos em listas ligadas.
- Endereçamento Aberto: Busca posições alternativas na própria tabela (ex: sondagem linear, quadrática).
Vantagens
- Tempo de acesso rápido (O(1) no caso médio).
- Eficiência em operações de inserção, busca e remoção.
Desvantagens
- Pior caso O(n) se muitas colisões ocorrerem.
- Não mantém ordem das chaves.
Aplicações em Concursos
Foco em: cálculo de funções hash, métodos de tratamento de colisões, complexidade de operações e comparação com outras estruturas (ex: árvores).