Desenhe uma tabela de hash resultante da introdução das chaves 12, 44, 13, 88, 23,
, 16 e 5 , usando a função de hash
e supondo que as colisões são tratadas por encadeamento separado.
Passo 1
O enunciado pede para montar uma tabela de hash inserindo as chaves 12, 44, 13, 88, 23, 94, 11, 39, 20, 16 e 5, usando a função de hash
e tratando colisões por encadeamento separado. Vamos aplicar conceitos de funções de hash e listas encadeadas para resolver.
Passo 2
Precisamos usar a função de hash para distribuir cada chave num índice de 0 a 10. Em caso de colisão, vamos colocar a chave no final de uma lista ligada (encadeamento separado) correspondente àquele índice.
Passo 3
Calculamos
para cada chave conforme a seguir:
Passo 4
Agora agrupamos as chaves em buckets (índices) de 0 a 10, mantendo a ordem de inserção em cada lista encadeada:
- Índice 0: vazio
- Índice 1: 20
- Índice 2: vazio
- Índice 3: vazio
- Índice 4: 16 → 5
- Índice 5: 44 → 88 → 11
- Índice 6: 94 → 39
- Índice 7: 12 → 23
- Índice 8: vazio
- Índice 9: 13
- Índice 10: vazio
Resposta
Tabela de hash com encadeamento separado (índices 0–10):
0 : –
1 : 20
2 : –
3 : –
4 : 16 → 5
5 : 44 → 88 → 11
6 : 94 → 39
7 : 12 → 23
8 : –
9 : 13
10: –
1 : 20
2 : –
3 : –
4 : 16 → 5
5 : 44 → 88 → 11
6 : 94 → 39
7 : 12 → 23
8 : –
9 : 13
10: –