Tabela Hash — Como o Hashing Funciona e Como Resolver Colisões

Uma tabela hash armazena pares chave-valor aplicando uma função hash a cada chave para obter um índice em um array. Isso permite que a tabela vá direto para perto da posição correta, em vez de percorrer cada item armazenado um por um.

É por isso que tabelas hash costumam ter custo próximo de $O(1)$ para busca, inserção e remoção em média. Essa condição importa: a função hash precisa distribuir as chaves de forma razoável, e a tabela ainda precisa de uma regra para lidar com colisões.

O Que Uma Tabela Hash Faz

Uma tabela hash armazena pares chave-valor como "name" -> "Ada" ou 42 -> "blue". Ela tem duas partes principais:

• um array de posições ou buckets
• uma função hash que mapeia cada chave para uma dessas posições

Se o array tem $m$ posições, você pode pensar na função hash como produzindo um índice de $0$ a $m-1$.

Em um exemplo simples com inteiros pequenos, a regra pode ser

$$h(k) = k \bmod 8$$

Então a chave $10$ vai para a posição $2$ porque $10 \bmod 8 = 2$.

Funções hash reais são projetadas com mais cuidado, especialmente para strings e conjuntos de dados maiores. Mas a ideia central continua a mesma: calcular um índice rapidamente e depois verificar o item armazenado ali.

Por Que Colisões de Hash São Inevitáveis

Uma colisão acontece quando duas chaves diferentes são mapeadas para a mesma posição.

Isso é normal porque a tabela geralmente tem menos posições do que o número de chaves possíveis. Com

$$h(k) = k \bmod 8$$

as chaves $10$, $18$ e $26$ são todas mapeadas para a posição $2$. Então, mesmo que a função esteja funcionando exatamente como foi definida, a tabela ainda tem um conflito para resolver.

Portanto, uma tabela hash não promete uma posição única para cada chave. Ela promete uma forma rápida de reduzir a busca, desde que as colisões sejam tratadas corretamente.

Exemplo Resolvido: Uma Tabela, Uma Colisão

Suponha que uma tabela tenha $8$ posições e use

$$h(k) = k \bmod 8$$

Insira as chaves $10$, $18$ e $7$.

Primeiro, $10$ vai para a posição $2$ porque $10 \bmod 8 = 2$.

Depois, $18$ também é mapeada para a posição $2$, então ocorre uma colisão.

Em seguida, $7$ vai para a posição $7$, então essa inserção não colide.

O padrão útil é sempre o mesmo:

1. Aplique hash à chave.
2. Vá para a posição sugerida.
3. Se já houver uma chave diferente ali, aplique a regra de colisão.

Quando esse padrão fica claro, as duas principais estratégias de colisão ficam mais fáceis de entender.

Encadeamento Vs. Endereçamento Aberto

O encadeamento mantém um bucket em cada posição

No encadeamento, cada posição armazena uma pequena coleção de entradas em vez de apenas uma.

Se $10$ e $18$ forem ambos mapeados para a posição $2$, o bucket $2$ pode armazenar

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

Para encontrar a chave $18$, a tabela vai direto ao bucket $2$ e compara apenas as entradas dentro desse bucket.

O encadeamento é conceitualmente simples, e a remoção costuma ser mais fácil do que no endereçamento aberto. A desvantagem é que buckets longos tornam as operações mais lentas.

O endereçamento aberto permanece dentro do array

No endereçamento aberto, cada posição do array guarda no máximo uma entrada. Se a posição original estiver ocupada, a tabela testa outras posições de acordo com uma regra fixa.

Uma regra comum é a sondagem linear: se a posição $2$ estiver ocupada, tente $3$, depois $4$, depois $5$, voltando ao início se necessário.

Isso evita listas separadas de buckets, mas posições preenchidas próximas umas das outras podem formar agrupamentos. Outro detalhe é que busca e remoção precisam respeitar a mesma regra de sondagem usada durante a inserção.

Quando $O(1)$ É Uma Afirmação Justa

Tabelas hash costumam ser descritas como tendo busca, inserção e remoção em $O(1)$ em média. Essa afirmação de caso médio depende de algumas condições:

• a função hash distribui as chaves de forma razoável
• o fator de carga permanece sob controle
• a estratégia de colisão é implementada corretamente

O fator de carga é a razão

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

Se a tabela ficar cheia demais, as colisões se tornam mais frequentes, e o desempenho piora. É por isso que muitas implementações redimensionam o array à medida que ele enche.

O desempenho no pior caso ainda pode se degradar em direção a $O(n)$ se muitas chaves se acumularem na mesma região.

Erros Comuns com Tabelas Hash

Supor que colisões significam que a função hash falhou

Não significam. Colisões são esperadas. A verdadeira questão é se a tabela lida com elas de forma eficiente.

Tratar $O(1)$ como algo incondicional

$O(1)$ geralmente é uma afirmação de caso médio, não uma promessa para toda entrada e em todo momento.

Confundir hashing aqui com criptografia

Uma função hash no contexto básico de estruturas de dados serve principalmente para indexação rápida, não para sigilo. Esses são objetivos diferentes.

Esquecer de comparar a chave real

Duas chaves podem compartilhar o mesmo resultado de hash. Depois de chegar ao bucket certo ou à posição de sondagem correta, a tabela ainda precisa verificar se a chave realmente corresponde.

Quando Tabelas Hash São Usadas

Tabelas hash são usadas sempre que a busca rápida por chave é importante. Exemplos comuns incluem dicionários, tabelas de símbolos, caches, indexação e contagem de frequências em dados.

Elas são uma ótima escolha quando a busca exata por chave é mais importante do que manter os itens em ordem. Se você precisa de travessia ordenada, consultas por intervalo ou valores mais próximos, outra estrutura pode ser melhor.

Tente Um Exemplo Parecido de Colisão

Pegue um array pequeno com $8$ posições e use $h(k)=k \bmod 8$. Insira algumas chaves como $3$, $11$, $19$ e $27$. Depois resolva as colisões uma vez com encadeamento e outra com sondagem linear.

Esse único exercício torna a ideia principal concreta muito rapidamente: colisões são inevitáveis, e a regra de colisão muda o comportamento da tabela. Se quiser um próximo passo útil, tente sua própria versão com um tamanho de tabela diferente e veja como as colisões mudam.