ブルームフィルターを使用して、セットの交差近似をシミュレートしています。値をフィルターにハッシュするために、多くの単純なハッシュ関数を試しました。しかし、衝突を避けるのは苦手です。そのため、誰かがユニバーサル ハッシュ関数を提案しました。しかし、それがどのように機能するかわかりません。私のプログラムはキーだけをハッシュ関数に渡すように設計されており、ハッシュ関数はハッシュを返します。誰でもコードを手伝ってもらえますか? ありがとう
1136 次
1 に答える
0
ブルーム フィルターを使用する場合、ハッシュ関数の衝突について心配する必要はありません。この場合、衝突を処理する必要はありません。get k different には、要素を挿入するときに m ビットの配列に k ビットを設定する関数があります。クエリの時点で、すべての k ハッシュ関数を使用してすべての k ビットをチェックします。それらのいずれかが設定されていない場合、検索は false になります。それらすべてが設定されている場合、何も結論付けることはできません (偽陽性の結果)。これはwikiで明確に説明されています：
于 2012-02-24T04:47:23.043 に答える