Colisões: quando duas chaves querem o mesmo balde

Por que colisões são inevitáveis

Suponha um vetor de dez posições e onze chaves para guardar. Por pura contagem, pelo menos duas vão parar no mesmo balde, não importa quão genial seja a função. Esse encontro tem nome: colisão. E ela não aparece só quando o vetor lota. Mesmo com espaço de sobra, chaves diferentes podem gerar o mesmo índice, porque a função comprime um universo enorme de chaves possíveis (todos os nomes, todos os números) numa quantidade pequena de posições. Comprimir muitos valores em poucos slots sempre gera coincidências. Uma boa função reduz a frequência das colisões, mas nenhuma função as elimina. Aceitar isso é o primeiro passo; tratar bem é o segundo.

O ponto importante é que colisão não é bug. Uma tabela hash bem feita já nasce esperando colisões e tem um plano para elas. O que seria um bug é ignorar a colisão e sobrescrever: se a Ana cai no balde 3 e depois o Bruno também cai no 3, guardar o Bruno por cima da Ana faria a Ana desaparecer. A estrutura precisa de uma regra que acomode os dois sem perder nenhum. Existem duas famílias de regras, e as duas resolvem o mesmo problema por caminhos diferentes. Uma cria espaço dentro do balde; a outra procura espaço em outro balde. Vamos ver as duas.

Encadeamento: uma lista dentro do balde

A primeira estratégia é o encadeamento. Nela, cada posição do vetor não guarda um par sozinho, mas uma lista de pares. Quando a Ana e o Bruno colidem no balde 3, os dois entram na lista daquele balde, um atrás do outro. Buscar a Ana passa a ter dois passos: calcular o índice (chega ao balde 3) e percorrer a lista curta daquele balde comparando as chaves até achar a Ana. Enquanto as listas ficam curtas, e ficam, se a função espalha bem, esse segundo passo é rápido, porque há pouca coisa em cada balde. O encadeamento é simples de entender e de implementar, e lida bem mesmo quando a tabela começa a encher: a lista só cresce um pouco.

// encadeamento: cada balde guarda uma lista de pares
tabela[3] <- [ ["Ana", "99999-1234"], ["Bruno", "98888-5678"] ]

// buscar "Bruno": vai ao balde e percorre a lista curta
i <- hash("Bruno")        // 3
PARA cada par de tabela[i] faça
  SE par[0] = "Bruno" ENTÃO
    escreva(par[1])       // achou: 98888-5678
  fim
fim

No balde 3 mora uma lista. Buscar é calcular o índice e percorrer só aquela lista curta comparando as chaves.

Sondagem: procurar outro slot livre

A segunda estratégia é a sondagem, também chamada de endereçamento aberto. Aqui não há lista nenhuma: cada balde guarda no máximo um par, e todos os itens moram dentro do próprio vetor. Quando a Ana já ocupa o balde 3 e o Bruno colide ali, a regra manda procurar o próximo balde livre: tenta o 4, se estiver ocupado tenta o 5, e assim por diante, até achar um vazio. Guardar o Bruno é depositá-lo nesse primeiro slot livre. E buscar segue a mesma trilha: calcula o índice, e se a chave dali não é a procurada, avança para o próximo, repetindo o mesmo caminho da inserção até encontrar a chave ou um balde vazio (sinal de que ela não está). A sondagem economiza a memória das listas, mas exige cuidado: se o vetor enche, a procura por um slot livre fica longa.

// sondagem linear: se ocupado, tenta o próximo slot
FUNÇÃO guardar(chave, valor)
  i <- hash(chave)
  ENQUANTO tabela[i] não está vazio faça
    i <- (i + 1) mod tamanho    // anda para o próximo slot
  fim
  tabela[i] <- [chave, valor]
fim

// Ana ocupou o 3; Bruno colide no 3 e vai para o 4
guardar("Ana", "99999-1234")   // fica no 3
guardar("Bruno", "98888-5678") // 3 ocupado, vai para o 4

Se o balde calculado está ocupado, a sondagem anda para o próximo slot livre. A busca refaz o mesmo caminho.

Cada estratégia tem seu perfil. O encadeamento é mais tolerante quando a tabela enche, porque só alonga as listas, e é mais simples de raciocinar; em troca, gasta memória com as listas e seus ponteiros. A sondagem aproveita melhor a memória (tudo cabe no vetor) e costuma ser amigável ao processador por manter os dados juntos, mas degrada rápido quando o vetor fica cheio, e remover itens exige truques para não quebrar as trilhas de busca. Na prática, as duas aparecem em bibliotecas reais, e a escolha depende do uso. O que você precisa levar é a ideia central: colisões são certas, e a estrutura vence não por evitá-las, mas por tratá-las bem.