Identificación única de URL con un número de 64 bits

Question

Esto es básicamente un problema matemático, pero muy relacionado con la programación: si tengo 1 000 millones de cadenas que contienen URL y tomo los primeros 64 bits del hash MD5 de cada uno de ellos, tipo de frecuencia de colisión debería esperar?

¿Cómo cambia la respuesta si solo tengo 100 millones de URL?

Me parece que las colisiones serán extremadamente raras, pero estas cosas tienden a ser confusas.

¿Sería mejor utilizar algo que no fuera MD5? Eso sí, no estoy buscando seguridad, solo una buena función rápida de hash. Además, el soporte nativo en MySQL es bueno.

EDITAR: not quite a duplicate

Answer 1

Si los primeros 64 bits del MD5 constituyeron un hash con una distribución ideal, la paradoja del cumpleaños todavía significaría que obtendría colisiones por cada 2^32 URL's. En otras palabras, la probabilidad de una colisión es el número de URL dividido por 4.294.967.296. Ver http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem para más detalles.

No me sentiría cómodo tirando la mitad de los bits en MD5; sería mejor usar XOR las palabras altas y bajas de 64 bits para darles la oportunidad de mezclar. Por otra parte, MD5 no es de ninguna manera rápido o seguro, así que no me molestaría en absoluto. Si quieres una velocidad deslumbrante con buena distribución, pero sin pretensiones de seguridad, puedes probar las versiones de 64 bits de MurmurHash. Ver http://en.wikipedia.org/wiki/MurmurHash para detalles y código.

Answer 2

ha etiquetado esto como "cumpleaños paradoja", te creo know the answer already.

P(Collision) = 1 - (2^64)!/((2^64)^n (1 - n)!) 

donde n es 1 mil millones en su caso.

Será un poco mejor usar algo que no sea MD5, porque MD5 tiene pratical collusion problem.

Answer 3

Por lo que veo, se necesita una función hash con los siguientes requisitos,

1. Hash cadenas de longitud arbitraria a un valor de 64 bits
   • ser bueno - Evitar colisiones
   • No necesariamente unidireccional (no se requiere seguridad)
   • Preferiblemente rápido - que es una característica necesaria para una aplicación no de seguridad

Este hash function survey puede ser útil para obtener la función más adecuada para usted.
Sugeriré probar varias funciones desde aquí y caracterizarlas para su posible conjunto de entrada (elija unos mil millones de URL que cree que verá).

Puede generar another column like this test survey para su lista de URL de prueba para caracterizar y seleccionar entre las funciones hash existentes o nuevas (más filas en esa tabla) que desee verificar. Tienen código fuente de MSVC++ para comenzar (reference to ZIP link).

Cambiando las funciones hash para adaptarse a su ancho de salida (64 bits) le dará una caracterización más precisa para su aplicación.

Answer 4

Simplemente usando un hash, siempre hay posibilidad de colisión. Y usted no sabe de antemano si las colisiones ocurrirán una o dos veces, o incluso cientos o miles de veces en su lista de direcciones URL.

La probabilidad sigue siendo solo una probabilidad. Es como tirar un dado 10 o 100 veces, ¿cuáles son las posibilidades de obtener los seis? La probabilidad dice que es baja, pero aún puede suceder. Tal vez incluso muchas veces seguidas ...

Por lo tanto, mientras que birthday paradox le muestra cómo calcular las probabilidades, aún necesita decidir si las colisiones son aceptables o no.

... y las colisiones son aceptables, y los hashes siguen siendo el camino correcto; encuentre un algoritmo hash de 64 bits en lugar de confiar en que "half-a-MD5" tenga una buena distribución. (Aunque probablemente tenga ...)

Answer 5

Si tiene 2^n posibilidades de hash, hay más de un 50% de posibilidades de colisión cuando tiene 2^(n/2) elementos.

E.G. si su hash es de 64 bits, tiene 2^64 posibilidades de hash, tendría un 50% de probabilidades de colisión si tiene 2^32 elementos en una colección.