在 JavaScript 中创建 GUID / UUID?

我正在尝试在 JavaScript 中创建全局唯一标识符。我不确定所有浏览器上都提供哪些例程,内置随机数生成器的 “随机性” 和种子状态如何,等等。

GUID / UUID 至少应包含 32 个字符,并且应保持在 ASCII 范围内,以免在传递它们时遇到麻烦。

答案

对于符合RFC4122版本 4 的解决方案,此一站式解决方案是我能想到的最紧凑的解决方案:

function uuidv4() {
  return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
    var r = Math.random() * 16 | 0, v = c == 'x' ? r : (r & 0x3 | 0x8);
    return v.toString(16);
  });
}

console.log(uuidv4());

更新,2015-06-02 :请注意,UUID 的唯一性很大程度上取决于基础随机数生成器(RNG)。上面的解决方案为简洁起见使用Math.random() ,但是不能保证Math.random()是高质量的 RNG。有关详细信息,请参见 Adam Hyland 在 Math.random()上出色文章 。对于更强大的解决方案,请考虑使用 uuid 模块 (免责声明:我是作者)之类东西, 该模块在可用时使用更高质量的 RNG API。

更新,2015-08-26 :作为旁注,本要点描述了如何确定在达到一定的碰撞概率之前可以生成多少个 ID。例如,使用 3.26x10 15版本 4 RFC4122 UUID,您有百万分之一的碰撞机会。

更新,2017-06-28Chrome 开发人员的一篇好文章,讨论了 Chrome,Firefox 和 Safari 中 Math.random PRNG 的质量状态。 tl; dr - 截至 2015 年末,它的 “相当好”,但没有加密质量。为了解决该问题,这是上述解决方案的更新版本,该解决方案使用 ES6, crypto API 和一些 JS 向导,我对此不以为然

function uuidv4() {
  return ([1e7]+-1e3+-4e3+-8e3+-1e11).replace(/[018]/g, c =>
    (c ^ crypto.getRandomValues(new Uint8Array(1))[0] & 15 >> c / 4).toString(16)
  );
}

console.log(uuidv4());

根据RFC 4122 ,UUID(通用唯一 IDentifier)也称为 GUID(全局唯一 IDentifier)是具有一定唯一性保证的标识符。

生成它们的最好方法是遵循上述 RFC 中的实现说明,使用许多社区审核的开源实现之一。

node-uuid是一种流行的用于在 JavaScript 中使用 UUID 的开源工具。

请注意,仅随机生成标识符(逐字节或逐字符)将不会为您提供与一致实现相同的保证。同样,非常重要的是,使用兼容 UUID 的系统可能会选择不接受随机生成的 UUID,并且许多开源验证程序实际上会检查有效结构。

UUID 必须具有以下格式:

xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

其中MN位置可能只有某些值。此时,M 的唯一有效值为 1、2、3、4 和 5,因此随机生成该位置将使大多数结果不可接受。

我真的很喜欢Broofa 的回答有多干净,但是不幸的是Math.random糟糕实现留下了碰撞的机会。

这是一个类似的符合RFC4122版本 4 的解决方案,它通过将时间戳记的十六进制部分偏移前 13 个十六进制数,并从页面加载以来一次偏移了微秒的十六进制部分来解决该问题。这样,即使Math.random处于同一种子上,两个客户端也必须生成自页面加载以来完全相同的微秒数(如果支持高性能时间)并且以完全相同的毫秒数(或 10,000 + 年)生成 UUID 稍后)以获取相同的 UUID:

function generateUUID() { // Public Domain/MIT
    var d = new Date().getTime();//Timestamp
    var d2 = (performance && performance.now && (performance.now()*1000)) || 0;//Time in microseconds since page-load or 0 if unsupported
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
        var r = Math.random() * 16;//random number between 0 and 16
        if(d > 0){//Use timestamp until depleted
            r = (d + r)%16 | 0;
            d = Math.floor(d/16);
        } else {//Use microseconds since page-load if supported
            r = (d2 + r)%16 | 0;
            d2 = Math.floor(d2/16);
        }
        return (c === 'x' ? r : (r & 0x3 | 0x8)).toString(16);
    });
}

console.log(generateUUID())


这是要测试的小提琴。

broofa 的答案确实很巧妙 - 确实非常聪明,确实... 符合 rfc4122 的要求,具有一定的可读性和紧凑性。太棒了!

但是,如果您正在查看该正则表达式,那么多的replace()回调, toString()Math.random()函数调用(其中他仅使用结果的 4 位,而浪费了其余部分),则可以开始想知道性能。确实,joelpt 甚至决定通过generateQuickGUID放弃 RFC 以获得通用 GUID 速度。

但是,我们可以获得速度 RFC 合规性吗?我说是!我们可以保持可读性吗?好吧... 并非如此,但是如果您继续这样做很容易。

但是首先,与 broofa, guid (公认的答案)和不符合 rfc 的generateQuickGuid相比,我的结果generateQuickGuid

Desktop   Android
           broofa: 1617ms   12869ms
               e1:  636ms    5778ms
               e2:  606ms    4754ms
               e3:  364ms    3003ms
               e4:  329ms    2015ms
               e5:  147ms    1156ms
               e6:  146ms    1035ms
               e7:  105ms     726ms
             guid:  962ms   10762ms
generateQuickGuid:  292ms    2961ms
  - Note: 500k iterations, results will vary by browser/cpu.

所以,我的优化迭代 6 日,我超过12 倍 ,超过9X接受的答案,以及2-3X不符合要求快速回答击败最流行的答案。而且我仍然兼容 rfc4122。

有兴趣如何?我将完整的源代码放在http://jsfiddle.net/jcward/7hyaC/3/http://jsperf.com/uuid-generator-opt/4 上

作为解释,让我们从 broofa 的代码开始:

function broofa() {
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
        var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
        return v.toString(16);
    });
}

console.log(broofa())

因此,它将x替换为任意随机的十六进制数字,将y替换为随机数据(根据 RFC 规范将前 2 位强制为10 ),并且正则表达式与-4字符不匹配,因此他不必处理跟他们。非常非常光滑

首先要知道的是,函数调用和正则表达式一样昂贵(尽管他仅使用 1,但它具有 32 个回调,每个匹配项一个,在 32 个回调中的每个回调中,它调用 Math.random()和 v。 toString(16))。

迈向性能的第一步是消除 RegEx 及其回调函数,而使用简单的循环。这意味着我们必须处理-4字符,而 broofa 则不需要。另外,请注意,我们可以使用字符串数组索引来保持其精巧的 String 模板体系结构:

function e1() {
    var u='',i=0;
    while(i++<36) {
        var c='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'[i-1],r=Math.random()*16|0,v=c=='x'?r:(r&0x3|0x8);
        u+=(c=='-'||c=='4')?c:v.toString(16)
    }
    return u;
}

console.log(e1())

基本上,除了检查-4 ,和使用 while 循环(而不是replace()回调),相同的内部逻辑使我们几乎提高了 3 倍!

下一步是台式机上的一小步,但在移动设备上将有很大的不同。让我们进行更少的 Math.random()调用,并利用所有这些随机位,而不是使用随机缓冲区将其丢弃 87%,该缓冲区在每次迭代中都移出。让我们也将该模板定义移出循环,以防万一它有帮助:

function e2() {
    var u='',m='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx',i=0,rb=Math.random()*0xffffffff|0;
    while(i++<36) {
        var c=m[i-1],r=rb&0xf,v=c=='x'?r:(r&0x3|0x8);
        u+=(c=='-'||c=='4')?c:v.toString(16);rb=i%8==0?Math.random()*0xffffffff|0:rb>>4
    }
    return u
}

console.log(e2())

根据平台的不同,这可以为我们节省 10-30%。不错。但是下一步要走的是 toString 函数调用以及优化经典方法 - 查找表。一个简单的 16 元素查找表将以更少的时间执行 toString(16)的工作:

function e3() {
    var h='0123456789abcdef';
    var k='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx';
    /* same as e4() below */
}
function e4() {
    var h=['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'];
    var k=['x','x','x','x','x','x','x','x','-','x','x','x','x','-','4','x','x','x','-','y','x','x','x','-','x','x','x','x','x','x','x','x','x','x','x','x'];
    var u='',i=0,rb=Math.random()*0xffffffff|0;
    while(i++<36) {
        var c=k[i-1],r=rb&0xf,v=c=='x'?r:(r&0x3|0x8);
        u+=(c=='-'||c=='4')?c:h[v];rb=i%8==0?Math.random()*0xffffffff|0:rb>>4
    }
    return u
}

console.log(e4())

下一个优化是另一个经典。由于我们在每次循环迭代中仅处理 4 位输出,因此让我们将循环数减少一半,并在每次迭代中处理 8 位。这很棘手,因为我们仍然必须处理 RFC 兼容位的位置,但这并不难。然后,我们必须制作一个更大的查找表(16x16 或 256)来存储 0x00-0xff,并且只在 e5()函数外部构建一次。

var lut = []; for (var i=0; i<256; i++) { lut[i] = (i<16?'0':'')+(i).toString(16); }
function e5() {
    var k=['x','x','x','x','-','x','x','-','4','x','-','y','x','-','x','x','x','x','x','x'];
    var u='',i=0,rb=Math.random()*0xffffffff|0;
    while(i++<20) {
        var c=k[i-1],r=rb&0xff,v=c=='x'?r:(c=='y'?(r&0x3f|0x80):(r&0xf|0x40));
        u+=(c=='-')?c:lut[v];rb=i%4==0?Math.random()*0xffffffff|0:rb>>8
    }
    return u
}

console.log(e5())

我尝试了一次可处理 16 位的 e6(),但仍使用 256 个元素的 LUT,它显示出优化收益递减。尽管迭代次数较少,但内部逻辑却因处理量的增加而变得复杂,并且在台式机上的性能相同,而在移动设备上的速度仅快 10%。

要应用的最终优化技术 - 展开循环。由于我们要循环固定的次数,因此从技术上讲,我们可以手动将其全部写出。我用一个随机变量 r 进行了一次尝试,我一直对其进行重新分配,并降低了性能。但是先给四个变量分配了随机数据,然后使用查找表并应用适当的 RFC 位,此版本将它们全部清除:

var lut = []; for (var i=0; i<256; i++) { lut[i] = (i<16?'0':'')+(i).toString(16); }
function e7()
{
    var d0 = Math.random()*0xffffffff|0;
    var d1 = Math.random()*0xffffffff|0;
    var d2 = Math.random()*0xffffffff|0;
    var d3 = Math.random()*0xffffffff|0;
    return lut[d0&0xff]+lut[d0>>8&0xff]+lut[d0>>16&0xff]+lut[d0>>24&0xff]+'-'+
    lut[d1&0xff]+lut[d1>>8&0xff]+'-'+lut[d1>>16&0x0f|0x40]+lut[d1>>24&0xff]+'-'+
    lut[d2&0x3f|0x80]+lut[d2>>8&0xff]+'-'+lut[d2>>16&0xff]+lut[d2>>24&0xff]+
    lut[d3&0xff]+lut[d3>>8&0xff]+lut[d3>>16&0xff]+lut[d3>>24&0xff];
}

console.log(e7())

模块化: httpUUID.generate()

有趣的是,生成 16 字节的随机数据很容易。整个技巧是使用符合 RFC 的 String 格式表示它,并且最紧密地实现是使用 16 个字节的随机数据,展开的循环和查找表。

我希望我的逻辑是正确的 - 在这种繁琐的工作中容易犯错。但是输出对我来说看起来不错。希望您喜欢这段疯狂的代码优化之旅!

忠告:我的主要目标是展示和教授潜在的优化策略。其他答案涵盖重要主题,例如冲突和真正的随机数,这对于生成良好的 UUID 至关重要。

这是一些基于RFC 4122第 4.4 节(根据真正随机数或伪随机数创建 UUID 的算法)的代码。

function createUUID() {
    // http://www.ietf.org/rfc/rfc4122.txt
    var s = [];
    var hexDigits = "0123456789abcdef";
    for (var i = 0; i < 36; i++) {
        s[i] = hexDigits.substr(Math.floor(Math.random() * 0x10), 1);
    }
    s[14] = "4";  // bits 12-15 of the time_hi_and_version field to 0010
    s[19] = hexDigits.substr((s[19] & 0x3) | 0x8, 1);  // bits 6-7 of the clock_seq_hi_and_reserved to 01
    s[8] = s[13] = s[18] = s[23] = "-";

    var uuid = s.join("");
    return uuid;
}
let uniqueId = Math.random().toString(36).substring(2) + Date.now().toString(36);

document.getElementById("unique").innerHTML =
  Math.random().toString(36).substring(2) + (new Date()).getTime().toString(36);
<div id="unique">
</div>

如果 ID 的生成间隔超过 1 毫秒,则它们是 100%唯一的。

如果以较短的时间间隔生成两个 ID,并且假设随机方法是真正随机的,则将生成 99.99999999999999%的 ID 可能是全局唯一的(冲突 10 ^ 15 中的 1 个)

您可以通过添加更多数字来增加此数字,但是要生成 100%的唯一 ID,您将需要使用全局计数器。

如果您需要 RFC 兼容性,此格式将作为有效的版本 4 GUID 传递:

let u = Date.now().toString(16) + Math.random().toString(16) + '0'.repeat(16);
let guid = [u.substr(0,8), u.substr(8,4), '4000-8' + u.substr(13,3), u.substr(16,12)].join('-');

let u = Date.now().toString(16)+Math.random().toString(16)+'0'.repeat(16);
let guid = [u.substr(0,8), u.substr(8,4), '4000-8' + u.substr(13,3), u.substr(16,12)].join('-');
document.getElementById("unique").innerHTML = guid;
<div id="unique">
</div>

编辑:上面的代码遵循意图,但不是 RFC 的字母。除其他差异外,还有一些随机数短。 (如果需要,可以添加更多随机数字)好处是,与 100%兼容的代码相比,它确实非常快。您可以在此处测试 GUID 的有效性

最快的类似于 GUID 的字符串生成器方法,格式为XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX 。这不会生成符合标准的 GUID。

此实现的一千万次执行仅需 32.5 秒,这是我在浏览器中见过的最快速度(这是唯一一种没有循环 / 迭代的解决方案)。

该函数很简单:

/**
 * Generates a GUID string.
 * @returns {string} The generated GUID.
 * @example af8a8416-6e18-a307-bd9c-f2c947bbb3aa
 * @author Slavik Meltser.
 * @link http://slavik.meltser.info/?p=142
 */
function guid() {
    function _p8(s) {
        var p = (Math.random().toString(16)+"000000000").substr(2,8);
        return s ? "-" + p.substr(0,4) + "-" + p.substr(4,4) : p ;
    }
    return _p8() + _p8(true) + _p8(true) + _p8();
}

要测试性能,可以运行以下代码:

console.time('t'); 
for (var i = 0; i < 10000000; i++) { 
    guid(); 
};
console.timeEnd('t');

我敢肯定你们中的大多数人都会明白我在那里所做的事情,但是也许至少有一个人需要解释:

算法:

  • Math.random()函数返回一个介于 0 和 1 之间的十进制数字,该数字在小数点之后是 16 位(例如0.4363923368509859 )。
  • 然后,我们将这个数字转换为以 16 为底的字符串(从上面的示例中我们将得到0.6fb7687f )。
    Math.random().toString(16)
  • 然后,我们截断0.前缀( 0.6fb7687f => 6fb7687f ),并得到一个长度为八个十六进制字符的字符串。
    (Math.random().toString(16).substr(2,8)
  • 有时,由于结尾为零, Math.random()函数将返回较短的数字(例如0.4363 )(从上面的示例中,实际上该数字是0.4363000000000000 )。这就是为什么我要将此字符串追加到"000000000" (具有九个零的字符串),然后使用substr()函数将其截断以使其准确地成为九个字符(在右侧填充零)的原因。
  • 之所以要精确地添加 9 个零是因为情况更糟,这是Math.random()函数将恰好返回 0 或 1(每一个概率为 1/10 ^ 16)的情况。这就是为什么我们需要为其添加九个零( "0"+"000000000""1"+"000000000" ),然后将其与长度为八个字符的第二个索引(第三个字符)相切。在其他情况下,加零不会损害结果,因为无论如何它都会切断结果。
    Math.random().toString(16)+"000000000").substr(2,8)

组装:

  • GUID 的格式如下XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX
  • 我将 GUID 分为 4 部分,每部分分为 2 种类型(或格式): XXXXXXXX-XXXX-XXXX
  • 现在,我正在使用这两种类型来构建 GUID,以用调用 4 件组装 GUID,如下所示: XXXXXXXX -XXXX-XXXX -XXXX-XXXX XXXXXXXX
  • 为了_p8(s)这两种类型,我在对创建器函数_p8(s)添加了一个 flag 参数, s参数告诉该函数是否添加破折号。
  • 最终,我们使用以下链接构建了 GUID: _p8() + _p8(true) + _p8(true) + _p8() ,然后将其返回。

链接到我博客上的这篇文章

请享用! :-)

以下是最受好评的答案的组合,以及针对Chrome 浏览器冲突的解决方法:

generateGUID = (typeof(window.crypto) != 'undefined' && 
                typeof(window.crypto.getRandomValues) != 'undefined') ?
    function() {
        // If we have a cryptographically secure PRNG, use that
        // https://stackoverflow.com/questions/6906916/collisions-when-generating-uuids-in-javascript
        var buf = new Uint16Array(8);
        window.crypto.getRandomValues(buf);
        var S4 = function(num) {
            var ret = num.toString(16);
            while(ret.length < 4){
                ret = "0"+ret;
            }
            return ret;
        };
        return (S4(buf[0])+S4(buf[1])+"-"+S4(buf[2])+"-"+S4(buf[3])+"-"+S4(buf[4])+"-"+S4(buf[5])+S4(buf[6])+S4(buf[7]));
    }

    :

    function() {
        // Otherwise, just use Math.random
        // https://stackoverflow.com/questions/105034/how-to-create-a-guid-uuid-in-javascript/2117523#2117523
        return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
            var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
            return v.toString(16);
        });
    };

如果要测试,请在 jsbin上进行。

这是一个完全不合规但非常高效的实现,用于生成类似 ASCII 安全的 GUID 的唯一标识符。

function generateQuickGuid() {
    return Math.random().toString(36).substring(2, 15) +
        Math.random().toString(36).substring(2, 15);
}

生成 26 个 [a-z0-9] 字符,产生的 UID 比符合 RFC 的 GUID 短且唯一。如果人类可读性很重要,则可以添加短划线。

这是此功能的用法示例和时间安排,以及该问题的其他一些答案。计时是在 Chrome m25 下执行的,每次进行 1000 万次迭代。

>>> generateQuickGuid()
"nvcjf1hs7tf8yyk4lmlijqkuo9"
"yq6gipxqta4kui8z05tgh9qeel"
"36dh5sec7zdj90sk2rx7pjswi2"
runtime: 32.5s

>>> GUID() // John Millikin
"7a342ca2-e79f-528e-6302-8f901b0b6888"
runtime: 57.8s

>>> regexGuid() // broofa
"396e0c46-09e4-4b19-97db-bd423774a4b3"
runtime: 91.2s

>>> createUUID() // Kevin Hakanson
"403aa1ab-9f70-44ec-bc08-5d5ac56bd8a5"
runtime: 65.9s

>>> UUIDv4() // Jed Schmidt
"f4d7d31f-fa83-431a-b30c-3e6cc37cc6ee"
runtime: 282.4s

>>> Math.uuid() // broofa
"5BD52F55-E68F-40FC-93C2-90EE069CE545"
runtime: 225.8s

>>> Math.uuidFast() // broofa
"6CB97A68-23A2-473E-B75B-11263781BBE6"
runtime: 92.0s

>>> Math.uuidCompact() // broofa
"3d7b7a06-0a67-4b67-825c-e5c43ff8c1e8"
runtime: 229.0s

>>> bitwiseGUID() // jablko
"baeaa2f-7587-4ff1-af23-eeab3e92"
runtime: 79.6s

>>>> betterWayGUID() // Andrea Turri
"383585b0-9753-498d-99c3-416582e9662c"
runtime: 60.0s

>>>> UUID() // John Fowler
"855f997b-4369-4cdb-b7c9-7142ceaf39e8"
runtime: 62.2s

这是时间码。

var r;
console.time('t'); 
for (var i = 0; i < 10000000; i++) { 
    r = FuncToTest(); 
};
console.timeEnd('t');

这是日期为 2011 年 10 月 9 日的解决方案,来自用户jedhttps://gist.github.com/982883的评论:

UUIDv4 = function b(a){return a?(a^Math.random()*16>>a/4).toString(16):([1e7]+-1e3+-4e3+-8e3+-1e11).replace(/[018]/g,b)}

这可以实现与当前最高评分答案相同的目标,但是通过利用强制,递归和指数表示法,可以减少 50 个字节以内。对于那些好奇它如何工作的人,这是该函数旧版本的带注释的形式:

UUIDv4 =

function b(
  a // placeholder
){
  return a // if the placeholder was passed, return
    ? ( // a random number from 0 to 15
      a ^ // unless b is 8,
      Math.random() // in which case
      * 16 // a random number from
      >> a/4 // 8 to 11
      ).toString(16) // in hexadecimal
    : ( // or otherwise a concatenated string:
      [1e7] + // 10000000 +
      -1e3 + // -1000 +
      -4e3 + // -4000 +
      -8e3 + // -80000000 +
      -1e11 // -100000000000,
      ).replace( // replacing
        /[018]/g, // zeroes, ones, and eights with
        b // random hex digits
      )
}