Cのブルームフィルタのための汎用ハッシュ関数の実装

Question

imブルームフィルタを使用したシミュレート集合交差近似。私はフィルターに値をハッシュするための単純なハッシュ関数をたくさん試してみました。衝突を避けることはできません。誰かが普遍的なハッシュ関数を提案しました。しかし、それはどのように動作するのかわからない。私のプログラムは、単にキーをハッシュ関数に渡すように設計されており、ハッシュ関数はハッシュを返します。誰でもコードを教えてくれますか？ ありがとう

Answer 1

ブルームフィルタで使用するとハッシュ関数が衝突する心配はありません。この場合、衝突を処理する必要はありません。ちょうどkを得るためには、要素を挿入するときにmビットの配列にkビットをセットする関数があります。クエリの時点で、すべてのkハッシュ関数を使用して、すべてのkビットをチェックします。それらのいずれかが設定されていない場合、検索は偽です。それらのすべてが設定されている場合は、何も結論できません（偽陽性の結果）。これは明らかにウィキで説明されています

http://en.wikipedia.org/wiki/Bloom_filter