Question Créer un GUID / UUID en JavaScript?


J'essaie de créer des identifiants uniques au monde en JavaScript. Je ne suis pas sûr de ce que les routines sont disponibles sur tous les navigateurs, comment "aléatoire" et ensemencé le générateur de nombres aléatoires intégré est, etc.

Le GUID / UUID doit contenir au moins 32 caractères et doit rester dans la plage ASCII pour éviter les problèmes lors de leur transmission.


3207


origine


Réponses:


Il y a eu quelques tentatives à ce sujet. La question est: voulez-vous des GUID réels, ou juste des nombres aléatoires Regardez comme les GUID? C'est assez facile de générer des nombres aléatoires.

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

Cependant, notez que de telles valeurs ne sont pas de véritables GUID.

Il n'y a aucun moyen de générer des GUID réels en Javascript, car ils dépendent des propriétés de l'ordinateur local que les navigateurs n'exposent pas. Vous devrez utiliser des services spécifiques au système d'exploitation tels que ActiveX: http://p2p.wrox.com/topicindex/20339.htm

Edit: pas correct - RFC4122 permet des GUID aléatoires ("version 4"). Voir d'autres réponses pour des détails.

Remarque: l'extrait de code fourni ne suit pas RFC4122 qui nécessite que la version (4) doit être intégré dans la chaîne de sortie générée. N'utilise pas cette réponse si vous avez besoin de GUID conformes.

Utilisation:

var uuid = guid();

Démonstration

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



Pour un RFC4122 solution conforme à la version 4, cette solution à un seul liner (ish) est la plus compacte que je puisse trouver:

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

Mise à jour, 2015-06-02: Sachez que l'unicité de l'UUID repose fortement sur le générateur de nombres aléatoires (RNG) sous-jacent. La solution ci-dessus utilise Math.random() pour la brièveté, cependant Math.random() est ne pas garantie d'être un RNG de haute qualité. Voir Adam Hyland's excellente rédaction sur Math.random () pour plus de détails. Pour une solution plus robuste, pensez à quelque chose comme le module uuid[Disclaimer: Je suis l'auteur], qui utilise des API RNG de meilleure qualité lorsqu'elles sont disponibles.

Mise à jour, 2015-08-26: En note, cette essentiel décrit comment déterminer combien d'identifiants peuvent être générés avant d'atteindre une certaine probabilité de collision. Par exemple, avec 3.26x1015 version 4 RFU4122 UUID vous avez 1 chance sur un million de collision.

Mise à jour, 2017-06-28: UNE bon article des développeurs Chrome discuter de l'état de la qualité PRNG de Math.random dans Chrome, Firefox et Safari. tl; dr - Fin 2015, c'est "plutôt bien", mais pas de qualité cryptographique. Pour résoudre ce problème, voici une version mise à jour de la solution ci-dessus qui utilise ES6, la crypto API, et un peu de JS wizardy je ne peux pas prendre le crédit pour:

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



J'aime vraiment comment nettoyer La réponse de Broofa est, mais il est regrettable que les mauvaises implémentations de Math.random laisser la chance de collision.

Voici un similaire RFC4122 solution conforme à la version 4 qui résout ce problème en décalant les 13 premiers nombres hexadécimaux par une partie hexadécimale de l'horodatage. De cette façon, même si Math.randomest sur le même germe, les deux clients devraient générer l'UUID à exactement la même milliseconde (ou 10 000+ ans plus tard) pour obtenir le même 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);
    });
}


Voici un violon à tester.


671



La réponse de Broofa est assez lisse, en effet - incroyablement intelligente, vraiment ... rfc4122 conforme, un peu lisible, et compact. Impressionnant!

Mais si vous regardez cette expression régulière, ces nombreux replace() rappels, toString()'le sable Math.random() appels de fonction (où il utilise seulement 4 bits du résultat et gaspiller le reste), vous pouvez commencer à s'interroger sur la performance. En effet, joelpt a même décidé de lancer RFC pour la vitesse GUID générique avec generateQuickGUID.

Mais, pouvons-nous obtenir de la vitesse et Conformité RFC? Je dis oui!  Pouvons-nous maintenir la lisibilité? Eh bien ... Pas vraiment, mais c'est facile si vous suivez.

Mais d'abord, mes résultats, par rapport à Broofa, guid (la réponse acceptée), et la non-rfc-conforme 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.

Donc, par ma sixième itération d'optimisations, j'ai battu la réponse la plus populaire par 12X, la réponse acceptée par plus de 9X, et la réponse rapide non conforme par 2-3X. Et je suis toujours compatible avec rfc4122.

Intéressé par comment? J'ai mis la source complète sur http://jsfiddle.net/jcward/7hyaC/3/ et sur http://jsperf.com/uuid-generator-opt/4

Pour une explication, commençons par le code de 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);
});

Donc, il remplace x avec n'importe quel nombre hexadécimal aléatoire, y avec des données aléatoires (sauf forcer les 2 premiers bits à 10 selon la spécification RFC), et l'expression régulière ne correspond pas à - ou 4 caractères, de sorte qu'il n'a pas à faire face à eux. Très, très lisse.

La première chose à savoir est que les appels de fonctions sont chers, tout comme les expressions régulières (bien qu'il n'utilise que 1, il a 32 rappels, un pour chaque correspondance, et dans chacun des 32 rappels il appelle Math.random () et v. toString (16)).

La première étape vers la performance est d'éliminer le RegEx et ses fonctions de rappel et d'utiliser une simple boucle à la place. Cela signifie que nous devons faire face à la - et 4 caractères alors que Broofa n'a pas. Notez également que nous pouvons utiliser l'indexation String Array pour conserver son architecture Slick 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;
}

Fondamentalement, la même logique interne, sauf que nous vérifions pour - ou 4, et en utilisant une boucle while (au lieu de replace() callbacks) nous apporte une amélioration de près de 3X!

La prochaine étape est un petit sur le bureau, mais fait une différence décente sur mobile. Faisons moins d'appels Math.random () et utilisons tous ces bits aléatoires au lieu de jeter 87% d'entre eux avec un tampon aléatoire qui est déplacé à chaque itération. Déplaçons également cette définition de modèle hors de la boucle, juste au cas où cela aiderait:

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
}

Cela nous permet d'économiser 10-30% selon la plate-forme. Pas mal. Mais la prochaine grande étape se débarrasse complètement des appels de fonction toString avec un classique d'optimisation - la table de recherche. Une simple table de recherche de 16 éléments effectuera le travail de toString (16) en beaucoup moins de temps:

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 prochaine optimisation est un autre classique. Puisque nous ne traitons que 4 bits de sortie dans chaque itération de boucle, diminuons le nombre de boucles de moitié et traitons 8 bits à chaque itération. C'est difficile car nous devons encore gérer les positions de bit RFC, mais ce n'est pas trop dur. Nous devons ensuite créer une table de recherche plus grande (16x16, ou 256) pour stocker 0x00 - 0xff, et nous la construisons une seule fois, en dehors de la fonction 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
}

J'ai essayé un e6 () qui traite 16 bits à la fois, en utilisant toujours le LUT à 256 éléments, et il a montré les rendements décroissants de l'optimisation. Bien qu'il ait eu moins d'itérations, la logique interne a été compliquée par le traitement accru, et il a effectué la même chose sur le bureau, et seulement ~ 10% plus rapide sur mobile.

La dernière technique d'optimisation à appliquer - dérouler la boucle. Puisque nous bouclons un nombre fixe de fois, nous pouvons techniquement tout écrire à la main. J'ai essayé ceci une fois avec une seule variable aléatoire r que j'ai continué à réattribuer, et la performance tankée. Mais avec quatre variables assignées à l'avance des données aléatoires, puis en utilisant la table de recherche, et en appliquant les bons bits RFC, cette version les fume tous:

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

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

La chose amusante est, générant 16 octets de données aléatoires est la partie facile. L'astuce consiste à l'exprimer au format String avec la conformité RFC, et il est le plus étroitement accompli avec 16 octets de données aléatoires, une boucle déroulée et une table de recherche.

J'espère que ma logique est correcte - il est très facile de faire une erreur dans ce genre de travail fastidieux. Mais les sorties me semblent bonnes. J'espère que vous avez apprécié cette course folle à travers l'optimisation du code!

Soyez avisé: mon objectif principal était de montrer et d'enseigner des stratégies d'optimisation potentielles. D'autres réponses couvrent des sujets importants tels que les collisions et les nombres vraiment aléatoires, qui sont importants pour générer de bons UUID.


305



Voici un code basé sur RFC 4122, section 4.4 (Algorithmes pour créer un UUID à partir d'un nombre vraiment aléatoire ou pseudo-aléatoire).

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



GUID le plus rapide comme la méthode de générateur de chaîne dans le format XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX. Cela ne génère pas de GUID conforme aux normes.

Dix millions d'exécutions de cette implémentation ne prennent que 32,5 secondes, ce qui est le plus rapide que j'ai jamais vu dans un navigateur (la seule solution sans boucles / itérations).

La fonction est aussi simple que:

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

Pour tester la performance, vous pouvez exécuter ce code:

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

Je suis sûr que la plupart d'entre vous comprendront ce que j'ai fait là-bas, mais il y a peut-être au moins une personne qui aura besoin d'une explication:

L'algorithme:

  • le Math.random() La fonction renvoie un nombre décimal compris entre 0 et 1 avec 16 chiffres après le point de fraction décimale (pour Exemple 0.4363923368509859).
  • Ensuite, nous prenons ce nombre et convertissons à une chaîne avec base 16 (de l'exemple ci-dessus, nous aurons 0.6fb7687f).
    Math.random().toString(16).
  • Ensuite, nous avons coupé la 0. préfixe (0.6fb7687f => 6fb7687f) et obtenir une chaîne avec huit hexadécimal Longs caractères.
    (Math.random().toString(16).substr(2,8).
  • Parfois l Math.random()la fonction reviendra nombre plus court (par exemple 0.4363), en raison des zéros à la fin (de l'exemple ci-dessus, en fait le nombre est 0.4363000000000000). Voilà pourquoi je joins à cette chaîne "000000000" (une chaîne avec neuf zéros), puis en le coupant avec substr() Fonction pour faire exactement neuf caractères (remplissage des zéros vers la droite).
  • La raison de l'ajout exact de neuf zéros est à cause du pire scénario, qui est quand le Math.random() La fonction retournera exactement 0 ou 1 (probabilité de 1/10 ^ 16 pour chacun d'entre eux). C'est pourquoi nous avions besoin d'ajouter neuf zéros ("0"+"000000000" ou "1"+"000000000"), puis en le coupant du deuxième index (3ème caractère) avec une longueur de huit caractères. Pour le reste des cas, l'ajout de zéros ne nuira pas au résultat car il le coupe de toute façon.
    Math.random().toString(16)+"000000000").substr(2,8).

L'Assemblée:

  • Le GUID est dans le format suivant XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX.
  • J'ai divisé le GUID en 4 morceaux, chaque pièce étant divisée en 2 types (ou formats): XXXXXXXX et -XXXX-XXXX.
  • Maintenant, je construis le GUID en utilisant ces 2 types pour assembler le GUID avec l'appel 4 pièces, comme suit: XXXXXXXX  -XXXX-XXXX  -XXXX-XXXX  XXXXXXXX.
  • Pour différer entre ces deux types, j'ai ajouté un paramètre de drapeau à une fonction de créateur de paire _p8(s), la s Le paramètre indique à la fonction si les tirets doivent être ajoutés ou non.
  • Finalement, nous construisons le GUID avec le chaînage suivant: _p8() + _p8(true) + _p8(true) + _p8()et retournez-le.

Lien vers cet article sur mon blog

Prendre plaisir! :-)


78



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

Si les ID sont générés à plus d'une milliseconde d'intervalle, ils sont uniques à 100%.

Si deux ID sont générés à des intervalles plus courts, et en supposant que la méthode aléatoire est vraiment aléatoire, cela génèrerait des ID qui sont 99,99999999999999% susceptibles d'être globalement uniques (collision dans 1 sur 10 ^ 15)

Vous pouvez augmenter ce nombre en ajoutant plus de chiffres, mais pour générer 100% d'ID uniques, vous devrez utiliser un compteur global.

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


68



Voici une combinaison de top réponse votée, avec une solution de contournement pour Les collisions de 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);
        });
    };

Sur jsbin si vous voulez le tester.


57