Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite
1

In the past I have made a function that generates an unique id (number) from a string. Today I discover that it is not as unique as should be. Never saw a problem before with it. Today two different inputs generates the same id (number).

I use the same technique in Delphi, C++, PHP and Javascript to generate the same id's so there is no difference when different languages are involved to a project. For example this can be handy to communicate, for HTML id's, tempfiles etc.

In general, what I do is calculate a CRC16 of a string, add the sum and return it.

For example, these two strings generate the same id (number):

o.uniqueId( 'M:/Mijn Muziek/Various Artists/Revs & ElBee - Tell It To My Heart.mp3' );
o.uniqueId( 'M:/Mijn Muziek/Various Artists/Dwight Yoakam - The Back Of Your Hand.Mp3');

They both generates an id of 224904.

The following example is a javascript example. My question is, how can i avoid (with a little change) that it generates a duplicate? (In case you might wonder what 'o.' means, it is the object where these functions belongs to):

o.getCrc16 = function (s, bSumPos) {
  if(typeof s !== 'string' || s.length === 0) {
    return 0;
  }
  var crc = 0xFFFF,
    L = s.length,
    sum = 0,
    x = 0,
    j = 0;
  for(var i = 0; i < L; i++) {
    j = s.charCodeAt(i);
    sum += ((i + 1) * j);
    x = ((crc >> 8) ^ j) & 0xFF;
    x ^= x >> 4;
    crc = ((crc << 8) ^ (x << 12) ^ (x << 5) ^ x) & 0xFFFF;
  }
  return crc + ((bSumPos ? 1 : 0) * sum);
}
o.uniqueId = function (s, bres) {
  if(s == undefined || typeof s != 'string') {
    if(!o.___uqidc) {
      o.___uqidc = 0;
    } else {
      ++o.___uqidc;
    }
    var od = new Date(),
      i = s = od.getTime() + '' + o.___uqidc;
  } else {
    var i = o.getCrc16(s, true);
  }
  return((bres) ? 'res:' : '') + (i + (i ? s.length : 0));
};

How can I avoid duplicates with use of a little change to the code?

Edit: It seem to be clear that I am not a Math guy ;-)

share|improve this question
If you're "hashing" long string into a short ID, you may encounter collision someday. – Passerby Mar 13 at 4:38

2 Answers

up vote 0 down vote

You should increase the number of bits created by your hash function. Assuming that your hash function approximately uniform over the space, you can mathematically derive the probability of observing a collision.

This is strongly related to the birthday paradox. In the case of CRC16, where the hash value is 17 bits (though your implementation may have a mistake; I don't see how you obtained 224094 as that is greater than 2^17), you will have a collision probability above 50% when you store more than approximately 2^8 items. In addition, CRC is not really a great hashing function because it's meant for error detection, not uniform hashing.

This table shows mathematical probabilities of collision based on hash length. For example, if you have a 128-bit hash key, you can store up to 10^31 elements before the collision probability increases beyond 10^-15. As a comparison, this probability is lower than that of your hard drive failing, or maybe your computer being zapped by lightning, so a safe number to use.

Just increase your hash length based on the number of strings you are planning to identify, and a pick a collision probability that is acceptable to you.

share|improve this answer
Okay, that is a clear answer (in some way) to me. To explain the higher CRC value, this is caused because of the multiply by the sum. Do you know a good example (source code) to get an unique id from a string? I am not a math guy anyway. – Erwinus Mar 13 at 5:05
That looks quite easy. But see some complains about it's uniqueness. Is it true? – Erwinus Mar 13 at 5:36
The accepted answer is for a 32-bit hash. But check out the other answers as well. – Andrew Mao Mar 13 at 5:38
Is that usable for a personal mp3 library of approx. 10.000 entries or more? – Erwinus Mar 13 at 6:00
show 1 more comment
up vote 0 down vote accepted

All right, did allot of testing and come to this. A relative short unique id generated by the following:

o.lz = function(i,c)
{
  if( typeof c != 'number' || c <= 0 || (typeof i != 'number' && typeof i != 'string') )
   { return i; }
  i+='';

  while( i.length < c )
   { i='0'+i; }
  return i;  
}

o.getHashCode = function(s)
{
 var hash=0,c=(typeof s == 'string')?s.length:0,i=0;
 while(i<c) 
 {
   hash = ((hash<<5)-hash)+s.charCodeAt(i++);
   //hash = hash & hash; // Convert to 32bit integer
 }

 return ( hash < 0 )?((hash*-1)+0xFFFFFFFF):hash; // convert to unsigned
}; 

o.uniqueId = function( s, bres )
{ 
  if( s == undefined || typeof s != 'string' )
  { 
     if( !o.___uqidc )
      { o.___uqidc=0; }
     else { ++o.___uqidc; } 
     var od = new Date(),
         i = s = od.getTime()+''+o.___uqidc; 
  }
  else { var i = o.getHashCode( s ); }
  return ((bres)?'res:':'')+i.toString(32)+'-'+o.lz((s.length*4).toString(16),3);  
};

Examples:

o.uniqueId( 'M:/Mijn Muziek/Various Artists/Revs & ElBee - Tell It To My Heart.mp3' );
o.uniqueId( 'M:/Mijn Muziek/Various Artists/Dwight Yoakam - The Back Of Your Hand.Mp3');

Will produce the following id's:

dh8qi9t-114
je38ugg-120

For my purpose it seems to be unique enough, also the extra length adds some more uniqueness. Test it on filesystem with approx 40.000 mp3 files and did not found any collision.

If you think this is not the way to go, please let me know.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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