ハッシュ値が衝突する確率について

はじめに

あるデータから一意の値を取得する際に、よくハッシュ値を取る方法が使われる。
その際、衝突する確率がどのくらいなのか気になったので調べてみた。

今回考えること

SHA256 によってハッシュ値を取ることを想定する。この際、 SHA256 が取る値は一様にランダムとする。
ある特定の SHA256 のハッシュ値になる確率($1/22561/2^{256}$)がどのくらいかを他の確率的な事象で比較する。

確率の比較

事象	2の累乗表記	10の累乗表記	%表示
ロイヤルストレートフラッシュ	$1/216.01/2^{16.0}$	$1/104.831/10^{4.83}$	$1.48∗10−31.48*10^{-3}$ %
天和	$1/218.31/2^{18.3}$	$1/105.521/10^{5.52}$	$3.03∗10−43.03*10^{-4}$ %
2択20問のテストででたらめ回答で0点	$1/220.01/2^{20.0}$	$1/106.021/10^{6.02}$	$9.54∗10−59.54*10^{-5}$ %
宝くじ一等	$1/223.21/2^{23.2}$	$1/107.001/10^{7.00}$	$1.00∗10−51.00*10^{-5}$ %
何もせず6Vが生まれる(ポケモンの話)	$1/230.01/2^{30.0}$	$1/109.031/10^{9.03}$	$9.31∗10−89.31*10^{-8}$ %
天和四暗刻大四喜字一色	$1/249.71/2^{49.7}$	$1/1015.01/10^{15.0}$	$1.08∗10−131.08*10^{-13}$ %
センター国語(2020)で適当回答で満点	$1/279.61/2^{79.6}$	$1/1024.01/10^{24.0}$	$1.12∗10−221.12*10^{-22}$ %
40人クラスの席替えが席替えにならない	$1/21591/2^{159}$	$1/1047.91/10^{47.9}$	$1.23∗10−461.23*10^{-46}$ %
54枚のトランプが購入時の並び順になる	$1/22371/2^{237}$	$1/1071.41/10^{71.4}$	$4.33∗10−704.33*10^{-70}$ %
100個のサイコロ振ってゾロ目	$1/2255.9111/2^{255.911}$	$1/1077.01/10^{77.0}$	$9.18∗10−769.18*10^{-76}$ %
SHA256 が衝突する	$1/22561/2^{256}$	$1/1077.11/10^{77.1}$	$8.64∗10−768.64*10^{-76}$ %
※もしかすると間違っているかもしれないが悪しからず

上記の計算結果から、衝突する確率は100個のサイコロを振ってゾロ目が出る確率とほぼ同じと言うことがわかった。

実際にサイコロ100個振ってみた

100個のサイコロを準備した。

それを手にもって振る！

その結果...
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓

全部ピンじゃねぇかっ・・・！

.
.
.
.
.
.
.
.
.
.
.

まぁ、そんなわけないよね。

あとがき

サイコロ100個振りたかっただけ。