java random string generation and birthday paradox

Question

Ho bisogno di scrivere una classe di generazione di stringhe casuali che generi stringhe di 7 carati da un set di caratteri di 31 caratteri e alcuni alfabeti (10 + 26-5, 5 vocali omesse). la semplice matematica fornisce un insieme di 31^7 combinazioni possibili ~ 27,5 miliardi. Ho domande sul paradosso del bday, ho fatto alcuni test e il numero di duplicati aumenta esponenzialmente. posso fare qualcosa per evitare questo?

At 1 million, duplicates encountered till now = 19 
At 2 million, duplicates encountered till now = 69 
At 3 million, duplicates encountered till now = 157 
At 4 million, duplicates encountered till now = 280 
At 5 million, duplicates encountered till now = 470 
At 6 million, duplicates encountered till now = 662 
At 7 million, duplicates encountered till now = 896 
At 8 million, duplicates encountered till now = 1185 
At 9 million, duplicates encountered till now = 1500 
At 10 million, duplicates encountered till now = 1823 
At 11 million, duplicates encountered till now = 2204 
At 12 million, duplicates encountered till now = 2584 
At 13 million, duplicates encountered till now = 3020 
At 14 million, duplicates encountered till now = 3527 
At 15 million, duplicates encountered till now = 4110 
At 16 million, duplicates encountered till now = 4683 
At 17 million, duplicates encountered till now = 5284 
At 18 million, duplicates encountered till now = 5919 
At 19 million, duplicates encountered till now = 6611 
At 20 million, duplicates encountered till now = 7343 
At 21 million, duplicates encountered till now = 8095 
At 22 million, duplicates encountered till now = 8858 
At 23 million, duplicates encountered till now = 9707 
At 24 million, duplicates encountered till now = 10547 
At 25 million, duplicates encountered till now = 11452 
At 26 million, duplicates encountered till now = 12399 
At 27 million, duplicates encountered till now = 13356 
At 28 million, duplicates encountered till now = 14393 
At 29 million, duplicates encountered till now = 15369 
At 30 million, duplicates encountered till now = 16436 

riportano di seguito le classe di test:

import java.util.Set; 

import org.apache.commons.lang3.RandomStringUtils; 

import com.google.common.collect.Sets; 

public class RandomUnivmylocaL { 

    public static void main(String[] argv) { 

     final int million = 1_000_000; 

     final int iterations = 30; 
     // 31 chars 
     final char[] charArr = new char[] { '1', '2', '3', '4', '5', '6', '7', 
       '8', '9', '0', 'B', 'C', 'D', 'F', 'G', 'H', 'J', 'K', 'L', 
       'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'V', 'W', 'X', 'Y', 'Z' }; 
     // System.out.println(charArr.length); 

     final Set<String> set = Sets.newHashSetWithExpectedSize(
       iterations * million); 

     for (int i = 0; i < iterations; i++) { 
      for (int j = 0; j < million; j++) { 
       final String univCode = RandomStringUtils.random(7, charArr); 
       set.add(univCode); 
      } 
      System.out.println("At " + (i + 1) + " million, " + 
        "duplicates encountered till now = " + 
        (((i + 1) * million) - set.size())); 
     } 
     System.out.println("done"); 
    } 
} 

Answer 1

Questo è il paradosso del compleanno.

sqrt (27,5bn) = 165831, la formula del paradosso di compleanno per M grande è 1.177 * sqrt (M), quindi quando si generano circa 200.000 ci sarebbe una possibilità 50/50 di un problema, nel momento in cui si ottiene per un milione avresti circa 18 problemi, ecc.

Il problema del compleanno - quanti fino a quando non ci sarà probabilità che subisca una collisione - circa 200.000. http://www.wolframalpha.com/input/?i=n%3D200000,+m%3D(31%5E7),+n+-+m(1+-+((m-1)%2Fm)%5En)

Impostare n = 23,0 e m = 365 per vedere le 23 persone in una stanza equivalente. http://www.wolframalpha.com/input/?i=n%3D23.0,+m%3D365,+n+-+m(1+-+((m-1)%2Fm)%5En)

È possibile vedere quanto è vicina la simulazione alla risposta prevista per i numeri grandi.

http://www.wolframalpha.com/input/?i=n%3D30e6,+m%3D(31%5E7),+n+-+m(1+-+((m-1)%2Fm)%5En)

L'articolo Quora è buono. http://www.quora.com/How-can-I-calculate-the-expected-number-of-cache-hits.

Quindi è necessario aumentare il numero di caratteri consentiti o utilizzare una stringa più lunga. O - per usare 7 cifre, basta incrementare il contatore. OPPURE usa quelli casuali, e controlla se hai già usato prima, e resetta quando ti stanchi di cercare nuovi numeri.

Ci sono anche generatori pseudo casuali che potrebbero coprire lo spazio senza doverli colpire nuovamente. 7 caratteri non ha intenzione di rendere sicura la tua soluzione.