URLに対するハッシュ関数考察

現在電車中。

64bitのハッシュ関数を使うと、どれも似たような結果になった。106億個URLがあると、大体全体の0.4%が衝突する。ちなみに、64bitの乱数を100億回生成しても大体6個しか衝突しない。シミュレート値と理論値が一致したので間違いないと思う。

ハッシュ値衝突しすぎ。しかし、今回は0〜255の値を取るバイト列を入力として受け取ることを想定しているハッシュ関数を使ったので、文句は言えないかもしれない。URLみたいに偏ったデータを与えたらハッシュ値が偏っちゃうこともあるかもしれんし。一見乱数と同じような分布にはなってたんだけど、分散を調べたりして考察を加える事は時間不足でできなかった。文字列みたいに限定されたデータを対象にしたハッシュ関数関数も使ってみたかったけど、時間がなかった…。

今後やるとしたら高速な完全ハッシュ関数を効率的に使う方法を考えたり、128bit値を効率的に使う方法を検討してみたり、URLに特化したハッシュ関数を考えてみたりかなぁ。逆に、衝突が発生することを前提にしたシステムを考えるか。どっちにしろ64bitハッシュ値だけでURL重複の判定をするのはやめた方がよさそう。でもハッシュ値だけで判定できたら、かなり処理が簡単かつ高速になるので、衝突が10万個切るくらいにできれば使っても良い気がする。

もっと調べたかったあああ。どっちにしろもう少し調べる必要がありますがねー。

追記：
残念な事に実験用に生成したURLに重複が含まれていたようです。仕様上発生確率は相当低いのですが、試行回数が6億回もありました。それを過小評価してました。新たに得た正しい結果によると、MurmurHash+SuperFastHashで重複は1件しか発生せずと言うすばらしい事実がわかりました。なので、完全に衝突を検出するのが難しい環境では、64bitハッシュ値でやっても100億くらいまでなら全く問題ないです。紛らわしい情報を書いてしまいすいませんでした。