Ist es sicher anzunehmen, dass eine GUID immer eindeutig ist?

Question

Ich weiß, dass es eine winzige Möglichkeit eines Konflikts gibt, aber wenn ich einen Stapel von 1000 GUIDs (zum Beispiel) generieren würde, wäre es sicher anzunehmen, dass sie alle einzigartig sind, um das Testen jedes einzelnen zu speichern?

Bonus Frage

Ein optimaler Weg, um eine GUID für Einzigartigkeit zu testen? Bloom Filter vielleicht?

Answer 1

Ja, Sie können. Da GUIDs 128 Bits lang sind, gibt es zugegebenermaßen eine winzige Möglichkeit eines Konflikts - aber das Wort "Minute" ist bei weitem nicht stark genug. Es gibt so viele GUIDs dass, wenn Sie mehrere Billionen von ihnen nach dem Zufallsprinzip generieren, Sie noch eher von einem Meteoriten getroffen werden, als nur eine Kollision zu haben (von Wikipedia). Und wenn Sie sie nicht zufällig erzeugen, sondern z.B. mit dem MAC-Adresse-und-Zeit-Stempel-Algorithmus, dann werden sie auch einzigartig sein, wie MAC-Adressen sind einzigartig unter den Computern und Zeitstempel sind einzigartig auf Ihre Computer.

Bearbeiten 1: Um Ihre Bonusfrage zu beantworten, ist der optimale Weg, um eine Reihe von GUIDs auf Eindeutigkeit zu testen, einfach davon auszugehen, dass sie alle einzigartig sind. Warum? Weil die Wahrscheinlichkeit einer GUID-Kollision angesichts der Anzahl der erzeugten GUIDs geringer ist als die Wahrscheinlichkeit, dass ein kosmischer Strahl ein wenig in den Speicher Ihres Computers einschlägt und die Antwort jedes "genauen" Algorithmus verdreht, den Sie interessieren würden zu rennen. (Siehe this StackOverflow answer für die Mathematik.)

Es gibt eine enorme Anzahl von GUIDs da draußen. Zitieren Douglas Adams Per Anhalter durch die Galaxis:...

„Space“, heißt es, „groß ist wirklich groß Sie will einfach nicht glauben, wie stark enorm mindbogglingly groß es ist, ich meine, Sie können denke, es ist auf dem Weg in die Apotheke ein langer Weg ist, aber das ist nur Erdnüsse Raum, hört ...“

und da es about 7×10²² stars in the universe ist, und knapp 2 GUIDs, dann gibt es etwa 4,86 ​​× 10 -fast Fünf Billiarden -GUIDs für jeden einzelnen Stern.Wenn jeder dieser Sterne eine Welt mit einer blühenden Bevölkerung wie der unsrigen hätte, dann würde um jeden einzelnen Stern every human or alien who had ever lived Anspruch auf über fünfundvierzigtausend GUIDs haben. Für jede Person in der Geschichte an jedem Stern im Universum. Der GUID-Raum befindet sich auf der gleichen Ebene der Größe wie die Größe des gesamten Universums. Sie tun nicht müssen sich sorgen.

(Edit 2: auf dieser Reflecting:.. Wow ich ich, was dies bedeutete nicht erkannt hatte, der Raum GUID ist unbegreiflich massiv ich in Ehrfurcht es irgendwie bin..)

Answer 2

Während eine Kollision möglich ist, ist es HOCH unwahrscheinlich. (Math here.) Es ist sicher anzunehmen, dass sie tatsächlich verschieden sind.

Answer 3

Im Allgemeinen ist es sicher anzunehmen.

Wenn Ihr GUID-Generator wirklich zufällig ist, sind die Möglichkeiten eines Konflikts innerhalb von 1000 GUIDs außerordentlich gering.

Das setzt natürlich einen guten GUID-Generator voraus. Die Frage ist also wirklich, wie viel Vertrauen Sie dem Tool, das Sie verwenden, um GUID zu generieren, und hat es eigene Tests?

Answer 4

Normalerweise ist es eine ziemlich sichere Annahme.

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

Is a GUID unique 100% of the time?

Answer 5

Eine Analyse der möglichen Kollision ist auf Wikipedia verfügbar: http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates

Wie in der Verknüpfung erwähnt, wird dies durch die Eigenschaften des Zufallszahlengenerators beeinflusst.

Es gibt auch die Möglichkeit eines Fehlers im GUID-Generator-Code; während die Chancen niedrig sind, sind sie wahrscheinlich höher als die Chancen einer Kollision basierend auf der Mathematik.

Ein Bloom-Filter könnte angebracht sein; Es kann Ihnen schnell sagen, ob eine GUID eindeutig ist, aber es besteht die Möglichkeit, dass eine Kollision falsch angezeigt wird. Eine alternative Methode, wenn Sie einen Stapel gleichzeitig testen, besteht darin, den Stapel zu sortieren und jedes nachfolgende Element zu vergleichen.

Answer 6

Kurze Antwort: für praktische Zwecke, ja.

Allerdings müssen Sie das Geburtstagsparadoxon berücksichtigen!

Ich habe ein paar repräsentative Kollisionswahrscheinlichkeiten berechnet. Bei 122-Bit-UUIDs, wie in the Wikipedia article angegeben, beträgt die Kollisionswahrscheinlichkeit 1/2, wenn Sie mindestens 2.71492e18 UUIDs generieren. Mit 10^19 UUIDs ist die Wahrscheinlichkeit 0.999918. Mit 10^17 UUIDs, 0,000939953.

Some numbers for comparison can be found on Wikipedia. So können Sie sicher eine UUID für jeden lebenden Menschen, jede Galaxie im beobachtbaren Universum, jeden Fisch im Ozean und jede einzelne Ameise auf der Erde zuweisen. Aber, Kollisionen sind fast sicher, wenn Sie eine UUID für jeden Transistor erzeugen, den die Menschheit in einem Jahr produziert, jedes Insekt auf der Erde, jedes Sandkorn auf der Erde, jeden Stern im beobachtbaren Universum oder irgendetwas Größeres.

Wenn Sie 1 Milliarde UUIDs pro Sekunde generieren, it would take about 36 years, um eine Kollisionswahrscheinlichkeit von 10% zu erhalten.

Schließlich wird es wahrscheinlich eine Kollision zwischen den UUIDs geben, die im Laufe der Menschheitsgeschichte erzeugt wurden. Dennoch ist die Wahrscheinlichkeit, dass kollidierende UUIDs für den gleichen Zweck verwendet werden, verschwindend gering, so dass es in der Praxis kein Problem gibt.