UUID・ランダムIDの衝突確率

独立・一様に生成される有限ビット空間のIDについて、少なくとも1組の衝突確率と許容確率以下のビット幅を算定する。

入力すると自動で計算します。Enterで次の項目へ進めます。次の入力欄を選んで進めます。

計算する内容

UUIDv4は全128 bitのうちランダム部分が122 bitです。

同一のID空間で、期間・サーバーを通じて合計生成する個数。


計算結果

必要な値を入力すると自動で計算します。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

ランダム部分をb bit、候補数をN=2^b、生成数をnとすると、n≤Nの衝突確率はP=1−∏(i=0,…,n−1)(1−i/N)。n>Nなら鳩の巣原理によりP=100%。小規模ではlog1pを用いた積の対数で計算。大規模ではλ=n(n−1)/(2N)とし、1−exp(−λ)を近似値として表示。δ=n(n−1)(2n−1)/[12N²(1−(n−1)/N)]を用い、P≤1−exp(−λ−δ)を上界として算定します。逆算は上界が目標以下になる最小の整数b(1~4096)を二分探索します。

少なくとも1組の衝突確率(%)、確率の上界(大規模時)、逆算で必要となるランダム部分のビット数。

計算例(架空の数値)

2 bitで3個のIDを生成する場合、重複しない確率は(4/4)×(3/4)×(2/4)=3/8。衝突確率は62.5%。2個生成して衝突確率を1%以下にするには7 bit必要です。

適用対象と限界

ランダム部分が独立かつ一様なID(UUIDv4のランダム122 bitを含む)。UUIDv1/v6/v7等の時刻・単調カウンタ・ノード情報、非一様乱数、生成器の再シード不備、照合・重複排除、ハッシュ関数の生成・暗号強度評価は対象外です。。

方法と出典

方法:E088 birthday collision v1.0(2026-11-13)。データ記録日:2026-11-13。