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

过去，我做了一个函数，它可以从一个字符串生成唯一的id（数字）。今天我发现它并不像应该那样独特。之前从来没有看到过问题。今天两个不同的输入产生相同的id（数字）。根据Javascript中的字符串输入生成唯一编号

我在Delphi，C++，PHP和Javascript中使用相同的技术来生成相同的ID，所以当不同的语言涉及到项目时没有区别。例如，这可以方便沟通，为HTML标识，临时文件等

一般来说，我所做的是计算一个字符串的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');

它们都产生的224904.

一个id下面的例子是一个JavaScript例子。我的问题是，我如何避免（有一点改变），它会产生重复？（如果你可能想知道什么。“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)); 
};

我怎样才能避免在使用一点点改变代码的副本？

来源

2013-03-13 Codebeat

如果您将长字符串“哈希”为短ID，[您可能在某一天遇到碰撞]（http://en.wikipedia.org/wiki/Pigeonhole_principle）。 – Passerby 2013-03-13 04:38:53

好吧，做了测试分配，并来此。通过以下产生的相对短的唯一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文件的文件系统上测试它，但没有发现任何碰撞。

如果您认为这不是一条路，请告诉我。

来源

2013-04-17 21:25:46 Codebeat

你应该增加散列函数创建的位数。假设你的散列函数在空间上大致均匀，你可以用数学方法导出观察碰撞的概率。

这与birthday paradox有很大关系。对于CRC16，散列值为17位（虽然您的实现可能有错误;我不明白你是如何获得224094的，因为它大于2^17），那么当你有一个碰撞概率在50％以上时存储超过2^8个物品。另外，CRC并不是一个很好的散列函数，因为它是用于错误检测的，而不是一致的散列函数。

This table shows mathematical probabilities of collision based on hash length。例如，如果您有128位散列键，那么在冲突概率增加超过10^-15之前，最多可以存储10^31个元素。作为比较，这个概率比硬盘驱动器故障的概率要低，或者你的电脑被雷电击中，所以要使用一个安全的数字。

只需根据您计划识别的字符串数量增加散列长度，并选择一个您可以接受的冲突概率。

来源

2013-03-13 04:41:48

好的，这是一个明确的答案（以某种方式）给我。为了解释更高的CRC值，这是由于乘以总和而引起的。你知道一个很好的例子（源代码）从字符串中获取唯一的ID吗？无论如何，我不是一个数学家。 – Codebeat 2013-03-13 05:05:26

[在Javascript/jQuery中从字符串生成散列]（http://stackoverflow.com/questions/7616461/generate-a-hash-from-string-in-javascript-jquery） – 2013-03-13 05:13:59

这看起来很容易。但看到一些抱怨它的独特性。这是真的吗？ – Codebeat 2013-03-13 05:36:39

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

回答

相关问题