Um método de busca bastante utilizado, conhecido como hash, ...
Um método de busca bastante utilizado, conhecido como hash, baseia-se na utilização que mapeia chaves em endereços de memória, de modo que os dados associados a cada chave possam ser rapidamente localizados e lidos. Quando há conflitos de localização, algum algoritmo de separação é adotado.
Considere uma tabela hash armazenada em um arquivo no disco rígido. Supondo-se que a mesma possua uma função de hash razoavelmente protegida de conflitos, o número médio de acessos ao disco, necessários para localizar uma chave em um universo de N chaves, é mais próximo de
Gabarito comentado
Confira o gabarito comentado por um dos nossos professores
A alternativa correta é a E.
Vamos entender o contexto e os conceitos abordados na questão sobre busca utilizando tabelas hash.
Uma tabela hash é uma estrutura de dados que mapeia chaves a endereços de memória utilizando uma função de dispersão (hash function). Esta função gera um índice que aponta para a posição onde a chave correspondente e seus dados associados são armazenados. A principal vantagem desse método é a rapidez na busca, inserção e remoção de dados.
Em um cenário ideal, onde a função hash distribui uniformemente as chaves (minimizando conflitos), o acesso a um elemento na tabela hash é realizado, em média, com um número constante de operações, independentemente do número de chaves N armazenadas.
Agora, vamos analisar as alternativas oferecidas:
A - N log2(N)
Essa alternativa sugere que o número médio de acessos ao disco é proporcional ao produto de N e o logaritmo de N. Isso não é consistente com o comportamento esperado de uma tabela hash, pois o tempo de acesso deve ser constante.
B - log2(N)
Embora essa alternativa sugira uma busca eficiente, está mais associada a estruturas de dados que utilizam árvores balanceadas, como árvores binárias de busca (AVL), onde o tempo de busca é logarítmico em relação ao número de elementos. Portanto, não é aplicável para tabelas hash.
C - N ÷ 2
Esta alternativa indica que o número médio de acessos ao disco seria a metade do número total de chaves N. Isso também não é consistente com o comportamento de tabelas hash, onde o tempo de acesso deve ser constante e não linear.
D - N ÷ log2(N)
Essa alternativa sugere um comportamento quase linear, mas com uma leve redução devido ao logaritmo. Ainda assim, não condiz com a eficiência esperada de uma tabela hash.
E - 2
Esta é a alternativa correta. Em uma tabela hash com uma boa função de dispersão, o número médio de acessos ao disco para localizar uma chave é constante. O valor 2 aqui é uma boa aproximação considerando que pode haver uma pequena sobrecarga devido a colisões ou consultas adicionais, mas, em geral, o acesso é realizado em uma quantidade fixa de operações.
Para resumir, a alternativa E é a correta porque reflete a eficiência das tabelas hash em termos de tempo constante de acesso a uma chave.
Clique para visualizar este gabarito
Visualize o gabarito desta questão clicando no botão abaixo
Comentários
Veja os comentários dos nossos alunos
GAB E
Na verdade, a complexidade média de busca em uma tabela hash é O(1)
O examinador deve estar considerando o acesso a primeira posição + o acesso a posição da hash, resultando em 2. Enfim, GAB E é o menos errado
tab hash 1 sempre 1
Clique para visualizar este comentário
Visualize os comentários desta questão clicando no botão abaixo
Conheça nossos planos