random key generator

zzz

I've been using a function that I've found that generates a random alpha key. It worked fine so far, until yesterday when it created a duplicate, which is no good. The function is below.

Why did it generate the duplicate?
What is the likelihood of this repeat again and
what modifications can be made to avoid it in the future?

function generator($lenght=5)
{
     for($i = 0; $i < $lenght; $i++)
     {
          $uniqueKey .= chr(rand(97,122));
     }
     return $uniqueKey;
}

$randomKey = generator();

laserlight

zzz wrote:
Why did it generate the duplicate?

That is like asking: I tossed a fair coin twice. Why did heads come up on both times?

zzz wrote:
What is the likelihood of this repeat again

The likelihood of this particular key being duplicated again is small: 1/(26^5), assuming the default length. The probability that you would get repeat of this unpleasant encounter is just going to get higher as you generate more keys. In fact, after about sqrt(26⁵⁾ keys (i.e., about 3400 to 3500 keys), it becomes likely that you will get duplicates (search the Web for birthday attack).

zzz wrote:
what modifications can be made to avoid it in the future?

To be absolutely sure that duplicates will not happen, you should record every key generated. When a new key is generated, check if it is a duplicate. If so, generate and repeat, otherwise add it to the records and use it. If it is infeasible to do this, then you have to increase the length of the key, increase the character set that it can consist of, and then keep your fingers crossed.

johanafm

You generate a string of 5 characters, where each character has a value between 97 and 122 inclusive.
As such, there are 122 - 97 + 1 = 26 possibilities per character.
And there are 26⁵ = 11 881 376 combinations in total

If you have generated N strings so far, the chance that the next generated string will be a duplicate is N / 11 881 376.

If it's important that you get no duplicates, it doesn't matter how unlikely it is for it to happen. Even if the chance of this happening is one in a billion, you could still get ten duplicates on the first couple of runs. It's not impossible, just unlikely.

You need to store all previously generated keys and then make sure the newly created key is not among those.

function generator($lenght=5) {
	$keys = somehowReadStoredKeys();
	// if $keys is not sorted, you should definitely
	array_sort($keys);
	$generate = true;

while ($generate) {
	$uniqueKey = '';
	for($i = 0; $i < $lenght; $i++) {
		$uniqueKey .= chr(rand(97,122));
	}
	if (array_search($uniqueKey, $keys) === false)
		$generate = false;
}

return $uniqueKey;
}

Do note that this approach won't be acceptable if the number of previously generated keys are significant compared to the number of possible keys. When half the keys have been used, the above while loop would have to run twice for every other generated key (on average). When all the keys have been used, it would run an extra round every time (which means it would loop infinitely).

zzz

Yes, the keys are stored. So far I've had about 6K of them but this is a good wake-up call for me. What I'll do is run the script, generate ID, query db for such value and if not found -- use it, if it is found, call the function again and repeat the steps.

Thanks for confirming my thought trend.

NogDog

Of course, there's a possibility, especially as more values get used, that you could get a sequence of several duplicates while trying to generate one of these, resulting in several database queries.

Kudose

I have yet to come across a duplicate when using the MySQL equivalent to UUID()

/**
   *  uuid
   *
   *  uuid() simply replicates MySQL's UUID function, which returns a 36
   *  character "random" hash (32 alphanumeric, 4 dashes).
   *  @return string
   */
  function uuid(){
    return sprintf('&#37;04x%04x-%04x-%04x-%04x-%04x%04x%04x',
      mt_rand(0, 0xffff), mt_rand(0, 0xffff), mt_rand(0, 0xffff),
      mt_rand(0, 0x0fff) | 0x4000,
      mt_rand(0, 0x3fff) | 0x8000,
      mt_rand(0, 0xffff), mt_rand(0, 0xffff), mt_rand(0, 0xffff));
  }

Laserlight and I have discussed this before and there is always a chance of getting a duplicate ... but using UUID(), there are more combinations than known stars in the universe.

zzz

I need a human readable key, with specified str length. What would the key look like in your code example?

zzz

OK, I'm working myself into a loop...

Here are the steps I need to accomplish:

Generate key
Check if the key exists
if YES -- repeat step 1 and 2
if NO -- use the key

Here's how I generate the key:

function generator($lenght=5)
{
     for($i = 0; $i < $lenght; $i++)
     {
          $uniqueKey .= chr(rand(97,122));
     }
     return $uniqueKey;
}

$randomKey = generator();

Here's how I check if the key is stored in db:

if ($randomKey == $db->get_var(“SELECT key FROM t1 WHERE key = '".$randomKey."' ") )
{
	// found match	-- re-generate key		
} else {
	// did not find match -- use key	
}

Need help putting it together without writing endless loops...

dagon

testkey($key){
if ($randomKey == $db->get_var(&#8220;SELECT key FROM t1 WHERE key = '".$randomKey."' ") )
{
  $randomKey = generator(); 
testkey($randomKey);
} else {

// did not find match -- use key    
}
}

zzz

Dah... coffee. i need more coffee.

Kudose

zzz;10936308 wrote:
I need a human readable key, with specified str length. What would the key look like in your code example?

4386bff0-e5fb-11de-8a39-0800200c9a66 see http://dev.mysql.com/doc/refman/5.0/en/miscellaneous-functions.html#function_uuid

dagon

the problem is he wanted one 5 chars long.

i use md5() on either mysql's UUID() or php's uniqid

but if you want a human to use it, it's not very friendly.

johanafm

And the problem is not circumventable with 5 characters. I do not know how many keys he has, or expect to have. But with a 5 character key, collisions will start to become somewhat frequent at about 3500 existing keys; see Laserlight's post above.
Moving up to an 8 character key, this threshold is moved up to about 450000 keys. A decent improvement.

Kudose

dagon;10936324 wrote:
the problem is he wanted one 5 chars long.

i use md5() on either mysql's UUID() or php's uniqid

but if you want a human to use it, it's not very friendly.

Granted the OP's default value for his function is 5 characters, I didn't see anywhere where the OP stated it had to be 5 characters, so I suggested UUID.

If you are going to have a substantial amount of users, you are not going to want a 5 or 8 character key for them. Just imagine you are the one in a million chance that your site gets as popular as Facebook is or MySpace was. I highly doubt the numbers 5 or 8 entered their mind for a user key.

But ... to each his own.

dagon

Kudose;10936408 wrote:
Granted the OP's default value for his function is 5 characters, I didn't see anywhere where the OP stated it had to be 5 characters, so I suggested UUID.

If you are going to have a substantial amount of users, you are not going to want a 5 or 8 character key for them. Just imagine you are the one in a million chance that your site gets as popular as Facebook is or MySpace was. I highly doubt the numbers 5 or 8 entered their mind for a user key.

But ... to each his own.

agreed, but he said 'human readable' so the assumption i was working with was 5 would be the default, or at least to few characters to use uuid. Humans are so annoying!

zzz

The key is a part of a unique URL. It has to be short because users often write that URL down. And yes, humans can be difficult sometimes.

zzz

I have a new case where I could use long unique IDs for naming images. I gave it a whirl and although the images are processed correctly and values stored in DB OK, I can't seem to be able to access images online with such name. Are there naming conventions that prevent such naming for images?

Kudose;10934541 wrote:
I have yet to come across a duplicate when using the MySQL equivalent to UUID()
/**
   *  uuid
   *
   *  uuid() simply replicates MySQL's UUID function, which returns a 36
   *  character "random" hash (32 alphanumeric, 4 dashes).
   *  @return string
   */
  function uuid(){
    return sprintf('%04x%04x-%04x-%04x-%04x-%04x%04x%04x',
      mt_rand(0, 0xffff), mt_rand(0, 0xffff), mt_rand(0, 0xffff),
      mt_rand(0, 0x0fff) | 0x4000,
      mt_rand(0, 0x3fff) | 0x8000,
      mt_rand(0, 0xffff), mt_rand(0, 0xffff), mt_rand(0, 0xffff));
  }
Laserlight and I have discussed this before and there is always a chance of getting a duplicate ... but using UUID(), there are more combinations than known stars in the universe.

Kudose

I cannot think of a reason an image named XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX.jpg would not load.

What happens when you try to access the image address directly?

bradgrafelman

If the entire URI is less than 255 or so characters, then no, the length won't be a problem.