Che ne dici di tagliare di tipo 4 UUID in questo modo

Question

Controlla questo,

    List<String> list = new ArrayList<String>();
    for (int i = 0; i < 10000; i++) {
        String value = (""+UUID.randomUUID().getLeastSignificantBits()).substring(3, 20);
        assertFalse(list.contains(value));
        assertTrue(value.length() < 18);
        list.add(value);
    }

Questo metodo sta passando come fascino. E io sono in l'impressione che sia un po 'meglio prendere bit meno significativi, piuttosto che il più significativo. Perché nei bit più significativi si hanno 6 bit fissi per alcune informazioni, e con meno significativa la sua non è il caso. Quindi, in media abbiamo bisogno di generare 2 ^ 29 UUID per ottenere una collisione con bit più significativi, ma 2 ^ 32 con molti bit meno significativi. Rif: SO discussione . Ho ragione nel ritenere che?

Ora, qui sto tritare altre 2 cifre più significative dei bit meno significativi che ho ottenuto dal metodo. Sto usando sottostringa a quella. Si noti che sto Tagliere 2 cifre e un segno po 'fuori. Vuol non significa che ora, in media, abbiamo bisogno di generare 2 ^ 31 UUID per ottenere una collisione?

Proprio, sto cercando di generare un identificativo univoco, che non dovrebbe superare i 17 di lunghezza cifre. E deve essere un numero intero, non in senso di tipo Java. Come affidabile è il mio approccio?

Informazioni Meta:

In realtà, stiamo integrando con qualche sistema legacy, e dobbiamo fornire qualche numero unico non più di 17 cifre. Stanno avendo come una chiave unica banca dati, suppongo. Possiamo anche utilizzare sequenza in questo caso, e ho proposto che, in primo luogo. Ma mi hanno detto che la sua buona se mi può trovare con un numero a caso, invece, in modo da consumatore non può indovinare.

Per quanto ne so quanto riguarda l'attuazione di tipo 4 di UUID in Java abbiamo bisogno di generare 2 ^ 61 UUID in media per ottenere una collisione. Fa che non significa che abbiamo bisogno di generare 2 ^ 32 per ottenere la collisione sul bit meno significativi, e 2 ^ 29 per ottenere la collisione sul bit più significativi? Se sì allora non è forse corretto presumere che abbiamo bisogno di generare in media 2 ^ 31 per ottenere la collisione sul bit meno significativi dopo lo spezzettamento delle 2 ha lasciato la maggior parte delle cifre?

Ho cercato di usare SecureRandom pure, ma che è anche dandomi 19 cifre valore a lungo. Quindi finisco tagliare prima cifra di tale troppo. Di seguito è riportato il codice per questo.

    List<String> list = new ArrayList();
    Random random = new SecureRandom();
    for (int i = 0; i < 10000; i++) {
        String value = ""+random.nextLong().substring(2, 19);
        assertFalse(list.contains(value));
        assertTrue(value.length() < 18);
        list.add(value);
    }

L'altra opzione mi viene in mente è quello di utilizzare data in un formato "yyMMddHHmmssSSS + 2-seq-cifre". Ma sarebbe processore abbastanza dipendente, e indovinare, immagino. Perché io non sono certo che ho avuto un cambiamento di millisecondo dopo 99 turni. Può essere io, ma ciò dipende dalla velocità del processore. 99 richieste simultanee sono abbastanza improbabile però.

Answer 1

Ti suggerisco di utilizzare sia casuale o SecureRandom per generare bit casuali e si trasformano quelli in un numero. Che dovrebbe essere più portabile.

Non capisco il tuo punto su cifre taglieri. Supponendo che si sta generando un numero 17 (decimale) cifre da abbastanza bit da un lungo ciclo di PRNG si dovrebbe avere una probabilità di 1 a 10 ** 17 di urto per qualsiasi data coppia di numeri generati. Se la fonte è buona, e si utilizza abbastanza bit, allora è irrilevante il fatto che si sta "tritare" ...

Non è chiaro per me che 1 in 10**17 è abbastanza buono. Dipende da quanti numeri stanno andando a esistere (nel tuo negozio persistente) in un dato momento. Per esempio, se si dispone di 44 milioni di numeri esistenti, la possibilità di una collisione tra almeno una coppia sarà di circa 1%.

Provare a collegare alcuni numeri in una Compleanno Paradox Calcolatrice .

EDIT: Penso che quello che vi serve è un generatore che si dà a 64 bit numeri pseudo casuali con una lunghezza di ciclo lunga e una garanzia assoluta di ripetizioni per più numeri di quanto si possa eventualmente generare. Deve anche essere possibile mantenere lo stato del generatore e riprenderla. Quindi, per ottenere un 17 cifre decimali numero "casuale", ottenere il valore successivo dal generatore e verificare se è nell'intervallo 0 ... 10**17 - 1. Se lo è, usarlo, se non ripetere.

Se si riesce correttamente il generatore, non si ottiene mai una ripetizione per tutta la durata del sistema, e quindi non v'è zero il rischio di una collisione. Ma è importante utilizzare un PRNG (non un vero RNG) e che si sceglie un PRNG che ha le giuste proprietà.

Da quello che posso dire, la classe Random offre una PRNG con una lunghezza del ciclo di 2**48; vale a dire si dovrebbe ottenere i numeri 2**48 (ad esempio utilizzando il metodo getLong()) prima dei numeri iniziano a ripetere. OTOH, SecureRandom dà sia veramente casuale o pseudo-casuale con un conteggio di ciclo molto lungo ... ma con un piccolo ma non zero possibilità di ripetere un numero su ogni chiamata.

Answer 2

OK, parecchie domande, io farò del mio meglio

1. Se si dispone di collusione nei bit più bassi, ma non nelle bit superiori, avete ancora ids uique. Lo stesso vale per il caso opposto. Pertanto, è necessario 2 ^ 61 numeri per ottenere una collusione.
2. Con una probabilità di 0,5, si sta tritare 3 cifre, dal momento che il segno + non è scritto. Pertanto, è necessario totale di 2 ^ 41 numeri possibili, quindi la dimensione del campione per concorso è 2 ^ 21. (10 ^ 18 = ~ 2 ^ 41)
3. Vediamo come si ottiene i risultati: Random.getLong () viene chiamato due volte, e quindi si rimuove alcuni dei bit (bit casuali PRNG creato). Non riesco a vedere come sia più affidabile di chiamare Random.getLong () o getInt ().

Se avete bisogno di un numero di 17 cifre, perché non fare quanto segue:

String id = String.valueOf(random.nextLong) % 1000000000000000000L);

Si noti che non darà distribuzione simmetrica - dal momento che è MAX_LONG 9223372036854775807L i numeri nel range [0,23372036854775807] verrà ad apparire un po 'più possibilità

.

Inoltre, sia per voi il metodo e questo non garantiscono ID univoco.

Answer 3

L'algoritmo UUID è l'attuazione specifica.

Tagliare il guid in numeri più piccoli non sta per avere la stessa diffusione unicità o la garanzia di. Sono i bit si sta salvando davvero così importante?