Ich benutze diese Zeile, um eine sha1-ID für node.js zu generieren:

crypto.createHash('sha1').digest('hex');

Das Problem ist, dass jedes Mal dieselbe ID zurückgegeben wird.

Ist es möglich, dass jedes Mal eine zufällige ID generiert wird, damit ich sie als Datenbankdokument-ID verwenden kann?

Schauen Sie hier: Wie verwende ich node.js Crypto, um einen HMAC-SHA1-Hash zu erstellen? Ich würde einen Hash des aktuellen Zeitstempels + eine Zufallszahl erstellen, um die Eindeutigkeit des Hash sicherzustellen:

var current_date = (new Date()).valueOf().toString();
var random = Math.random().toString();
crypto.createHash('sha1').update(current_date + random).digest('hex');

243.583.606.221.817.150.598.111.409x mehr Entropie

Ich würde empfehlen, crypto.randomBytes zu verwenden . Es ist nicht sha1, aber für ID-Zwecke ist es schneller und genauso "zufällig".

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

Die resultierende Zeichenfolge ist doppelt so lang wie die von Ihnen generierten zufälligen Bytes. Jedes in Hex codierte Byte besteht aus 2 Zeichen. 20 Bytes sind 40 hexadezimale Zeichen.

Bei Verwendung von 20 Bytes haben wir 256^20oder 1.461.501.637.330.902.918.203.684.832.716.283.019.655.932.542.976 eindeutige Ausgabewerte. Dies ist identisch mit den möglichen 160-Bit-Ausgängen (20 Byte) von SHA1.

Wenn wir das wissen, ist es für uns für shasumunsere zufälligen Bytes nicht wirklich bedeutungsvoll . Es ist, als würde man zweimal einen Würfel werfen, aber nur den zweiten Wurf akzeptieren. Egal was passiert, Sie haben 6 mögliche Ergebnisse pro Wurf, also ist der erste Wurf ausreichend.

Warum ist das besser?

Um zu verstehen, warum dies besser ist, müssen wir zuerst verstehen, wie Hashing-Funktionen funktionieren. Hashing-Funktionen (einschließlich SHA1) erzeugen immer die gleiche Ausgabe, wenn die gleiche Eingabe gegeben wird.

Angenommen, wir möchten IDs generieren, aber unsere zufällige Eingabe wird durch einen Münzwurf generiert. Wir haben "heads"oder"tails"

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

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

Wenn "heads"es erneut angezeigt wird, ist der SHA1-Ausgang derselbe wie beim ersten Mal

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

Ok, ein Münzwurf ist also kein großartiger Zufallsgenerator, da wir nur zwei mögliche Ausgaben haben.

Wenn wir einen standardmäßigen 6-seitigen Würfel verwenden, haben wir 6 mögliche Eingänge. Ratet mal, wie viele mögliche SHA1-Ausgänge? 6!

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

Es ist einfach , sie zu täuschen , indem nur weil die Leistung unserer Funktion Denken sieht sehr zufällig, dass es ist sehr zufällig.

Wir sind uns beide einig, dass ein Münzwurf oder ein 6-seitiger Würfel einen schlechten Zufallsgenerator erzeugen würde, da unsere möglichen SHA1-Ergebnisse (der Wert, den wir für die ID verwenden) sehr gering sind. Aber was ist, wenn wir etwas verwenden, das viel mehr Ausgänge hat? Wie ein Zeitstempel mit Millisekunden? Oder JavaScript Math.random? Oder sogar eine Kombination dieser beiden?!

Berechnen wir, wie viele eindeutige IDs wir erhalten würden ...

Die Einzigartigkeit eines Zeitstempels mit Millisekunden

Bei Verwendung erhalten (new Date()).valueOf().toString()Sie eine 13-stellige Nummer (z 1375369309741. B. ). Da dies jedoch eine fortlaufend aktualisierte Zahl ist (einmal pro Millisekunde), sind die Ausgänge fast immer gleich. Lass uns mal sehen

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

Um zu Vergleichszwecken fair zu sein, haben Sie in einer bestimmten Minute (eine großzügige Ausführungszeit für Operationen) 60*1000oder haben Sie 60000Unikate.

Die Einzigartigkeit von Math.random

Bei Verwendung Math.randomvon JavaScript erhalten Sie aufgrund der Darstellung von 64-Bit-Gleitkommazahlen eine Zahl mit einer Länge zwischen 13 und 24 Zeichen. Ein längeres Ergebnis bedeutet mehr Ziffern, was mehr Entropie bedeutet. Zuerst müssen wir herausfinden, welche Länge am wahrscheinlichsten ist.

Das folgende Skript bestimmt, welche Länge am wahrscheinlichsten ist. Dazu generieren wir 1 Million Zufallszahlen und erhöhen einen Zähler basierend auf der .lengthvon jeder Zahl.

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

Durch Teilen jedes Zählers durch 1 Million erhalten wir die Wahrscheinlichkeit der Länge der zurückgegebenen Zahl 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

Also, auch wenn es nicht ganz stimmt, lassen Sie uns großzügig sein und sagen, Sie erhalten eine 19 Zeichen lange zufällige Ausgabe; 0.1234567890123456789. Die ersten Zeichen werden immer 0und sein ., also bekommen wir wirklich nur 17 zufällige Zeichen. Dies lässt uns 10^17 +1(für möglich 0; siehe Anmerkungen unten) oder 100.000.000.000.000.001 Unikate.

Wie viele zufällige Eingaben können wir also generieren?

Ok, wir haben die Anzahl der Ergebnisse für einen Millisekunden-Zeitstempel berechnet und Math.random

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

Das ist ein einzelner 6.000.000.000.000.000.000.060.000-seitiger Würfel. Oder, um diese Zahl menschlicher verdaulich zu machen, ist dies ungefähr die gleiche Zahl wie

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

Klingt ziemlich gut, oder? Nun, lass es uns herausfinden ...

SHA1 erzeugt einen 20-Byte-Wert mit möglichen 256 ^ 20 Ergebnissen. Wir nutzen SHA1 also wirklich nicht in vollem Umfang. Wie viel verbrauchen wir?

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

Ein Millisekunden-Zeitstempel und Math.random nutzen nur 4,11 bis 27 Prozent des 160-Bit-Potenzials von SHA1!

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

Heilige Katzen, Mann! Schau dir all diese Nullen an. Wie viel besser ist es also crypto.randomBytes(20)? 243.583.606.221.817.150.598.111.409 mal besser.

Hinweise zur +1und Häufigkeit von Nullen

Wenn Sie sich über das wundern +1, können Sie Math.randomein zurückgeben, 0was bedeutet, dass wir noch 1 mögliches eindeutiges Ergebnis berücksichtigen müssen.

Aufgrund der Diskussion, die unten stattfand, war ich neugierig auf die Häufigkeit, mit der a 0auftauchen würde. Hier ist ein kleines Skript random_zero.js, das ich erstellt habe, um einige Daten zu erhalten

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

Dann habe ich es in 4 Threads ausgeführt (ich habe einen 4-Core-Prozessor) und die Ausgabe an eine Datei angehängt

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

Es stellt sich also heraus, dass a 0nicht so schwer zu bekommen ist. Nachdem 100 Werte aufgezeichnet wurden, betrug der Durchschnitt

1 in 3.164.854.823 Zufälligkeiten ist eine 0

Cool! Weitere Untersuchungen wären erforderlich, um zu wissen, ob diese Zahl einer gleichmäßigen Verteilung der Math.randomImplementierung von v8 entspricht

Mach es auch im Browser!

EDIT: Das passte nicht wirklich in den Fluss meiner vorherigen Antwort. Ich lasse es hier als zweite Antwort für Leute, die dies im Browser tun möchten.

Sie können diese Client-Seite in modernen Browsern ausführen, wenn Sie möchten

// 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 = 40) {
  var arr = new Uint8Array(len / 2);
  window.crypto.getRandomValues(arr);
  return Array.from(arr, byteToHex).join("");
}

console.log(generateId())
// "1e6ef8d5c851a3b5c5ad78f96dd086e4a77da800"

console.log(generateId(20))
// "d2180620d8f781178840"

Browseranforderungen

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