Carregando...
Carregando...
Ajude a melhorar a plataforma
Durante uma palestra sobre estruturas de dados avançadas, um especialista em ciência da computação introduz o conceito de Hashing como uma técnica eficiente para a busca e armazenamento de dados em aplicações de grande escala. Ele explica que, ao contrário dos métodos tradicionais de pesquisa que dependem de comparações sequenciais ou binárias, o Hashing utiliza uma função matemática para converter chaves de pesquisa em endereços de tabela diretamente, acelerando significativamente o processo de busca. No entanto, ele também destaca que o método enfrenta desafios. Como exemplo, considere um cenário hipotético em que as chaves são de quatro dígitos decimais, podendo originar 10.000 chaves distintas. Caso a tabela for capaz de armazenar em M=97 posições, ou endereços distintos, ocorrerão colisões, ou seja, chaves distintas estarão associadas a mesma posição ou ao mesmo registro armazenado na tabela.
Com base nesta descrição, qual das seguintes alternativas sobre Hashing e o tratamento de colisões é correta?
Explique melhor esta questão
Abre o Tutor com o enunciado e as alternativas já no campo — você revisa e envia.
Esta questão foi verificada por um de nossos administradores.
🎓 Gabarito Comentado (AVA):
A alternativa "Métodos como encadeamento e sondagem linear são eficazes para resolver colisões, mantendo a eficiência da busca" é correta, pois, quando a quantidade de chaves únicas é bem maior do que o número de índices para registros na tabela (ou seja, que o número de endereços na tabela), a questão das colisões em Hashing torna-se um problema inevitável. Assim sendo, métodos de resolução de colisões, como encadeamento (onde colisões são tratadas adicionando-se os registros em uma lista ligada no mesmo endereço de tabela) e sondagem linear (onde se busca sequencialmente o próximo endereço vazio na tabela), são estratégias comprovadas para manter a eficiência da pesquisa mesmo na presença de colisões.
A alternativa "A função de Hashing deve ser complexa para evitar completamente as colisões, garantindo uma distribuição uniforme das chaves na tabela" é incorreta, pois se o tamanho M da tabela for muito menor que o tamanho R do universo de chaves não será possível evitar colisões, independentemente de quão complexa for a função de Hashing. Embora uma função de Hashing bem projetada possa ajudar a minimizar as colisões distribuindo as chaves mais uniformemente, nenhuma função poderá evitar completamente as colisões em tabelas com um espaço de endereçamento limitado em comparação com o universo de chaves possíveis.
A alternativa "As colisões são um fenômeno raro e podem ser ignoradas na maioria das aplicações práticas de Hashing" é incorreta, pois ao contrário, as colisões são frequentes. Quanto mais registros são adicionados à tabela, mais crítico se torna o gerenciamento eficiente de colisões.
A alternativa "A probabilidade de colisões diminui à medida que o número de registros na tabela aumenta, tornando o Hashing mais eficiente com grandes volumes de dados" é incorreta, pois na verdade, a probabilidade de colisões aumenta com o número de registros (princípio do paradoxo do aniversário). Portanto, quanto mais registros são adicionados à tabela, mais crítico se torna o gerenciamento eficiente de colisões.
A alternativa "O Hashing não é adequado para aplicações dinâmicas, pois a inserção de novos registros é computacionalmente dispendiosa devido ao alto risco de colisões" é incorreta, pois apesar das colisões apresentarem desafios, o Hashing é amplamente utilizado em aplicações dinâmicas devido à sua capacidade de realizar buscas rápidas. As estratégias de resolução de colisões, quando bem implementadas, permitem que o Hashing lide eficientemente com a inserção e a busca de novos registros.