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?
Bei einem früheren Arbeitgeber hatten wir eine eindeutige Spalte, die eine zufällige UUID enthielt. Wir hatten in der ersten Woche nach der Bereitstellung eine Kollision. Sicher, die Chancen stehen niedrig, aber sie sind nicht null. Deshalb enthält Log4j 2 UuidUtil.getTimeBasedUuid. Es generiert eine UUID, die für 8.925 Jahre eindeutig ist, solange Sie nicht mehr als 10.000 UUIDs/Millisekunde auf einem einzigen Server generieren.
Es wird nach der Wahrscheinlichkeit einer Kollision gefragt. Die Implikation ist, dass er sicherstellen möchte, diese zu vermeiden.
Die Kollision war höchstwahrscheinlich auf eine defekte Quelle der Zufälligkeit für das Nachfüllen der PRNGs zurückzuführen. Ich denke jedoch, dass es möglich war, dass es auf reines Glück zurückzuführen war.
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.
Diese Erklärung macht mich optimistisch, in der Praxis keine Kollisionen zu sehen. Kannst du auf eine Referenz für diese Aussage hinweisen (ein Quellcode wäre noch besser)?
Fand dies in Spezifikationen ietf.org/rfc/rfc4122.txt. Trotzdem wäre es großartig, die Implementierung zu sehen.
Dieses Schema wird nicht von Java implementiert. Java implementiert Typ-4-UUID, der rein zufällig ist und keine MAC-Adresse oder Zeit enthält. Übrigens, da es mittlerweile viele physische und virtuelle Geräte gibt, bei denen Sie Ihre MAC-Adresse wählen können, garantiert der ursprüngliche Algorithmus keine Eindeutigkeit.
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)
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
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
15 Stimmen
In meiner Erfahrung habe ich noch nie eine Kollision gesehen ;-)
4 Stimmen
Die Algorithmen sind in RFC1422 spezifiziert: ietf.org/rfc/rfc4122.txt
9 Stimmen
@skaffman: Das RFC sagt überhaupt nichts über den verwendeten Algorithmus zur Generierung der Zufallszahlen aus.
5 Stimmen
Da es sich um eine offene Frage handelt, werde ich keine Antwort als die richtige Antwort markieren. Stattdessen werde ich jeder Antwort, die ich gut finde, eine Stimme geben :)
10 Stimmen
Von Wikipedia: ... Mit anderen Worten, nur nachdem 1 Milliarde UUIDs pro Sekunde für die nächsten 100 Jahre generiert wurden, läge die Wahrscheinlichkeit, nur einen einzigen Duplikat zu erstellen, bei etwa 50%.
0 Stimmen
Wir haben bisher 2 Kollisionen erlebt. Ich weiß nicht, wie es uns gelungen ist, sie zu verursachen :(
0 Stimmen
Die Quintessenz ist also, dass eine Kollision möglich ist. Es ist möglich, dass die ersten 2 UUIDs, die Sie generieren, identisch sind. Unwahrscheinlich, ja.
1 Stimmen
@MaVRoSCy es ist "mindestens einer" und nicht nur "einer"
1 Stimmen
Wenn Sie nicht zwei IDs innerhalb derselben Sekunde generieren müssen, ist es zu 100 % sicher für das aktuelle Datum + die Uhrzeit.