Probability of collision of SecureRandom.urlsafe_base64(8) in Ruby?

Question

I am using `SecureRandom.urlsafe_base64(8)` in order to create unique ids in my system that are URL safe. I would like to know how to calculate the probability of collision? I am inserting about 10.000 of those ids into an array, and I want to avoid checking if one of the keys is already in the array, but I also want to make sure that are not repeated? What are the chances?

Accepted Answer

There is a good approximation of this probability (which relates to the birthday problem). If there are `k` potential values and `n` are sampled, the probability of collision is:

```
k! / (k^n * (k - n)!)
```

The base64 method returns a base 64 string built from the inputted number of random bytes, not that number of random digits. Eight random bytes gives us `k = 256^8`, about `1.8446744e+19`. You are generating 10,000 of these strings, so `n = 10,000`, which gives us a probability of `2.710498492319857e-12`, which is very low.

Probability of collision of SecureRandom.urlsafe_base64(8) in Ruby?

Solution

Problem