337

ランダム化されたUUIDは、理論的には衝突の可能性が非常に非常に低いことを知っていますが、実際にrandomUUID()は、衝突がないという点で Java がどれほど優れているか疑問に思っています。共有できる経験はありますか？

4

10 に答える 10

186

UUIDはjava.security.SecureRandom、「暗号的に強い」と思われるを使用します。実際の実装は指定されておらず、JVM間で異なる可能性がありますが（つまり、作成された具体的なステートメントは1つの特定のJVMに対してのみ有効です）、出力は統計的乱数ジェネレーターテストに合格する必要があります。

実装にこれらすべてを台無しにする微妙なバグが含まれる可能性は常にありますが（OpenSSHキー生成バグを参照）、JavaUUIDのランダム性について心配する具体的な理由はないと思います。

于 2010-03-25T10:43:48.950 に答える
122

ウィキペディアには非常に良い答えがあります http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

少なくとも 1 回の衝突を 50% の確率で発生させるために生成する必要があるランダム バージョン 4 UUID の数は、次のように計算されて 2.71 京です。

...

この数は、毎秒 10 億の UUID を約 85 年間生成したことに相当し、この数の UUID を含むファイル (UUID あたり 16 バイト) は約 45 エクサバイトになり、現在存在する最大のデータベースよりも何倍も大きくなります。数百ペタバイトのオーダー。

...

したがって、10 億分の 1 の確率で重複するためには、103 兆のバージョン 4 UUID を生成する必要があります。

于 2010-08-30T13:11:14.140 に答える
72

共有できる経験はありますか？

タイプ 4 UUID には2^122可能な値があります。(仕様では、型の場合は 2 ビット、バージョン番号の場合はさらに 4 ビットを失うと書かれています。)

1 秒間に 100 万個のランダムな UUID を生成すると仮定すると、生涯で重複が発生する可能性はほとんどありません。また、重複を検出するには、1 秒あたり 100 万の新しい UUIDを、以前に生成したすべてのUUID と比較するという問題を解決する必要があります1 !

誰もが実際に複製を経験した (つまり、実際に気づいた) 可能性は、衝突を探すのが実際に難しいため、無視できるほど小さいよりもさらに小さいです。

もちろん、通常は真の乱数のソースではなく、疑似乱数ジェネレーターを使用します。しかし、暗号強度の乱数に信頼できるプロバイダーを使用している場合、それは暗号強度になり、繰り返しの確率は理想的な (バイアスのない) 乱数ジェネレーターと同じになると確信できると思います。 .

ただし、「壊れた」暗号乱数ジェネレーターで JVM を使用する場合、すべての賭けはオフになります。(そして、これには、一部のシステムでの「エントロピー不足」の問題に対するいくつかの回避策が含まれる場合があります。または、システムまたはアップストリームのいずれかで、誰かが JRE をいじった可能性もあります。)

1-匿名のコメント投稿者によって提案された「ある種のバイナリbtree」を使用したと仮定すると、各UUIDには、ビットの密度が低くランダムに分布していると仮定して、個別のUUIDO(NlogN)を表すためにRAMメモリのビットが必要になります。Nこれに 1,000,000 と実験を実行する秒数を掛けます。高品質の RNG の衝突をテストするために必要な時間の長さについては、実用的ではないと思います。（仮想の）巧妙な表現でさえありません。

于 2010-03-25T10:33:08.910 に答える
21

私は専門家ではありませんが、何年にもわたって十分な数の賢い人々がJavaの乱数ジェネレーターを検討していたと思います。したがって、ランダムなUUIDも適切であると思います。したがって、実際には理論上の衝突確率が必要です（これは、すべての可能なUUIDに対して約1：3×10 ^ 38です。これがランダムなUUIDに対してのみどのように変化するかを知っている人はいます1/(16*4)か？上記のことですか？）

私の実際の経験から、私はこれまで衝突を見たことがありません。私が最初のあごひげを手に入れた日、私はおそらく驚くほど長いあごひげを生やしたでしょう;）

于 2010-03-25T08:22:27.897 に答える
10

UUID の元の生成スキームは、UUID バージョンを、UUID を生成しているコンピューターの MAC アドレスと連結し、西側でグレゴリオ暦が採用されてからの 100 ナノ秒間隔の数と連結することでした。空間 (コンピューター) と時間 (間隔の数) で単一のポイントを表すことにより、値の衝突の可能性は事実上ゼロになります。

于 2015-09-25T11:53:29.500 に答える
4

私は昨年宝くじに参加しましたが、一度も当たったことはありません....しかし、宝くじには当選者がいるようです...

ドキュメント: https://www.rfc-editor.org/rfc/rfc4122

タイプ 1 : 実装されていません。uuid が同時に生成された場合、衝突が発生する可能性があります。この問題を回避するために、impl を人為的に a-synchronize することができます。

タイプ 2 : 実装が見られない。

タイプ 3 : md5 ハッシュ : 衝突可能 (128 ビット - 2 テクニカル バイト)

タイプ 4 : ランダム : 衝突可能 (抽選)。PRNGアルゴリズムは開発者によって選択されておらず、システムに「貧弱な」PRNGアルゴリズムを使用させることができるため、jdk6 implは「真の」安全なランダムを使用しないことに注意してください。したがって、UUID は予測可能です。

タイプ 5 : sha1 ハッシュ : 実装されていません : 衝突の可能性があります (160 ビット 2 テクニカル バイト)

于 2015-04-23T06:36:33.600 に答える
0

アプリケーションでJavaのランダムUUIDを1年以上使用しており、それは非常に広範囲に及びます。しかし、衝突に遭遇することはありません。

于 2014-11-11T21:03:22.483 に答える