読者です 読者をやめる 読者になる 読者になる

マッピィ Techlog

日々思うこと

【Programming】UUIDの衝突確率

Programming

UUIDについて扱う機会があり、気になったので考えてみました。

「絶対に衝突しないのだろうか?」

ただ「生成されるもの」と聞いたので、いつか万が一にでも衝突することがあるのでは?と疑問に思いました。

 

UUIDとは

UUIDは全世界で同じ値を持つことがない識別子です。

長さは128ビットで、バージョン情報が6ビットあるため、固有の値は122ビットになります。

 

バージョン

Versionは1~5があります。

・Version1…MACアドレスと生成日時によって計算される。

・Version2…DCE Security(Version1+αのようなイメージ?)

・Version3…バイト列とMD5ハッシュで計算

・Version4…乱数計算

・Version5…バイト列SHA-1ハッシュで計算

形式はxxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxxとなっています。

 

衝突確率

さて、固有の値ですが、2の122乗イコール5316911983139663491615228241121378304通りあることになります。

Universally unique identifier - Wikipedia, the free encyclopedia

によると、毎秒10億個生成を100年回し、その後1個の生成は50%の確率で衝突するようです。

 

その前の生成でも衝突があるでしょうし、多い印象ではあります。

が、コンピュータに限っていえば、全人口それぞれが10台持っていても700億台でしょうから、ほぼほぼ問題はなさそうですね。