根據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中的字符串輸入生成唯一編號

回答

相關問題