A função hash: espalhar bem as chaves

O que faz uma função hash ser boa

A função hash é a peça que faz ou quebra a tabela. Três qualidades definem uma boa função. A primeira é ser determinística: a mesma chave tem que gerar sempre o mesmo índice, em qualquer momento. Se a Ana caísse hoje no escaninho 2 e amanhã no 5, guardar e buscar nunca combinariam. A segunda é ser rápida de calcular, porque o objetivo da estrutura é justamente evitar trabalho; se calcular o índice fosse tão caro quanto varrer a lista, não haveria ganho. A terceira, e a mais delicada, é espalhar bem: chaves diferentes devem cair em posições variadas, de modo que os itens fiquem distribuídos pelo vetor e não empilhados num canto só.

A distribuição uniforme é o que sustenta a promessa de velocidade. Pense de novo no armário de escaninhos. Se a função mandasse todos os moradores para o escaninho 3, aquele escaninho viraria uma pilha enorme e achar uma carta específica exigiria vasculhar a pilha toda, exatamente o que a tabela queria evitar. Com uma função que espalha bem, cada escaninho fica com poucas cartas, e olhar dentro de um escaninho é rápido porque há pouca coisa ali. Uniformidade não significa perfeição, um espalhamento ideal e impossível; significa que, na média, as chaves se distribuem sem grandes montanhas e vales.

Por dentro de uma função simples

Dá para sentir a diferença com um exemplo. Uma função que só olha a primeira letra do nome espalha mal: muitos nomes brasileiros começam com as mesmas letras, então vários cairiam no mesmo balde. Uma função que soma os códigos de todas as letras e tira o resto pelo tamanho do vetor espalha melhor, porque usa a chave inteira e o resto embaralha os valores. Funções profissionais vão além, misturando os bits da chave com multiplicações e deslocamentos para que até chaves parecidas, como Ana e Ano, terminem longe uma da outra. O princípio, porém, é sempre o mesmo: usar bem a informação da chave e encaixar o resultado na faixa de posições do vetor.

// vetor de 10 posições (índices 0 a 9)
// função: soma dos códigos das letras, resto por 10

FUNÇÃO hash(chave)
  soma <- 0
  PARA cada letra de chave faça
    soma <- soma + codigo(letra)
  fim
  RETORNE soma mod 10
fim

// códigos: R=82 E=69 I=73
// "REI" -> 82 + 69 + 73 = 224
// 224 mod 10 = 4
escreva(hash("REI"))   // 4

A função soma os códigos das letras e tira o resto por 10. O resto é o índice, sempre entre 0 e 9.

// códigos: S=83  O=79  L=76
// vetor de 5 posições (resto por 5)

FUNÇÃO hash(chave)
  soma <- 0
  PARA cada letra de chave faça
    soma <- soma + codigo(letra)
  fim
  RETORNE soma mod 5
fim

escreva(hash("SOL"))

Quando a função atrapalha em vez de ajudar

Uma função hash mal escolhida transforma a estrutura veloz numa estrutura lenta, sem aviso. O sintoma é sempre o mesmo: chaves se acumulando em poucos baldes. Isso acontece quando a função ignora parte da chave (só a primeira letra), quando o tamanho do vetor combina mal com o padrão das chaves, ou quando a regra é fraca demais para embaralhar. No pior caso, se tudo cai no mesmo balde, a tabela hash se comporta como uma lista comum, e buscar volta a ser vasculhar item por item. Por isso, na prática, você raramente escreve a própria função hash: usa a que a linguagem oferece, testada e ajustada por especialistas. Saber o que uma boa função faz ajuda a entender por que a estrutura às vezes desacelera.