Por que a busca é quase instantânea

De onde vem o tempo constante

Compare os custos. Achar um valor numa lista comum pela busca item por item é O(n): no pior caso, você olha os n itens. Numa lista ordenada, a busca binária corta pela metade a cada passo e chega a O(log n), bem melhor, mas ainda cresce com o tamanho. A tabela hash faz algo diferente: calcula o índice da chave e vai direto ao balde. Esse cálculo não olha os outros itens, então não importa se a tabela tem dez ou dez milhões de pares, o número de passos para chegar ao balde é praticamente o mesmo. Esse custo que quase não cresce com o tamanho é o tempo constante, escrito O(1). É a razão de o dicionário ser a estrutura preferida quando o que você faz o tempo todo é buscar pela chave.

Vale insistir numa palavra: em média. O O(1) da tabela hash é uma média, não uma garantia para cada operação. Se a função espalha bem e a tabela não está lotada, cada balde tem pouquíssimos itens, e ir ao balde mais conferir um ou dois pares é rápido, praticamente constante. Mas se muitos itens colidem no mesmo balde, achar a chave certa ali dentro vira uma pequena varredura, e no pior caso, com tudo num balde só, a tabela hash se comporta como uma lista, de volta ao O(n). O bom projeto trabalha para que o pior caso quase nunca aconteça, mantendo a média perto do O(1). E a alavanca principal para isso é o fator de carga.

O fator de carga: quão cheia está a tabela

O fator de carga é uma conta simples: a quantidade de itens guardados dividida pelo número de posições do vetor. Um vetor de dez posições com três itens tem fator de carga 0,3; com nove itens, 0,9. Esse número resume a lotação da tabela e prevê o desempenho. Fator baixo significa muita folga, poucos itens por balde e busca rápida. Fator alto significa vetor apertado, muitas colisões e busca cada vez mais lenta. Por isso o fator de carga é o termômetro da tabela hash: enquanto ele fica baixo, o O(1) se sustenta; quando sobe demais, a estrutura começa a perder o que a tornava especial. As implementações reais vigiam esse número de perto.

// fator de carga = itens guardados / posições do vetor
itens <- 6
posicoes <- 10
carga <- itens / posicoes
escreva("Fator de carga: ", carga)   // 0.6

// muitas implementações crescem quando a carga passa de ~0.7
SE carga > 0.7 ENTÃO
  escreva("Hora de crescer o vetor e reposicionar as chaves")
fim

O fator de carga mede a lotação. Passando de um limite (por volta de 0,7), a tabela costuma crescer o vetor.

Crescer e reorganizar para manter a velocidade

O que uma tabela hash faz quando o fator de carga sobe demais? Ela cresce. Ao passar de um limite (nas implementações reais, algo por volta de 0,7), a estrutura cria um vetor maior, geralmente com o dobro de posições, e recoloca cada item, recalculando o índice de cada chave no vetor novo. Esse processo tem nome, reidratação ou redimensionamento, e é a manutenção que mantém a busca rápida ao longo do tempo. Recolocar tudo tem um custo pontual, aquela operação específica é cara, mas acontece raramente e, diluído entre as muitas inserções baratas, o custo médio por operação continua constante. É por isso que, mesmo com a tabela crescendo, você quase nunca sente lentidão: o preço da mudança de casa é pago aos poucos.