HashScope
Visual Hash Engineering Lab
HashScope Theory
Uma tabela hash usa uma função para transformar uma chave em um índice. Quando duas chaves apontam para o mesmo lugar, acontece uma colisão. O HashScope mostra esse caminho de forma visual.
Role a página para entender a ideia e depois teste 15, 25 e 35 no laboratório.
O caminho da chave
A estrutura não procura item por item. Ela calcula onde o valor deveria ficar.
chave
key = 25
A chave é o valor usado como entrada para decidir a posição na tabela.
função
hash(key) = Math.abs(key) % 10
A função hash converte a chave em um índice dentro do tamanho da tabela.
bucket
25 % 10 = 5
O resultado indica o bucket calculado, ou seja, a célula de memória provável.
Por que colisões acontecem?
15 % 10 = 5
25 % 10 = 5
35 % 10 = 5
ADDR 0x05
5
As três chaves apontam para o bucket 5. Como elas querem ocupar o mesmo endereço, a tabela precisa usar uma estratégia de resolução.
É uma estrutura de dados que tenta acessar valores de forma direta usando um cálculo de índice. Em vez de percorrer tudo, ela usa a função hash para chegar perto do destino.
Buckets são as posições da tabela. No HashScope, existem 10 buckets fixos, de 0 até 9, para deixar o comportamento fácil de visualizar.
Uma colisão acontece quando chaves diferentes geram o mesmo índice. Isso é normal em tabelas hash e precisa ser tratado pela estratégia escolhida.
Estratégia
15, 25 e 35 colidem no mesmo bucket. A diferença está em como cada estratégia organiza essa colisão.
01
Quando ocorre colisão, o bucket guarda uma lista de valores. Assim, vários elementos podem viver no mesmo endereço calculado.
Bucket 5 → [15, 25, 35]
02
Cada bucket guarda apenas um valor. Se o bucket calculado está ocupado, o linear probing procura o próximo bucket livre.
15 → 5 25 → 6 35 → 7
Tabelas hash costumam ser rápidas, mas a eficiência depende da função hash, da quantidade de colisões e do load factor.
melhor caso
Θ(1)
A chave cai diretamente no bucket esperado e o acesso é praticamente constante.
caso médio
Θ(1 + α)
No encadeamento, o custo médio cresce com o load factor α.
pior caso
O(n)
Pode acontecer quando muitas chaves colidem ou ficam concentradas.
No laboratório, digite 15, 25 e 35. Primeiro observe a prévia, depois insira os valores e compare Separate Chaining com Open Addressing.
Ir para o laboratórioVisual Hash Engineering Lab
Função fixa
hash(key) = Math.abs(key) % 10Chave
aguardando
Função hash
key % 10
Bucket calculado
—
Resultado
sem operação
Insira 15, 25 e 35 para ver a colisão acontecer no bucket 5.
load factor
0.00
elementos
0
tamanho
10
estratégia
Separate Chaining
estado de colisão
sem colisão
Θ(1 + α)
10 células fixas observando colisões em tempo real
0
ADDR 0x00
chaves
slot vazio
1
ADDR 0x01
chaves
slot vazio
2
ADDR 0x02
chaves
slot vazio
3
ADDR 0x03
chaves
slot vazio
4
ADDR 0x04
chaves
slot vazio
5
ADDR 0x05
chaves
slot vazio
6
ADDR 0x06
chaves
slot vazio
7
ADDR 0x07
chaves
slot vazio
8
ADDR 0x08
chaves
slot vazio
9
ADDR 0x09
chaves
slot vazio