kペアワイズ独立ハッシュ関数を生成する

Question

私はScalaでCount-Min Sketchアルゴリズムを実装しようとしているので、k個のペアごとに独立したハッシュ関数を生成する必要があります。

これは私が今までにプログラムしたことのあるものよりも低いレベルで、Algorithmsクラス以外のハッシュ関数についてはあまり知らないので、私はこれらのk個のペアごとの独立したハッシュ関数をどのように生成するのですか？

私はMD5やMurmurHashのようなハッシュ関数を使用するはずですか？ f(x) = ax + b (mod p)という形式のkハッシュ関数を生成しますか？pは素数で、aとbはランダムな整数です。 （すなわち、universal hashing family誰もがアルゴリズム101で学習する）

簡単なことは、生の速度よりももっと見ています（たとえば、実装が簡単な場合は5倍速くなります）。

Answer 1

おそらく最も簡単なアプローチは、いくつかの暗号化ハッシュ関数をとり、さまざまなバイトシーケンスで「シード」することです。ほとんどの実用的な目的のために、結果は独立しているべきです。これは、暗号化ハッシュ関数が持つべき重要なプロパティの1つです（メッセージの一部を置き換えた場合、ハッシュは完全に異なるはずです）。

私のような何かをしたい：

// for each 0 <= i < k generate a sequence of random numbers 
val randomSeeds: Array[Array[Byte]] = ... ; // initialize by random sequences 

def hash(i: Int, value: Array[Byte]): Array[Byte] = { 
    val dg = java.security.MessageDigest.getInstance("SHA-1"); 
    // "seed" the digest by a random value based on the index 
    dg.update(randomSeeds(i)); 
    return dg.digest(value); 
    // if you need integer hash values, just take 4 bytes 
    // of the result and convert them to an int 
} 

---

編集：は 私はカウントミンスケッチの正確な要件を知らない、機能は十分であるかもしれないシンプルがありますが、それは最も簡単な解決策ではないようです。

私は暗号ハッシュ関数を提案しました。なぜなら、生成されたハッシュ関数は非常に強固であり、実装が簡単で、標準ライブラリを使用することが非常に強いからです。一方

、フォームf1(x) = ax + b (mod p)とf2(x) = cx + d (mod p)の2つのハッシュ関数を持っている場合は、あなたが使用して1を計算することができ、他の彼らは非常に独立していないことを示唆している単純な線形式f2(x) = c/a * (f1(x) - b) + d (mod p)を使用して、（xを知らなくても） 。だからここで予期せぬ問題に遭遇する可能性がある。

Answer 2

既にScalaにMurmurHashが実装されています（それはscala.util.MurmurHashです）。それは非常に速く、値を配布するのに非常に優れています。暗号化されたハッシュは過度のものです。必要以上に数十倍から数百倍の時間がかかります。最初にkという異なる種を選んでください。品質がほぼ暗号化されているので、ほとんど独立したハッシュコードがkになります。 （2.10では、おそらくscala.util.hashing.MurmurHash3を使用するように切り替える必要がありますが、使い方はかなり異なりますが、ミキシングでも同じことができます）。

近くの値をランダムに遠くの​​値にマップする必要がある場合、これは機能します。衝突を回避したい場合（つまり、AとBがハッシュ1を使用して衝突する場合、おそらくハッシュ2を使用して衝突することはありません）、少なくとも1つのステップを実行し、オブジェクト全体ではなくハッシュのサブコンポーネントをハッシュする必要がありますハッシュが異なるものから始める機会があります。