Próbuję utworzyć unikalne globalnie identyfikatory w JavaScript. Nie jestem pewien, jakie procedury są dostępne we wszystkich przeglądarkach, jak „losowy” i zaszczepiony jest wbudowany generator liczb losowych itp.
Identyfikator GUID / UUID powinien mieć co najmniej 32 znaki i powinien pozostawać w zakresie ASCII, aby uniknąć problemów z ich przekazywaniem.
javascript
guid
uuid
Jason Cohen
źródło
źródło
Odpowiedzi:
Identyfikatory UUID (Universally Unique IDentifier), znane również jako GUID (Globally Unique IDentifier), zgodnie z RFC 4122 , są identyfikatorami zaprojektowanymi w celu zapewnienia pewnych gwarancji unikalności.
Chociaż możliwe jest zaimplementowanie UUID zgodnych z RFC w kilku liniach JS (np. Patrz odpowiedź @ broofa poniżej), istnieje kilka typowych pułapek:
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
”, gdzie x oznacza jeden z [0–9, af] M oznacza jeden z [1-5], a N oznacza [8, 9, a lub b]Math.random
)Dlatego programiści piszący kod dla środowisk produkcyjnych są zachęcani do stosowania rygorystycznej, dobrze utrzymanej implementacji, takiej jak moduł uuid .
źródło
W przypadku rozwiązania zgodnego z RFC4122 w wersji 4 to jedno-liniowe (ish) rozwiązanie jest najbardziej kompaktowe, jakie mogłem wymyślić:
Aktualizacja, 2015-06-02 : Należy pamiętać, że unikalność UUID w dużej mierze zależy od generatora liczb losowych (RNG). Powyższe rozwiązanie wykorzystuje
Math.random()
zwięzłość, jednak nieMath.random()
ma gwarancji, że będzie wysokiej jakości RNG. Szczegółowe informacje można znaleźć w znakomitym piśmie Adama Hylanda w Math.random () . Aby uzyskać bardziej niezawodne rozwiązanie, rozważ użycie modułu uuid , który używa interfejsów API RNG wyższej jakości.Aktualizacja, 26.08.2015 : Na marginesie, ta lista opisuje, jak ustalić, ile identyfikatorów można wygenerować przed osiągnięciem pewnego prawdopodobieństwa kolizji. Na przykład w przypadku UUID RFC4122 w wersji 3.26x10 15 w wersji 4 masz szansę na kolizję 1 na milion.
Aktualizacja, 28.06.2017 : Dobry artykuł od twórców Chrome omawiający stan jakości Math.random PRNG w Chrome, Firefox i Safari. tl; dr - Na koniec 2015 r. jest „całkiem niezły”, ale nie kryptograficzny. Aby rozwiązać ten problem, oto zaktualizowana wersja powyższego rozwiązania, która używa ES6,
crypto
interfejsu API i odrobiny czarodziejstwa JS, za które nie mogę liczyć :Aktualizacja, 2020-01-06 : W pracach jest propozycja standardowego
uuid
modułu jako części języka JSźródło
c== 'x'
zamiastc === 'x'
. Ponieważ jshint nie powiodło się.Bardzo podoba mi się, jak czysta jest odpowiedź Broofa , ale niefortunne jest to, że słabe implementacje
Math.random
pozostawiają szansę na kolizję.Oto podobne rozwiązanie zgodne z RFC4122 w wersji 4, które rozwiązuje ten problem poprzez przesunięcie pierwszych 13 liczb szesnastkowych o część szesnastkową znacznika czasu, a po wyczerpaniu przesunięcie o część szesnastkową mikrosekund od załadowania strony. W ten sposób, nawet jeśli
Math.random
znajduje się na tym samym ziarnie, obaj klienci musieliby wygenerować UUID dokładnie taką samą liczbę mikrosekund od czasu ładowania strony (jeśli obsługiwany jest czas wysokiej wydajności) ORAZ dokładnie w tej samej milisekundie (lub ponad 10 000 lat później), aby uzyskaj ten sam UUID:Oto skrzypce do przetestowania.
źródło
new Date().getTime()
nie jest aktualizowany co milisekundę. Nie jestem pewien, jak to wpływa na oczekiwaną losowość algorytmu.performance.now()
nie są ograniczone do rozdzielczości jednej milisekundy. Zamiast tego reprezentują czasy jako liczby zmiennoprzecinkowe z dokładnością do mikrosekundy . Również w przeciwieństwie do Date.now, wartości zwracane przez performance.now () zawsze rosną ze stałą szybkością , niezależnie od zegara systemowego, który może być regulowany ręcznie lub przekrzywiony przez oprogramowanie takie jak Network Time Protocol.d = Math.floor(d/16);
?Odpowiedź Broroofa jest naprawdę sprytna - imponująco sprytna, naprawdę ... zgodna z RFC4122, nieco czytelna i kompaktowa. Niesamowite!
Ale jeśli patrzysz na to wyrażenie regularne, te wiele
replace()
wywołań zwrotnych, wywołań funkcjitoString()
iMath.random()
funkcji (gdzie używa tylko 4 bitów wyniku i marnuje resztę), możesz zacząć zastanawiać się nad wydajnością. Rzeczywiście, joelpt postanowił nawet wyrzucić RFC dla ogólnej prędkości GUIDgenerateQuickGUID
.Ale czy możemy uzyskać szybkość i zgodność z RFC? Powiedziałem tak! Czy możemy zachować czytelność? Cóż ... Niezupełnie, ale łatwo jest postępować zgodnie z nimi.
Ale najpierw moje wyniki, w porównaniu do Broofa
guid
(zaakceptowana odpowiedź) i niezgodne z RFCgenerateQuickGuid
:Więc moim 6 iteracji optymalizacji, pobiłem najpopularniejszą odpowiedź o ponad 12X , przyjętym Odpowiedź na 9X , a odpowiedź szybko niezgodnego przez 2-3x . I nadal jestem zgodny z RFC4122.
W jaki sposób? Umieściłem pełne źródło na http://jsfiddle.net/jcward/7hyaC/3/ i na http://jsperf.com/uuid-generator-opt/4
Aby uzyskać wyjaśnienie, zacznijmy od kodu broofa:
Zastępuje więc
x
dowolną losową cyfrą szesnastkową,y
losowymi danymi (z wyjątkiem wymuszania 2 najwyższych bitów10
zgodnie ze specyfikacją RFC), a wyrażenie regularne nie pasuje do znaków-
lub4
, więc nie musi się z nimi obchodzić. Bardzo, bardzo zręczny.Pierwszą rzeczą, którą należy wiedzieć, jest to, że wywołania funkcji są drogie, podobnie jak wyrażenia regularne (chociaż używa tylko 1, ma 32 wywołania zwrotne, po jednym dla każdego dopasowania, a w każdym z 32 wywołań wywołuje Math.random () i v. toString (16)).
Pierwszym krokiem w kierunku wydajności jest wyeliminowanie RegEx i jego funkcji zwrotnych oraz użycie prostej pętli. Oznacza to, że mamy do czynienia z postaciami
-
i,4
podczas gdy Broofa nie. Zauważ też, że możemy użyć indeksowania tablicy ciągów, aby zachować jego elegancką architekturę szablonów ciągów:Zasadniczo ta sama wewnętrzna logika, z wyjątkiem tego, że sprawdzamy
-
lub4
, a użycie pętli while (zamiastreplace()
wywołań zwrotnych) daje nam prawie trzykrotną poprawę!Kolejny krok jest niewielki na komputerze, ale robi znaczną różnicę na urządzeniach mobilnych. Wykonajmy mniej wywołań Math.random () i wykorzystajmy wszystkie losowe bity zamiast wyrzucać 87% z nich losowym buforem, który jest przesuwany z każdą iteracją. Przenieśmy też tę definicję szablonu z pętli, na wypadek, gdyby pomogła:
To oszczędza nam 10-30% w zależności od platformy. Nie jest zły. Ale kolejny duży krok pozbywa się wywołań funkcji toString wraz z klasycznym optymalizatorem - tabelą przeglądową. Prosta 16-elementowa tabela odnośników wykona zadanie toString (16) w znacznie krótszym czasie:
Kolejna optymalizacja to kolejny klasyk. Ponieważ obsługujemy tylko 4 bity wyjścia w każdej iteracji pętli, zmniejszmy liczbę pętli o połowę i przetwarzamy 8 bitów w każdej iteracji. Jest to trudne, ponieważ wciąż musimy obsługiwać pozycje bitów zgodne z RFC, ale nie jest to zbyt trudne. Następnie musimy stworzyć większą tabelę wyszukiwania (16 x 16 lub 256) do przechowywania 0x00 - 0xff i budujemy ją tylko raz, poza funkcją e5 ().
Próbowałem e6 (), który przetwarza 16-bitów jednocześnie, wciąż używając 256-elementowej LUT, i wykazywał malejące zwroty z optymalizacji. Chociaż miało mniej iteracji, wewnętrzna logika była skomplikowana przez zwiększone przetwarzanie i działała tak samo na komputerze stacjonarnym, a tylko ~ 10% szybciej na telefonie komórkowym.
Ostateczna technika optymalizacji do zastosowania - rozwiń pętlę. Ponieważ zapętlamy określoną liczbę razy, technicznie możemy to wszystko zapisać ręcznie. Próbowałem tego raz z jedną losową zmienną r, którą ciągle zmieniałem, a wydajność była pełna. Ale z czterema zmiennymi przypisanymi losowymi danymi z góry, a następnie za pomocą tabeli odnośników i zastosowania odpowiednich bitów RFC, ta wersja pali je wszystkie:
Zmodyfikowany: http://jcward.com/UUID.js -
UUID.generate()
Zabawne jest to, że generowanie 16 bajtów losowych danych jest łatwą częścią. Cała sztuczka polega na wyrażaniu tego w formacie String z zachowaniem zgodności z RFC, a najsilniej osiąga się to dzięki 16 bajtom losowych danych, rozwijanej pętli i tabeli odnośników.
Mam nadzieję, że moja logika jest poprawna - bardzo łatwo jest popełnić błąd w tego rodzaju żmudnej pracy. Ale wyniki wyglądają dobrze dla mnie. Mam nadzieję, że podobała Ci się ta szalona jazda dzięki optymalizacji kodu!
Pamiętaj: moim głównym celem było pokazanie i nauczenie potencjalnych strategii optymalizacji. Inne odpowiedzi obejmują ważne tematy, takie jak kolizje i naprawdę losowe liczby, które są ważne dla generowania dobrych UUID.
źródło
Math.random()*0xFFFFFFFF
wiersze powinny byćMath.random()*0x100000000
dla pełnej losowości i>>>0
powinny być używane zamiast|0
utrzymywania wartości bez znaku (choć w obecnym kodzie myślę, że to wychodzi OK, mimo że są podpisane). Wreszcie, byłoby bardzo dobrym pomysłem w tych dniach, aby użyć,window.crypto.getRandomValues
jeśli są dostępne, i powrócić do Math.random tylko wtedy, gdy jest to absolutnie konieczne. Math.random może mieć mniej niż 128 bitów entropii, w takim przypadku byłoby to bardziej podatne na zderzenia niż to konieczne.Oto kod oparty na RFC 4122 , sekcja 4.4 (Algorytmy tworzenia UUID z naprawdę losowej lub pseudolosowej liczby).
źródło
var s = new Array(36);
Pokaż fragment kodu
Jeśli identyfikatory są generowane w odległości większej niż 1 milisekunda od siebie, są one w 100% unikalne.
Jeśli dwa identyfikatory są generowane w krótszych odstępach czasu i przy założeniu, że metoda losowa jest naprawdę losowa, wygenerowałoby to identyfikatory, które na 99.9999999999999999% są globalnie unikalne (kolizja w 1 z 10 ^ 15)
Możesz zwiększyć tę liczbę, dodając więcej cyfr, ale aby wygenerować 100% unikatowych identyfikatorów, musisz użyć licznika globalnego.
jeśli potrzebujesz zgodności z RFC, to formatowanie przejdzie jako prawidłowy identyfikator GUID wersji 4:
Pokaż fragment kodu
Edycja: Powyższy kod jest zgodny z intencją, ale nie jest literą RFC. Wśród innych rozbieżności jest kilka krótkich cyfr losowych. (W razie potrzeby dodaj więcej losowych cyfr) Plusem jest to, że jest to naprawdę szybkie :) Tutaj możesz przetestować ważność swojego identyfikatora GUID
źródło
[slug, date, random].join("_")
Do tworzeniausr_1dcn27itd_hj6onj6phr
. To sprawia, że id również podwaja się jako pole „utworzone w”Najszybsza metoda GUID podobna do generatora łańcuchów w formacie
XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX
. Nie generuje GUID zgodnego ze standardami.Dziesięć milionów wykonań tej implementacji zajmuje zaledwie 32,5 sekundy, co jest najszybszym, jakie kiedykolwiek widziałem w przeglądarce (jedyne rozwiązanie bez pętli / iteracji).
Funkcja jest tak prosta, jak:
Aby przetestować wydajność, możesz uruchomić ten kod:
Jestem pewien, że większość z was zrozumie, co tam zrobiłem, ale może jest co najmniej jedna osoba, która będzie potrzebowała wyjaśnienia:
Algorytm:
Math.random()
Zwraca liczbę dziesiętną wynoszącą od 0 do 1 z 16 cyfr po ułamek dziesiętny (na przykład0.4363923368509859
).0.6fb7687f
).Math.random().toString(16)
.0.
prefiks (0.6fb7687f
=>6fb7687f
) i otrzymujemy ciąg o długości ośmiu znaków szesnastkowych.(Math.random().toString(16).substr(2,8)
.Math.random()
funkcja zwraca krótszą liczbę (na przykład0.4363
), z powodu zer na końcu (z powyższego przykładu tak naprawdę jest to liczba0.4363000000000000
). Dlatego dołączam do tego ciągu"000000000"
(ciąg z dziewięcioma zerami), a następnie odcinam gosubstr()
funkcją, aby dokładnie dziewięć znaków (wypełnianie zer po prawej stronie).Math.random()
funkcja zwróci dokładnie 0 lub 1 (prawdopodobieństwo 1/10 ^ 16 dla każdego z nich). Dlatego musieliśmy dodać do niego dziewięć zer ("0"+"000000000"
lub"1"+"000000000"
), a następnie odciąć go od drugiego indeksu (3. znak) o długości ośmiu znaków. W pozostałych przypadkach dodanie zer nie zaszkodzi wynikowi, ponieważ i tak go odcina.Math.random().toString(16)+"000000000").substr(2,8)
.Montaż:
XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX
.XXXXXXXX
i-XXXX-XXXX
.XXXXXXXX
-XXXX-XXXX
-XXXX-XXXX
XXXXXXXX
._p8(s)
,s
parametr mówi funkcji, czy dodać myślniki, czy nie._p8() + _p8(true) + _p8(true) + _p8()
i zwracamy go.Link do tego postu na moim blogu
Cieszyć się! :-)
źródło
Oto kombinacja najczęściej głosowanej odpowiedzi z obejściem kolizji Chrome :
Na jsbin, jeśli chcesz go przetestować.
źródło
, does not keep the Version 4 UUIDs format defined by RFC 4122. That is instead of
xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx` dajexxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx
.Oto całkowicie niezgodna, ale bardzo wydajna implementacja w celu wygenerowania bezpiecznego dla ASCII unikalnego identyfikatora typu GUID.
Generuje 26 [a-z0-9] znaków, dając identyfikator UID, który jest zarówno krótszy, jak i bardziej unikalny niż identyfikatory GUID zgodne z RFC. Kreski można dodawać w trywialny sposób, jeśli liczy się czytelność dla człowieka.
Oto przykłady użycia i czasy dla tej funkcji oraz kilka innych odpowiedzi na to pytanie. Czas został wykonany w Chrome m25, każda z 10 milionami iteracji.
Oto kod czasowy.
źródło
Oto rozwiązanie z 9 października 2011 r. Z komentarza użytkownika jed na https://gist.github.com/982883 :
Osiąga to ten sam cel, co obecnie najwyżej oceniana odpowiedź , ale w ponad 50 bajtach mniej poprzez wykorzystanie przymusu, rekurencji i notacji wykładniczej. Dla ciekawskich, jak to działa, oto adnotowana forma starszej wersji funkcji:
źródło
Z technicznego bloga sagi shkedy :
Istnieją inne metody, które wymagają użycia kontrolki ActiveX, ale trzymaj się od nich z daleka!
Edycja: Pomyślałem, że warto zauważyć, że żaden generator GUID nie może zagwarantować unikatowych kluczy (zobacz artykuł na Wikipedii ). Zawsze istnieje szansa na kolizje. GUID po prostu oferuje wystarczająco duży wszechświat kluczy, aby zredukować zmianę kolizji do prawie zera.
źródło
Możesz użyć node-uuid ( https://github.com/kelektiv/node-uuid )
Prosta, szybka generacja UFCID RFC4122.
Funkcje:
Zainstaluj za pomocą NPM:
Lub Korzystanie z UUID przez przeglądarkę:
Pobierz plik Raw (Uuid v1): https://raw.githubusercontent.com/kelektiv/node-uuid/master/v1.js Pobierz plik Raw (Uuid v4): https://raw.githubusercontent.com/kelektiv/node -uuid / master / v4.js
Chcesz jeszcze mniejszy? Sprawdź to: https://gist.github.com/jed/982883
Stosowanie:
ES6:
źródło
EDYTOWAĆ:
Znowu odwiedziłem mój projekt, który korzystał z tej funkcji i nie podobało mi się gadatliwość. - Ale potrzebował odpowiedniej losowości.
Wersja oparta na odpowiedzi Briguy37 i kilku bitowych operatorach, aby wyodrębnić z bufora okna wielkości skubków.
Powinien być zgodny ze schematem RFC Type 4 (losowym), ponieważ miałem ostatnio problemy podczas analizowania niezgodnych UUID z UUID Javy.
źródło
Prosty moduł JavaScript jako kombinacja najlepszych odpowiedzi w tym wątku.
Stosowanie:
źródło
GUID
jakostring
. Twoja odpowiedź dotyczy przynajmniej znacznie bardziej wydajnego przechowywania za pomocąUint16Array
.toString
Funkcja powinna być pomocą reprezentację binarną w JavaScriptobject
Tworzy to UUID w wersji 4 (utworzony z pseudolosowych liczb):
Oto próbka wygenerowanych UUID:
źródło
Cóż, ma to już wiele odpowiedzi, ale niestety nie ma w tym „prawdziwym” losowym przypadku. Poniższa wersja jest adaptacją odpowiedzi broofa, ale została zaktualizowana o „prawdziwą” losową funkcję, która wykorzystuje biblioteki kryptograficzne, o ile są dostępne, oraz funkcję Alea () jako awarię.
źródło
Projekt JavaScript na GitHub - https://github.com/LiosK/UUID.js
źródło
źródło
Chciałem zrozumieć odpowiedź Broszy, więc ją rozwinąłem i dodałem komentarze:
źródło
Dostosowałem mój własny generator UUID / GUID z kilkoma dodatkami tutaj .
Używam następującego generatora liczb losowych Kybos , aby być nieco bardziej kryptograficznie dobrym .
Poniżej znajduje się mój skrypt z wykluczonymi metodami Mash i Kybos z baagoe.com.
źródło
Dla tych, którzy chcą rozwiązania zgodnego z rfc4122 w wersji 4 z uwzględnieniem prędkości (kilka wywołań Math.random ()):
Powyższa funkcja powinna mieć odpowiednią równowagę między prędkością a losowością.
źródło
Próbka ES6
źródło
Lepszy sposób:
Zminimalizowane:
źródło
Wiem, to stare pytanie. Dla kompletności, jeśli twoje środowisko to SharePoint, istnieje funkcja narzędzia o nazwie
SP.Guid.newGuid
( link msdn ), która tworzy nowy przewodnik. Ta funkcja znajduje się w pliku sp.init.js. Jeśli przepiszesz tę funkcję (aby usunąć niektóre inne zależności z innych funkcji prywatnych), wygląda to tak:źródło
Ten jest oparty na dacie i dodaje losowy przyrostek, aby „zapewnić” wyjątkowość. Działa dobrze dla identyfikatorów css. Zawsze zwraca coś podobnego i jest łatwy do zhakowania:
uid-139410573297741
źródło
Prosty kod, który wykorzystuje się
crypto.getRandomValues(a)
w obsługiwanych przeglądarkach (IE11 +, iOS7 +, FF21 +, Chrome, Android Chrome). Unika używania,Math.random()
ponieważ może to powodować kolizje (na przykład 20 kolizji dla 4000 wygenerowanych płynów w rzeczywistej sytuacji przez Muxa ).Uwagi:
źródło
Jeśli potrzebujesz tylko losowego ciągu 128-bitowego bez określonego formatu, możesz użyć:
Który zwróci coś takiego
2350143528-4164020887-938913176-2513998651
.źródło
Array.from((window.crypto || window.msCrypto).getRandomValues(new Uint32Array(4))).map(n => n.toString(16)).join('-')
Kolejny bardziej czytelny wariant z tylko dwiema mutacjami.
źródło
OK, używając uuid pakiet, to wsparcie dla wersji 1, 3, 4 i 5 UUID zrobić:
i wtedy:
Możesz to również zrobić przy użyciu w pełni określonych opcji:
Aby uzyskać więcej informacji, odwiedź stronę npm tutaj
źródło
Ważne jest, aby używać dobrze przetestowanego kodu, który jest obsługiwany przez więcej niż 1 współautorów, zamiast biczować własne rzeczy. Jest to jedno z miejsc, w których prawdopodobnie wolisz najbardziej stabilny kod niż najkrótszą możliwą sprytną wersję, która działa w przeglądarce X, ale nie bierze pod uwagę osobliwości Y, co często prowadzi do bardzo trudnych do zbadania błędów niż manifestuje się tylko losowo dla niektórych użytkowników. Osobiście używam uuid-js na https://github.com/aurigadl/uuid-js, w którym włączono altanę, dzięki czemu mogę łatwo pobierać aktualizacje.
źródło