Caso real
La paradoja del cumpleaños
En un grupo de 23 personas, la probabilidad de que dos cumplan años el mismo día ya pasa del 50 %. Es la razón por la que las colisiones aparecen mucho antes de lo que parece: con 365 cubetas, bastan unas 23 claves al azar para que probablemente dos colisionen. Con claves que no se conocen de antemano, ninguna función hash evita las colisiones: la tabla tiene que manejarlas.
Escala el razonamiento: el número de parejas de claves crece con el cuadrado de las claves, así que el 50 % de probabilidad llega cuando el número de claves se acerca a la raíz del número de cubetas, multiplicada por algo más de 1. Con 365 cubetas son unas 23 claves. ¿Y con un millón de cubetas?