Ensuring No Random Sequence Is Repeated Indefinitely

Question

I'm attempting to generate a random string of length X. I want to ensure that no two sequences are ever identically produced, even if this code is being run on multiple machines and at the same time.

"list" is the list of characters I'm using, "min" and "max" are the range of indexes, and "length" is the desired length of the String.

Currently, I am using System.nanoTime() as the seed for the Random object. While I realize it is likely improbable for 2 machines to run at the exact same time down to the nano second and produce the same output, I want to make this a foolproof solution.

How can I increase the randomness of this code so that no 2 strings will ever be the same without increasing the length of the string or increasing the number of characters available to be included in the string?

String seq = "";
for (int i = 0; i < length; i++)
    {
      Random rnd = new Random();
      rnd.setSeed(System.nanoTime());
      int randomNum = rnd.nextInt((max - min) + 1) + min;
      seq = seq + list[randomNum];
    }

return seq;

What will the random strings be used for? If they will further information security in any way (e.g., they serve as random nonces, passwords, or encryption keys), then only a cryptographic RNG is appropriate (such as `java.security.SecureRandom`). Answering this question could clarify why you need each machine to generate its own "unique" random string (which is impossible in principle without a uniqueness check with a central database) rather than using a centralized database in which "unique" strings are stored. — Peter O., Aug 30 '19 at 01:25
Maybe your goal is that each string should merely be _unique_ (rather than unique _and random_); in which case just use sequentially assigned numbers rather than "unique" strings. — Peter O., Aug 30 '19 at 01:25

score 3 · Accepted Answer · answered Aug 29 '19 at 19:31

This is not possible in principle: if you generate a String with length n of k different characters there are exactly k^n possible Strings. Once you generated as much Strings, repetitions will occur, in practice much earlier.

When running on a single machine, you might remember generated Strings and only output new ones, but on two machines without synchronization even this will not be possible.

Furthermore, taking system nanos into account will not help, since the same Strings might occur in different positions of the generated sequences.

But if you are asking that the sequence of the generated Strings must differ for two machines, your solution is probably fine, but ...

there might be a correlation between the boot times of the involved machines which can in turn increase the chance of a collision of System.nanoTime().
As the Javadoc for System.nanoTime() says, the accuracy of the returned long might be worse than the precision, i.e. not every possible long value might be returned actually.

BTW, new Random()would have the same effect as your code, since System.nanoTime() is used internally for seeding in this case.

Would I possibly have more success with System.currentTimeMillis()? I wanted to go as small as possible to provide as much variation between the seeds as possible but if it can't hit every value due to precision I'm wondering if milliseconds could be better for precision — Slenderbowman, Aug 30 '19 at 00:25
`System.currentTimeMillis()` has the same shortcomings as `System.nanoTime()` — Mark Schäfer, Aug 30 '19 at 06:56

score 2 · Answer 2 · answered Aug 29 '19 at 19:34

2

You could use SecureRandom or the built-in UUID system.

The UUID library generates unique random strings for you. (see https://docs.oracle.com/javase/7/docs/api/java/util/UUID.html)

Using UUIDs:

import java.util.UUID;

public class GetRandString {
    public static void main(String[] args) {
        UUID uuid = UUID.randomUUID();
        String randString = uuid.toString();

        System.out.println("Random string: " + randString);
    }
}

You second option is SecureRandom (https://docs.oracle.com/javase/8/docs/api/java/security/SecureRandom.html).

Another stackoverflow question answers how to generate a SecureRandom string: How to generate a SecureRandom string of length n in Java?

answered Aug 29 '19 at 19:34

Rotartsi

527
5
19

A UUID is not *guaranteed* to be unique, it is only highly probable – Hans Keﬆing Aug 29 '19 at 19:50
To add to what @HansKeﬆing said, the sequence I'm looking for has a length shorter than a standard UUID, making this harder – Slenderbowman Aug 29 '19 at 23:13
Do you require the string to be constructed from a specific alphabet? because otherwise you could simply splice it with `string.substring()` – Rotartsi Aug 29 '19 at 23:32
UUId is alphanumeric right? I am also looking for alphanumeric but doesn't doesn't just taking X digits of it limit me to the 36^X problem mentioned above (10 digits and 26 letters)? – Slenderbowman Aug 30 '19 at 00:21

Ensuring No Random Sequence Is Repeated Indefinitely

2 Answers2