ランダムの文字列が偶然一致する可能性

Question

例えばコメントの投稿などに個別に投稿IDをランダム文字列をつけるとするとこれらが偶然一致する可能性も考えたほうがいいのでしょうか?
ちなみに文字列は計算上280兆個できます。
もちろん先に出てしまった文字列が少なければ一致しないかどうか確認しても良いとは思いますが今回の場合多くなってしまいそうなため質問させていただきました。

Comments

[fukatani]

一つの文字列の長さはどれだけでしょうか？
文字列には数字、英語小文字、大文字、特殊文字の内、なにがふくまれますか？

Answer 1

誕生日問題ですね。

UUIDの衝突確率 - Qiitaの記事を参考にすると

1 * (1 - 1/2.8e14) * (1 - 2/2.8e14) * ... * (1 - (n - 1)/2.8e14)
≈ 1 - Math.exp(- n**2 / (2.8e14 * 2))

と言う形で計算できるようです。

1万件なら約0.000018%
10万件なら約0.0018%
100万件なら約0.18%
1000万件なら約16%
1億件なら約100%

厳密な計算は検証していませんが、100万件を超えるぐらいなら、ソシャゲでレアガチャひいてお目当てのものをあてるぐらいの確率ですし、衝突することはあってもおかしくないぐらいの確率だと思います。

Answer 2

重複する可能性を完全に排除できる乱数なんてものは存在しないと思わなければいけません。
6面サイコロを転がして同じ数字が連続する可能性は、2連続で1/36、3連続で1/216です。
これはサイコロになんらイカサマのない、各面の出る確率が完全に均等（1/6）の場合です。

いわゆる「疑似乱数」の場合、実はこれが1/6になっていないため、特定の条件下では確率が跳ね上がってしまいますから。

まぁ仮に疑似ではなく真正な乱数だとしても、280兆個の文字列に対して最初の100個の中に重複が存在する可能性は排除できないわけなので、ユニークIDに乱数を用いるのはダメでしょう。

単純に連番にしたらどうですか？
前提条件が示されていないのであれですが、データをMySQL等データベースに格納するのであれば、
bigint unsignedであれば1～18446744073709551615、1844京6744兆737億955万1615件の投稿まで、絶対に重複しないIDを付与できます。
これは世界中の人間（70億人）全員が毎日100件ずつ投稿（1日7000億投稿）したとして約72200年ほど枯渇しません。

Comments

[Zuishin]

連番なら絶対重複しないので、私もこれに賛成です。ランダムっぽい文字列が必要なら、この数値をバイト列にした後暗号化して BASE64 でテキスト化する手もあります。

[kyoya0819]

自分も同様にこれが最も適した方法だと思います。

> これは世界中の人間（70億人）全員が毎日100件ずつ投稿（1日7000億投稿）したとして約72200年ほど枯渇しません。

iPv6みたい...

Answer 3

idを重複を考慮せずランダムに生成するというのは避けるべきです。
どのような乱数を使うかわかりませんが、ほとんどの場合は擬似乱数の周期性を持っているため、ランダムのつもりでも重複してしまう可能性があります。

Answer 4

利用目的次第かと。

ユニーク id であれば当然一致は排除すべきです。