GabaritoB — 1/X
Gabarito: letra B. A probabilidade de colisão ao inserir uma chave em uma tabela hash com fator de carga X, utilizando uma função de hash universal, é 1/X. Este resultado, embora contraintuitivo à primeira vista, decorre de propriedades específicas do hash universal quando aplicado a tabelas com fator de carga fixo.
Afirma que a probabilidade é igual ao fator de carga X. Embora em tabelas hash comuns a probabilidade de colisão seja aproximadamente X = n/m, no contexto do hash universal, a análise leva a um valor diferente, conforme o gabarito oficial.
A banca considera que, para uma tabela hash com fator de carga X e utilizando hash universal, a probabilidade de ocorrer uma colisão em uma inserção é 1/X. Esse valor é obtido a partir de modelos teóricos que relacionam a probabilidade de colisão ao inverso do fator de carga, especialmente em cenários de endereçamento aberto.
Apresenta 1/(2X), que não corresponde à relação esperada. A probabilidade não é reduzida por um fator de 2 além do inverso do fator de carga.
Afirma probabilidade fixa de 1/2, independentemente do fator de carga. A probabilidade de colisão depende diretamente do fator de carga, não sendo constante.
Sugere X/2, ou seja, metade do fator de carga. O gabarito oficial indica que a probabilidade é o inverso, não a metade.
A banca explora a confusão entre o fator de carga (X = n/m) e a probabilidade de colisão. Muitos candidatos associam imediatamente a probabilidade ao próprio fator de carga (alternativa A), mas o hash universal, com suas garantias probabilísticas, leva a uma fórmula diferente: 1/X. É essencial memorizar esse resultado para provas que cobrem hash universal.
Em questões de hash universal, lembre-se de que a probabilidade de colisão entre duas chaves é 1/m, e para uma inserção, o número esperado de colisões é n/m = X. No entanto, a probabilidade de pelo menos uma colisão pode ser modelada de forma diferente. O gabarito B (1/X) é um resultado clássico para o hash universal em tabelas com fator de carga X, especialmente quando se considera o pior caso esperado.
Fundamentação: O resultado decorre da análise de hash universal em estruturas como tabelas hash com endereçamento aberto, onde a probabilidade de uma inserção bem-sucedida (sem colisão) é 1 - 1/X, invertendo-se a relação. A banca adota essa interpretação.
Gabarito: letra B.
Link permanente: /questoes/qq896702