Probability of getting the same value using Math.random

Question

The requirement is to send a unique identifier to the database when the user clicks the submit button. Therefore, I use the Javascript Math.random method. I just want to know what are the odds or the opportunity to get the same number and size of bits using Math.random .

Answer 1

You are faced with a problem called a birthday: even if there are 366 possible birthdays, when you get only 26 people in the room, the likelihood that some couple will have the same birthday will be better than 50-50. In the general case, collisions are likely when your numbers approach the square root of the sample size (26 is in the vicinity of the square root of 366).

Javascript Math.random () has about 52 bits of randomness. Therefore, collisions should be probable, as the number of your records is approaching 2 ** 26, which is about 60 million, and this is a rather modest size for the database.

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

For a given number of keys k and key space N, approximate collision factors:

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

So, for k = 1 million entries, N = 2 ** 52, which is about 1 in 9000 if I did the math correctly. This also assumes that Javascript Math.random () does indeed use the fill of 52 bits of randomness available to it ... this is also an assumption I would not make.

Answer 2

Do not do this. Trusted (multiple) clients to come up with unique values ​​will not work.

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

If you create database records, your database should provide functionality such as this. Most or all SQL databases have the concept of automatic growth, and many NoSQL databases have an equivalent (Mongo, of course, for identifiers). Allowing the processing of this database can be useful for performance (it can tune indexes and allocate space for the correct processing of identifiers), and the database has the last word in the data, so it can guarantee the uniqueness of identifiers.

Otherwise, you can create a unique identifier on your server (for example, UUID) and use it. Having a server and using a well-known algorithm, such as a UUID of type 4, guarantees sufficient chance that conflicts should never occur. Note that using UUIDs, if your database does not have a type for them, will have very different index performance than consecutive identifiers.

Answer 3

If you support the client side hash function, use crypto.getRandomValues ​​()

Here is an example implementation:

 const randomHash = function () { let array = new Uint32Array(1); let hash = window.crypto.getRandomValues(array); if (myExistingIds.includes(hash[0])) { randomHash(); } else { myExistingIds.push(hash[0]); } } 

This function will recursively reject the generated hashes until it finds one that is not already in your collection of identifiers, which should take only a few iterations - and most likely, only one.

Answer 4

I would prefer my own random number generated using the timestamp identifier, client or user.

Answer 5

In my browser (some version of Chrome) every call to Math.random returns a decimal digit with 17 decimal precision points.

This means that the probability that the two Math.random values ​​will be the same is

 ((1/10)(1/10))^17 

Or 0.0000000000000000000000000000000001 (34 zero).

However, this is a customer-specific feature.

If someone wanted to, they could change the function to return the same value every time or whatever, so I would not use Math.random to pass a unique identifier to the database.

Instead, I would recommend looking at this front_stack question , this jsFiddle UUID generation, or create your own server side random number generator and pass it a JavaScript seed or something that guarantees randomness and security.