Alternativa D - key % 20 e (result + 7) % 20
Análise Detalhada
Para resolver esta questão, precisamos identificar as funções de hash (h(x)) e de re-hash (r(x)) analisando o comportamento da tabela de dispersão (hash table) apresentada na imagem.
1. Determinação do Tamanho da Tabela
Observando a estrutura da tabela na imagem, vemos que os índices (array index) variam de 0 a 19.
- Isso indica que o tamanho da tabela é 20.
- Consequentemente, qualquer operação de hash válida deve utilizar o operador módulo 20 (\% 20).
Isso nos permite eliminar imediatamente as alternativas c e e, pois elas utilizam % 30. A alternativa b também pode ser descartada porque uma função de re-hash que apenas repete o resultado (result % 20) causaria um loop infinito na mesma posição caso houvesse colisão.
2. Simulação da Função Hash Inicial h(x)
Testemos a função proposta nas alternativas restantes: h(x) = \text{key} \% 20. Vamos verificar se as chaves principais coincidem com seus índices iniciais antes de eventuais colisões.
| Chave | Cálculo (key \% 20) | Posição Final na Tabela | Coincidência? |
|---|
| 62 | $62 \% 20 = 2$ | Índice 2 | Sim |
| 81 | $81 \% 20 = 1$ | Índice 1 | Sim |
| 79 | $79 \% 20 = 19$ | Índice 19 | Sim |
| 12 | $12 \% 20 = 12$ | Índice 12 | Sim |
| 54 | $54 \% 20 = 14$ | Índice 14 | Sim |
| 97 | $97 \% 20 = 17$ | Índice 17 | Sim |
| 34 | $34 \% 20 = 14$ | Índice 8 | Não (Colisão!) |
Todas as chaves estão na posição esperada pela função módulo 20, exceto a chave 34, que deveria ir para o índice 14 (ocupado por 54), mas acabou indo para o índice 8.
3. Dedução da Função de Re-hash r(x)
A chave 34 sofreu uma colisão no índice 14. Para encontrar a nova posição (índice 8), aplicamos a função de re-hash iterativamente.
- Opção A (Passo +13):
- Passo 1: (14 + 13) \% 20 = 7. (O índice 7 está vazio na tabela final, mas a chave 34 está no 8). Esta opção falha.
- Opção D (Passo +7):
- Passo 1: (14 + 7) \% 20 = 21 \% 20 = 1.
- O índice 1 já estava ocupado pela chave 81. Novamente, há colisão.
- Passo 2: (1 + 7) \% 20 = 8.
- O índice 8 estava vazio. A chave 34 é inserida aqui.
- Isso coincide exatamente com a tabela fornecida.
Conclusão
A combinação que explica corretamente a distribuição das chaves, incluindo o tratamento da colisão da chave 34 através de múltiplas iterações de re-hash, é a Alternativa D.