random generated strings, possible to be equals?

given a script that generates a string of 12 characters randomly generated, how many possibilities there are for two string t开发者_运维问答o be equal?

function rand_string( $length ) {
    $chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";  

    $size = strlen( $chars );
    for( $i = 0; $i < $length; $i++ ) {
        $str .= $chars[ rand( 0, $size - 1 ) ];
    }

    return $str;
}

---

Assuming, A-Za-z0-9, there are 62 possible character values. Therefore, there are 62^12 (to-the-power-of) possible strings. That's roughly 3x10^21 (3 with 21 zeros).

Assuming a perfect random number generator, that's a 1 in 3x10^21 chance that any two particular strings will be equal.

---

Given that code and a length of 12, there are 62¹² possible values. So (assuming a perfectly uniform random number generator, which rand() probably isn't) the chances are 1 in 3226266762397899821056 that a single call to that function will return any arbitrary 12-character string.

OTOH, if you are calling the function repeatedly and want to know how long until you are likely to get a repeat of any previously returned value, you would have to call it about 6.7e+10 times to have a 50% chance of a collision (again, assuming a uniform random number generator). You can get a reasonable approximation of the number of calls required for any collision probability p between 0 and 1 by calculating sqrt(-ln(1 - p) * 2 * 6212).

---

This falls under the Birth Paradox (how many people do you need in a room to have a 50% chance of two or more people having the same birthday).

Your 12-long 62-char strings come out to be about 72 bits. With the approximate detailed here, you can expect to generate about SQRT((pi / 2) * 62^12)) = 7.112x10^10 strings before getting a collision. So about 1 in 70 billion.