Я использую эту строку для генерации идентификатора sha1 для node.js:
crypto.createHash('sha1').digest('hex');
Проблема заключается в том, что он возвращает один и тот же идентификатор каждый раз.
Возможно ли, чтобы он каждый раз генерировал случайный идентификатор, поэтому я могу использовать его как идентификатор документа базы данных?
Посмотрите здесь: Как использовать node.js Crypto для создания хеша HMAC-SHA1? Я бы создал хэш текущей метки времени + случайное число, чтобы обеспечить уникальность хэша:
var current_date = (new Date()).valueOf().toString();
var random = Math.random().toString();
crypto.createHash('sha1').update(current_date + random).digest('hex');
Я бы порекомендовал использовать crypto.randomBytes. Это не sha1, но для id-целей, это быстрее, и просто как "случайный".
var id = crypto.randomBytes(20).toString('hex');
//=> f26d60305dae929ef8640a75e70dd78ab809cfe9
Результирующая строка будет в два раза длиннее случайных байтов, которые вы генерируете; каждый байт, закодированный в шестнадцатеричный код, состоит из 2 символов. 20 байтов будут 40 символами гекса.
Используя 20 байтов, мы имеем 256^20 или 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976 уникальных выходных значений. Это идентично 160-битным (20-байтовым) возможным выходам SHA1.
Зная это, нам не очень важно shasum наши случайные байты. Это как бросить кубик дважды, но только принять второй бросок; несмотря ни на что, у вас есть 6 возможных результатов в каждом броске, поэтому первого броска достаточно.
Почему это лучше?
Чтобы понять, почему это лучше, мы сначала должны понять, как работают функции хеширования. Функции хеширования (включая SHA1) всегда будут генерировать один и тот же вывод, если дан один и тот же ввод.
Скажем, мы хотим генерировать идентификаторы, но наш случайный ввод генерируется броском монеты. У нас есть "heads" или "tails"
% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f -
% echo -n "tails" | shasum
71ac9eed6a76a285ae035fe84a251d56ae9485a4 -
Если снова появятся "heads", выход SHA1 будет таким же, как в первый раз
% echo -n "heads" | shasum
c25dda249cdece9d908cc33adcd16aa05e20290f -
Итак, бросок монеты не является хорошим генератором случайных идентификаторов, потому что у нас есть только 2 возможных выхода.
Если мы используем стандартный 6-сторонний кристалл, у нас есть 6 возможных входов. Угадайте, сколько возможных выходов SHA1? 6!
input => (sha1) => output
1 => 356a192b7913b04c54574d18c28d46e6395428ab
2 => da4b9237bacccdf19c0760cab7aec4a8359010b0
3 => 77de68daecd823babbb58edb1c8e14d7106e83bb
4 => 1b6453892473a467d07372d45eb05abc2031647a
5 => ac3478d69a3c81fa62e60f5c3696165a4e5e6ac4
6 => c1dfd96eea8cc2b62785275bca38ac261256e278
Мы оба согласны с тем, что бросок монеты или шестигранный кубик могли бы стать плохим генератором случайных идентификаторов, потому что наших возможных результатов SHA1 (значение, которое мы используем для идентификатора) очень мало. Но что, если мы используем что-то, что имеет гораздо больше результатов? Как timestamp с миллисекундами? Или JavaScript Math.random? Или даже сочетание этих двух?
Давайте посчитаем, сколько уникальных идентификаторов мы получим...
Уникальность отметки времени с миллисекундами
При использовании (new Date()).valueOf().toString() вы получаете номер из 13 символов (например, 1375369309741). Однако, поскольку это последовательно обновляемое число (один раз в миллисекунду), выходные данные почти всегда одинаковы. Давай посмотрим
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
Чтобы быть справедливым, в целях сравнения, в данную минуту (щедрое время выполнения операции) у вас будет 60*1000 или 60000 уникальных значений.
Уникальность Math.random
Теперь, при использовании Math.random, из-за того, что JavaScript представляет 64-битные числа с плавающей запятой, вы получите число длиной от 13 до 24 символов. Более длинный результат означает больше цифр, что означает больше энтропии. Во-первых, нам нужно выяснить, какая длина наиболее вероятна.
Сценарий ниже определит, какая длина наиболее вероятна. Мы делаем это, генерируя 1 миллион случайных чисел и увеличивая счетчик в зависимости от .length каждого числа.
// 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 });
Разделив каждый счетчик на 1 миллион, мы получим вероятность длины числа, возвращенного из 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
Итак, хотя это не совсем так, давайте проявим щедрость и скажем, что вы получаете случайный вывод длиной 19 символов; 0.1234567890123456789. Первые символы всегда будут 0 и . так что на самом деле мы получаем только 17 случайных символов. Это оставляет нам 10^17 +1 (для возможных 0; см. Примечания ниже) или 100 000 000 000 000 001 уникальных.
Итак, сколько случайных входов мы можем генерировать?
Хорошо, мы вычислили количество результатов для отметки времени в миллисекундах и Math.random
100,000,000,000,000,001 (Math.random)
* 60,000 (timestamp)
-----------------------------
6,000,000,000,000,000,060,000
Это один 6 000 000 000 000 000 060 000 односторонний кубик. Или, чтобы сделать это число более удобоваримым, это примерно столько же, сколько
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
Звучит неплохо, правда? Ну, давай узнаем...
SHA1 выдает 20-байтовое значение с возможными 256 ^ 20 результатами. Таким образом, мы действительно не используем SHA1 для его полного потенциала. Ну, сколько мы используем?
node> 6000000000000000060000 / Math.pow(256,20) * 100
generator sha1 potential used
-----------------------------------------------------------------------------
crypto.randomBytes(20) 100%
Date() + Math.random() 0.00000000000000000000000000411%
6-sided die 0.000000000000000000000000000000000000000000000411%
A coin 0.000000000000000000000000000000000000000000000137%
Святые коты, мужик! Посмотри на все эти нули. Так насколько лучше crypto.randomBytes(20)? В 243 583 606 221 817 15050981111409 раз лучше.
Заметки о +1 и частоте нулей
Если вы задаетесь вопросом о +1, Math.random может вернуть 0 что означает, что мы должны учесть еще 1 уникальный результат.
Основываясь на обсуждении, которое произошло ниже, мне было любопытно, как будет расти частота 0. Вот небольшой скрипт random_zero.js, который я сделал, чтобы получить некоторые данные
#!/usr/bin/env node
var count = 0;
while (Math.random() !== 0) count++;
console.log(count);
Затем я запустил его в 4 потока (у меня 4-ядерный процессор), добавив вывод в файл
$ yes | xargs -n 1 -P 4 node random_zero.js >> zeroes.txt
Так что получается, что 0 не так сложно получить. После того, как было записано 100 значений, среднее значение было
1 в 3 164 854 823 рандомах - это 0
Здорово! Потребовались бы дополнительные исследования, чтобы узнать, соответствует ли это число равномерному распределению реализации v8 Math.random
РЕДАКТИРОВАТЬ: это действительно не вписывается в поток моего предыдущего ответа. Я оставляю это здесь в качестве второго ответа для людей, которые могут делать это в браузере.
Вы можете сделать это на стороне клиента в современных браузерах, если хотите
// 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"