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?

Answer 1

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.