A respeito de algoritmos de hash, julgue o item que se segue. A ferramenta mais utilizada para reduzir a probabilidade de acontecerem colisões em uma função de resumo (hash) é o aj

Gabarito

Errado

Comentário do professor

A afirmação foi julgada ERRADO porque usou o termo heterogênea em vez de uniforme. Ajustar a distribuição dos resumos realmente reduz colisões, mas a propriedade desejada é que a função seja uniforme e dispersa, não simplesmente heterogênea.

Uma função uniforme tende a produzir cada valor de saída com frequência semelhante quando alimentada por entradas diversas, evitando concentrações que aumentam colisões.
Uma função dispersa apresenta grande conjunto de saídas e efeito avalanche, de modo que pequenas mudanças na entrada geram saídas muito diferentes.

Mesmo com uniformidade, se o espaço de saídas for pequeno colisões são inevitáveis pelo princípio da casa dos pombos. Em termos práticos, a probabilidade de colisão cresce conforme o número de chaves \(k\) em relação ao número de possíveis resumos \(M\); aproximações do tipo \(P\!\approx\!1-\exp(-k(k-1)/(2M))\) ilustram esse ponto.

Portanto, o correto é buscar funções de hash que sejam simultaneamente uniformes e dispersas para minimizar colisões.