Visualizador de Tabela Hash

Digite chaves e observe como elas são mapeadas para slots. Veja o que acontece quando ocorrem colisões.

Exemplo resolvido — Visualizador de Tabela Hash

Fator de carga alfa	0.75
Comportamento atual	5 colisão(ões)
Sondagens extras	15
Sondagens médias	3.5
Probabilidade de colisão	85%

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

A predefinição de colisão total não tem um hash avariado — tem o tamanho de tabela errado 🖖

As suas chaves são 0, 8, 16, 24, 32 e 40, e a tabela tem 8 lugares. Todas essas chaves são múltiplos de 8, portanto key mod 8 manda as seis para o lugar 0 e a tabela degenera numa única lista. A função de hash não tem nada de errado: faz exatamente o que promete. A falha é o tamanho da tabela partilhar um fator com o padrão das chaves. É nisto que consiste todo o argumento a favor de tamanhos primos — um tamanho de 8 está indefeso contra chaves que avançam de 8 em 8, enquanto um primo não oferece fator nenhum onde cair. Passe às predefinições de sondagem e veja a mesma colisão tratada de duas maneiras.

Salte direto para a posição certa 🖖

Uma tabela de dispersão é simplesmente um vetor associado a uma regra, a função de dispersão, que transforma qualquer chave no número de uma posição. Em vez de percorrer cada entrada, calcula-se onde o elemento deve ficar e vai-se diretamente até lá. Por isso, as consultas continuam rápidas mesmo com milhões de chaves. A rapidez depende de uma distribuição uniforme das chaves. Insira algumas e veja como depressa duas chaves acabam por disputar a mesma posição.

Quando colisões viram arma 🖖

Como uma tabela hash degenera em uma busca linear lenta quando chaves demais caem na mesma posição — exatamente o pior caso que você pode provocar acima —, um atacante que conheça sua função hash pode forjar milhares de chaves que colidem de propósito. Em 2011, esse truque de 'hash-flooding' travou servidores web em PHP, Java, Python e Ruby com uma única requisição manipulada. A solução foram funções hash com semente aleatória como SipHash, hoje padrão em muitas linguagens.

TABELAS HASH — ONDE UMA CHAVE CAI E O QUE ACONTECE QUANDO DUAS CAEM JUNTAS

Qual caso de colisão você está tratando?

Uma tabela hash é O(1) só enquanto as chaves se espalham. Duas perguntas decidem tudo: a função hash espalha suas chaves e, quando duas colidem, você pendura a segunda no mesmo slot ou sai procurando outro? O fator de carga α = n/m decide com que frequência há colisões; a estratégia decide quanto custa cada uma.

Sem colisões — o caso que a promessa O(1) pressupõe h(k) = k mod m, α = n/m

Todas as chaves num slot — o encadeamento degenera em lista O(n)

Sondagem linear — endereçamento aberto com agrupamento primário (h + i) mod m

Sondagem quadrática — sem agrupamento, mas pode recusar a inserção (h + i²) mod m

Sem colisões — o caso que a promessa O(1) pressupõe

O que você sabe: Cada chave cai num slot diferente. O fator de carga α = n/m está abaixo de 1 e o hash espalha as chaves uniformemente pela tabela.

Regra de sondagem: h(k) = k mod m, α = n/m

Exemplo resolvido: chaves 0–5 em m = 8 com h(k) = k mod 8 → slots 0–5, uma sondagem cada: α = 0,75 e média de exatamente 1,00 sondagem

Abrir este caso: Sem colisão

Sem colisões — o caso que a promessa O(1) pressupõe. Seis chaves, seis slots diferentes, uma sondagem cada: só o fator de carga precisa de atenção. Cada chave cai num slot diferente. O fator de carga α = n/m está abaixo de 1 e o hash espalha as chaves uniformemente pela tabela. — Seis chaves, seis slots diferentes, uma sondagem cada: só o fator de carga precisa de atenção.

Todas as chaves num slot — o encadeamento degenera em lista

O que você sabe: Todas as chaves são múltiplos do tamanho da tabela, então k mod m dá o mesmo slot para todas. O encadeamento ainda guarda todas, mas numa única corrente.

Regra de sondagem: O(n)

Exemplo resolvido: chaves 0, 8, 16, 24, 32, 40 em m = 8 → todas caem no slot 0; inseri-las custa 1+2+3+4+5+6 = 21 sondagens, média de 3,50

Abrir este caso: Todas colidem

Todas as chaves num slot — o encadeamento degenera em lista. As seis chaves no slot 0: uma tabela hash que virou lista encadeada. Todas as chaves são múltiplos do tamanho da tabela, então k mod m dá o mesmo slot para todas. O encadeamento ainda guarda todas, mas numa única corrente. — As seis chaves no slot 0: uma tabela hash que virou lista encadeada.

Sondagem linear — endereçamento aberto com agrupamento primário

O que você sabe: Sem correntes: na colisão, avança-se um slot por vez até aparecer um vazio. Cada entrada vive dentro da própria tabela.

Regra de sondagem: (h + i) mod m

Exemplo resolvido: chaves 3, 11, 19, 6, 14, 22 em m = 8 → slots 3, 4, 5, 6, 7, 0 com 1, 2, 3, 1, 2, 3 sondagens: média 2,00, e as seis entradas formam um bloco contínuo

Abrir este caso: Sondagem linear

Sondagem linear — endereçamento aberto com agrupamento primário. Slots ocupados se fundem num bloco; uma chave que caia dentro precisa percorrê-lo até o fim. Sem correntes: na colisão, avança-se um slot por vez até aparecer um vazio. Cada entrada vive dentro da própria tabela. — Slots ocupados se fundem num bloco; uma chave que caia dentro precisa percorrê-lo até o fim.

Sondagem quadrática — sem agrupamento, mas pode recusar a inserção

O que você sabe: Na colisão, salta-se i² slots em vez de i. Isso quebra os blocos, mas a sequência de sondagem deixa de visitar todos os slots.

Regra de sondagem: (h + i²) mod m

Exemplo resolvido: as mesmas chaves em m = 8 → 3, 4, 7, 6, 2 — e então 22 falha de vez: com m potência de dois, i² mod 8 só vale 0, 1 ou 4, então três slots é tudo o que ela alcança

Abrir este caso: Sondagem quadrática

Sondagem quadrática — sem agrupamento, mas pode recusar a inserção. A sequência salta e depois se repete: sobram slots vazios e a última chave não tem para onde ir. Na colisão, salta-se i² slots em vez de i. Isso quebra os blocos, mas a sequência de sondagem deixa de visitar todos os slots. — A sequência salta e depois se repete: sobram slots vazios e a última chave não tem para onde ir.

Problemas resolvidos na íntegra

Uma tabela 75% cheia com média de 3,5 sondagens por pesquisa 5 passos
A tabela está 75% cheia e regista uma média de 3,5 sondagens por pesquisa. A fórmula padrão para sondagem linear prevê 2,5 para essa carga. Descubra qual das duas está errada.
1. Nenhuma está errada, e a razão reside nas chaves. Calcule o hash de cada uma das seis com a própria função da tabela e todas elas retornam 3 — formam uma progressão aritmética de razão 8, e a tabela tem exatamente 8 posições.
  
  $h (k) = k mod 8 : 3, 11, 19, 27, 35, 43 ⟼ 3, 3, 3, 3, 3, 3$
2. O fator de carga continua a ser uns honestos 0,75: seis chaves em oito posições. Simplesmente não diz nada sobre onde elas foram parar.
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
3. Portanto, a sequência de sondagem é a pior disponível. A primeira chave fica numa posição livre; a segunda avança uma posição; a terceira avança duas. Seis chaves custam 1 + 2 + … + 6 = 21 sondagens, das quais 15 correspondem ao trabalho extra reportado pelo painel.
  
  $probes = 1, 2, 3, 4, 5, 6 ⟹ \sum = 21, extra = 21 - 6 = 15$
4. Isso dá uma média de 3,5 sondagens por pesquisa.
  
  $\overset{p}{ˉ} = \frac{21}{6} = 3.5$
5. A estimativa dos manuais assume que as chaves se dispersam uniformemente, e para α = 0,75 fornece 2,5. A diferença entre 2,5 e 3,5 não é um erro — é o custo de uma função de hash que partilha um fator com o tamanho da tabela, aplicada a chaves que também o partilham.
  
  $\frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5 (random keys) < 3.5$
Resposta

A ferramenta apresenta α = 0,75, 15 sondagens de trabalho extra e uma média de 3,5. A lição é que o fator de carga é o número famoso e o número errado a observar isoladamente: é idêntico aqui ao de uma tabela que contenha seis chaves bem dispersas, o que custaria 2,5. O que mudou foi a interação entre o conjunto de chaves e o módulo. É por isto que os tamanhos das tabelas são escolhidos como números primos, e por que fazer o hash de uma estrutura por um campo que por acaso é múltiplo da capacidade transforma O(1) em O(n), mesmo mantendo todas as métricas com aspeto saudável. Altere o tamanho de 8 para 7 e observe a média a colapsar.

$\overset{p}{ˉ} = 3.5 observed vs 2.5 predicted : α is not the whole story$
Um mapa de hash real a redimensionar no fator de carga de 0,75 6 passos
O painel mete 6 chaves em 8 posições, fator de carga 0,75, e reporta 3,5 sondagens. Uma pesquisa bem sucedida com essa carga custa cerca de 2,5 — confortável. Então porque é que toda a tabela de dispersão real se redimensiona precisamente a 0,75 em vez de encher?
1. Comece onde o painel está. Três quartos cheia, o que soa a um uso sensato da memória.
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
2. A pesquisa bem sucedida é o número tranquilizador: em média examina cerca de duas posições e meia até encontrar a chave que queria.
  
  $S (α) \approx \frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5$
3. A pesquisa falhada segue outra fórmula, e é nessa diferença que está toda a resposta. Uma falha tem de percorrer até ao fim uma sequência de posições ocupadas para provar a ausência — por isso o termo do espaço livre entra ao quadrado, e não linearmente.
  
  $U (α) \approx \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) = \frac{1}{2} (1 + 16) = 8.5$
4. Suba um pouco a carga e leia o que o quadrado faz. De 0,75 para 0,90 soa a uma mudança modesta de ocupação.
  
  $U (0.90) = \frac{1}{2} (1 + 100) = 50.5, U (0.95) = \frac{1}{2} (1 + 400) = 200.5$
5. Compare as duas taxas de crescimento nesse mesmo passo. O custo do acerto pouco mais do que duplica; o da falha multiplica-se por seis.
  
  $α : 0.75 \to 0.90 ⟹ S : 2.5 \to 5.5 (\times 2.2), U : 8.5 \to 50.5 (\times 5.9)$
6. Por isso a tabela duplica em vez disso. Todas as chaves são redispersas, o que custa m operações, mas compra mais m inserções antes de voltar a acontecer.
  
  $m \to 2 m ⟹ α \to \frac{α}{2}, \frac{m}{m} = O (1)$
Resposta

Uma falha a 0,75 custa 8,5 sondagens; a 0,90 custa 50,5, e a 0,95 custa 200,5. É por isso que 0,75 é o limiar de redimensionamento numa biblioteca padrão atrás da outra — menos um compromisso entre memória e velocidade do que o último ponto antes do precipício. E o que manda é a falha, porque é por uma falha que começa cada inserção, e é de falha que é feita por inteiro cada pesquisa infrutífera. O tranquilizador 2,5 descreve o caso com que não estava preocupado.

$U (α) = \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) : 2.5 (0.50), 8.5 (0.75), 50.5 (0.90), 200.5 (0.95)$

Percurso de aprendizagem

Quando duas coisas vão dar ao mesmo valor

Referências (1)

Hashing, collision resolution and why table size matters, at length: Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.4. Addison-Wesley, 1998. ISBN 978-0-201-89685-5.

Pela equipa 42Math · Atualizado 2026-07-27

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

Sem colisão - Chaves de 0 a 5 numa tabela de 8: seis posições diferentes, uma sondagem por chave e nenhuma colisão. O fator de carga já é 0,75.
Todas colidem - Todas as chaves são múltiplas de 8, por isso as seis são enviadas para a posição 0 e a cadeia fica com seis elementos. A média é de 3,5 sondagens, o valor de que parte o problema resolvido.
Sondagem linear - 3, 11 e 19 disputam a posição 3; 6, 14 e 22 disputam a posição 6. A sondagem linear acomoda as seis chaves com 1, 2, 3, 1, 2 e 3 sondagens, o que dá uma média de 2.
Sondagem quadrática - Com as mesmas seis chaves, a sondagem quadrática não consegue acomodar a última. Os quadrados módulo 8 só podem ser 0, 1 ou 4. A partir da posição 6, a sequência passa por 6, 7 e 2, sem chegar a mais nenhuma, embora as posições 0, 1 e 5 permaneçam vazias.