Używam tej linii do generowania identyfikatora sha1 dla node.js:

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

Problem w tym, że za każdym razem zwraca ten sam identyfikator.

Czy jest możliwe, aby za każdym razem generował losowy identyfikator, abym mógł go używać jako identyfikatora dokumentu bazy danych?

Spójrz tutaj: Jak użyć kodu node.js Crypto do utworzenia skrótu HMAC-SHA1? Utworzyłbym hash aktualnego znacznika czasu + losową liczbę, aby zapewnić unikalność skrótu:

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 większa entropia

Polecam użycie crypto.randomBytes . Nie jest sha1, ale dla celów identyfikacyjnych jest szybszy i równie „losowy”.

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

Wynikowy ciąg będzie dwa razy dłuższy niż losowe bajty, które wygenerujesz; każdy bajt zakodowany w kodzie szesnastkowym to 2 znaki. 20 bajtów to 40 znaków szesnastkowych.

Korzystanie 20 bajtów, mamy 256^20lub 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976 unikalne wartości wyjściowe. Jest to identyczne z 160-bitowymi (20-bajtowymi) możliwymi wyjściami SHA1.

Wiedząc o tym, nie ma to dla nas znaczenia dla shasumnaszych losowych bajtów. To tak, jakby dwukrotnie rzucić kostką, ale zaakceptować tylko drugi rzut; nie ważne co, masz 6 możliwych wyników w każdym rzucie, więc pierwszy rzut jest wystarczający.

Dlaczego tak jest lepiej?

Aby zrozumieć, dlaczego jest to lepsze, musimy najpierw zrozumieć, jak działają funkcje haszujące. Funkcje haszujące (w tym SHA1) zawsze generują te same dane wyjściowe, jeśli podane są te same dane wejściowe.

Powiedzmy, że chcemy wygenerować identyfikatory, ale nasze losowe dane wejściowe są generowane przez rzut monetą. Mamy "heads"lub"tails"

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

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

Jeśli "heads"pojawi się ponownie, wyjście SHA1 będzie takie samo, jak za pierwszym razem

% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f  -

Ok, więc rzut monetą nie jest świetnym generatorem losowych identyfikatorów, ponieważ mamy tylko 2 możliwe wyjścia.

Jeśli używamy standardowej sześciościennej matrycy, mamy 6 możliwych wejść. Zgadnij, ile możliwych wyjść SHA1? 6!

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

Łatwo się oszukać, myśląc tylko dlatego, że wynik naszej funkcji wygląda bardzo przypadkowo, że jest bardzo przypadkowy.

Obaj zgadzamy się, że rzut monetą lub sześciościenna kostka stworzyłby zły generator losowych identyfikatorów, ponieważ nasze możliwe wyniki SHA1 (wartość, której używamy jako ID) są bardzo nieliczne. Ale co, jeśli użyjemy czegoś, co ma o wiele więcej wyników? Jak znacznik czasu z milisekundami? Albo JavaScript Math.random? A może nawet połączenie tych dwóch ?!

Obliczmy, ile unikalnych identyfikatorów otrzymalibyśmy ...

Wyjątkowość sygnatury czasowej z milisekundami

Podczas używania (new Date()).valueOf().toString()otrzymujesz 13-znakową liczbę (np 1375369309741.). Jednak ponieważ jest to numer aktualizowany sekwencyjnie (raz na milisekundę), wyniki są prawie zawsze takie same. Spójrzmy

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

Aby być uczciwym, dla celów porównawczych, w danej minucie (hojny czas wykonania operacji) będziesz mieć unikaty 60*1000lub 60000.

Wyjątkowość Math.random

Teraz, gdy używasz Math.random, ze względu na sposób, w jaki JavaScript reprezentuje 64-bitowe liczby zmiennoprzecinkowe, otrzymasz liczbę o długości od 13 do 24 znaków. Dłuższy wynik oznacza więcej cyfr, co oznacza większą entropię. Najpierw musimy dowiedzieć się, która długość jest najbardziej prawdopodobna.

Poniższy skrypt określi, która długość jest najbardziej prawdopodobna. Robimy to, generując 1 milion liczb losowych i zwiększając licznik na podstawie .lengthkażdej liczby.

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

Dzieląc każdy licznik przez 1 milion, otrzymujemy prawdopodobieństwo długości zwróconej liczby 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

Tak więc, nawet jeśli nie jest to do końca prawdą, bądźmy hojni i powiedzmy, że otrzymujesz losowe wyjście o długości 19 znaków; 0.1234567890123456789. Pierwsze postacie zawsze będą 0i ., więc tak naprawdę otrzymujemy tylko 17 losowych postaci. To pozostawia nam 10^17 +1(możliwe 0; zobacz uwagi poniżej) lub 100 000 000 000 000 001 unikatów.

Więc ile losowych danych wejściowych możemy wygenerować?

Ok, obliczyliśmy liczbę wyników dla milisekundowego znacznika czasu i Math.random

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

To pojedyncza kostka 6,000,000,000,000,000 060,000. Lub, aby uczynić tę liczbę bardziej strawną dla człowieka, jest to mniej więcej taka sama liczba jak

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

Brzmi całkiem nieźle, prawda? Cóż, dowiedzmy się ...

SHA1 generuje 20-bajtową wartość z możliwymi 256 ^ 20 wynikami. Więc naprawdę nie używamy SHA1 do pełnego potencjału. Ile używamy?

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

Milisekundowy znacznik czasu, a Math.random wykorzystuje tylko 4,11e-27 procent 160-bitowego potencjału SHA1!

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

Święte koty, człowieku! Spójrz na te wszystkie zera. Więc o ile lepiej crypto.randomBytes(20)? 243,583,606,221,817,150,598,111,409 razy lepszy.

Uwagi dotyczące +1i częstotliwości zer

Jeśli zastanawiasz się nad tym +1, możliwe Math.randomjest zwrócenie a, 0co oznacza, że ​​istnieje jeszcze jeden możliwy unikalny wynik, który musimy uwzględnić.

Opierając się na dyskusji, która odbyła się poniżej, byłem ciekawy, jaka 0będzie częstotliwość a . Oto mały skrypt, random_zero.jszrobiłem, aby uzyskać dane

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

Następnie uruchomiłem go w 4 wątkach (mam 4-rdzeniowy procesor), dołączając dane wyjściowe do pliku

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

Okazuje się więc, że 0nie jest to takie trudne. Po zarejestrowaniu 100 wartości średnia wyniosła

1 na 3164,854,823 randoms to 0

Chłodny! Wymagane byłyby dalsze badania, aby dowiedzieć się, czy ta liczba jest równa jednorodnemu rozkładowi Math.randomimplementacji wersji 8

Zrób to też w przeglądarce!

EDYCJA: to nie pasowało do mojej poprzedniej odpowiedzi. Zostawiam to tutaj jako drugą odpowiedź dla osób, które mogą chcieć to zrobić w przeglądarce.

Jeśli chcesz, możesz to zrobić po stronie klienta w nowoczesnych przeglądarkach

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

Wymagania dotyczące przeglądarki

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