Domanda Crea GUID / UUID in JavaScript?


Sto cercando di creare identificatori univoci a livello globale in JavaScript. Non sono sicuro quali sono le routine disponibili su tutti i browser, quanto è "casuale" e seminato il generatore di numeri casuali incorporato, ecc.

Il GUID / UUID dovrebbe essere di almeno 32 caratteri e dovrebbe rimanere nell'intervallo ASCII per evitare problemi durante il loro passaggio.


3203


origine


risposte:


Ci sono stati un paio di tentativi in ​​questo. La domanda è: vuoi effettivi GUID o solo numeri casuali Guarda come GUID? È abbastanza facile generare numeri casuali.

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

Tuttavia, si noti che tali valori non sono autentici GUID.

Non c'è modo di generare GUID reali in Javascript, perché dipendono dalle proprietà del computer locale che i browser non espongono. Avrai bisogno di utilizzare servizi specifici del sistema operativo come ActiveX: http://p2p.wrox.com/topicindex/20339.htm

Modifica: non corretto - RFC4122 consente GUID casuali ("versione 4"). Vedi altre risposte per le specifiche.

Nota: lo snippet di codice fornito non segue RFC4122 che richiede che la versione (4) deve essere integrato nella stringa di output generata. Non usare questa risposta se hai bisogno di GUID conformi.

Uso:

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"/>


1893



Per un RFC4122 soluzione conforme alla versione 4, questa soluzione one-liner (ish) è la più compatta che potrei trovare:

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

Aggiornamento, 2015-06-02: Tenere presente che l'univocità dell'UUID dipende fortemente dal generatore di numeri casuali (RNG) sottostante. La soluzione sopra utilizza Math.random() per brevità, comunque Math.random() è non garantito per essere un RNG di alta qualità. Vedi Adam Hyland's eccellente riscrittura su Math.random () per dettagli. Per una soluzione più robusta, considera qualcosa di simile il modulo uuid[Disclaimer: I'm the author], che utilizza API RNG di qualità superiore, laddove disponibili.

Aggiornamento, 25/08/2015: Come nota a margine, questo nocciolo descrive come determinare quanti ID possono essere generati prima di raggiungere una certa probabilità di collisione. Ad esempio, con 3,26x1015 versione 4 Gli UUID RFC4122 hanno una probabilità di collisione di 1 su un milione.

Aggiornamento, 2017-06-28: A buon articolo dagli sviluppatori di Chrome discutere dello stato di Math.random qualità PRNG in Chrome, Firefox e Safari. tl; dr - A fine 2015 è "abbastanza buono", ma non di qualità crittografica. Per risolvere il problema, ecco una versione aggiornata della soluzione di cui sopra che utilizza ES6, il crypto API e un po 'di maghi JS di cui non posso prendermi il merito:

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


3140



Mi piace molto come pulito La risposta di Broofa è, ma è un peccato che le cattive implementazioni di Math.random lasciare la possibilità di scontro.

Ecco un simile RFC4122 soluzione conforme alla versione 4 che risolve tale problema compensando i primi 13 numeri esadecimali con una porzione esadecimale del timestamp. In questo modo, anche se Math.randomè sullo stesso seme, entrambi i client dovrebbero generare l'UUID allo stesso millisecondo (o 10.000 anni dopo) per ottenere lo stesso UUID:

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


Ecco un violino da provare.


670



La risposta di broofa è piuttosto lucida, anzi - straordinariamente intelligente, davvero ... conforme a rfc4122, in qualche modo leggibile e compatta. Eccezionale!

Ma se stai guardando quell'espressione regolare, quelle molte replace() callback, toString()e Math.random() chiamate di funzione (dove sta usando solo 4 bit del risultato e sprecando il resto), potresti iniziare a pensare alle prestazioni. Infatti, joelpt ha persino deciso di eliminare RFC per la generica velocità GUID con generateQuickGUID.

Ma possiamo ottenere velocità e Conformità RFC? Io dico si!  Possiamo mantenere la leggibilità? Beh ... Non proprio, ma è facile se segui.

Ma prima, i miei risultati, rispetto al broofa, guid (la risposta accettata) e non conforme a RFFC 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.

Quindi con la mia sesta iterazione di ottimizzazioni, ho battuto la risposta più popolare da oltre 12X, la risposta accettata da oltre 9Xe la risposta veloce non conforme di 2-3X. E sono ancora conforme a rfc4122.

Interessato a come? Ho messo la fonte completa su http://jsfiddle.net/jcward/7hyaC/3/ e via http://jsperf.com/uuid-generator-opt/4

Per una spiegazione, iniziamo con il codice di 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);
});

Quindi sostituisce x con qualsiasi cifra esadecimale casuale, y con dati casuali (eccetto forzare i primi 2 bit a 10 secondo le specifiche RFC) e la regex non corrisponde a - o 4 personaggi, quindi non ha a che fare con loro. Molto, molto lucido.

La prima cosa da sapere è che le chiamate di funzione sono costose, così come le espressioni regolari (anche se usa solo 1, ha 32 callback, uno per ogni corrispondenza e in ciascuno dei 32 callback chiama Math.random () e v. toString (16)).

Il primo passo verso le prestazioni è eliminare la RegEx e le sue funzioni di callback e utilizzare invece un semplice ciclo. Questo significa che dobbiamo fare i conti con - e 4 personaggi mentre broofa no. Inoltre, si noti che è possibile utilizzare l'indicizzazione di stringhe per mantenere la sua architettura di modello di stringa liscia:

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

Fondamentalmente, la stessa logica interna, eccetto che controlliamo - o 4e usando un ciclo while (invece di replace() callbacks) ci ottiene un miglioramento quasi 3X!

Il prossimo passo è piccolo sul desktop, ma fa una differenza decente sul cellulare. Facciamo un minor numero di chiamate Math.random () e utilizziamo tutti quei bit casuali invece di buttare via l'87% di essi con un buffer casuale che viene spostato di ogni iterazione. Spostiamo anche la definizione del modello fuori dal ciclo, nel caso in cui aiuti:

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
}

Questo ci fa risparmiare il 10-30% a seconda della piattaforma. Non male. Ma il prossimo grande passo si sbarazza della funzione toString con un classico di ottimizzazione: la tabella di ricerca. Una semplice tabella di ricerca a 16 elementi eseguirà il lavoro di toString (16) in molto meno tempo:

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
}

La prossima ottimizzazione è un altro classico. Dato che stiamo trattando solo 4 bit di output in ogni iterazione del ciclo, tagliamo il numero di loop a metà e processiamo 8 bit per ogni iterazione. Questo è complicato dal momento che dobbiamo ancora gestire le posizioni di bit conformi a RFC, ma non è troppo difficile. Quindi dobbiamo creare una tabella di ricerca più grande (16x16 o 256) per memorizzare 0x00 - 0xff, e la compiliamo solo una volta, al di fuori della funzione 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
}

Ho provato un e6 () che elabora 16-bit alla volta, utilizzando ancora la LUT a 256 elementi, e ha mostrato i rendimenti decrescenti dell'ottimizzazione. Anche se ha avuto meno iterazioni, la logica interna è stata complicata dall'aumento dell'elaborazione, e ha funzionato allo stesso modo sul desktop, e solo ~ 10% più velocemente sui dispositivi mobili.

La tecnica di ottimizzazione finale da applicare: srotolare il ciclo. Dal momento che stiamo eseguendo un ciclo di un numero fisso di volte, possiamo tecnicamente scrivere tutto questo a mano. L'ho provato una volta con una singola variabile casuale r che ho continuato a riassegnare, e le prestazioni sono state sfruttate. Ma con quattro variabili assegnate in anticipo ai dati casuali, quindi utilizzando la tabella di ricerca e applicando i bit RFC corretti, questa versione li fuma tutti:

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

La cosa divertente è che generare 16 byte di dati casuali è la parte facile. L'intero trucco è esprimerlo in formato String con la conformità RFC, ed è il risultato più stretto con 16 byte di dati casuali, un loop srotolato e una tabella di ricerca.

Spero che la mia logica sia corretta - è molto facile fare un errore in questo tipo di noioso lavoro di bit. Ma le uscite mi sembrano buone. Spero ti sia piaciuto questo giro folle attraverso l'ottimizzazione del codice!

Essere informati: il mio obiettivo principale era mostrare e insegnare potenziali strategie di ottimizzazione. Altre risposte trattano argomenti importanti come collisioni e numeri veramente casuali, che sono importanti per generare buoni UUID.


305



Ecco un codice basato su RFC 4122, sezione 4.4 (Algoritmi per la creazione di un UUID da numero veramente casuale o pseudo-casuale).

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



Il GUID più veloce come il metodo del generatore di stringhe nel formato XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX. Questo non genera GUID conforme allo standard.

Dieci milioni di esecuzioni di questa implementazione richiedono solo 32,5 secondi, il più veloce che abbia mai visto in un browser (l'unica soluzione senza loop / iterazioni).

La funzione è semplice come:

/**
 * 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();
}

Per testare le prestazioni, è possibile eseguire questo codice:

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

Sono sicuro che molti di voi capiranno cosa ho fatto lì, ma forse c'è almeno una persona che avrà bisogno di una spiegazione:

L'algoritmo:

  • Il Math.random() funzione restituisce un numero decimale compreso tra 0 e 1 con 16 cifre dopo il punto decimale della frazione (per esempio 0.4363923368509859).
  • Quindi prendiamo questo numero e convertiamo a una stringa con base 16 (dall'esempio sopra otterremo 0.6fb7687f).
    Math.random().toString(16).
  • Quindi interrompiamo il 0. prefisso (0.6fb7687f => 6fb7687f) e ottieni una stringa con otto esadecimali personaggi lunghi.
    (Math.random().toString(16).substr(2,8).
  • A volte il Math.random()la funzione ritornerà numero più breve (ad esempio 0.4363), a causa di zeri alla fine (dall'esempio sopra, in realtà il numero è 0.4363000000000000). Ecco perché sto aggiungendo questa stringa "000000000" (una stringa con nove zeri) e poi tagliandola con substr() funzione per renderlo esattamente nove caratteri (riempiendo gli zeri a destra).
  • Il motivo per cui si aggiungono esattamente nove zeri è a causa dello scenario peggiore, che è quando il Math.random() la funzione restituirà esattamente 0 o 1 (probabilità di 1/10 ^ 16 per ognuno di essi). Ecco perché abbiamo dovuto aggiungere nove zeri ("0"+"000000000" o "1"+"000000000"), quindi tagliandolo dal secondo indice (3 ° carattere) con una lunghezza di otto caratteri. Per il resto dei casi, l'aggiunta di zeri non danneggerà il risultato perché lo sta tagliando comunque.
    Math.random().toString(16)+"000000000").substr(2,8).

L'assemblea:

  • Il GUID è nel seguente formato XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX.
  • Ho diviso il GUID in 4 pezzi, ogni pezzo diviso in 2 tipi (o formati): XXXXXXXX e -XXXX-XXXX.
  • Ora sto costruendo il GUID utilizzando questi 2 tipi per assemblare il GUID con chiamata 4 pezzi, come segue: XXXXXXXX  -XXXX-XXXX  -XXXX-XXXX  XXXXXXXX.
  • Per distinguere tra questi due tipi, ho aggiunto un parametro flag a una funzione creator di coppia _p8(s), il s parametro indica alla funzione se aggiungere trattini o meno.
  • Alla fine costruiamo il GUID con il seguente concatenamento: _p8() + _p8(true) + _p8(true) + _p8()e restituirlo.

Link a questo post sul mio blog

Godere! :-)


78



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

Se gli ID sono generati più di 1 millisecondo, sono unici al 100%.

Se due ID sono generati a intervalli più brevi e supponendo che il metodo casuale sia veramente casuale, questo genererebbe ID che sono 99.9999999999999999% che possono essere globalmente unici (collisione in 1 su 10 ^ 15)

È possibile aumentare questo numero aggiungendo più cifre, ma per generare ID unici al 100% è necessario utilizzare un contatore globale.

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


68