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 m=9 posições e a função hash como sendo h(k)=k % m. Reconstrua a tabela para m=11 (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 m=9 e função de hash h(k)=kbmod m. Depois vamos refazer tudo com m=11 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 k, calculamos h(k)=kbmod 9 e anexamos k ao final da lista em T[h(k)]. 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: –

Passo 3

Agora repetimos o processo com m=11: calculamos h(k)=kbmod 11 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

Passo 4

Comparação e comentário: usando m=11 (primo) as colisões praticamente desaparecem e as listas têm no máximo um elemento. Com m=9 tivemos buckets com 3 e 2 itens, o que piora o tempo de busca. Portanto, escolher m primo geralmente melhora a distribuição das chaves.

Resposta

Tabela de hash com m=9 e encadeamento separado:
0: –
1: 28 → 19 → 10
2: 20
3: 12
4: –
5: 5
6: 15 → 33
7: 7
8: –
Tabela de hash com m=11 e encadeamento separado:
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 ( m=11) reduzimos drasticamente as colisões e garantimos listas mais curtas, o que melhora a eficiência das operações de busca e inserção.

Exercícios relacionados