Questões

A analista Ana precisou implementar rapidamente uma função hash denominada AHash. A AHash deve determinar um valor numérico entre 0 e 5 para uma chave de entrada. Ana optou por implementar em AHash o método de hashing denominado Método da Divisão. Para compatibilizar possíveis chaves alfanuméricas com o Método da Divisão, Ana implementou um dicionário que atribui a cada caracter um valor numérico. Internamente, a AHash utiliza como chave o produto dos números correspondentes aos caracteres da chave original.

Sabendo que os caracteres C, V e M correspondem, respectivamente, aos números 67, 86 e 77, a AHash retornará para a chave “CVM”:

No Hash extensível, considerando d como sendo a profundidade global do diretório, o tamanho do bucket será:

A técnica de hashing que, no pior caso, realiza O(1) acessos à memória para executar uma busca é denominada hashing

Um Programador da Defensoria Pública do Estado de São Paulo foi solicitado a propor uma solução para o problema: Há uma quantidade grande de dados classificáveis por chave e estes dados devem ser divididos em subconjuntos com base em alguma característica das chaves. Um método eficiente deve ser capaz de localizar em qual subconjunto deve-se colocar cada chave e depois estes subconjuntos bem menores devem ser gerenciados por algum método simples de busca para que se localize uma chave rapidamente. O Programador propôs como solução, corretamente, a implementação de

Considere as afirmações a seguir.

I. Função de Hash: h(x) = x % 10 mapeia uma chave x para um índice entre 0 e 9.

II. Operação de Módulo: % retorna o resto da divisão.

III. Colisões: quando várias chaves mapeiam para o mesmo índice, ocorre uma colisão.

IV. Encadeamento: técnica para resolver colisões na qual cada posição na tabela contém uma lista de chaves.

Nesse contexto, o analista Zudo está implementando um sistema de armazenamento de dados utilizando uma tabela Hash de tamanho 10. Ele escolhe a função de Hash h(x) = x % 10 para mapear as chaves. Ao enfrentar o desafio das colisões, Zudo opta pela técnica de encadeamento para gerenciá-las. Ele então insere as chaves {15, 25, 35, 45, 55} na tabela Hash. A estrutura final dessa tabela será: