Identificar URL de forma única con un número de 64 bits

Question

Este es básicamente un problema matemático, pero muy relacionado con la programación:Si tengo mil millones de cadenas que contienen URL y tomo los primeros 64 bits del hash MD5 de cada una de ellas, ¿qué tipo de frecuencia de colisión debo esperar?

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

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

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

EDITAR: no es un duplicado

Answer 1

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

No me sentiría cómodo simplemente tirar la mitad de los bits en MD5; sería mejor que las palabras XOR de alta y baja de 64 bits para darles la oportunidad de mezclarse. Por otra parte, MD5 no es en modo rápido o seguro, por lo que no se molestaría con él en absoluto. Si quieres velocidad cegamiento con buena distribución, pero sin pretensión de la seguridad, usted podría tratar de las versiones de 64 bits de MurmurHash. Ver http://en.wikipedia.org/wiki/MurmurHash para obtener más información y código.

Answer 2

Has etiquetado esto como "paradoja del cumpleaños", creo que ya sabes la respuesta.

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

donde n es mil millones en su caso.

Será un poco mejor usando algo que no sea MD5, porque MD5 tiene problema de colusión práctica.

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 en un solo sentido (la seguridad no es obligatorio)
   • Preferiblemente rápida - que es una característica necesaria para una aplicación de seguridad no

Esta función hash href="http://www.strchr.com/hash_functions" rel="nofollow encuesta puede ser útil para la perforación hasta la función más adecuada para usted. < br> Voy a sugerir probar múltiples funciones de aquí y caracterizarlos para su conjunto de entrada probable (recoger unos cuantos mil millones de URL que cree que va a ver).

Puede generar realmente otra columna como ésta encuesta de prueba para su lista de URL de prueba para caracterizar y seleccione una de las nuevas funciones de hash (más filas de esa tabla) existentes o que es posible que desee comprobar. Tienen MSVC ++ código fuente para comenzar con (referencia de enlace postal ).

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

Answer 4

Si usted tiene 2 posibilidades de hash ^ n, hay más de un 50% de probabilidades de colisión cuando se tiene 2 ^ (n / 2) artículos.

por ejemplo. Si el hash es de 64 bits, que tiene 2 ^ 64 posibilidades de hash, tendría una probabilidad del 50% de colisión si tiene 2 ^ 32 elementos de una colección.

Answer 5

Sólo mediante el uso de un hash, siempre hay una posibilidad de colisiones. Y no se sabe de antemano wether colisiones ocurrirán una vez o dos veces, o incluso cientos o miles de veces en la lista de direcciones URL.

La probabilidad sigue siendo sólo una probabilidad. Es como tirar un dado 10 o 100 veces, ¿cuáles son las posibilidades de conseguir todos los seises? La probabilidad dice que es bajo, pero aún puede ocurrir. Tal vez incluso muchas veces en una fila ...

Así, mientras que los href="http://en.wikipedia.org/wiki/Birthday_problem" paradoja del cumpleaños muestra cómo calcular las probabilidades, usted todavía necesita decidir si las colisiones son aceptables o no.

... y las colisiones son aceptables, y los hashes siguen siendo el camino correcto a seguir; encontrar un algoritmo de hash de 64 bits en lugar de depender de "medio-a-MD5" tener una buena distribución. (Aunque es probable que tenga ...)