A tabela hash: o dicionário por dentro

Por que o dicionário parece mágica

No curso intermediário o dicionário entrou como uma ferramenta pronta: você criava um par chave-valor, tipo agenda["Ana"] guardando o telefone da Ana, e recuperava o telefone só citando o nome. Funcionava, e era rápido, mas ficou uma pergunta no ar: como o programa acha o valor da Ana tão depressa? Se fosse uma lista de mil contatos, procurar a Ana varrendo um por um levaria, no pior caso, mil comparações. O dicionário não faz isso. Ele acha a Ana quase no mesmo tempo, tenha ele dez ou dez milhões de contatos. Essa velocidade constante não é mágica nem sorte: é a tabela hash trabalhando por baixo.

A ideia central é trocar procura por cálculo. Imagine um armário de correspondência com cem escaninhos numerados. Se cada morador tivesse um número de escaninho fixo e você soubesse calcular esse número a partir do nome, não precisaria abrir escaninho por escaninho até achar a carta certa. Bastaria calcular o número e ir direto. A tabela hash faz exatamente isso: o vetor interno são os escaninhos, e a função de dispersão é a regra que transforma o nome (a chave) no número do escaninho (o índice). Guardar a carta da Ana é calcular o índice do nome Ana e depositar ali; buscar é calcular o mesmo índice e olhar naquele escaninho.

Da chave ao índice: um cálculo, não uma busca

O coração da estrutura é a passagem da chave para o índice. A chave pode ser um texto, um número, uma data, qualquer coisa que identifique o dado. O índice, porém, precisa ser um número inteiro entre 0 e o tamanho do vetor menos um, porque é uma posição de vetor. A função hash é a ponte entre esses dois mundos: recebe uma chave qualquer e devolve um índice válido. Um jeito simples, só para enxergar a ideia, é somar os códigos das letras do nome e tirar o resto da divisão pelo tamanho do vetor. O resto sempre cai dentro da faixa de posições, e a mesma chave sempre gera o mesmo índice.

// vetor com 7 posições (escaninhos 0 a 6)
tabela <- [vazio, vazio, vazio, vazio, vazio, vazio, vazio]

FUNÇÃO indice_de(chave)
  soma <- 0
  PARA cada letra de chave faça
    soma <- soma + codigo(letra)   // codigo("A") = 65, etc.
  fim
  RETORNE soma mod 7               // resto da divisão: cai entre 0 e 6
fim

// guardar: calcula o índice e deposita ali
i <- indice_de("Ana")
tabela[i] <- ["Ana", "99999-1234"]

// buscar: calcula o MESMO índice e vai direto
j <- indice_de("Ana")
escreva(tabela[j])   // vai direto ao escaninho, sem varrer

A função soma os códigos das letras e tira o resto pelo tamanho do vetor. A mesma chave sempre cai no mesmo índice.

O que muda em relação à lista

Vale comparar com o que você já domina. Numa lista, achar um valor pelo conteúdo (não pela posição) obriga a percorrer, porque a lista não sabe onde cada coisa está, só a ordem em que foram colocadas. Numa lista ordenada dá para usar busca binária e cortar pela metade, mas ainda são vários passos, e manter a lista ordenada tem custo. A tabela hash muda o jogo ao pagar um preço diferente: ela gasta um pouco de memória extra (o vetor costuma ter mais posições do que itens guardados) e um cálculo rápido por acesso, e em troca vai direto ao dado sem depender do tamanho da coleção. É uma troca clássica em computação: usar mais espaço para ganhar tempo.