Est-il prudent de supposer qu'un GUID sera toujours unique?

Je sais qu'il y a une possibilité infime de conflit, mais si j'ai généré un lot de 1000 GUID (par exemple), serait-il prudent de supposer qu'ils sont tous uniques pour éviter de tester chacun d'eux?

Question bonus

Une façon optimale de tester un GUID pour l'unicité? Filtre Bloom peut-être?

Oui, vous pouvez. Puisque les GUID ont une longueur de 128 bits, il y a certes une possibilité minime de conflit, mais le mot «minute» est loin d'être assez fort. Il y a tellement de GUID que si vous en générez plusieurs trillions au hasard, vous êtes toujours plus susceptible d'être touché par une météorite que d'avoir même une collision (de Wikipedia ). Et si vous ne les générez pas de manière aléatoire, mais que vous utilisez par exemple l'algorithme d'adresse MAC et d'horodatage, ils seront également uniques, car les adresses MAC sont uniques parmi les ordinateurs et les horodatages sont uniques sur votre ordinateur.

Edit 1: Pour répondre à votre question bonus, la façon optimale de tester un ensemble de GUID pour l'unicité est simplement de supposer qu'ils sont tous uniques. Pourquoi? Parce que, étant donné le nombre de GUID que vous générez, les chances d'une collision de GUID sont plus petites que les chances d'un rayon cosmique retournant un peu dans la mémoire de votre ordinateur et foirant la réponse donnée par tout algorithme "précis" qui vous intéresserait courir. (Voir cette réponse StackOverflow pour les mathématiques.)

Il existe un nombre énorme de GUID. Pour citer le guide de l'auto-stoppeur de Douglas Adams sur la galaxie :

«L'espace», dit-il, «est grand. Vraiment grand. Vous ne croirez tout simplement pas à quel point il est extrêmement grand. , Ecoutez…"

Et comme il y a environ 7 × 10 ²² étoiles dans l'univers , et un peu moins de 2 ¹²⁸ GUID, alors il y a environ 4,86 ​​× 10 ^{15 -} près de cinq quadrillions - de GUID pour chaque étoile. Si chacune de ces étoiles avait un monde avec une population florissante comme la nôtre, alors autour de chaque étoile, chaque humain ou extraterrestre qui avait jamais vécu aurait droit à plus de quarante-cinq mille GUID. Pour chaque personne de l'histoire à chaque étoile de l'univers. L'espace GUID est au même niveau de grandeur que la taille de l'univers entier. Vous n'avez pas besoin de vous inquiéter.

( Edit 2: Réfléchir à ceci: wow. Je n'avais pas réalisé moi-même ce que cela signifiait. L'espace GUID est incroyablement énorme. Je suis en quelque sorte impressionné.)

Réponse courte: pour des raisons pratiques, oui.

Cependant, vous devez considérer le paradoxe de l'anniversaire!

J'ai calculé quelques probabilités de collision représentatives. Avec des UUID de 122 bits comme spécifié dans l'article de Wikipédia , la probabilité de collision est de 1/2 si vous générez au moins des 2.71492e18UUID. Avec 10 ^ 19 UUID, la probabilité est de 0,999918. Avec 10 ^ 17 UUID, 0,000939953.

Quelques chiffres à comparer peuvent être trouvés sur Wikipedia. Ainsi, vous pouvez attribuer en toute sécurité un UUID à chaque humain qui a vécu, à chaque galaxie de l'univers observable, à chaque poisson de l'océan et à chaque fourmi sur 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 Terre, chaque grain de sable sur Terre, chaque étoile de l'univers observable, ou quelque chose de plus grand.

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

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

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 y a aussi la possibilité d'un bogue dans le code du générateur GUID; alors que les chances sont faibles, elles sont probablement plus élevées que les chances d'une collision basée 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 pour une fausse indication d'une collision. Une autre méthode si vous testez un lot à la fois consiste à trier le lot et à comparer chaque élément successif.

En général, oui, il est prudent de supposer.

Si votre générateur de GUID est vraiment aléatoire, les possibilités d'un conflit dans un 1000 GUID sont extrêmement faibles.

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 a-t-il ses propres tests?

Bien qu'une collision soit possible, elle est TRÈS improbable. (Math ici .) Il est sûr de supposer qu'ils sont en fait distincts.

C'est généralement une hypothèse assez sûre.

http://en.wikipedia.org/wiki/Globally_Unique_Identifier

Un GUID est-il unique à 100% du temps?