Probabilidad de colisión utilizando los bits más significativos de un UUID en Java

235

Si estoy usando, Long uuid = UUID.randomUUID().getMostSignificantBits()¿qué tan probable es que tenga una colisión? Corta los bits menos significativos, por lo que existe la posibilidad de que se encuentre con una colisión, ¿verdad?

dlinsin
fuente

Respuestas:

213

Según la documentación , el método estático UUID.randomUUID()genera un UUID de tipo 4.

Esto significa que se utilizan seis bits para algún tipo de información y los 122 bits restantes se asignan aleatoriamente.

Los seis bits no aleatorios se distribuyen con cuatro en la mitad más significativa del UUID y dos en la mitad menos significativa. Entonces, la mitad más significativa de su UUID contiene 60 bits de aleatoriedad, lo que significa que en promedio necesita generar 2 ^ 30 UUID para obtener una colisión (en comparación con 2 ^ 61 para el UUID completo).

Entonces diría que estás bastante seguro. Sin embargo, tenga en cuenta que esto no es absolutamente cierto para otros tipos de UUID, como menciona Carl Seleborg.

Por cierto, estaría un poco mejor usando la mitad menos significativa del UUID (o simplemente generando un largo aleatorio usando SecureRandom).

Rasmus Faber
fuente
3
No estoy seguro de que esto sea completamente correcto: al observar la implementación, está claro que la información de la versión / variante no se almacena en los bits más significativos, sino en algún lugar en el medio.
Tom
2
@RasmusFaber El comentario de Tom es correcto: la respuesta aquí es incorrecta sobre los seis bits más significativos que son información de tipo. De hecho, hay seis bits de datos no aleatorios, pero cuatro bits identifican la Versión 4 y otros dos bits están reservados. Los cuatro y dos bits se encuentran en diferentes posiciones cerca de la mitad del valor de 128 bits. Ver el artículo de Wikipedia .
Basil Bourque
10

Es mejor que solo genere un valor largo aleatorio, luego todos los bits son aleatorios. En Java 6, el nuevo Random () usa System.nanoTime () más un contador como semilla.

Hay diferentes niveles de singularidad.

Si necesita unicidad en muchas máquinas, podría tener una tabla de base de datos central para asignar identificadores únicos, o incluso lotes de identificadores únicos.

Si solo necesita tener unicidad en una aplicación, puede tener un contador (o un contador que comience desde el CurrentTimeMillis () * 1000 o nanoTime () según sus requisitos)

Peter Lawrey
fuente
7

Use el tiempo YYYYDDDD(año + día del año) como prefijo. Esto disminuye la fragmentación de la base de datos en tablas e índices. Este método vuelve byte[40]. Lo utilicé en un entorno híbrido donde el SID de Active Directory ( varbinary(85)) es la clave para los usuarios de LDAP y una identificación autogenerada de la aplicación se usa para usuarios que no son de LDAP. Además, la gran cantidad de transacciones por día en las tablas transaccionales (industria bancaria) no puede usar Inttipos estándar para claves

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
fuente
3
¿Por qué no utilizar un UUID V1 estándar en su lugar?
ShadowChaser