Wahrscheinlichkeit einer Kollision mit den wichtigsten Bits einer UUID in Java

235

Wenn ich benutze, Long uuid = UUID.randomUUID().getMostSignificantBits()wie wahrscheinlich ist es, dass es zu einer Kollision kommt. Es schneidet die niedrigstwertigen Bits ab, so dass die Möglichkeit besteht, dass Sie auf eine Kollision stoßen, oder?

Dlinsin
quelle

Antworten:

213

Gemäß der DokumentationUUID.randomUUID() generiert die statische Methode eine UUID vom Typ 4.

Dies bedeutet, dass sechs Bits für einige Typinformationen verwendet werden und die verbleibenden 122 Bits zufällig zugewiesen werden.

Die sechs nicht zufälligen Bits sind mit vier in der höchstwertigen Hälfte der UUID und zwei in der niedrigstwertigen Hälfte verteilt. Die höchstwertige Hälfte Ihrer UUID enthält also 60 Zufallsbits, was bedeutet, dass Sie durchschnittlich 2 ^ 30 UUIDs generieren müssen, um eine Kollision zu erhalten (im Vergleich zu 2 ^ 61 für die vollständige UUID).

Also würde ich sagen, dass Sie ziemlich sicher sind. Beachten Sie jedoch, dass dies für andere Arten von UUIDs absolut nicht gilt, wie Carl Seleborg erwähnt.

Übrigens wären Sie etwas besser dran, wenn Sie die niedrigstwertige Hälfte der UUID verwenden (oder einfach mit SecureRandom eine zufällige Long-Position generieren).

Rasmus Faber
quelle
3
Ich bin mir nicht sicher, ob dies völlig richtig ist. Wenn man sich die Implementierung ansieht, ist klar, dass die Versions- / Varianteninformationen nicht in den höchstwertigen Bits gespeichert sind, sondern irgendwo in der Mitte.
Tom
2
@RasmusFaber Der Kommentar von Tom ist richtig: Die Antwort hier ist falsch, da die sechs wichtigsten Bits Typinformationen sind . Es gibt zwar sechs Bits nicht zufälliger Daten, aber vier Bits identifizieren die Version 4 und zwei andere Bits sind reserviert. Die vier und zwei Bits befinden sich an verschiedenen Positionen nahe der Mitte des 128-Bit-Werts. Siehe den Wikipedia-Artikel .
Basil Bourque
10

Sie sind besser dran, nur einen zufälligen langen Wert zu generieren, dann sind alle Bits zufällig. In Java 6 verwendet new Random () System.nanoTime () plus einen Zähler als Startwert.

Es gibt verschiedene Ebenen der Einzigartigkeit.

Wenn Sie die Eindeutigkeit auf vielen Computern benötigen, können Sie über eine zentrale Datenbanktabelle verfügen, um eindeutige IDs oder sogar Stapel eindeutiger IDs zuzuweisen.

Wenn Sie nur eine Eindeutigkeit in einer App benötigen, können Sie einfach einen Zähler haben (oder einen Zähler, der je nach Ihren Anforderungen mit currentTimeMillis () * 1000 oder nanoTime () beginnt).

Peter Lawrey
quelle
7

Verwenden Sie die Zeit YYYYDDDD(Jahr + Tag des Jahres) als Präfix. Dies verringert die Datenbankfragmentierung in Tabellen und Indizes. Diese Methode gibt zurück byte[40]. Ich habe es in einer Hybridumgebung verwendet, in der die Active Directory-SID ( varbinary(85)) der Schlüssel für LDAP-Benutzer ist und eine automatisch generierte Anwendungs-ID für Nicht-LDAP-Benutzer verwendet wird. Auch die große Anzahl von Transaktionen pro Tag in Transaktionstabellen (Bankenbranche) kann keine Standardtypen Intfür Schlüssel verwenden

private static final DecimalFormat timeFormat4 = new DecimalFormat("0000;0000");

public static byte[] getSidWithCalendar() {
    Calendar cal = Calendar.getInstance();
    String val = String.valueOf(cal.get(Calendar.YEAR));
    val += timeFormat4.format(cal.get(Calendar.DAY_OF_YEAR));
    val += UUID.randomUUID().toString().replaceAll("-", "");
    return val.getBytes();
}
Dr. Bob
quelle
3
Warum nicht stattdessen eine Standard-V1-UUID verwenden?
ShadowChaser