Тест на столкновение с уникальным номером Java не исчерпывается

Question

У меня есть системное требование для генерации строки из 11 символов, где должно быть уникально 8 самых правых символов.

Теперь из моего понимания, самое большее это происходит несколько сотен раз в день. Из-за проблем с скоростью меня попросили не использовать DB, чтобы просто получить nextval() в последовательности, к сожалению.

Итак, я остался, чтобы проверить различные способы генерации случайного числа как можно лучше, и я придумал решение, основанное на классе SecureRandom.

Я решил проверить его, чтобы увидеть, насколько вероятно, что сгенерированная строка повторится сама; Я тестировал с помощью HashMap (строка, строка) для 10 миллионов поколений - отлично смотрел и надеялся протестировать ночь на миллиард случайных строк, но это произошло из-за исключения в потоке «main» java.lang.OutOfMemoryError: Java куча пространство

тест код, который я до сих пор это:

public class Main { 
public static BigInteger BASE = BigInteger.valueOf(62); 
public static final String DIGITS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 

public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    long lStartTime = System.nanoTime(); 
    HashMap<String, String> orders = new HashMap<String, String>(); 

    for (int i = 0; i < 960000000; i++) { 
     SecureRandom randObj = new SecureRandom(); 
     BigInteger BigRand = new BigInteger(128, randObj); 
     String rand = BigRand.toString(62); 

     StringBuilder result = new StringBuilder(); 
     while (BigRand.compareTo(BigInteger.ZERO) == 1 && result.length()<11) { // number > 0 
       BigInteger[] divmod = BigRand.divideAndRemainder(BASE); 
       BigRand = divmod[0]; 
       int digit = divmod[1].intValue(); 
       result.insert(0, DIGITS.charAt(digit)); 
      } 
     String doesKeyExistString = orders.get(result); 
     if (doesKeyExistString != null) { 
      System.out.print("Duplicate key found!: "+result.toString()+"\n"); 
     } else { 
      orders.put(result.toString(), result.toString()); // No such key 
     } 
    } 
    long lEndTime = System.nanoTime(); 
    long difference1 = lEndTime - lStartTime; 
    double difference = (double)difference1/1000000000; 
    System.out.println("Elapsed seconds: " + difference); 
    System.out.println("Elapsed exact: " + difference1); 

} 

есть ли у вас какой-либо предложения, как доказать, что мы можем полагаться на этом методе генерации случайных чисел, с вероятностью получения тех же строк вдвое меньше?

я наткнулся на этот вопрос: random number generator test Ответ выглядит интересно, но я не совсем понимаю, как применить это к моему делу (статистика была моя трудная, конечно, я едва прошел его вторую попытку ...)

Я также не уверен, как настроить этот генератор случайных чисел, чтобы динамически установить длину генерируемого числа .. там должен быть лучший способ сделать это, чем то, что я здесь ...

Спасибо!

Answer 1

Вы пытались использовать UUID (Universally Unique Identifier) в JAVA.

UUID idOne = UUID.randomUUID(); 
System.out.println(idOne.toString()); 

Answer 2

Рассматривали ли вы последовательные номера? Начиная с 000000000? Тогда вам нужно запомнить только последний номер, который вы выделили.

Трудно волноваться об этом как о проблеме с производительностью, когда это происходит только несколько сотен раз в день. Это только 41 в час в 24 часа раз 999 операций.

Answer 3

Вы получаете ошибку «из памяти», потому что у вас заканчивается память.

Текст говорит, что вы запускаете 10 миллионов проб, но код пытается запустить 960 миллионов (for (int i = 0; i < 960000000; i++) {).

Уменьшите размер этого цикла или увеличьте объем памяти, доступный программе (например, с помощью java-командной строки).

Если вы не можете выделить память и действительно нуждаетесь в такой массивной пробной версии, прикрепите таблицу базы данных или другое внешнее хранилище.

Answer 4

Давайте посмотрим на необработанные цифры здесь.

Вы пытаетесь сохранить один миллиард 11 символов длинных строк в HashMap.

Если посчитать абсолютно минимальное пространство для этого (11 символьного массива + INT для длины), что дает нам:

1e9 * (11 * 2 bytes + 4 bytes) = 26e9 bytes 

или около 24 гигабайтов. Это то, сколько памяти требуется вашему решению.

Если мы посмотрим на другую сторону уравнения. Вы произвольно генерируете две равные строки длиной 8 с использованием 62-символьного алфавита. Это означает, что у вас есть

62^8 = 218340105584896 

или около 2.18e14 различных комбинаций. Глядя на birthday problem, мы можем рассчитать количество строк, которые нам нужно сгенерировать, чтобы иметь вероятность не менее 50% сгенерировать одну и ту же строку дважды. По формуле это число составляет около 1.74e7 раз. Поэтому, если вы создаете 18 миллионов строк, вероятность того, что вы сгенерировали одну и ту же строку, составляет более 50%.

18000000 строки требуются только

1.8e7 * (11 * 2 bytes + 4 bytes) = 4.68e8 bytes 

или около 470 мегабайтов, которые должны быть в пределах ваших ограничений.

Теперь, что касается вашей фактической проблемы, используйте, по возможности, random UUID, так как вы можете полагаться на возможность генерации одного и того же UUID дважды, для всех практических целей, неэксентирующ.

Если вы не можете использовать UUID, но должны использовать эти 8 символов, я предлагаю вам немного расширить свой алфавит. Используя все печатные символы ASCII (95 символов), вы увеличиваете количество возможных комбинаций чуть меньше 6.1e15, хотя количество поколений для 50% вероятности столкновения увеличивается только до 90 миллионов.