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

Uma tabela hash é uma estrutura de dados que usa uma função hash para transformar uma chave (como um e-mail) em um índice numérico, permitindo acesso rápido aos dados. Para que funcione bem, a função hash deve distribuir as chaves de forma uniforme pelo vetor de listas, minimizando colisões (quando chaves diferentes geram o mesmo índice).

• (A) Incorreta: Multiplicar os códigos ASCII por N antes de somar e aplicar o módulo N faria com que a soma H fosse um múltiplo de N em muitos casos. Se H é múltiplo de N, H Mod N será sempre 0, resultando em uma péssima distribuição, onde todas as mensagens iriam para a primeira lista.
• (B) Incorreta: A soma é uma operação comutativa; a ordem em que os códigos ASCII são somados (do início para o fim ou do fim para o início) não altera o valor final da soma H. Consequentemente, o resultado de H Mod N e a distribuição não seriam afetados.
• (C) Correta: Para funções hash que utilizam o operador módulo (Mod N), escolher um N (o tamanho do vetor de listas) que seja um número primo é uma prática comum e eficaz. Isso ajuda a garantir uma distribuição mais uniforme dos valores de hash pelos índices do vetor, pois um número primo tem menos fatores em comum com outros números, o que reduz a probabilidade de padrões nos dados de entrada causarem colisões frequentes e concentradas.
• (D) Incorreta: Incluir a mensagem na posição N – H (onde H já é H Mod N) poderia, por exemplo, resultar em N se H fosse 0, o que seria um índice fora dos limites do vetor V (0 a N-1). Mesmo se ajustado para (N - H) Mod N, essa alteração na fórmula do índice não resolve o problema fundamental da distribuição, que depende mais da escolha de N e da qualidade da soma H.
• (E) Incorreta: Um N par é geralmente uma escolha ruim para o tamanho de uma tabela hash. Se N for par e a soma dos códigos ASCII (H) tender a ser par (o que é comum, já que muitos códigos ASCII são pares), então H Mod N sempre resultará em um número par. Isso significaria que todas as mensagens seriam armazenadas apenas nas posições pares do vetor V, deixando metade das listas (as de índice ímpar) completamente vazias e concentrando as colisões nas posições pares. Armadilha: Esta alternativa tenta induzir ao erro, sugerindo que um número "simétrico" ou "redondo" como um par seria bom, quando na verdade é o oposto do que se busca para uma boa distribuição em funções de hash com módulo.