100億個程度のURLに対する効率の良いハッシュ関数調査

Webクローラを作る際に重複URLを除去しつつ幅優先っぽい探索をしていく問題があるわけですが、今はそのときのURLの重複判定をどうやって効率よくやろうかという話を勉強中。その前処理として、URLに対するハッシュ関数を考え中。

とりあえずURLの数が数なのでハッシュ値は64bitに納めたい。その状態でハッシュ値の衝突を極限まで押さえつつ、速度も維持したいという感じ。理論的な事は良くわからんので色々やってみるしかない感じの状態。

現在はMurmur Hash2とCRC32を組み合わせた64bitのハッシュ値を使う実験をしてみたところ。その結果日本の3億個くらいのURLに対しては衝突無し。でも、あまりにも数が少なすぐる。64bitの乱数を生成し続けると、10億くらいから衝突するものが発生する確率が跳ね上がるので、少なくとも20〜30億個くらいのURLで実験してみたいところ。