Java で、任意の数のランダム ハッシュ関数 (私の場合は 240 個のハッシュ関数) を生成し、任意の数の整数 (現時点では 2000 個) を実行する必要があるミンハッシュ アルゴリズムをプログラミングしています。
これを行うために、240 個のハッシュ関数のそれぞれに対して乱数 a、b、c (1 ～ 2001 の範囲) を生成してきました。次に、ハッシュ関数は h = ((a*x) + b) % c を返します。ここで、h は戻り値で、x はそれを通る整数の 1 つです。
これはランダムハッシュの効率的な実装ですか、それとももっと一般的/受け入れられる方法はありますか?
この投稿は同様の質問をしていましたが、回答の文言にまだ混乱しています: Minhash implementation how to find hash functions for permutations
数年前、Bloom フィルターを扱っていたときに、最小限のコードで複数のハッシュ関数を非常に簡単に生成する方法を説明している記事に出くわしました。彼が説明する方法は非常にうまく機能します。ハッシングを減らしても同じパフォーマンス: より優れたブルーム フィルターの構築.
基本的な考え方は、2 つのハッシュ関数を作成し、それらh1を および と呼びます。これにより、次の式を使用して、を通じてh2複数のハッシュ関数をシミュレートできます。g1gk
gi = h1(x) + i*h2(x)
i1 からk(必要なハッシュ関数の数) まで変化します。
彼のアイデアを実行しないと決めたとしても、この論文は読む価値があります。それを読んだ後、それを実装したくないとは想像できません。これにより、Bloom フィルター コードがはるかに扱いやすくなり、パフォーマンスに悪影響を与えることはありませんでした。
したがって、上で説明した方法はほぼ正しいものでした。数値 a と b はランダムに生成する必要があります。ただし、c は、x の可能な最大値よりもわずかに大きい素数である必要があります。これらの数値が選択されると、h = ((a*x)+b) % c を使用してハッシュ値 h を見つけることが、ハッシュ関数を生成するための標準的で受け入れられている方法です。
また、a と b は 1 から c-1 の範囲の乱数でなければなりません。