クローゼットでブルームフィルタを構築するときに使用するハッシュテクニックは何ですか？

Question

Clojureにブルームフィルタを作成したいが、JVMベースの言語で利用できるすべてのハッシュライブラリについて多くの知識がない。

Clojureで最も速く（最も正確なものとは対照的に）ブルームマップの実装にはどのようなものを使用しますか？

Answer 1

ブルームフィルタについての楽しいことは、効果的に動作するためには、複数のハッシュ関数が必要であるということです。

Java文字列には既に、 - String.hashCode()と32ビットの整数ハッシュを返す1つのハッシュ関数が組み込まれています。これはほとんどの目的でOKのハッシュコードです。これは十分である可能性があります。たとえば、これを2つの別々の16ビットハッシュコードに分割すると、ブルームフィルタが機能するのに十分です。あなたはおそらくいくつかの衝突を得るでしょうが、それはうまくいきます - ブルームフィルタはいくつかの衝突を持つと予想されます。

もしそうでない場合は、独自のロールを作成したい場合は、String.getChars()を使用して生のcharデータにアクセスし、複数のハッシュコードを計算することをお勧めします。

あなたは（単に文字の値を合計）始めるためにClojureのコード：

(let [s "Hello" 
     n (count s) 
     cs (char-array n)] 
    (.getChars s 0 n cs 0) 
    (areduce cs i v 0 (+ v (int (aget cs i))))) 
=> 500 

注GetCharsはを呼び出すためのClojureのJava相互運用機能を使用すると、あなたの上に非常に高速な繰り返しを与えるためにareduceの使用文字配列

Githubで見つかったJava Bloomフィルタの実装については、https://github.com/MagnusS/Java-BloomFilterをご覧ください。ハッシュコードの実装は一目瞭然ですが、バイト配列を使用しています。これは文字エンコーディングのオーバーヘッドを処理する必要があるため、charを使用するよりも少し効率が悪いと思います。

Answer 2

Bloom Filterの実装をApache Cassandraに見てください。これは非常に高速のMurmurHash3アルゴリズムを使用し、異なる方法で2つのハッシュ（または同じハッシュの2つの部分をMurmurHash2の代わりにMurmurHash3にアップグレードした後）を組み合わせて、目的のハッシュ数を計算します。

組み合わせの生成方法は、this paper

に記載されており、ここではカサンドラのソースコードからの抜粋ですされています

long[] hash = MurmurHash.hash3_x64_128(b, b.position(), b.remaining(), 0L); 
    long hash1 = hash[0]; 
    long hash2 = hash[1]; 
    for (int i = 0; i < hashCount; ++i) 
    { 
     result[i] = Math.abs((hash1 + (long)i * hash2) % max); 
    } 

を参照してください

も Bloomfilter and Cassandra = Why used and why hashed several times?