Ceci est essentiellement un problème de mathématiques, mais très en programmation connexe: Si j'ai 1 milliard de cordes contenant des URL, et je prends les 64 premiers bits du hachage de MD5 de chacun d'eux, quel type de fréquence de collision devrais-je m'attendre? < / p>
Comment la réponse change-t-elle si je n'ai que 100 millions d'URL?
Il me semble que les collisions seront extrêmement rares, mais ces choses ont tendance à être déroutantes.
Est-ce que je ferais mieux d'utiliser quelque chose d'autre que MD5? Espille toi, je ne cherche pas la sécurité, juste une bonne fonction de hachage rapide. En outre, le soutien natif dans MySQL est agréable.
5 Réponses :
Vous avez étiqueté cela comme "anniversaire-paradoxe", je pense que vous Connaître la réponse déjà . où n est 1 milliard dans votre cas. Vous serez un peu mieux en utilisant quelque chose d'autre que MD5, car MD5 a
Si les 64 premiers bits du MD5 constituaient un hachage avec une distribution idéale, le paradoxe d'anniversaire signifierait toujours que vous obtiendriez des collisions pour toutes les 2 ^ 32 URL. En d'autres termes, la probabilité d'une collision est le nombre d'URL divisé par 4 294 967 296. 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 de jeter la moitié des bits en MD5; Il serait préférable de Xor les mots hauts et bas 64 bits pour leur donner une chance de se mélanger. Là encore, MD5 n'est en aucun cas rapide ni sécurisé, alors je ne me dérangerais pas du tout. Si vous souhaitez une vitesse aveuglante avec une bonne distribution, mais pas de prétention de sécurité, vous pouvez essayer les versions 64 bits de Murmurhash. Voir http://en.wikipedia.org/wiki/murmurhash pour plus de détails et code.
Alors, euh, tu veux dire 2 ^ 64 (18 446,744,073 709 551 616) où vous avez dit 2 ^ 32, ci-dessus? La question parle d'environ 64 bits, mais pas 32.
Non, il veut dire 2 ^ 32. Cela signifie que pour 100 millions d'URL, il y a moins de 1% de chances de 1 collision. Je pense que je vais le prendre.
C'est correct, itsadok, je veux dire 2 ^ 32, pas 2 ^ 64. C'est tout le point du paradoxe d'anniversaire: les chances de deux valeurs aléatoires correspondant à l'autre sont contre-arrivées beaucoup plus élevées que les chances d'une valeur aléatoire correspondant à une cible unique.
De ce que je vois, vous avez besoin d'une fonction de hachage avec les exigences suivantes,
Ce Sondage de la fonction de hachage peut être utile pour percer la fonction la plus appropriée pour vous. < BR> Je vais suggérer d'essayer de multiples fonctions d'ici et de les caractériser pour votre ensemble d'entrées probable (choisissez quelques milliards d'URL que vous pensez voir).
Vous pouvez réellement générer une autre colonne comme cette enquête de test pour votre liste d'URL de test pour caractériser et sélectionnez parmi les nouvelles fonctions de hachage existantes ou nouvelles (plus de lignes dans ce tableau) que vous voudrez peut-être vérifier. Ils ont un code source MSVC ++ pour commencer avec ( Référence à Zip Lien ).
Modification des fonctions de hachage en fonction de votre largeur de sortie (64 bits) vous donnera une caractérisation plus précise pour votre application.
Juste en utilisant un hachage, il y a toujours une chance de collisions. Et vous ne savez pas à l'avance que les collisions que les collisions se produiront une ou deux fois, voire des centaines ou des milliers de fois dans votre liste d'URL.
La probabilité est toujours juste une probabilité. C'est comme jeter un dés 10 ou 100 fois, quelles sont les chances d'obtenir tous les six? La probabilité dit qu'il est faible, mais cela peut toujours arriver. Peut-être même plusieurs fois de suite ...
Alors alors que le Paradox anniversaire montre comment calculer les probabilités, vous devez toujours avoir besoin de Décidez si les collisions sont acceptables ou non.
... et les collisions sont acceptables et les hachages sont toujours la bonne façon d'y aller; Trouvez un algorithme de hachage de 64 bits au lieu de s'appuyer sur «Half A-MD5» ayant une bonne distribution. (Bien que cela a probablement ...)
Si vous avez 2 ^ n possibilités de hachage, il y a plus de 50% de chances de collision lorsque vous avez 2 ^ (n / 2) articles.
E.g. 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 articles dans une collection.