Wie gut ist Java's UUID.randomUUID?

Question

Ich weiß, dass zufällige UUIDs in der Theorie eine sehr, sehr, sehr geringe Kollisionswahrscheinlichkeit haben, aber ich frage mich, wie gut Java's randomUUID() in der Praxis ist, um Kollisionen zu vermeiden? Hat jemand Erfahrungen zu teilen?

Answer 1

Viele der Antworten befassen sich damit, wie viele UUIDs generiert werden müssten, um eine 50%ige Chance auf eine Kollision zu erreichen. Aber eine 50%, 25% oder sogar 1%ige Kollisionschance ist für eine Anwendung, in der Kollision praktisch unmöglich sein muss, wertlos.

Weisen Programmierer routinemäßig andere Ereignisse als "unmöglich" ab, die tatsächlich eintreten können?

Wenn wir Daten auf eine Festplatte oder in den Speicher schreiben und sie dann wieder auslesen, nehmen wir selbstverständlich an, dass die Daten korrekt sind. Wir verlassen uns auf die Fehlerkorrektur des Geräts, um jede Beschädigung zu erkennen. Aber die Chance auf unerkannte Fehler liegt tatsächlich bei etwa 2-50.

Wäre es nicht sinnvoll, einen ähnlichen Standard auf zufällige UUIDs anzuwenden? Wenn Sie dies tun, werden Sie feststellen, dass eine "unmögliche" Kollision in einer Sammlung von rund 100 Milliarden zufälligen UUIDs (236.5) möglich ist.

Dies ist eine astronomische Zahl, aber Anwendungen wie die Aufschlüsselung von Rechnungen in einem nationalen Gesundheitssystem oder das Protokollieren von hochfrequenten Sensordaten auf einer großen Anzahl von Geräten könnten definitiv an diese Grenzen stoßen. Wenn Sie gerade den nächsten Per Anhalter durch die Galaxis schreiben, versuchen Sie nicht, jedem Artikel UUIDs zuzuweisen!

Answer 2

Das ursprüngliche Generierungsschema für UUIDs bestand darin, die UUID-Version mit der MAC-Adresse des Computers zu verknüpfen, der die UUID generiert, und mit der Anzahl der 100-Nanosekunden-Intervalle seit der Einführung des gregorianischen Kalenders im Westen. Durch die Darstellung eines einzigen Punktes im Raum (dem Computer) und in der Zeit (der Anzahl der Intervalle) ist die Wahrscheinlichkeit einer Kollision bei den Werten effektiv gleich Null.

Answer 3

Ich habe letztes Jahr bei der Lotterie gespielt und noch nie gewonnen .... aber es scheint, dass es dort Gewinner gibt ...

doc : https://www.rfc-editor.org/rfc/rfc4122

Typ 1 : nicht implementiert. Kollisionen sind möglich, wenn die UUID im selben Moment generiert wird. Die Implementierung kann künstlich asynchron sein, um dieses Problem zu umgehen.

Typ 2 : Habe nie eine Implementierung gesehen.

Typ 3 : md5 hash : Kollision möglich (128 Bit-2 technische Byte)

Typ 4 : zufällig : Kollision möglich (wie bei einer Lotterie). Beachten Sie, dass die Implementierung von jdk6 kein "echt" sicheres Zufallsprinzip verwendet, da der PRNG-Algorithmus nicht vom Entwickler ausgewählt wird und das System dazu gebracht werden kann, einen "schlechten" PRNG-Algorithmus zu verwenden. Daher ist Ihre UUID vorhersehbar.

Typ 5 : sha1 hash : nicht implementiert : Kollision möglich (160 Bit-2 technische Bytes)

Answer 4

Wir verwenden seit mehr als einem Jahr das zufällige UUID von Java in unserer Anwendung, und das sehr umfangreich. Aber wir sind noch nie auf eine Kollision gestoßen.

Answer 5

Da die meisten Antworten sich auf die Theorie konzentrierten, denke ich, dass ich etwas zur Diskussion beitragen kann, indem ich einen praktischen Test vorstelle, den ich gemacht habe. In meiner Datenbank habe ich ungefähr 4,5 Millionen UUIDs, die mit Java 8 UUID.randomUUID() generiert wurden. Die folgenden sind nur einige, die ich herausgefunden habe:

c0f55f62-b990-47bc-8caa-f42313669948

c0f55f62-e81e-4253-8299-00b4322829d5

c0f55f62-4979-4e87-8cd9-1c556894e2bb

b9ea2498-fb32-40ef-91ef-0ba00060fe64

be87a209-2114-45b3-9d5a-86d00060fe64

4a8a74a6-e972-4069-b480-bdea1177b21f

12fb4958-bee2-4c89-8cf8-edea1177b21f

Wenn es wirklich zufällig wäre, wäre die Wahrscheinlichkeit, dass solche ähnlichen UUIDs auftreten, beträchtlich gering (siehe Bearbeitung), da wir nur 4,5 Millionen Einträge betrachten. Also, obwohl diese Funktion gut ist, was Kollisionen betrifft, scheint sie mir in der Praxis nicht so gut zu sein, wie es in der Theorie wäre.

Bearbeitung:

Es scheint, dass viele Leute diese Antwort nicht verstehen, also werde ich meinen Standpunkt klären: Ich weiß, dass die Ähnlichkeiten "gering" sind und weit von einer vollständigen Kollision entfernt. Ich wollte jedoch nur Java's UUID.randomUUID() mit einem wirklich zufälligen Zahlengenerator vergleichen, was die eigentliche Frage ist.

Bei einem wirklich zufälligen Zahlengenerator wäre die Wahrscheinlichkeit, dass der letzte Fall eintritt, etwa = 0,007%. Deshalb denke ich, dass meine Schlussfolgerung Bestand hat.

Die Formel wird in diesem Wiki-Artikel erklärt: de.wikipedia.org/wiki/Geburtstagsparadoxon