Questão de Tecnologia da Informação · FGV CVM 2024 (nº 18)

Uma função hash transforma uma chave de entrada (como um texto) em um valor numérico de tamanho fixo, usado para indexar dados. O Método da Divisão calcula o valor hash como o resto da divisão da chave numérica pelo tamanho da tabela (ou módulo), ou seja, $h(chave) = chave \pmod{M}$.

Cálculo:

1. Converter a chave alfanumérica em numérica: A chave "CVM" é convertida usando os valores fornecidos: C=67, V=86, M=77.
2. Calcular a chave interna (produto): A AHash usa o produto desses números como chave interna:
   Chave Interna $= 67 \times 86 \times 77$.
   Para simplificar o cálculo do módulo, podemos aplicar a propriedade $(A \times B \times C) \pmod M = ((A \pmod M) \times (B \pmod M) \times (C \pmod M)) \pmod M$.
3. Determinar o módulo (M): A função AHash deve retornar um valor entre 0 e 5. Isso significa que há 6 valores possíveis (0, 1, 2, 3, 4, 5). Portanto, o módulo $M$ é 6.
4. Calcular o hash usando o Método da Divisão:
   • $67 \pmod 6 = 1$ (pois $67 = 11 \times 6 + 1$)
   • $86 \pmod 6 = 2$ (pois $86 = 14 \times 6 + 2$)
   • $77 \pmod 6 = 5$ (pois $77 = 12 \times 6 + 5$)
   • Agora, multiplicamos os restos e aplicamos o módulo novamente:
     $(1 \times 2 \times 5) \pmod 6 = (10) \pmod 6$
   • $10 \pmod 6 = 4$ (pois $10 = 1 \times 6 + 4$)

O valor retornado pela AHash para a chave "CVM" é 4.

(A) Incorreta: O cálculo do hash não resulta em 0.
(B) Incorreta: O cálculo do hash não resulta em 1.
(C) Incorreta: O cálculo do hash não resulta em 2.
(D) Incorreta: O cálculo do hash não resulta em 3.
(E) Correta: O valor hash é 4, obtido pela aplicação do Método da Divisão ($67 \times 86 \times 77 \pmod 6$). A armadilha mais tentadora seria usar 5 como módulo em vez de 6, pois o intervalo é de 0 a 5. No entanto, um intervalo de 0 a $N-1$ significa que o módulo é $N$.