Vraag Maak GUID / UUID in JavaScript?


Ik probeer globaal unieke ID's te maken in JavaScript. Ik weet niet zeker welke routines beschikbaar zijn in alle browsers, hoe "willekeurig" en gezaaid de ingebouwde willekeurige nummergenerator is, enz.

De GUID / UUID moet minimaal 32 tekens bevatten en moet in het ASCII-bereik blijven om problemen te voorkomen bij het doorgeven ervan.


3207


oorsprong


antwoorden:


Er zijn een paar pogingen hiertoe geweest. De vraag is: wil je echte GUID's, of gewoon willekeurige getallen kijken zoals GUID's? Het is gemakkelijk genoeg om willekeurige getallen te genereren.

function guid() {
  function s4() {
    return Math.floor((1 + Math.random()) * 0x10000)
      .toString(16)
      .substring(1);
  }
  return s4() + s4() + '-' + s4() + '-' + s4() + '-' + s4() + '-' + s4() + s4() + s4();
}

Merk echter op dat dergelijke waarden zijn geen echte GUID's.

Er is geen manier om echte GUID's in Javascript te genereren, omdat ze afhankelijk zijn van eigenschappen van de lokale computer die browsers niet blootstellen. U moet OS-specifieke services zoals ActiveX gebruiken: http://p2p.wrox.com/topicindex/20339.htm

Bewerken: niet correct - RFC4122 maakt willekeurige ("versie 4") GUID's mogelijk. Zie andere antwoorden voor details.

Notitie: het bijgeleverde codefragment volgt RFC4122 niet en vereist dat de versie (4) moet in de gegenereerde output-string worden geïntegreerd. Gebruik dit antwoord niet als u compatibele GUID's nodig hebt.

Gebruik:

var uuid = guid();

demo:

function guid() {
  return s4() + s4() + '-' + s4() + '-' + s4() + '-' +
    s4() + '-' + s4() + s4() + s4();
}

function s4() {
  return Math.floor((1 + Math.random()) * 0x10000)
    .toString(16)
    .substring(1);
}

document.getElementById('jsGenId').addEventListener('click', function() {
  document.getElementById('jsIdResult').value = guid();
})
input { font-family: monospace; }
<button id="jsGenId" type="button">Generate GUID</button>
<br>
<input id="jsIdResult" type="text" placeholder="Results will be placed here..." readonly size="40"/>


1895



Voor een RFC4122 versie één oplossing, deze one-liner (ish) oplossing is de meest compacte die ik kon bedenken:

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

Update, 2015-06-02: Houd er rekening mee dat UUID-uniciteit veel afhankelijk is van de onderliggende willekeurige nummergenerator (RNG). De bovenstaande oplossing gebruikt Math.random() voor beknoptheid echter Math.random() is niet gegarandeerd een hoogwaardige RNG. Zie Adam Hyland's uitstekende beschrijving op Math.random () voor details. Voor een meer robuuste oplossing, bedenk iets als de uuid-module[Disclaimer: ik ben de auteur], die, waar beschikbaar, RNG-API's van hogere kwaliteit gebruikt.

Update, 2015-08-26: Als een kanttekening, dit kern beschrijft hoe te bepalen hoeveel ID's kunnen worden gegenereerd voordat een bepaalde botsingskans wordt bereikt. Bijvoorbeeld met 3,26x1015 versie 4 RFC4122 UUID's heb je een kans van 1 op miljoen om te botsen.

Update, 2017-06-28: EEN goed artikel van Chrome-ontwikkelaars bespreken van de staat van de PRNG-kwaliteit van Math.random in Chrome, Firefox en Safari. tl; dr - Vanaf eind 2015 is het "redelijk goed", maar geen cryptografische kwaliteit. Om dit probleem aan te pakken, hier is een bijgewerkte versie van de bovenstaande oplossing die ES6 gebruikt, de crypto API, en een beetje JS-tovenaar waar ik geen eer voor heb:

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


3141



Ik hou echt van hoe schoon Broofa's antwoord is, maar het is jammer dat slechte implementaties van Math.random laat de kans op een botsing.

Hier is een soortgelijk RFC4122 versie 4-compatibele oplossing die dat probleem oplost door de eerste 13 hexadecimale getallen te verrekenen met een hexadecimaal gedeelte van de tijdstempel. Op die manier, zelfs als Math.randomzit in hetzelfde seed, beide clients zouden de UUID exact dezelfde milliseconde (of 10.000+ later) moeten genereren om dezelfde UUID te krijgen:

function generateUUID() { // Public Domain/MIT
    var d = new Date().getTime();
    if (typeof performance !== 'undefined' && typeof performance.now === 'function'){
        d += performance.now(); //use high-precision timer if available
    }
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function (c) {
        var r = (d + Math.random() * 16) % 16 | 0;
        d = Math.floor(d / 16);
        return (c === 'x' ? r : (r & 0x3 | 0x8)).toString(16);
    });
}


Hier is een vuurtje om te testen.


671



Het antwoord van broofa is behoorlijk glad, inderdaad - indrukwekkend slim, echt ... rfc4122 compliant, enigszins leesbaar en compact. Geweldig!

Maar als je naar die reguliere expressie kijkt, die van velen replace() callbacks, toString()en Math.random() functieaanroepen (waarbij hij slechts 4 bits van het resultaat gebruikt en de rest verspilt), kun je je afvragen wat de prestaties zijn. Inderdaad, joelpt heeft zelfs besloten om RFC voor algemene GUID-snelheid uit te gooien met generateQuickGUID.

Maar kunnen we snelheid krijgen en RFC-naleving? Ik zeg ja!  Kunnen we de leesbaarheid behouden? Nou ... Niet echt, maar het is makkelijk als je meegaat.

Maar eerst, mijn resultaten, vergeleken met broofa, guid (het geaccepteerde antwoord) en de non-rfc-compliant 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 that results will vary by browser/cpu.

Dus bij mijn zesde iteratie van optimalisaties versloeg ik het populairste antwoord 12X, het geaccepteerde antwoord van over 9X, en het snel-niet-conforme antwoord van 2-3X. En ik ben nog steeds rfc4122 compliant.

Geïnteresseerd in hoe? Ik heb de volledige bron ingeschakeld http://jsfiddle.net/jcward/7hyaC/3/ en verder http://jsperf.com/uuid-generator-opt/4

Laten we voor de uitleg beginnen met de code van broofa:

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

Dus het vervangt x met willekeurig willekeurig hexadecijfer, y met willekeurige gegevens (behalve het dwingen van de bovenste 2 bits naar 10 volgens de RFC-specificatie), en de regex komt niet overeen met de - of 4 tekens, zodat hij ze niet hoeft aan te pakken. Heel erg glad.

Het eerste wat je moet weten is dat functieaanroepen duur zijn, net als reguliere expressies (hoewel hij er slechts 1 gebruikt, hij heeft 32 callbacks, één voor elke match, en in elk van de 32 callbacks die hij Math.random () en v noemt. toString (16)).

De eerste stap naar prestaties is om de RegEx en zijn callback-functies te verwijderen en in plaats daarvan een eenvoudige lus te gebruiken. Dit betekent dat we te maken hebben met de - en 4 personages terwijl broofa dat niet deed. Merk ook op dat we String Array-indexering kunnen gebruiken om zijn gelikte String-sjabloonarchitectuur te behouden:

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

Eigenlijk dezelfde innerlijke logica, behalve dat we controleren - of 4en een while-lus gebruiken (in plaats van replace() callbacks) bezorgt ons een bijna 3X verbetering!

De volgende stap is een kleine stap op de desktop, maar maakt een behoorlijk verschil op mobiel. Laten we minder Math.random () aanroepen en al die willekeurige bits gebruiken in plaats van 87% ervan weg te gooien met een willekeurige buffer die uit elke iteratie wordt verwijderd. Laten we ook die sjabloondefinitie uit de kring halen, voor het geval het helpt:

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
}

Dit scheelt ons 10-30%, afhankelijk van het platform. Niet slecht. Maar de volgende grote stap verwijdert de toString-functieaanroepen helemaal met een optimalisatieklassieker - de opzoektabel. Een eenvoudige opzoektabel met 16 elementen voert de taak van toString (16) in veel minder tijd uit:

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
}

De volgende optimalisatie is een andere klassieker. Omdat we alleen 4-bits uitvoer verwerken in elke lus-iteratie, laten we het aantal lussen in tweeën knippen en 8 bits per iteratie verwerken. Dit is lastig, want we moeten nog steeds omgaan met de RFC-compatibele bitposities, maar het is niet zo moeilijk. We moeten dan een grotere opzoektabel maken (16x16 of 256) om 0x00 - 0xff op te slaan, en we bouwen het slechts eenmaal, buiten de e5 () functie.

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
}

Ik heb een e6 () geprobeerd die 16 bits per keer verwerkt, waarbij de LUT met 256 elementen nog steeds wordt gebruikt, en deze liet het afnemende rendement van optimalisatie zien. Hoewel het minder iteraties had, werd de innerlijke logica gecompliceerd door de toegenomen verwerking en presteerde hetzelfde op desktop en slechts ~ 10% sneller op mobiel.

De laatste optimalisatietechniek die moet worden toegepast - ontrol de lus. Omdat we een vast aantal keren herhalen, kunnen we dit technisch allemaal met de hand schrijven. Ik probeerde dit een keer met een enkele willekeurige variabele r die ik steeds opnieuw toewijzigde, en de prestaties getankt. Maar met vier variabelen die willekeurige gegevens vooraf zijn toegewezen, en vervolgens de opzoektabel gebruiken en de juiste RFC-bits toepassen, rookt deze versie ze allemaal:

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

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

Het grappige is dat het genereren van 16 bytes willekeurige gegevens het makkelijke deel is. De hele slag is het uitdrukken in String-formaat met RFC-compliantie, en het is het meest strak uitgevoerd met 16 bytes aan willekeurige gegevens, een ontrolled lus en een opzoektabel.

Ik hoop dat mijn logica klopt - het is heel gemakkelijk om een ​​fout te maken in dit soort vervelend bit-werk. Maar de resultaten zien er goed uit voor mij. Ik hoop dat je hebt genoten van deze gekke rit door code-optimalisatie!

Wees gewaarschuwd: mijn primaire doel was om potentiële optimalisatiestrategieën te tonen en te onderwijzen. Andere antwoorden hebben betrekking op belangrijke onderwerpen, zoals botsingen en echt willekeurige getallen, die belangrijk zijn voor het genereren van goede UUID's.


305



Hier is wat code op gebaseerd RFC 4122, paragraaf 4.4 (Algoritmen voor het maken van een UUID van Echt willekeurig of pseudo-willekeurig getal).

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

136



Snelste GUID-achtige methode voor stringgenerator in het formaat XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX. Dit genereert geen GUID met standaardcompatibiliteit.

Tien miljoen uitvoeringen van deze implementatie nemen slechts 32,5 seconden in beslag, wat de snelste is die ik ooit in een browser heb gezien (de enige oplossing zonder loops / iteraties).

De functie is zo simpel als:

/**
 * Generates a GUID string.
 * @returns {String} The generated GUID.
 * @example af8a8416-6e18-a307-bd9c-f2c947bbb3aa
 * @author Slavik Meltser (slavik@meltser.info).
 * @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();
}

Om de prestaties te testen, kunt u deze code uitvoeren:

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

Ik weet zeker dat de meesten van jullie zullen begrijpen wat ik daar heb gedaan, maar misschien is er tenminste één persoon die een uitleg nodig heeft:

Het algoritme:

  • De Math.random() functie retourneert een decimaal getal tussen 0 en 1 met 16 cijfers achter het decimale breukstreepje (voor voorbeeld 0.4363923368509859).
  • Dan nemen we dit nummer en zetten het om het naar een string met base 16 (uit het bovenstaande voorbeeld zullen we krijgen 0.6fb7687f).
    Math.random().toString(16).
  • Toen hebben we de 0. voorvoegsel (0.6fb7687f => 6fb7687f) en krijg een string met acht hexadecimalen karakters lang.
    (Math.random().toString(16).substr(2,8).
  • Soms het Math.random()functie zal terugkeren korter nummer (bijvoorbeeld 0.4363), als gevolg van nullen aan het einde (uit het bovenstaande voorbeeld is het nummer eigenlijk 0.4363000000000000). Dat is waarom ik aan deze reeks toevoeg "000000000" (een reeks met negen nullen) en dan afsnijden met substr() functie om er negen karakters precies van te maken (nullen aan de rechterkant vullen).
  • De reden voor het toevoegen van precies negen nullen is vanwege het slechtste scenario, dat is wanneer het Math.random() functie zal exact 0 of 1 retourneren (waarschijnlijkheid van 1/10 ^ 16 voor elk van hen). Daarom moesten we er negen nullen aan toevoegen ("0"+"000000000" of "1"+"000000000") en vervolgens af te snijden van de tweede index (3e teken) met een lengte van acht tekens. Voor de rest van de gevallen zal het toevoegen van nullen het resultaat niet schaden, omdat het het toch afsnijdt.
    Math.random().toString(16)+"000000000").substr(2,8).

De vergadering:

  • De GUID heeft de volgende indeling XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX.
  • Ik verdeelde de GUID in 4 stukken, elk stuk verdeeld in 2 types (of formaten): XXXXXXXX en -XXXX-XXXX.
  • Nu bouw ik de GUID met behulp van deze 2 typen om de GUID te assembleren met 4-delen, als volgt: XXXXXXXX  -XXXX-XXXX  -XXXX-XXXX  XXXXXXXX.
  • Om te verschillen tussen deze twee typen, heb ik een vlagparameter toegevoegd aan een paarschepselfunctie _p8(s), de s parameter vertelt de functie of streepjes moeten worden toegevoegd of niet.
  • Uiteindelijk bouwen we de GUID met de volgende keten: _p8() + _p8(true) + _p8(true) + _p8()en stuur het terug.

Link naar dit bericht op mijn blog

Genieten! :-)


78



var uniqueId = Math.random().toString(36).substring(2) 
               + (new Date()).getTime().toString(36);

Als ID's meer dan 1 milliseconde van elkaar worden gegenereerd, zijn ze 100% uniek.

Als twee ID's met kortere tussenpozen worden gegenereerd en aangenomen dat de willekeurige methode echt willekeurig is, zou dit ID's genereren die 99.99999999999999% waarschijnlijk globaal uniek zijn (botsing in 1 van 10 ^ 15)

Je kunt dit aantal verhogen door meer cijfers toe te voegen, maar om 100% unieke ID's te genereren, moet je een globale teller gebruiken.

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


68



Hier is een combinatie van de top gestemd antwoord, met een tussenoplossing voor Botsingen van 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);
        });
    };

Op jsbin als je het wilt testen.


57



Hier is een oplossing van 9 oktober 2011 uit een opmerking van gebruiker jed op https://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)}

Dit bereikt hetzelfde doel als het huidig ​​antwoord met de hoogste waardering, maar in 50+ minder bytes door gebruik te maken van dwang, recursie en exponentiële notatie. Voor de nieuwsgierigen hoe het werkt, hier is de geannoteerde vorm van een oudere versie van de functie:

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

52