◆ 10000 通りだと平均 150 回くらい
◆ 1000 億通りだと平均 30 万回くらい
◆ git のハッシュ値 (16 進数 40 桁) は約 1.5 極通りある

重複しないユニークな ID をもたせるためにランダムな値をセットすることってありますよね
どれくらいで重複するんだろうって思うこと ありませんか?
今回はそれを試してみました

const f = ({result_length, pattern, max_try}) => {
const rdm = () => Math.floor(Math.random() * pattern)
const len = parseInt(result_length) || 0
const max = parseInt(max_try) || 0

const results = []
for(let i=0;i<len;i++){
const set = new Set()
let result = null
for(let x=0;x<max;x++){
const value = rdm()
if(set.has(value)){
result = x
break
}else{
set.add(value)
}
}
results.push(result)
}
return {
results,
max: results.reduce((a, e) => Math.max(a, e)),
min: results.reduce((a, e) => Math.min(a, e)),
avg: results.reduce((a, e) => a + e) / results.length,
med: results.slice().sort((a, b) => a - b)[~~(results.length/2)],
}
}

引数の pattern に設定したパターンのランダムな数字が出力される関数を用意し 同じ数が出るまでループして実行します
max_try を指定すると それ以上の回数試しても重複しなかったら諦めます
result_length を設定するとその回数だけ 何度目に重複するかを計算します
平均や最小・最大も表示するので result_length が多いほど信頼できる情報になります

10000 パターンの数字だと

f({result_length: 10, max_try: 1000000, pattern: 10000})
// {results: (10) [168, 214, 248, 86, 121, 151, 106, 106, 354, 129], max: 354, min: 86, avg: 168.3, med: 151}

150 回くらいで重複するようです
少ないときは 86 回です
奇跡的な確率では最小の 1 回目から重複することはあり得るわけなので最小にそこまで意味はないですけど 100 回程度で重複することもそれなりにあるようです

今度はちょっと多めに 100000000000 パターン (1000億) です

f({result_length: 10, max_try: 1000000, pattern: 100000000000})
// {results: [221868, 297601, 248429, 389775, 535574, 326565, 176580, 293954, 357700, 136349], max: 535574, min: 136349, avg: 298439.5, med: 297601}

平均では 30 万回くらいで重複するようです
10 回の最小は 136349 でした
千~万くらいのユニークな値がほしいなら余裕を持ってこれくらいのパターンはあったほうがいいですね

ところで 普段よくランダムな ID を作るときに

Math.random().toString(16).slice(2)
// "99bcf73098aab"

としています
今の Chrome で試したところ 基本 13 桁でときどき 10 桁や 12 桁などもあります
少ないのは 0 があるとして 13 桁で計算すると

16**13
// 4503599627370496

4503 兆もあります
これも試してみたのですが パターン数がここまで多くなると過去に出た値を全部メモリ上に保持できないのか devtools がクラッシュしました
どこかで重複が出たことではなく 最初にでたものがもう一度出るまで試すほうがメモリには優しそうです

ついでに git で使われているハッシュ値ですが 16 進数で 40 桁もあります
過去は 7 桁だったらしいですが 7 桁だと

16**7
// 268435456

2.5 億パターンくらいです
試してみると 平均が 20000 回程度でした
大きめのプロジェクトだと数千コミットになることは少なくないので普通にハッシュ値の衝突が起きそうですね
V8 なんか 50000 コミット超えてますし Chromium や Linux kernel にいたっては 70 万とか 80 万とか文字通り桁が違います

で 今の 40 桁では

16n ** 40n
// 1461501637330902918203684832716283019655932542976n

1極
4615載
0163正
7330澗
9029溝
1820穣
3684𥝱
8327垓
1628京
3019兆
6559億
3254万
2976

無量大数までは行かないものの漢字一文字で書ける一番上の単位の「極」まで行ってます
さすがにこれを実際に重複するまで計算するのは終わる気がしないのでやめておきます
数学の確率計算で出せそうな気はしますがそういうのは詳しくないのでパスで
垓か𥝱くらいでかぶるのかな?

これを数百や数千程度の現実的なコミット量で重複させれるならかなりの奇跡的な確率ですよね