Prawdopodobieństwo kolizji przy użyciu najbardziej znaczących bitów UUID w Javie

235

Jeśli używam, jakie Long uuid = UUID.randomUUID().getMostSignificantBits()jest prawdopodobieństwo kolizji. Odcina najmniej znaczące bity, więc istnieje możliwość, że wpadniesz na kolizję, prawda?

dlinsin
źródło

Odpowiedzi:

213

Zgodnie z dokumentacją metoda statyczna UUID.randomUUID()generuje UUID typu 4.

Oznacza to, że dla niektórych informacji o typie używanych jest sześć bitów, a pozostałe 122 bity są przypisywane losowo.

Sześć bitów nielosowych jest rozdzielonych, z czterema w najbardziej znaczącej połowie UUID i dwoma w najmniej znaczącej połowie. Więc najbardziej znacząca połowa twojego UUID zawiera 60 bitów losowości, co oznacza, że ​​średnio musisz wygenerować 2 ^ 30 UUID, aby uzyskać kolizję (w porównaniu do 2 ^ 61 dla pełnego UUID).

Powiedziałbym więc, że jesteś raczej bezpieczny. Należy jednak pamiętać, że absolutnie nie jest to prawdą w przypadku innych typów UUID, jak wspomina Carl Seleborg.

Nawiasem mówiąc, byłoby nieco lepiej, używając najmniej znaczącej połowy identyfikatora UUID (lub po prostu generując losową długość za pomocą SecureRandom).

Rasmus Faber
źródło
3
Nie jestem pewien, czy jest to całkowicie poprawne - patrząc na implementację, jasne jest, że informacje o wersji / wariancie nie są przechowywane w najbardziej znaczących bitach, ale raczej gdzieś pośrodku.
Tom
2
@RasmusFaber Komentarz Toma jest poprawny: Odpowiedź tutaj jest nieprawidłowa w odniesieniu do sześciu najbardziej znaczących bitów, które są informacją typu. Rzeczywiście jest sześć bitów nieprzypadkowych danych, ale cztery bity identyfikują wersję 4, a dwa inne bity są zarezerwowane. Cztery i dwa bity znajdują się w różnych pozycjach w pobliżu środka wartości 128-bitowej. Zobacz artykuł w Wikipedii .
Basil Bourque,
10

Lepiej jest po prostu wygenerować losową długą wartość, wtedy wszystkie bity są losowe. W Javie 6 nowy Random () używa System.nanoTime () plus licznika jako ziarna.

Istnieją różne poziomy wyjątkowości.

Jeśli potrzebujesz wyjątkowości na wielu komputerach, możesz mieć centralną tabelę bazy danych do przydzielania unikalnych identyfikatorów, a nawet partii niepowtarzalnych identyfikatorów.

Jeśli potrzebujesz tylko wyjątkowości w jednej aplikacji, możesz po prostu mieć licznik (lub licznik, który zaczyna się od currentTimeMillis () * 1000 lub nanoTime () w zależności od Twoich wymagań)

Peter Lawrey
źródło
7

Użyj YYYYDDDDprefiksu Czas (rok + dzień roku). Zmniejsza to fragmentację bazy danych w tabelach i indeksach. Ta metoda zwraca byte[40]. Użyłem go w środowisku hybrydowym, w którym SID ( varbinary(85)) usługi Active Directory jest kluczem dla użytkowników LDAP, a dla użytkowników innych niż LDAP używany jest automatycznie wygenerowany identyfikator aplikacji. Również duża liczba transakcji dziennie w tabelach transakcyjnych (sektor bankowy) nie może używać standardowych Inttypów kluczy

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
źródło
3
Dlaczego zamiast tego nie użyć standardowego UUID V1?
ShadowChaser,