ローリングハッシュや木の同型判定など、競プロでハッシュを使う機会はあるけど、衝突確率とか必要な値域についてあまり考えたことがなかったので計算してみた。
ハッシュを使う場合、以下の２通りではそれぞれ衝突確率がかなり異なる。（少し考えれば当たり前の話だけど、「ハッシュ」という言葉で思考停止しがち）
２つが同じであるかを比較するだけ
２つのハッシュが衝突する確率さえ低ければ良い。
比較を何度かする場合でも、それほど大したことはない。
１回の衝突確率をp (大抵の場合 1/mod とか) として比較回数をNとすると、1回でも衝突する確率は1-(1-p)^N。
N=1e5, mod = 1e9 としたときに１回でも衝突する確率は 0.01% ほど。まぁ十分低いと言えそう？100個テストケースがあっても衝突確率は1%くらい。
種類数を求めたりする
いわゆるお誕生日。かなり衝突しやすい。
少なくとも N=1e5, mod = 1e9 としたときに答えが変わる確率は 99.3% ほど。むしろ衝突しない方がおかしいくらい。
まぁ、２つのハッシュの比較を二乗回やってると考えればわざわざ上の項と別にして書くことも無い気はするが、でもやっぱり衝突のしやすさには有意差がある。
ちなみに、１組でも衝突が起きる確率が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
...
もっと違うのが欲しければこれで生成して下さい。
注意・参考リンク
上記はハッシュが良質なものだと仮定した時の話なので、いい加減なハッシュだとこの限りではないでしょう。
いい加減ハッシュといえば、これは知っておくと良いと思います。
あとは、これの解説とか詳しいです。
あと、根付き木のハッシュについての記事を書きました。
