Uma função de hash produz 6 bits de saída por dado. Ao aplicar essa função a 200 entradas distintas, qual o…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções de problemas usando a técnica de recursão e automatizar tais soluções usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Uma função de hash produz 6 bits de saída por dado. Ao aplicar essa função a 200 entradas distintas, qual o número mínimo de colisões que o algoritmo terá?
- A) 0 colisões, pois cada entrada tem um hash único.
- B) 136 colisões mínimas
- C) 200 colisões, já que cada entrada deve colidir.
- D) 128 colisões, que é meio do total de entradas.
- E) 64 colisões, pois só 64 hashes podem ser gerados.
✅ Resposta correta: alternativa B
Resolução passo a passo
- Com 6 bits de saída, a função de hash pode produzir 2^6 = 64 valores distintos (de 000000 a 111111). Passo 2: São 200 entradas distintas sendo mapeadas para apenas 64 valores possíveis. Pelo princípio da casa dos pombos, é impossível que todas tenham hashes diferentes, então colisões são inevitáveis. Passo 3: Para minimizar as colisões, distribuímos as entradas o mais uniformemente possível entre os 64 valores. Como 200 = 64 x 3 + 8, temos 8 valores com 4 entradas e 56 valores com 3 entradas. Passo 4: Contamos colisões como o número de entradas que excedem a primeira em cada valor de hash: 200 - 64 = 136 colisões, que é o mínimo possível. Passo 5: Por isso a alternativa B está correta, e coincide com o gabarito oficial. A alternativa A está errada porque ignora que o espaço de saída é finito. A alternativa C está errada porque nem toda entrada precisa colidir; apenas as excedentes em cada valor colidem. A alternativa D está errada porque 128 é um número arbitrário, sem relação com 64 valores possíveis. A alternativa E está errada porque confunde o número de hashes possíveis com o número de colisões.
💡 Dica: Calcule o número total de saídas possíveis e compare com as entradas.
Alternativa por alternativa
O aluno supõe que uma função de hash sempre associa cada entrada a um hash único, sem considerar que há apenas 64 saídas possíveis para 200 entradas.
Por que engana: O aluno pode confundir o número total de entradas com o número de hashes únicos possíveis, subestimando as colisões.
6 bits geram 2^6 = 64 valores possíveis; com 200 entradas, pelo princípio da casa dos pombos, ao menos 200-64 = 136 entradas compartilham valores.
O aluno acredita que todas as 200 entradas colidem, confundindo colisão com todas as entradas compartilhando um hash, quando apenas as excedentes em cada valor contam como colisão.
O aluno chuta que o número de colisões é a metade das entradas, sem fazer nenhum cálculo com a quantidade de valores de hash possíveis.
O aluno confunde a quantidade de hashes possíveis (64) com a quantidade de colisões, em vez de calcular quantas entradas excedem a capacidade dos valores disponíveis.
Raio-X da questão
função de hash
avaliacao
função de hash · princípios de probabilidade
Revisar conceitos de funções de hash e colisões.
O aluno pode confundir o número total de entradas com o número de hashes únicos possíveis, subestimando as colisões.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Uma senha é representada por uma sequência de 6 bits em um sistema de autenticação. Quantas senhas distintas o algoritmo…
- Quantos bits são necessários para codificar 20 valores distintos em um algoritmo de codificação de dados?
- Em protocolos que transmitem dados de sensores em rede, que propriedade de um algoritmo de hash faz pequenas alterações…
- Um algoritmo precisa atribuir códigos distintos a 95 caracteres imprimíveis (incluindo espaço). Qual é o menor número de…
- Em uma rede, um campo chamado 'checksum' tem 8 bits. Quantos padrões diferentes de checksum um algoritmo pode gerar para…
- Em um algoritmo que organiza uma tabela hash para acessar registros por chave, qual componente transforma uma chave em…
Todas as questões de Programação - Programação com listas e recursão
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog