2
$\begingroup$

I'm aiming to create UUIDs, for a project I'm working on.

The standard UUID generators create a very long strings. I'm only anticipating a maximum of 10 million uses and because I'm storing that many potential uuids and other information in-memory, I want to cut it down a bit.

What is the shortest string length containing a-z, A-Z and 0-9 that is good for 10 million unique uuids? If I shorten the string like this, will I also increase the chance of repeats or are the chances of repeats still fairly astronomical?

$\endgroup$
  • $\begingroup$ Since there are $62$ allowed characters, there will be $62^L$ strings of length $L$. Thus you are looking for $L$ such that $62^L = 10^7$ or equivalently $L = \log_{62}(10^7) \approx 3.9$. Thus the ideal string length would be $4$ characters. $\endgroup$ – Abel Jun 13 '13 at 8:50
  • 1
    $\begingroup$ permutation doesn't mean what you might think it means. A permutation is a rearrangement of some objects, like for example the characters in a string. In general, $n$ distinguishable objects can be arranged in $n!$ ways. However, a string over some alphabet isn't in general a permutation of the alphabet, since it may include some letters more than once and others not at all. $\endgroup$ – fgp Jun 13 '13 at 9:00
1
$\begingroup$

In the previous answer, only the probability of a new collision is considered. What matters is the probability of there being any collision in ten million randomly chosen UUIDs. This is related to the birthday problem.

From the table in this article, you can see that if you have about six million 64-bit UUIDs, then the probability of there being a collision is about $10^{-6}$, which I'd expect might be the correct order of magnitude to avoid all problems.

Given a 62-character alphabet, a 64-bit UUID requires eleven characters since $$ \frac{\log2^{64}}{\log62}\;\approx\;10.75. $$ The article also gives a simple approximation which can be rearranged to give the formula $m=n^2/2p$ for the required number of UUIDs, where $n$ is the maximum number of users ($10^7$ for you) and $p$ is the acceptable chance of a collision.

So, for example, if you're happy with a $10^{-3}$ (0.1%) chance of failure, then you need approximately $5\times10^{16}$ UUIDs which still requires ten characters.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is a better answer. $\endgroup$ – parsiad Jun 16 '13 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.