243 583 606 221 817 150 598 111 409 x Plus d'entropie

je recommande d'utiliser crypto.randomBytes . Ce n'est pas sha1 , mais pour l'identification, c'est plus rapide, et tout comme "aléatoire".

var id = crypto.randomBytes(20).toString('hex');
//=> f26d60305dae929ef8640a75e70dd78ab809cfe9

la chaîne résultante sera deux fois plus longue que les octets aléatoires que vous générez; chaque octet encodé à hex est de 2 caractères. 20 octets seront 40 caractères de hexadécimal.

en utilisant 20 octets, nous avons 256^20 ou 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976 uniques valeurs de sortie. C'est identique aux sorties possibles de 160 bits (20 octets) de SHA1.

sachant cela, ce n'est pas vraiment significatif pour nous de shasum nos octets aléatoires. C'est comme rouler une filière deux fois mais n'accepter que le deuxième rouleau; peu importe ce que, vous avez 6 résultats possibles chaque rouleau, donc le premier rouleau est suffisant.

---

Pourquoi est-ce mieux?

Pour comprendre pourquoi c'est mieux, nous devons d'abord comprendre comment les fonctions de hachage du travail. Les fonctions de hachage (y compris SHA1) généreront toujours la même sortie si la même entrée est donnée.

disent que nous voulons générer des IDs mais notre entrée aléatoire est générée par un lancer de pièce. Nous avons "heads" ou "tails"

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

% echo -n "tails" | shasum
71ac9eed6a76a285ae035fe84a251d56ae9485a4  -

si "heads" revient, la sortie SHA1 sera le même comme il était la première fois

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

Ok, donc un lancer de pièce n'est pas un grand générateur d'ID aléatoire parce que nous n'avons que 2 sorties possibles.

si nous utilisons une matrice standard à 6 côtés, nous avons 6 entrées possibles. Devinez combien de sorties SHA1 possibles? 6!

input => (sha1) => output
1 => 356a192b7913b04c54574d18c28d46e6395428ab
2 => da4b9237bacccdf19c0760cab7aec4a8359010b0
3 => 77de68daecd823babbb58edb1c8e14d7106e83bb
4 => 1b6453892473a467d07372d45eb05abc2031647a
5 => ac3478d69a3c81fa62e60f5c3696165a4e5e6ac4
6 => c1dfd96eea8cc2b62785275bca38ac261256e278

il est facile de se faire des illusions penser juste parce que la sortie de notre fonction semble très aléatoire, qu'il est très aléatoire.

nous sommes tous les deux d'accord qu'un lancer de pièce ou un dé à 6 faces ferait un mauvais générateur d'id aléatoire, parce que nos possibles résultats SHA1 (la valeur que nous utilisons pour L'ID) sont très peu nombreux. Mais que faire si nous utilisons quelque chose qui a beaucoup plus de sorties? Comme un horodatage avec des millisecondes? Ou Math.random de JavaScript ? Ou même un combinaison de ces deux?!

calculons combien d'identifiants uniques nous obtiendrions ...

---

le caractère unique d'un horodatage avec des millisecondes

en utilisant (new Date()).valueOf().toString() , vous obtenez un numéro de 13 caractères (par exemple, 1375369309741 ). Cependant, comme il s'agit d'un numéro de mise à jour séquentielle (une fois par milliseconde), les sorties sont presque toujours les mêmes. Nous allons jetez un oeil

for (var i=0; i<10; i++) {
  console.log((new Date()).valueOf().toString());
}
console.log("OMG so not random");

// 1375369431838
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431839
// 1375369431840
// 1375369431840
// OMG so not random

pour être juste, à des fins de comparaison, dans une minute donnée (un temps d'exécution d'opération généreux), vous aurez 60*1000 ou 60000 uniques.

---

le caractère unique de Math.random

maintenant, en utilisant Math.random , en raison de la façon dont JavaScript représente 64 bits des nombres à virgule flottante, vous obtiendrez un nombre de longueur entre 13 et 24 caractères. Un plus, cela signifie plus de chiffres qui signifie plus d'entropie. Tout d'abord, nous devons trouver quelle est la longueur la plus probable.

le script ci-dessous va déterminer quelle longueur est la plus probable. Nous le faisons en générant 1 million de nombres aléatoires et en incrémentant un compteur basé sur le .length de chaque nombre.

// get distribution
var counts = [], rand, len;
for (var i=0; i<1000000; i++) {
  rand = Math.random();
  len  = String(rand).length;
  if (counts[len] === undefined) counts[len] = 0;
  counts[len] += 1;
}

// calculate % frequency
var freq = counts.map(function(n) { return n/1000000 *100 });

en divisant chaque compteur par 1 million, on obtient le Probabilité de la longueur du nombre retourné de Math.random .

len   frequency(%)
------------------
13    0.0004  
14    0.0066  
15    0.0654  
16    0.6768  
17    6.6703  
18    61.133  <- highest probability
19    28.089  <- second highest probability
20    3.0287  
21    0.2989  
22    0.0262
23    0.0040
24    0.0004

donc, même si ce n'est pas entièrement vrai, soyons généreux et disons que vous obtenez une sortie aléatoire de 19 caractères; 0.1234567890123456789 . Les premiers caractères seront toujours 0 et . , donc nous n'aurons que 17 caractères aléatoires. Cela nous laisse avec 10^17 +1 (pour possible 0 ; voir les notes ci-dessous) ou 100,000,000,0000,001 uniques.

---

combien d'entrées aléatoires pouvons-nous générer?

Ok, nous avons calculé le nombre de résultats pour une durée de MILLISECONDE et Math.random

      100,000,000,000,000,001 (Math.random)
*                      60,000 (timestamp)
-----------------------------
6,000,000,000,000,000,060,000

c'est un simple 6,000,000, 000,000,000, 060,000-sided die. Ou, pour rendre ce nombre plus humainement digestible, c'est à peu près le même nombre que

input                                            outputs
------------------------------------------------------------------------------
( 1×) 6,000,000,000,000,000,060,000-sided die    6,000,000,000,000,000,060,000
(28×) 6-sided die                                6,140,942,214,464,815,497,21
(72×) 2-sided coins                              4,722,366,482,869,645,213,696

ça sonne bien, non ? Eh bien, nous allons le découvrir ...

SHA1 produit une valeur de 20 octets, avec une possibilité de 256^20 Résultats. Donc on n'utilise pas SHA1 à plein potentiel. Bien combien sommes-nous à l'aide?

node> 6000000000000000060000 / Math.pow(256,20) * 100

a milliseconde timestamp and Math.random n'utilise que 4,11 e-27% du potentiel de 160 bits de SHA1!

generator               sha1 potential used
-----------------------------------------------------------------------------
crypto.randomBytes(20)  100%
Date() + Math.random()    0.00000000000000000000000000411%
6-sided die               0.000000000000000000000000000000000000000000000411%
A coin                    0.000000000000000000000000000000000000000000000137%

Saint chats, l'homme! Regardez tous les ces zéros. Combien de mieux vaut crypto.randomBytes(20) ? 243 583 606 221 817 150 598 111 409 times better.

---

Notes sur le +1 et la fréquence des zéros

si vous vous interrogez sur le +1 , il est possible pour Math.random de retourner un 0 ce qui signifie qu'il y a 1 résultat unique possible que nous devons rendre compte.

basé sur la discussion qui s'est produite ci-dessous, j'étais curieux au sujet de la fréquence un 0 viendrait. Voici un petit script, random_zero.js , j'ai fait pour obtenir quelques données

#!/usr/bin/env node
var count = 0;
while (Math.random() !== 0) count++;
console.log(count);

ensuite, je l'ai lancé en 4 threads( j'ai un processeur 4-core), ajoutant la sortie à un fichier

$ yes | xargs -n 1 -P 4 node random_zero.js >> zeroes.txt

Ainsi, il s'avère qu'un 0 n'est pas difficile à obtenir. Après 100 valeurs ont été enregistrées, le moyenne était de

1 3,164,854,823 randoms est 0

Cool! Plus de recherche serait nécessaire pour savoir si ce nombre est à la hauteur d'une distribution uniforme de v8 Math.random mise en œuvre

Ne dans le navigateur, trop !

EDIT: cela ne correspondait pas vraiment à la suite de ma réponse précédente. Je le laisse ici comme une deuxième réponse pour les gens qui pourraient être à la recherche de faire cela dans le navigateur.

vous pouvez faire ce côté client dans les navigateurs modernes, si vous voulez

// str byteToHex(uint8 byte)
//   converts a single byte to a hex string 
function byteToHex(byte) {
  return ('0' + byte.toString(16)).slice(-2);
}

// str generateId(int len);
//   len - must be an even number (default: 40)
function generateId(len) {
  var arr = new Uint8Array((len || 40) / 2);
  window.crypto.getRandomValues(arr);
  return [].map.call(arr, byteToHex).join("");
}

OK, allons voir !

generateId();
// "1e6ef8d5c851a3b5c5ad78f96dd086e4a77da800"

generateId(20);
// "d2180620d8f781178840"

exigences relatives au navigateur

Browser    Minimum Version
--------------------------
Chrome     11.0
Firefox    21.0
IE         11.0
Opera      15.0
Safari     5.1