Cómo usarla
- Introduce el tamaño del hash o del identificador aleatorio en bits.
- Introduce el número de elementos: archivos, registros, ID. Los números grandes pueden escribirse como 1e9 o 5e12.
- Lee la probabilidad de colisión, los pares repetidos esperados y los elementos que llevan al 50 %, al 1 % y a una entre un millón.
Fórmula
Con N = 2ᵇ valores posibles y n elementos:
- P(colisión) = 1 − exp(−n(n − 1) ÷ 2N), calculada de forma que las probabilidades diminutas conserven sus cifras.
- Pares esperados = n(n − 1) ÷ 2N; mientras es pequeño, casi coincide con la probabilidad.
- Elementos para una probabilidad p: n = ½ + √(¼ + 2N·ln(1 ÷ (1 − p))).
Ejemplo resuelto
Un hash de 64 bits para 1.000.000.000 (10⁹) elementos:
- N = 2⁶⁴ = 1,845e+19 valores posibles.
- n(n − 1) ÷ 2N ≈ 10¹⁸ ÷ 3,69 × 10¹⁹ = 0,0271 pares esperados.
- Probabilidad = 1 − e^(−0,0271) = 2,674 %, aproximadamente 1 entre 37,4.
- El 50 % se alcanza con 5.056.937.541 elementos; el 1 %, con 608.926.882; una entre un millón, con 6.074.003.
Consejos
- El doble de elementos, cuatro veces el riesgo mientras es pequeño, porque crece con n².
- Dos bits más duplican los elementos que puedes guardar con el mismo riesgo: cada bit multiplica N por 2 y el n seguro por √2.
- Los hashes recortados (los 8 primeros caracteres hex de un SHA-256, por ejemplo) tienen solo 4 bits por carácter: 8 caracteres son 32 bits, y las colisiones aparecen tras decenas de miles de elementos.