根据Javascript中的字符串输入生成唯一的数字

Generate unique number based on string input in Javascript

本文关键字：唯一 数字 字符串 Javascript 根据 输入      更新时间：2023-09-26

在过去，我做了一个从字符串生成唯一id(数字)的函数。今天我发现它并不像它应该的那样独特。以前从没见过它有问题。今天两个不同的输入产生相同的id(数字)。

我在Delphi, c++， PHP和Javascript中使用相同的技术来生成相同的id，因此当不同的语言涉及到一个项目时没有差异。例如，对于HTML id, tempfile等，这可以方便地进行通信。

一般来说，我所做的是计算字符串的CRC16，添加和并返回它。

例如，这两个字符串生成相同的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');

它们都生成一个id 224904。

下面的示例是一个javascript示例。我的问题是，我怎样才能避免(有一点改变)它产生一个副本?(如果你想知道……'表示，它是这些函数所属的对象):

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

如何通过对代码进行一点更改来避免重复?

好吧，我做了很多测试，得出了这个结论。由以下内容生成的相对较短的唯一id:

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

例子:

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

将产生以下id:

dh8qi9t-114
je38ugg-120

对于我来说，它似乎是足够独特的，而且额外的长度增加了一些独特性。在大约40000个mp3文件的文件系统上测试，没有发现任何冲突。

如果你认为这是不正确的方式，请告诉我。

您应该增加哈希函数创建的位数。假设你的哈希函数在空间上近似均匀，你可以从数学上推导出观察到碰撞的概率。

这与生日悖论密切相关。在CRC16的情况下，哈希值是17位(尽管你的实现可能有一个错误;我不知道你是怎么得到224094的，因为它比2^17大，当你存储超过大约2^8个项目时，你将有超过50%的碰撞概率。此外，CRC并不是一个很好的哈希函数，因为它是用于错误检测，而不是统一哈希。

该表显示了基于哈希长度的碰撞的数学概率。例如，如果您有一个128位哈希键，那么在碰撞概率超过10^-15之前，您最多可以存储10^31个元素。作为比较，这个概率低于你的硬盘故障，或者你的电脑被闪电击中，所以使用一个安全的数字。

只需根据您计划识别的字符串数量增加哈希长度，并选择您可以接受的碰撞概率

相关文章：