Probability of getting the same value using Math.random

Question

The requirement is to send a unique id to database when user click on submit button. So I am using Javascript Math.random method. I just want to know what are the chances or possibility to get same number and what bit size of using Math.random.

Answer 1

You're up against something called the birthday problem: even though there are 366 possible birthdays, when you get only 26 people in a room, the chance that some pair will have the same birthday is better than 50-50. In general, collisions are likely when your numbers approach the square root of the sample size (26 is in the neighborhood of the square root of 366).

Javascript's Math.random() has about 52 bits of randomness. Therefore, collisions should be likely as your record count approaches 2**26, which is about 60 million, a quite modest size for a database.

You should use a cryptographically-secure PRNG with at least 128 bits, preferably 256, to avoid collisions. There are probably ready-to-use UUID libraries for this available.

For an given number of keys k, and a keyspace N, the approximate odds of collision are:

1 - exp((-k * (k-1))/(2 * N))

So for k=1 million records, N=2**52, that comes to about 1 in 9000, if I did the math right. That's further assuming that Javascript's Math.random() is truly using the fill 52 bits of randomness available to it...that too is an assumption I wouldn't make.

Answer 2

Don't do it. Trusting (multiple) clients to come up with unique values is not going to work.

Even if each client is guaranteed to generate unique values, you could have two clients generate the same value. Since most pseudo-random number generators are seeded with the current time, that becomes more likely as you get more users.

If you're creating database records, your database should provide some functionality like this. Most or all SQL databases have an auto-increment concept, and many NoSQL databases have an equivalent (Mongo certainly does for IDs). Allowing the database to handle this can be good for performance (it can set up indexes and allocate space to handle the IDs well) and the DB has the final say on the data, so it can guarantee that IDs are unique.

Failing that, you can have your server-side generated some unique identifier (like a UUID) and use that. Having the server do it and using a known-good algorithm, like a type 4 UUID, guarantees sufficient randomness that conflicts should never occur. Note that using UUIDs, unless your database has a type for them, will have very different index performance than sequential IDs.