Demonstre a inserção das chaves 5, 28, 19, 15, 20, 33, 12, 7 e 10 numa tabela de hash com colisões resolvidas por encadeamento separado. Considere a tabela com
posições e a função hash como sendo
. Reconstrua a tabela para
(primo) e comente os resultados.
Passo 1
Resumo da questão: a gente precisa inserir as chaves 5, 28, 19, 15, 20, 33, 12, 7 e 10 numa tabela de hash usando encadeamento separado, primeiro com tamanho
e função de hash
. Depois vamos refazer tudo com
e comparar a distribuição.
Passo 2
Entendendo o encadeamento separado: cada posição da tabela é um ponteiro para uma lista ligada. Para inserir uma chave
, calculamos
e anexamos
ao final da lista em
. Fazendo isso para as 9 chaves obtemos a tabela:
0: –
1: 28 → 19 → 10
2: 20
3: 12
4: –
5: 5
6: 15 → 33
7: 7
8: –
0: –
1: 28 → 19 → 10
2: 20
3: 12
4: –
5: 5
6: 15 → 33
7: 7
8: –
Passo 3
Agora repetimos o processo com
: calculamos
e inserimos em listas separadas. O resultado é:
0: 33
1: 12
2: –
3: –
4: 15
5: 5
6: 28
7: 7
8: 19
9: 20
10: 10
0: 33
1: 12
2: –
3: –
4: 15
5: 5
6: 28
7: 7
8: 19
9: 20
10: 10
Passo 4
Comparação e comentário: usando
(primo) as colisões praticamente desaparecem e as listas têm no máximo um elemento. Com
tivemos buckets com 3 e 2 itens, o que piora o tempo de busca. Portanto, escolher
primo geralmente melhora a distribuição das chaves.
Resposta
Tabela de hash com
e encadeamento separado:
0: –
1: 28 → 19 → 10
2: 20
3: 12
4: –
5: 5
6: 15 → 33
7: 7
8: –
0: –
1: 28 → 19 → 10
2: 20
3: 12
4: –
5: 5
6: 15 → 33
7: 7
8: –
Tabela de hash com
e encadeamento separado:
0: 33
1: 12
2: –
3: –
4: 15
5: 5
6: 28
7: 7
8: 19
9: 20
10: 10
0: 33
1: 12
2: –
3: –
4: 15
5: 5
6: 28
7: 7
8: 19
9: 20
10: 10
Comentário final: usando um tamanho de tabela primo (
) reduzimos drasticamente as colisões e garantimos listas mais curtas, o que melhora a eficiência das operações de busca e inserção.