Uma tabela hash não procura — ela calcula onde um valor está. Uma função converte a chave em um índice de array, transformando busca, inserção e remoção em operações de tempo praticamente constante.
A "mágica" da tabela hash é só um array comum. O que muda é como o índice é escolhido: em vez de você decidir, uma função decide por você, a partir da chave.
Existem várias formas de fazer isso; este site usa uma soma ponderada dos códigos dos caracteres, reduzida ao tamanho da tabela com o operador módulo.
A mesma entrada sempre produz a mesma saída — é isso que permite reencontrar o valor depois.
Uma boa função hash evita concentrar chaves diferentes nos mesmos poucos índices.
Colisão não é um bug — é estatisticamente inevitável. A técnica usada para resolver é o que diferencia uma implementação de outra.
Quando dois itens colidem no mesmo índice, eles ficam encadeados dentro do mesmo balde. É a técnica usada no visualizador abaixo.
Em vez de encadear, o item colidido é movido para outro índice livre, seguindo uma sequência de tentativas.
Cada chave é convertida em um índice pela função hash acima. Quando dois itens caem no mesmo balde, eles se encadeiam — veja isso acontecer ao inserir chaves parecidas.
O desempenho depende diretamente da qualidade da função hash e de quantas colisões ela produz.
| Operação | Caso médio | Pior caso | Quando o pior caso ocorre |
|---|---|---|---|
| Inserção | O(1) | O(n) | Todas as chaves colidem no mesmo índice |
| Busca | O(1) | O(n) | Cadeia longa em um único balde |
| Remoção | O(1) | O(n) | Mesma causa da busca no pior caso |