Wie man eine GUID / UUID erstellt

Question

Ich versuche, in JavaScript global eindeutige Bezeichner zu erstellen. Ich bin mir nicht sicher, welche Routinen in allen Browsern verfügbar sind, wie "zufällig" und gesetzt der eingebaute Zufallszahlengenerator ist, usw.

Die GUID / UUID sollte mindestens 32 Zeichen lang sein und im ASCII-Bereich bleiben, um Probleme bei der Weitergabe zu vermeiden.

Answer 1

[Geändert am 2021-10-16, um die neuesten Best Practices für die Erstellung von RFC4122-konformen UUIDs zu berücksichtigen]

Die meisten Leser hier werden die le site uuid Modul . Sie ist gut erprobt und wird unterstützt.

El crypto.randomUUID() Funktion ist ein aufkommender Standard, der unterstützt wird von Node.js y eine wachsende Zahl von Browsern .

Wenn beides nicht funktioniert, gibt es diese Methode (basierend auf der ursprünglichen Antwort auf diese Frage):

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

Nota: Die Verwendung von jede Von einem UUID-Generator, der sich auf Math.random() stützt, wird dringend abgeraten (einschließlich der in früheren Versionen dieser Antwort enthaltenen Auszüge) für Gründe, die hier am besten erläutert werden . TL;DR: Math.random()-basierte Lösungen bieten keine guten Einzigartigkeitsgarantien.

Answer 2

UUIDs (Universally Unique IDentifier), auch bekannt als GUIDs (Globally Unique IDentifier), nach RFC 4122 sind Bezeichner, die bestimmte Garantien für die Einzigartigkeit bieten sollen.

Es ist zwar möglich, RFC-konforme UUIDs in ein paar Zeilen JavaScript-Code zu implementieren (siehe z. B. @broofa's Antwort (siehe unten) gibt es mehrere häufige Fallstricke:

• Ungültiges ID-Format (UUIDs müssen die Form " xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx ", wobei x einer der Werte [0-9, a-f] ist M ist eine von [1-5], und N ist [8, 9, a, oder b]
• Verwendung einer minderwertigen Zufallsquelle (z. B. Math.random )

Daher wird Entwicklern, die Code für Produktionsumgebungen schreiben, empfohlen, eine strenge, gut gewartete Implementierung wie die uuid Modul.

Answer 3

Ich mag wirklich, wie sauber Broofa's Antwort ist, aber es ist bedauerlich, dass schlechte Umsetzungen von Math.random Lassen Sie die Möglichkeit einer Kollision offen.

Hier ist eine ähnliche RFC4122 Version 4-konforme Lösung, die dieses Problem löst, indem sie die ersten 13 Hex-Zahlen um einen Hex-Anteil des Zeitstempels versetzt und, sobald dieser aufgebraucht ist, um einen Hex-Anteil der Mikrosekunden seit dem Laden der Seite versetzt. Auf diese Weise kann, selbst wenn Math.random auf demselben Seed ist, müssten beide Clients die UUID exakt dieselbe Anzahl von Mikrosekunden seit dem Pageload (wenn High-Perfomance-Time unterstützt wird) UND zur exakt gleichen Millisekunde (oder 10.000+ Jahre später) erzeugen, um dieselbe UUID zu erhalten:

function generateUUID() { // Public Domain/MIT
    var d = new Date().getTime();//Timestamp
    var d2 = ((typeof performance !== 'undefined') && 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);
    });
}

var onClick = function(){
    document.getElementById('uuid').textContent = generateUUID();
}
onClick();

#uuid { font-family: monospace; font-size: 1.5em; }

<p id="uuid"></p>
<button id="generateUUID" onclick="onClick();">Generate UUID</button>

Hier ist eine Fiddle zum Testen.

---

Modernisiertes Snippet für ES6

const generateUUID = () => {
  let
    d = new Date().getTime(),
    d2 = (performance && performance.now && (performance.now() * 1000)) || 0;
  return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, c => {
    let r = Math.random() * 16;
    if (d > 0) {
      r = (d + r) % 16 | 0;
      d = Math.floor(d / 16);
    } else {
      r = (d2 + r) % 16 | 0;
      d2 = Math.floor(d2 / 16);
    }
    return (c == 'x' ? r : (r & 0x7 | 0x8)).toString(16);
  });
};

const onClick = (e) => document.getElementById('uuid').textContent = generateUUID();

document.getElementById('generateUUID').addEventListener('click', onClick);

onClick();

#uuid { font-family: monospace; font-size: 1.5em; }

<p id="uuid"></p>
<button id="generateUUID">Generate UUID</button>

Answer 4

broofa's Antwort ist in der Tat ziemlich raffiniert - beeindruckend clever, wirklich... RFC4122-konform, einigermaßen lesbar und kompakt. Fantastisch!

Aber wenn man sich diesen regulären Ausdruck ansieht, sind diese vielen replace() Rückrufe, toString() und Math.random() Funktionsaufrufe (bei denen er nur vier Bits des Ergebnisses verwendet und den Rest verschwendet), können Sie anfangen, sich über die Leistung Gedanken zu machen. In der Tat hat joelpt sogar beschlossen, einen RFC für generische GUID-Geschwindigkeit mit generateQuickGUID .

Aber, können wir Geschwindigkeit bekommen und RFC-Konformität? Ich sage: JA! Können wir die Lesbarkeit aufrechterhalten? Nun ja... Nicht wirklich, aber es ist einfach, wenn Sie mitmachen.

Doch zunächst zu meinen Ergebnissen im Vergleich zu broofa, guid (die akzeptierte Antwort), und die nicht rfc-konforme 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.

Mit meiner 6. Iteration der Optimierungen habe ich die beliebteste Antwort um mehr als 12 Mal die akzeptierte Antwort von über 9 Mal und die schnelle nicht-konforme Antwort von 2-3 Mal . Und ich bin immer noch konform mit RFC 4122.

Interessiert Sie das wie? Ich habe die vollständige Quelle auf http://jsfiddle.net/jcward/7hyaC/3/ und weiter https://jsben.ch/xczxS

Beginnen wir zur Erläuterung mit dem Code von 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())

Es ersetzt also x mit einer beliebigen hexadezimalen Ziffer, y mit zufälligen Daten (mit Ausnahme des Erzwingens der oberen zwei Bits zu 10 gemäß der RFC-Spezifikation), und die Regex stimmt nicht mit der - o 4 Figuren, damit er sich nicht mit ihnen auseinandersetzen muss. Sehr, sehr raffiniert.

Zunächst muss man wissen, dass Funktionsaufrufe teuer sind, ebenso wie reguläre Ausdrücke (obwohl er nur einen verwendet, hat er 32 Rückrufe, einen für jede Übereinstimmung, und in jedem der 32 Rückrufe ruft er Math.random() und v.toString(16) auf).

Der erste Schritt zur Verbesserung der Leistung besteht darin, RegEx und seine Callback-Funktionen zu eliminieren und stattdessen eine einfache Schleife zu verwenden. Das bedeutet, dass wir uns mit der - y 4 Zeichen, während Broofa dies nicht tat. Beachten Sie auch, dass wir String Array Indizierung verwenden können, um seine glatte String-Vorlage Architektur zu halten:

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())

Im Grunde die gleiche innere Logik, außer dass wir prüfen, ob - o 4 und die Verwendung einer while-Schleife (anstelle von replace() Rückrufe) bringt uns eine fast 3-fache Verbesserung!

Der nächste Schritt ist auf dem Desktop nur ein kleiner, aber auf dem Handy ein großer Unterschied. Wir machen weniger Math.random()-Aufrufe und nutzen all diese Zufallsbits, anstatt 87 % von ihnen mit einem Zufallspuffer wegzuwerfen, der bei jeder Iteration verschoben wird. Verschieben wir auch die Template-Definition aus der Schleife, nur für den Fall, dass es hilft:

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())

Dadurch sparen wir je nach Plattform 10-30 %. Nicht schlecht. Der nächste große Schritt besteht darin, die toString-Funktionsaufrufe mit einem Optimierungsklassiker - der Look-up-Tabelle - ganz loszuwerden. Eine einfache Nachschlagetabelle mit 16 Elementen erledigt die Aufgabe von toString(16) in viel kürzerer Zeit:

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())

Die nächste Optimierung ist ein weiterer Klassiker. Da wir in jeder Schleifeniteration nur vier Bits der Ausgabe verarbeiten, sollten wir die Anzahl der Schleifen halbieren und in jeder Iteration acht Bits verarbeiten. Das ist zwar nicht ganz einfach, da wir immer noch die RFC-konformen Bitpositionen verarbeiten müssen, aber es ist nicht allzu schwer. Wir müssen dann eine größere Nachschlagetabelle (16x16, oder 256) erstellen, um 0x00 - 0xFF zu speichern, und wir erstellen sie nur einmal, außerhalb der Funktion 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())

Ich habe ein e6() ausprobiert, das 16 Bits auf einmal verarbeitet, wobei immer noch die 256-Elemente LUT und zeigte die abnehmenden Erträge der Optimierung. Obwohl es weniger Iterationen gab, wurde die innere Logik durch die vermehrte Verarbeitung kompliziert, und die Leistung war auf dem Desktop gleich und auf dem Handy nur ~10 % schneller.

Die letzte Optimierungstechnik, die angewendet werden muss, ist das Abrollen der Schleife. Da wir die Schleife eine feste Anzahl von Malen durchlaufen, können wir dies technisch gesehen von Hand schreiben. Ich habe das einmal mit einer einzelnen Zufallsvariablen ausprobiert, r die ich immer wieder neu zugewiesen habe, und die Leistung sank. Aber mit vier Variablen, denen im Vorfeld Zufallsdaten zugewiesen wurden, und der Verwendung der Nachschlagetabelle und der Anwendung der richtigen RFC-Bits, übertrifft diese Version alle anderen:

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())

Modualisiert: http://jcward.com/UUID.js - UUID.generate()

Das Lustige daran ist, dass das Erzeugen von 16 Byte Zufallsdaten der einfache Teil ist. Der ganze Trick besteht darin, es auszudrücken in String Format mit RFC-Konformität, das mit 16 Byte Zufallsdaten, einer unrollierten Schleife und einer Nachschlagetabelle am einfachsten zu bewerkstelligen ist.

Ich hoffe, dass meine Logik richtig ist - bei dieser Art von mühsamer Kleinarbeit kann man sehr leicht einen Fehler machen. Aber die Ergebnisse sehen für mich gut aus. Ich hoffe, Sie haben diesen verrückten Ritt durch die Code-Optimierung genossen!

Bitte beachten Sie: mein primäres Ziel war es, mögliche Optimierungsstrategien aufzuzeigen und zu vermitteln. Andere Antworten behandeln wichtige Themen wie Kollisionen und echte Zufallszahlen, die für die Erzeugung guter UUIDs wichtig sind.

Answer 5

Verwendung:

let uniqueId = Date.now().toString(36) + Math.random().toString(36).substring(2);

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

<div id="unique">
</div>

Wenn die IDs im Abstand von mehr als 1 Millisekunde erzeugt werden, sind sie zu 100 % eindeutig.

Wenn zwei IDs in kürzeren Abständen generiert werden, und unter der Annahme, dass die Zufallsmethode wirklich zufällig ist, würde dies IDs generieren, die mit einer Wahrscheinlichkeit von 99,99999999999999% global eindeutig sind (Kollision in 1 von 10^15).

Sie können diese Zahl durch Hinzufügen weiterer Ziffern erhöhen, aber um 100% eindeutige IDs zu erzeugen, müssen Sie einen globalen Zähler verwenden.

Wenn Sie RFC-Kompatibilität benötigen, wird diese Formatierung als gültige GUID der Version 4 übergeben:

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>

Der obige Code folgt der Absicht, aber nicht dem Buchstaben des RFC. Neben anderen Unstimmigkeiten fehlen ein paar zufällige Ziffern. (Fügen Sie bei Bedarf weitere zufällige Ziffern hinzu.) Der Vorteil ist, dass dies wirklich schnell geht :) Sie können Testen Sie die Gültigkeit Ihrer GUID hier