基于JavaScript中的字符串输入生成唯一数字

Question

基于JavaScript中的字符串输入生成唯一数字

javascriptstringnumbersunique

6

过去我曾经编写了一个从字符串生成唯一id（数字）的函数。今天我发现它不如想象中那么唯一。以前用它从未出现过问题，但今天两个不同的输入产生了相同的id（数字）。

我在 Delphi、C++、PHP 和 Javascript 中使用相同的技术来生成相同的 id，因此在涉及到不同语言的项目中没有区别。例如，这对于通信、HTML id、临时文件等非常方便。

总体上，我的做法是计算字符串的CRC16，加上总和并返回它。

例如，这两个字符串将生成相同的id（数字）：

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示例。我的问题是，如何在稍加更改的情况下避免生成重复的id？（如果您想知道'o.'意味着什么，它是这些函数所属对象）：

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

如何通过对代码进行小改动来避免重复？

- Codebeat

如果你将长字符串“哈希”成短ID，你可能会在某一天遇到冲突。 - Passerby

2个回答

0

你应该增加哈希函数创建的位数。假设你的哈希函数在空间上大致均匀分布，你可以通过数学推导出观察到碰撞的概率。

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

此表显示基于哈希长度的碰撞数学概率。例如，如果你有一个128位的哈希键，你可以存储多达10^31个元素，然后碰撞概率才会超过10^-15。相比之下，这个概率比你的硬盘故障或者电脑被闪电击中的概率还要低，所以这是一个安全的数字。

根据您计划识别的字符串数量增加哈希长度，选择一个对您可接受的碰撞概率。

- Andrew Mao

好的，这对我来说是一个清晰的答案（在某种程度上）。为了解释更高的CRC值，这是由于乘以总和所引起的。你知道一个从字符串获取唯一ID的好例子（源代码）吗？反正我不是数学家。 - Codebeat

在Javascript/jQuery中从字符串生成哈希 - Andrew Mao

1

看起来很简单。但是有一些关于它的独特性的抱怨。这是真的吗？ - Codebeat

接受的答案是针对32位哈希的。但也请查看其他答案。 - Andrew Mao

这对于大约10,000个条目的个人mp3库是否可用？ - Codebeat

我之所以问这个问题，是因为我不知道像DivShare这样的文件共享服务如何可以使用如'726721-2d6'这样短的文件ID。他们有2793106个用户。这怎么可能？ - Codebeat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Codebeat · Accepted Answer

好的，我进行了大量测试并得出以下结论。通过以下方法生成一个相对较短的唯一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

对于我的目的来说，它似乎足够独特，而额外的长度增加了一些独特性。在大约40,000个mp3文件的文件系统上进行测试，并没有发现任何碰撞。

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