Double-hashing and The Birthday Problem
The birthday problem (also called the birthday paradox) deals with the probability, that in a set of n randomly selected people, at least two people share the same birthday. Though it is not technically a paradox, it is often referred to as such because the probability is counter-intuitively high. The birthday problem is an answer to the following question: In a set of n randomly selected people, what is the probability, that at least two people share the same birthday? What is the smallest value of n where the probability is at least 50% or 99%? Let p(n) be the probability that at least two of a group of n randomly selected people share the same birthday. By the pigeonhole principle , since there are 366 possibilities for birthdays (including February 29), it follows that when n≥367, p(n)=100%. The counterintuitive part of the answer is that for smaller n, the relationship between n and p(n) is (very) non-linear. In fact, the thresholds to surpass 50% and 99% are quite sm