読者です 読者をやめる 読者になる 読者になる

ハッシュの衝突

ローリングハッシュや木の同型判定など、競プロでハッシュを使う機会はあるけど、衝突確率とか必要な値域についてあまり考えたことがなかったので計算してみた。

ハッシュを使う場合、以下の2通りではそれぞれ衝突確率がかなり異なる。(少し考えれば当たり前の話だけど、「ハッシュ」という言葉で思考停止しがち)

2つが同じであるかを比較するだけ

2つのハッシュが衝突する確率さえ低ければ良い。
比較を何度かする場合でも、それほど大したことはない。
1回の衝突確率をp (大抵の場合 1/mod とか) として比較回数をNとすると、1回でも衝突する確率は1-(1-p)^N。
N=1e5, mod = 1e9 としたときに1回でも衝突する確率は 0.01% ほど。まぁ十分低いと言えそう?100個テストケースがあっても衝突確率は1%くらい。

種類数を求めたりする

いわゆるお誕生日。かなり衝突しやすい。
少なくとも N=1e5, mod = 1e9 としたときに答えが変わる確率は 99.3% ほど。むしろ衝突しない方がおかしいくらい。
まぁ、2つのハッシュの比較を二乗回やってると考えればわざわざ上の項と別にして書くことも無い気はするが、でもやっぱり衝突のしやすさには有意差がある。
ちなみに、1組でも衝突が起きる確率が50%を超えるようなNはだいたいO(√mod)くらいらしい。
とりあえず各N,modごとの衝突確率の表は以下の通り。(値は適当に丸めてある)
O(√mod)くらいというのも納得できる。

mod\N 103 104 105 106 107
109 0.05% 4.9% 99.3% 100% 100%
1010 0.005% 0.5% 39.3% 100% 100%
1011 5e-4% 0.05% 4.9% 99.3% 100%
1012 5e-5% 0.005% 0.5% 39.3% 100%
1013 5e-6% 5e-4% 0.05% 4.9% 99.3%
1014 5e-7% 5e-5% 0.005% 0.5% 39.3%
1015 5e-8% 5e-6% 5e-4% 0.05% 4.9%
1016 5e-9% 5e-7% 5e-5% 0.005% 0.5%
1017 eps% 5e-8% 5e-6% 5e-4% 0.05%
1018 eps% 5e-9% 5e-7% 5e-5% 0.005%

まぁmodを1e18くらいにしとけばそうそう落ちることはないって感じかな。
ただ、それだと掛け算がオーバーフローするからバイナリ法とかで計算しないといけなくなって重そうだしなぁ。
とりあえず僕は1e9くらいのmodのpairにすることにしてライブラリを作ってみました。

1e9くらいの素数
999999797
999999883
999999893
999999929
999999937
1000000007
1000000009
1000000021
1000000033
1000000087
...
1e18くらいの素数
999999999999999829
999999999999999863
999999999999999877
999999999999999967
999999999999999989
1000000000000000003
1000000000000000009
1000000000000000031
1000000000000000079
1000000000000000177
...
もっと違うのが欲しければこれで生成して下さい。

注意・参考リンク

上記はハッシュが良質なものだと仮定した時の話なので、いい加減なハッシュだとこの限りではないでしょう。
いい加減ハッシュといえば、これは知っておくと良いと思います。
あとは、これの解説とか詳しいです。
あと、根付き木のハッシュについての記事を書きました。