【Programming】UUIDの衝突確率

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通りあることになります。

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

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

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

マッピィ Techlog