Uma certa função hash, h(x), aplicada à chave, coloca registros com as chaves: 62, 79, 81, 12, 54, 97, 34, em uma tabela hash. As colisões são tratadas por uma função re-hash, r(x), que recebe como argumento o resultado da aplicação da função hash. Os valores-chave são introduzidos na ordem indicada acima, para produzir a seguinte tabela: Tabela Hash Quais são as funções h(x) e r(x), respectivamente?

Alternativa D

A questão solicita a identificação das funções de hash h(x) e de re-hash r(x) com base na disposição final dos elementos na tabela. Para resolver, devemos analisar o tamanho da tabela e simular o processo de inserção das chaves para identificar a lógica de resolução de colisões.

Análise Detalhada

1. Identificação da Função Hash $h(x)$

• Tamanho da Tabela: Os índices apresentados variam de 0 a 19, indicando um tamanho de tabela M = 20.
• Verificação: Testamos as chaves mais simples contra o módulo 20.
• Chave 62: $62 \% 20 = 2$. Na tabela, 62 está no índice 2.
• Chave 81: $81 \% 20 = 1$. Na tabela, 81 está no índice 1.
• Conclusão: A função primária é $h(x) = key \% 20$. Isso descarta imediatamente as opções c e e, que utilizam módulo 30.

2. Identificação da Função Re-hash $r(x)$

• Cenário de Colisão: A maioria das chaves foi inserida sem conflitos diretos. A única colisão significativa ocorre com a chave 34.
• Cálculo inicial: $34 \% 20 = 14$.
• Estado do índice 14: Já ocupado pela chave 54 ($54 \% 20 = 14$).
• Posição final da chave 34: Índice 8.
• Teste das Opções Restantes (a, b, d):
• Opção b: result \% 20. Manteria a chave no índice 14. Incorreto.
• Opção a: (result + 13) \% 20.
• Aplicação: (14 + 13) \% 20 = 27 \% 20 = 7.
• Próximo passo: (7 + 13) \% 20 = 0. Não converge rapidamente para o índice 8.
• Opção d: (result + 7) \% 20.
• Aplicação 1: (14 + 7) \% 20 = 21 \% 20 = 1. (Índice 1 ocupado por 81).
• Aplicação 2: (1 + 7) \% 20 = 8. (Índice 8 livre, corresponde à posição final de 34).
• Conclusão: A função de re-hash desloca a busca em passos de 7 unidades até encontrar um espaço vazio.

Conclusão

A combinação correta que explica a distribuição dos dados na tabela é a função hash padrão módulo 20 e a função de re-hash que adiciona 7 ao resultado atual, módulo 20.

Portanto, a alternativa correta é a d.