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 50 % 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 m possíveis valores (assim como cada pessoa cai em um dos 365 dias). Se inserirmos N entradas distintas, a probabilidade de NÃO ocorrer nenhuma colisão é dada por
Psem colisão = prodk=0^N-1 m - km ã
Logo, a probabilidade de pelo menos uma colisão é
Pcolisão = 1 - Psem colisão ãã

Passo 3

Para valores de N bem menores que m, podemos aproximar:
Psem colisão approx e^-N(N-1)/(2m), ã
então
Pcolisão approx 1 - e^-N(N-1)/(2m) ã
Da mesma forma que no paradoxo do aniversário acontece Pcolisão>50%ã já para Napprox1.2raiz m, em hashes também basta inserir cerca de O(raiz m) 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 O(m) entradas para encontrar colisões, mas apenas O(raiz m). 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 O(raiz m) valores num espaço de tamanho m 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.

Exercícios relacionados