Generer unik nummer basert på strenginngang i Javascript

Tidligere har jeg laget en funksjon som genererer en unik ID (nummer) fra en streng. I dag oppdaget jeg at den ikke er så unik som den burde være. Har aldri sett et problem med den før. I dag genererer to forskjellige input samme ID (nummer).

Jeg bruker den samme teknikken i Delphi, C++, PHP og Javascript for å generere de samme ID-ene, slik at det ikke er noen forskjell når forskjellige språk er involvert i et prosjekt. For eksempel kan dette være nyttig for kommunikasjon, for HTML-id'er, midlertidige filer osv.

Generelt gjør jeg det jeg gjør, å beregne en CRC16 av en streng, legge til summen og returnere den.

For eksempel genererer disse to strengene samme id (nummer):

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');

De genererer begge en ID på 224904.

Følgende eksempel er et JavaScript-eksempel. Mitt spørsmål er, hvordan kan jeg unngå (med en liten endring) at det genererer en duplikat? (I tilfelle du lurer på hva 'o.' betyr, er det objektet som disse funksjonene tilhører):

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));
};

Hvordan kan jeg unngå duplikater ved å gjøre en liten endring i koden?

Svar #1

Greit, gjorde mye testing og kom fram til dette. En relativt kort unik ID generert av følgende:

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);  
};

Eksempler :

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');

Vil produsere følgende ID-er:

dh8qi9t-114
je38ugg-120

For mitt formål ser det ut til å være unikt nok, også den ekstra lengden gir litt mer unikhet. Testet det på filsystemet med omtrent 40.000 mp3-filer og fant ingen kollisjon.

Hvis du tror dette ikke er veien å gå, vennligst gi meg beskjed.

Svar #2

Du bør øke antallet biter som genereres av hash-funksjonen din. Hvis vi antar at hash-funksjonen din er tilnærmet jevn over rommet, kan du matematisk utlede sannsynligheten for å observere en kollisjon.

Dette er sterkt relatert til bursdagsparadokset. I tilfelle CRC16, der hash-verdien er 17 biter (selv om implementeringen din kan ha en feil; jeg ser ikke hvordan du fikk 224094 siden det er større enn 2^17), vil du ha en kollisjons-sannsynlighet på over 50 % når du lagrer mer enn omtrent 2^8 elementer. I tillegg er ikke CRC egentlig en god hash-funksjon fordi den er ment for feildeteksjon, ikke for jevn hashing.

Denne tabellen viser matematiske sannsynligheter for kollisjon basert på hash-lengde. For eksempel, hvis du har en 128-bits hash-nøkkel, kan du lagre opptil 10^31 elementer før kollisjons-sannsynligheten øker utover 10^-15. Til sammenligning er denne sannsynligheten lavere enn at harddisken din feiler, eller kanskje at datamaskinen din blir truffet av lyn, så det er et trygt antall å bruke.

Bare øk hash-lengden din basert på antall strenger du planlegger å identifisere, og velg en kollisjons-sannsynlighet som er akseptabel for deg.