Há um resultado matemático surpreendente chamado “paradoxo do aniversário” que afirma que, se há mais de 23 pessoas em uma sala, há mais de
de chance de que duas pessoas façam aniversário no mesmo dia. Explique porque este paradoxo é um exemplo do maior problema do hash.
Passo 1
O enunciado apresenta o paradoxo do aniversário, que mostra que com apenas 23 pessoas numa sala (365 dias possíveis) já temos mais de 50% de chance de duas pessoas comemorarem no mesmo dia. O conteúdo é de probabilidade discreta e o que vamos precisar é entender como a lógica desse paradoxo se aplica ao problema de colisões em funções de hash.
Passo 2
Num hash, cada entrada é mapeada para um dos
possíveis valores (assim como cada pessoa cai em um dos 365 dias). Se inserirmos
entradas distintas, a probabilidade de NÃO ocorrer nenhuma colisão é dada por
Logo, a probabilidade de pelo menos uma colisão é
Passo 3
Para valores de
bem menores que
, podemos aproximar:
então
Da mesma forma que no paradoxo do aniversário acontece
já para
, em hashes também basta inserir cerca de
entradas para ter alta chance de colisão.
Passo 4
Isso mostra que, mesmo que o espaço de saída do hash seja enorme, não precisamos de
entradas para encontrar colisões, mas apenas
. Esse é o “maior problema do hash”: colisões aparecem bem antes do que se poderia pensar se contássemos de forma linear.
Resposta
O paradoxo do aniversário ilustra diretamente o problema de colisões em funções de hash: basta inserir cerca de
valores num espaço de tamanho
para ter mais de 50% de chance de colisão, mostrando que colisões são inerentes e aparecem muito antes de se encher todo o espaço de hash.