Identifier de manière unique les URL avec un nombre de 64 bits

Question

Ceci est essentiellement un problème de mathématiques, mais très programmant connexes: si j'ai 1 milliard de chaînes contenant des URL, et je prends les 64 premiers bits du hachage MD5 de chacun d'eux, quel type de fréquence de collision dois-je attendre

Comment le changement de réponse si je ne dispose que de 100 millions d'URL?

Il me semble que les collisions sont extrêmement rares, mais ces choses ont tendance à être source de confusion.

Serais-je mieux d'utiliser autre chose que MD5? Rappelez-vous, je ne suis pas à la recherche de la sécurité, juste une bonne fonction de hachage rapide. En outre, le support natif MySQL est agréable.

EDIT : pas tout à fait en double

Answer 1

Si les 64 premiers bits du MD5 constitué un hachage avec une distribution idéale, le paradoxe d'anniversaire signifierait encore vous obtiendrez des collisions pour chaque 2 ^ 32 URL. En d'autres termes, la probabilité d'une collision est le nombre de URL divisé par 4294967296. Voir http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem pour plus de détails.

Je ne me sentirais pas à l'aise juste jeter la moitié des bits MD5; il serait préférable de XOR les hauts et bas mots 64 bits pour leur donner une chance de mélanger. Là encore, MD5 est pas rapide ou sûr, donc je ne se souciaient pas du tout. Si vous voulez une vitesse aveuglante avec une bonne répartition, mais n'a pas la prétention de la sécurité, vous pouvez essayer les versions 64 bits de MurmurHash. Voir pour les détails et le code http://en.wikipedia.org/wiki/MurmurHash.

Answer 2

Vous avez marqué cela comme « anniversaire-paradoxe », je pense que vous connaissez déjà la réponse .

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

où n est 1 milliard dans votre cas.

Vous serez un peu mieux en utilisant autre chose alors MD5, parce que MD5 ont problème de collusion pratical .

Answer 3

D'après ce que je vois, vous avez besoin d'une fonction de hachage avec les exigences suivantes,

1. hachage des chaînes de longueur arbitraire à une valeur de 64 bits
   • Soyez bon - éviter les collisions
   • Pas nécessairement à sens unique (sécurité non nécessaire)
   • De préférence rapide - ce qui est une caractéristique nécessaire pour une application non-sécurité

Cette fonction de hachage pour votre liste d'URL de test une autre colonne comme cette enquête essai pour caractériser et sélectionnez l'existant ou de nouvelles fonctions de hachage (plus de lignes dans cette table) que vous pouvez vérifier. Ils ont le code source de MSVC pour commencer ( référence lien postal ).

Modification des fonctions de hachage en fonction de la largeur de votre sortie (64 bits) vous donnera une caractérisation plus précise pour votre application.

Answer 4

Si vous avez 2 ^ possibilités de hachage n, il y a plus d'une chance de 50% de collision lorsque vous avez 2 ^ (n / 2) éléments.

par exemple. si votre hachage est de 64 bits, vous avez 2 ^ 64 possibilités de hachage, vous auriez une chance de 50% de collision si vous avez 2 ^ 32 éléments dans une collection.

Answer 5

Juste en utilisant un hachage, il y a toujours une chance de collisions. Et vous ne savez pas à l'avance wether collisions auront lieu une ou deux fois, voire des centaines ou des milliers de fois dans la liste des urls.

La probabilité est encore juste une probabilité. Son comme jeter un dé 10 ou 100 fois, quelles sont les chances d'obtenir tous les six places? La probabilité dit qu'il est faible, mais il peut encore se produire. Peut-être même plusieurs fois de suite ...

Ainsi, alors que les d'anniversaire vous montre comment calculer les probabilités, vous devez toujours décider si les collisions sont acceptables ou non.

... et les collisions sont acceptables, et hash sont toujours le droit chemin à parcourir; trouver un algorithme de hachage 64 bits au lieu de compter sur « un demi-MD5 » ayant une bonne distribution. (Bien qu'il ait probablement ...)