Создать GUID / UUID в JavaScript?

Я пытаюсь создать глобально уникальные идентификаторы в JavaScript. Я не уверен, какие подпрограммы доступны во всех браузерах, насколько «случайным» и затравленным является встроенный генератор случайных чисел и т. Д.

GUID / UUID должен быть не менее 32 символов и должен оставаться в диапазоне ASCII, чтобы избежать проблем при их передаче.

3519

Решение

UUID (универсальный уникальный идентификатор), также известный как GUID (глобальный уникальный идентификатор), в соответствии с RFC 4122, являются идентификаторами с определенной гарантией уникальности.

Лучший способ их генерирования — следовать инструкциям по реализации в указанном RFC, использовать одну из многих проверенных реализаций с открытым исходным кодом или использовать встроенную реализацию для языков, в которых она есть.

Некоторые примеры инструментов с открытым исходным кодом для работы с UUID, для некоторых популярных языков программирования перечислены здесь.

JavaScript

PHP

Идти

Рубин

питон


Обратите внимание, что просто случайная генерация идентификаторов побайтово или посимвольно не даст вам таких же гарантий, как соответствующая реализация. Кроме того, очень важно, что системы, работающие с совместимыми UUID, могут не принимать случайно сгенерированные, и многие валидаторы с открытым исходным кодом фактически проверяют правильность структуры.

UUID должен иметь этот формат:

xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

Где M а также N позиции могут иметь только определенные значения. В настоящее время единственными допустимыми значениями для M являются 1, 2, 3, 4 и 5, поэтому случайная генерация этой позиции сделает большинство результатов неприемлемыми.

2086

Другие решения

Для RFC4122 решение, совместимое с версией 4, это однострочное (ish) решение — самое компактное, которое я мог придумать:

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

Обновление, 2015-06-02Имейте в виду, что уникальность UUID в значительной степени зависит от базового генератора случайных чисел (RNG). Решение выше использует Math.random() для краткости, однако Math.random() является не гарантированно будет качественный ГСЧ. Смотрите Адама Хайленда отличная рецензия на Math.random () для деталей. Для более надежного решения рассмотрим что-то вроде модуль uuid[Отказ от ответственности: я автор], который использует API RNG более высокого качества, где это возможно.

Обновление, 2015-08-26: Как примечание, это суть описывает, как определить, сколько идентификаторов может быть сгенерировано до достижения определенной вероятности столкновения. Например, с 3.26×1015 версия 4 RFC4122 UUID у вас есть шанс столкновения 1 на миллион.

Обновление, 2017-06-28: A хорошая статья от разработчиков Chrome обсуждение состояния Math.random PRNG в Chrome, Firefox и Safari. tl; dr — По состоянию на конец 2015 года это «довольно хорошо», но не криптографическое качество. Чтобы решить эту проблему, вот обновленная версия вышеупомянутого решения, которое использует ES6, crypto API и немного волшебства JS, я не могу взять кредит на:

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

Мне очень нравится как чисто Бруфа ответ есть, но, к сожалению, плохие реализации Math.random оставь шанс на столкновение.

Вот похожий RFC4122 совместимое с версией 4 решение, которое решает эту проблему путем смещения первых 13 шестнадцатеричных чисел на шестнадцатеричную часть метки времени. Таким образом, даже если Math.random на одном и том же начальном этапе оба клиента должны будут сгенерировать UUID в одну и ту же миллисекунду (или более 10 000 лет спустя), чтобы получить тот же 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);
});
}

Вот скрипка для проверки.

+723

Ответ broofa довольно приятный, действительно — впечатляюще умный, действительно … rfc4122-совместимый, несколько читабельный и компактный. Потрясающие!

Но если вы посмотрите на это регулярное выражение, те многие replace() обратные вызовы, toString()и Math.random() вызовы функций (когда он использует только 4 бита результата и тратит впустую все остальное), вы можете начать задумываться о производительности. Действительно, joelpt даже решил отказаться от RFC для общей скорости GUID с generateQuickGUID,

Но мы можем получить скорость а также Соответствие RFC? Я говорю да! Можем ли мы сохранить читабельность? Ну … Не совсем, но это легко, если вы будете следовать.

Но сначала мои результаты, по сравнению с бройфой, guid (принятый ответ) и не соответствующий RFC 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: 500k iterations, results will vary by browser/cpu.

Таким образом, благодаря шестой итерации оптимизаций, я опередил самый популярный ответ 12X, принятый ответ более 9X, и быстрый несоответствующий ответ 2-3x. И я все еще совместим с rfc4122.

Заинтересованы в том, как? Я поставил полный источник на http://jsfiddle.net/jcward/7hyaC/3/ и на http://jsperf.com/uuid-generator-opt/4

Для объяснения давайте начнем с кода брофы:

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

Так он заменяет x с любой случайной шестнадцатеричной цифрой, y со случайными данными (кроме форсирования 2 верхних битов 10 согласно спецификации RFC), и регулярное выражение не соответствует - или же 4 персонажи, поэтому он не должен иметь с ними дело. Очень, очень гладко.

Первое, что нужно знать, это то, что вызовы функций являются дорогими, как и регулярные выражения (хотя он использует только 1, он имеет 32 обратных вызова, по одному на каждое совпадение, и в каждом из 32 обратных вызовов он вызывает Math.random () и v. ToString (16)).

Первым шагом к производительности является устранение RegEx и его функций обратного вызова и использование вместо этого простого цикла. Это означает, что мы должны иметь дело с - а также 4 символов, тогда как брофа нет. Кроме того, обратите внимание, что мы можем использовать индексирование String Array, чтобы сохранить его простую архитектуру шаблона 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;
}

По сути, та же самая внутренняя логика, за исключением того, что мы проверяем - или же 4и используя цикл while (вместо replace() обратные вызовы) дает нам почти 3х улучшение!

Следующим шагом будет небольшой шаг на рабочем столе, но он будет иметь большое значение для мобильных устройств. Давайте сделаем меньше вызовов Math.random () и используем все эти случайные биты вместо того, чтобы выбрасывать 87% из них со случайным буфером, который смещается при каждой итерации. Давайте также уберем это определение шаблона из цикла, на случай, если это поможет:

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
}

Это экономит нам 10-30% в зависимости от платформы. Неплохо. Но следующий большой шаг избавляет от вызовов функции toString вместе с классикой оптимизации — справочной таблицей. Простая 16-элементная таблица поиска выполнит работу toString (16) за гораздо меньшее время:

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
}

Следующая оптимизация — еще одна классика. Поскольку в каждой итерации цикла мы обрабатываем только 4-битные выходные данные, давайте сократим количество циклов пополам и обработаем 8-битные в каждой итерации. Это сложно, так как нам все еще приходится обрабатывать битовые позиции, соответствующие RFC, но это не слишком сложно. Затем нам нужно создать таблицу поиска большего размера (16×16 или 256) для хранения 0x00 — 0xff, и мы создадим ее только один раз, вне функции 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
}

Я попробовал e6 (), который обрабатывает 16 бит одновременно, используя LUT из 256 элементов, и он показал убывающую отдачу от оптимизации. Несмотря на меньшее количество итераций, внутренняя логика усложнялась из-за увеличения обработки, и она выполняла то же самое на настольном компьютере и только на ~ 10% быстрее на мобильном устройстве.

Последняя применяемая техника оптимизации — разверните цикл. Поскольку мы зацикливаемся фиксированное количество раз, технически мы можем выписать все это вручную. Я попробовал это однажды с одной случайной переменной r, которую я продолжал перераспределять, и производительность снижалась. Но с четырьмя переменными, которым заранее назначены случайные данные, затем с помощью таблицы поиска и применения правильных битов RFC, эта версия выкуривает их все:

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

Modualized: http://jcward.com/UUID.jsUUID.generate()

Самое смешное, что генерация 16 байтов случайных данных — самая простая часть. Весь трюк состоит в том, чтобы выразить его в формате String с соблюдением требований RFC, и он наиболее тщательно выполнен с 16 байтами случайных данных, развернутым циклом и таблицей поиска.

Я надеюсь, что моя логика верна — очень легко ошибиться в этом утомительном занятии. Но результаты выглядят хорошо для меня. Надеюсь, вам понравилась эта безумная поездка благодаря оптимизации кода!

Имейте в виду: моей главной целью было показать и научить потенциальных стратегий оптимизации. Другие ответы охватывают важные темы, такие как столкновения и действительно случайные числа, которые важны для создания хороших UUID.

352

Вот код, основанный на RFC 4122, раздел 4.4 (Алгоритмы для создания UUID из действительно случайного или псевдослучайного числа).

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

Самый быстрый GUID, как метод строкового генератора в формате XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX, Это не генерирует стандартный GUID.

Десять миллионов выполнений этой реализации занимают всего 32,5 секунды, что является самым быстрым, что я когда-либо видел в браузере (единственное решение без циклов / итераций).

Функция так же проста, как:

/**
* Generates a GUID string.
* @returns {String} The generated GUID.
* @example af8a8416-6e18-a307-bd9c-f2c947bbb3aa
* @author Slavik Meltser ([email protected]).
* @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();
}

Чтобы проверить производительность, вы можете запустить этот код:

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

Я уверен, что большинство из вас поймет, что я там делал, но, возможно, есть хотя бы один человек, которому понадобится объяснение:

Алгоритм:

  • Math.random() функция возвращает десятичное число от 0 до 1 с 16 цифрами после запятой (для
    пример 0.4363923368509859).
  • Затем мы берем это число и конвертируем
    это в строку с основанием 16 (из примера выше мы получим
    0.6fb7687f).
    Math.random().toString(16),
  • Затем мы отрезаем 0. префикс (0.6fb7687f =>
    6fb7687f) и получить строку с восемью шестнадцатеричными
    персонажи длинные.
    (Math.random().toString(16).substr(2,8),
  • Иногда Math.random() функция вернется
    более короткий номер (например, 0.4363), из-за нулей в конце (из примера выше, на самом деле число 0.4363000000000000). Вот почему я добавляю в эту строку "000000000" (строка с девятью нулями), а затем отрезать его substr() функция, чтобы сделать его ровно девятью символами (заполняя нули справа).
  • Причиной добавления ровно девяти нулей является худший сценарий, когда Math.random() функция вернет ровно 0 или 1 (вероятность 1/10 ^ 16 для каждого из них). Вот почему нам нужно было добавить девять нулей ("0"+"000000000" или же "1"+"000000000"), а затем обрезать его из второго индекса (3-й символ) длиной восемь символов. В остальных случаях добавление нулей не повредит результату, так как он все равно обрезает его.
    Math.random().toString(16)+"000000000").substr(2,8),

Ассамблея:

  • GUID имеет следующий формат XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX,
  • Я разделил GUID на 4 части, каждая часть разделена на 2 типа (или форматы): XXXXXXXX а также -XXXX-XXXX,
  • Сейчас я строю GUID, используя эти 2 типа для сборки GUID с помощью вызова 4 частей, следующим образом: XXXXXXXX -XXXX-XXXX -XXXX-XXXX XXXXXXXX,
  • Чтобы различать эти два типа, я добавил параметр flag в функцию создания пары _p8(s), s Параметр сообщает функции, следует ли добавлять тире или нет.
  • В конце концов мы создаем GUID со следующей цепочкой: _p8() + _p8(true) + _p8(true) + _p8()и вернуть его.

Ссылка на этот пост в моем блоге

Наслаждайтесь! 🙂

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

Вот комбинация Топ проголосовал ответ, с обходным путем для Столкновения 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);
});
};

На jsbin если вы хотите проверить это.

60
По вопросам рекламы [email protected]