Probabilità di collisione utilizzando i bit più significativi di un UUID in Java

Question

Se sto usando Long uuid = UUID.randomUUID (). getMostSignificantBits () quanto è probabile che si verifichi una collisione. Taglia i bit meno significativi, quindi c'è la possibilità di incorrere in una collisione, giusto?

Answer 1

Secondo la documentazione , il il metodo statico UUID.randomUUID () genera un UUID di tipo 4.

Ciò significa che vengono utilizzati sei bit per alcune informazioni sul tipo e i rimanenti 122 bit vengono assegnati in modo casuale.

I sei bit non casuali sono distribuiti con quattro nella metà più significativa dell'UUID e due nella metà meno significativa. Quindi la metà più significativa dell'UUID contiene 60 bit di casualità, il che significa che in media è necessario generare 2 ^ 30 UUID per ottenere una collisione (rispetto a 2 ^ 61 per l'intero UUID).

Quindi direi che sei piuttosto al sicuro. Si noti, tuttavia, che ciò non è assolutamente vero per altri tipi di UUID, come menziona Carl Seleborg.

Per inciso, saresti leggermente meglio usando la metà meno significativa dell'UUID (o semplicemente generando un lungo casuale usando SecureRandom).

Answer 2

Raymond Chen ha un post sul blog davvero eccellente su questo:

I GUID sono univoci a livello globale, ma le sottostringhe dei GUID non lo sono

Answer 3

Penso che questo sia il miglior esempio per l'uso di randomUUID:

http://www.javapractices.com/topic/TopicAction.do? id = 56

Answer 4

Stai meglio semplicemente generando un valore lungo casuale, quindi tutti i bit sono casuali. In Java 6, new Random () utilizza System.nanoTime () più un contatore come seed.

Esistono diversi livelli di unicità.

Se è necessaria l'univocità su più macchine, è possibile disporre di una tabella di database centrale per l'allocazione di ID univoci o persino lotti di ID univoci.

Se hai solo bisogno di avere unicità in un'app puoi semplicemente avere un contatore (o un contatore che parte da currentTimeMillis () * 1000 o nanoTime () a seconda delle tue esigenze)

Answer 5

Utilizza l'ora YYYYDDDD (anno + giorno dell'anno) come prefisso. Ciò riduce la frammentazione del database in tabelle e indici. Questo metodo restituisce byte [40] . L'ho usato in un ambiente ibrido in cui il SID di Active Directory ( varbinary (85) ) è la chiave per gli utenti LDAP e un ID generato automaticamente dall'applicazione viene utilizzato per utenti non LDAP. Inoltre, il gran numero di transazioni al giorno nelle tabelle transazionali (settore bancario) non può utilizzare i tipi Int standard per le chiavi

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();
}