数十億のクッキー、文字列のようなUUIDがある場合、このサンプルのmurmur3のような32ビットハッシュ関数の衝突率をテストする最良の方法は何ですか?ハッシュ関数の衝突率をどのようにスパイクするのですか?
まず、何十億ものユニークな文字列を生成することは困難です。メモリに保持することは不可能であり、100%正確なランダムストリングジェネレータはありません。私は考えることができる
唯一の方法は次のとおりです。
- それらを生成し、約使用します。可能な重複を破棄するためにbloomfilterまたはcuckooフィルタのようなデータ構造。次に、ファイルに格納されているユニークなUUIDを正確に5B個と言います。
- それらを繰り返し、それらをハッシュし、ハッシュコードでステップ1)を繰り返しながら、いくつのコリジョンがあるかを数えます。
これを実行する方法はありますか?これには、2)のハッシュコードをテストしているときにある程度の誤検知率があるという欠点があります。ハッシュコードはファイルにも書き込まれなければならず、偽陽性の可能性がある場合に手動でチェックする必要があります。