25

ブルームフィルターのハッシュ関数の選択について、次の質問があります。

  • どの関数を使用しますか？

ほぼすべてのドキュメント/ペーパーで、ブルームフィルターで使用されるハッシュ関数は独立しており、均一に分散されている必要があることがわかります。

これが何を意味するのか（独立して均一に分散されている）はわかっていますが、どのハッシュ関数がこれらの要件を満たしているため適切であるかについての議論や議論を見つけるのに苦労しています。多くの投稿で、 FNVまたはMurmurハッシュ関数の使用法に関する提案について読んだことがありますが、なぜ（または少なくとも証明なしで）それらが適しているのかはわかりません。

前もって感謝します！

4

3 に答える 3

22

Java Bloom フィルタ ライブラリを構築する際に、同じ質問を自問しました。ブルーム フィルターのハッシュ関数の分析の詳細については、Github の readmeを参照してください。

この問題を次の 2 つの観点から考察しました。

  • 計算はどれくらい速いですか？
  • 出力分布はどの程度均一ですか?

速度は、ランダム入力のベンチマークで簡単に測定できます。均一性は少し難しく、いくつかの統計が必要です。カイ二乗適合度テストを使用して、ハッシュ値の分布が一様分布にどの程度似ているかを測定しました。

結果は次のとおりです。

  • 速度と均一性の間で最良のトレードオフを得るには、 Murm3を使用してください。小さな増分で変化する入力に対して均一ではないため、Murmur2 を使用しないでください。
  • 最適な均一性を得るには、SHA-256 などの暗号化ハッシュ関数を使用してください。
  • Kirsch-Mitzenmacher-Optimizationを適用して、k 個ではなく 2 個のハッシュ関数のみを計算します ( hash_i = hash1 + ix hash2 )。

実装で Java を使用している場合は、ブルーム フィルター ハッシュ ライブラリを使用することをお勧めします。十分に文書化され、徹底的にテストされています。さまざまなハッシュ関数のベンチマーク結果やカイ 2 乗検定による不均一性などの詳細については、リポジトリのGithub readme を参照してください。

于 2016-10-31T14:08:20.620 に答える
5

ハッシュ関数は、FNVが悪い選択である理由、およびMurmur2またはBobJenkinsのハッシュの1つが良い選択である理由のグラフィカルな証拠を提供する必要があります。

于 2012-08-21T04:00:01.687 に答える