Peut-on supposer qu'un GUID sera toujours unique ?

Question

Je sais qu'il existe une infime possibilité de conflit, mais si je génère un lot de 1000 GUID (par exemple), serait-il prudent de supposer qu'ils sont tous uniques pour éviter de les tester tous ?

Question bonus

Une façon optimale de tester l'unicité d'un GUID ? Un filtre Bloom peut-être ?

Answer 1

Si, vous le pouvez. Les GUID ayant une longueur de 128 bits, la possibilité d'un conflit est certes infime, mais le mot "infime" est loin d'être assez fort. Il existe tant de GUIDs que si vous générez plusieurs milliers de milliards d'entre eux au hasard, vous avez toujours plus de chances d'être frappé par une météorite que d'avoir ne serait-ce qu'une seule collision (de Wikipedia ). Et si vous ne les générez pas de manière aléatoire, mais que vous par exemple en utilisant l'algorithme de l'adresse MAC et de l'horodatage, ils seront également uniques, car les adresses MAC sont uniques parmi les ordinateurs et les horodatages sont uniques sur les ordinateurs. votre ordinateur.

Edit 1 : Pour répondre à votre question bonus, la meilleure façon de tester l'unicité d'un ensemble de GUIDs est de supposer qu'ils sont tous uniques. Pourquoi ? Parce que, compte tenu du nombre de GUID que vous générez, les chances de collision de GUID sont plus faibles que les chances qu'un rayon cosmique retourne un bit dans la mémoire de votre ordinateur et bousille la réponse donnée par n'importe quel algorithme "précis" que vous voudriez exécuter. (Voir cette réponse de StackOverflow pour le calcul).

Il existe un énorme nombre de GUIDs qui existent. Pour citer la phrase de Douglas Adams Le Guide du routard de la galaxie :

"L'espace", dit-il, "est grand. Vraiment grand. Vous n'allez pas croire à quel point c'est énorme et époustouflant. Je veux dire, vous pouvez penser que c'est un long chemin jusqu'au pharmacien, mais c'est juste des cacahuètes par rapport à l'espace, écoutez "

Et comme il y a environ 7×10 22 les étoiles dans l'univers et un peu moins de 2 128 GUIDs, alors il y a approximativement 4,86×10 15 -presque cinq quadrillions -GUIDs pour chaque étoile. Si chacune de ces étoiles avait un monde avec une population prospère comme la nôtre, alors autour de chaque étoile, chaque humain ou alien qui a vécu aurait droit à plus de quarante-cinq mille GUIDs. Pour chaque personne de l'histoire et chaque étoile de l'univers. L'espace des GUID est au même niveau d'immensité que la taille de l'univers entier. Vous faites no doivent s'inquiéter.

( Edit 2 : En y réfléchissant : wow. Je n'avais pas réalisé moi-même ce que cela signifiait. L'espace GUID est incompréhensiblement massif. Je suis en quelque sorte en admiration devant lui).

Answer 2

Réponse courte : à des fins pratiques, oui.

Cependant, il faut tenir compte du paradoxe de l'anniversaire !

J'ai calculé quelques probabilités de collision représentatives. Avec des UUIDs de 122 bits comme spécifié dans l'article de Wikipedia la probabilité de collision est de 1/2 si on génère au moins 2.71492e18 UUIDs. Avec 10^19 UUIDs, la probabilité est de 0,999918. Avec 10^17 UUIDs, 0.000939953.

Quelques chiffres à titre de comparaison peuvent être trouvés sur Wikipedia. Vous pouvez donc attribuer sans risque un UUID à chaque être humain ayant vécu, à chaque galaxie de l'univers observable, à chaque poisson de l'océan et à chaque fourmi de la Terre. Cependant Les collisions sont presque certaines si vous générez un UUID pour chaque transistor que l'humanité produit en un an, chaque insecte sur la Terre, chaque grain de sable sur la Terre, chaque étoile dans l'univers observable ou tout autre objet plus grand.

Si vous générez 1 milliard d'UUIDs par seconde, cela prendrait environ 36 ans pour obtenir une probabilité de collision de 10%.

À terme, il y aura probablement une collision entre l'ensemble des UUID générés au cours de l'histoire de l'humanité. Toutefois, la probabilité que les UUID entrés en collision soient utilisés dans le même but est extrêmement faible, de sorte qu'il n'y a pas de problème en pratique.

Answer 3

Une analyse de la possibilité de collision est disponible sur Wikipedia : http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates

Comme mentionné dans le lien, cela sera affecté par les propriétés du générateur de nombres aléatoires.

Il est également possible qu'un bogue se soit glissé dans le code du générateur de GUID ; bien que les chances soient faibles, elles sont probablement plus élevées que les chances de collision basées sur les mathématiques.

Un filtre Bloom pourrait être approprié ; il peut vous dire rapidement si un GUID est unique, mais il y a un risque de fausse indication de collision. Une autre méthode, si vous testez un lot à la fois, consiste à trier le lot et à comparer chaque élément successif.

Answer 4

En général, oui, on peut le supposer.

Si votre générateur de GUID est vraiment aléatoire, la possibilité d'un conflit entre 1000 GUID est extraordinairement faible.

Bien sûr, cela suppose un bon générateur de GUID. La question est donc de savoir dans quelle mesure vous faites confiance à l'outil que vous utilisez pour générer des GUID et s'il dispose de ses propres tests.

Answer 5

Bien qu'une collision soit possible, elle est HAUTEMENT improbable. (Mathématiques aquí .) On peut supposer qu'ils sont en fait distincts.