Colisiones de hash esperadas

Cuando se dispersan n claves distintas de forma uniforme en m cubetas, algunas comparten hueco incluso con un factor de carga modesto. La intuición subestima la ocupación: se recuerda la probabilidad de la paradoja del cumpleaños de que al menos un par colisione y se trata esa probabilidad como si fuera un recuento. Esta calculadora de colisiones de hash esperadas responde a otra pregunta de planificación. Emplea el modelo clásico de bolas en urnas —cada elemento elige una de m cubetas de modo independiente y uniforme— y devuelve el número esperado de claves en colisión, es decir, las que no están solas en su cubeta. Junto a esa cifra principal informa claves singleton, cubetas ocupadas y vacías, claves de desbordamiento más allá del primer ocupante, colisiones por pares y el factor de carga n dividido por m. La aritmética es una identidad de forma cerrada evaluada en espacio logarítmico, plenamente determinista, sin muestreo Monte Carlo ni modelo de lenguaje. Sirve para dimensionar una tabla hash, ajustar un factor de carga, comparar un espacio de hash de 32 bits con otro más estrecho o comprobar una afirmación de ocupación de manual antes de comprometer memoria.

Qué miden las claves en colisión esperadas en el modelo de bolas en urnas

Lance n bolas de forma independiente y uniforme en m urnas y tendrá el modelo habitual de un hash uniforme. Una clave en colisión es una bola que comparte urna con al menos otra. Esa no es la misma magnitud que la probabilidad de la paradoja del cumpleaños de que al menos dos bolas compartan urna, ni el número de coincidencias por pares.

Para planificar capacidad suele quererse un recuento: cuántas claves, en promedio, no logran un hueco privado, cuántas cubetas quedan vacías mientras otras se desbordan, y cuántas claves extra se apilan sobre el primer ocupante. La linealidad de la esperanza da respuestas limpias sin simulación. Fije una clave cualquiera.

Las otras n menos una fallan la cubeta de esa clave con probabilidad uno menos uno sobre m, de modo que la chance de que la clave elegida sea singleton es (1 − 1/m) elevada a n menos uno. Multiplique por n y tendrá el número esperado de claves singleton. Reste de n y tendrá el número esperado de claves en colisión: n veces uno menos (1 − 1/m) a la n menos uno.

El mismo argumento de ocupación da el número esperado de cubetas vacías, m veces (1 − 1/m) a la n, y por tanto el de cubetas ocupadas. Las claves de desbordamiento son los elementos más allá del primero en cada cubeta ocupada, iguales a n menos ocupadas. Las colisiones por pares equivalen a n sobre dos dividido por m, porque cualquier par concreto cae junto con probabilidad uno sobre m.

El factor de carga es simplemente n sobre m. Juntas, estas cifras indican si una tabla propuesta carece de cubetas, está apenas ocupada o ya paga un recargo de longitud de cadena que un m mayor eliminaría.

Contrato de entrada, fórmulas, estabilidad numérica y errores

Envíe dos enteros obligatorios: n, el número de elementos, y m, el número de cubetas. Ambos valores deben ser enteros finitos dentro de los límites publicados: n de uno a un billón, y m de uno a un billón, lo que cubre ejemplos de aula, mapas en memoria y un espacio de hash de 32 bits completo de cuatro mil doscientos noventa y cuatro millones novecientos sesenta y siete mil doscientos noventa y seis huecos.

Tras la validación el motor evalúa potencias de uno menos uno sobre m en espacio logarítmico como la exponencial del exponente por log1p de menos uno sobre m, de modo que n y m grandes no se desbordan hacia un cero silencioso como haría un bucle ingenuo de multiplicaciones.

Los casos especiales permanecen exactos: un solo elemento nunca colisiona; una sola cubeta con dos o más elementos hace colisionar a todas las claves; un exponente cero se trata como uno para que (1 − 1/m) a la potencia cero no se vuelva un cero a la cero indeterminado. Es un oráculo de recuento esperado bajo un hash uniforme e independiente, no un simulador de una función hash concreta ni una calculadora de probabilidad de colisión.

Planificación de capacidad, límites, precio y dónde rinden las cifras

Utilice la herramienta del navegador cuando elija el tamaño de una tabla, compare factores de carga o explique a un equipo por qué un factor de carga de uno sigue dejando una fracción grande de claves compartiendo cubeta. Incremente m hasta que las claves en colisión esperadas o las de desbordamiento queden bajo su presupuesto de servicio, y reserve un margen de crecimiento.

Contraste el resultado con una probabilidad de la paradoja del cumpleaños si también necesita la chance de que exista alguna colisión; esa probabilidad se satura cerca de uno mucho antes de que el recuento esperado de claves en colisión se vuelva grande, y por eso las dos herramientas responden a tickets distintos. Los resultados son plenamente deterministas: los mismos n y m producen siempre el mismo vector de ocupación, de modo que puede fijar ejemplos en pruebas y materiales didácticos.

No hay modelo de lenguaje, ni servicio externo de estadística, ni aleatoriedad.