ブルームフィルターの原理は非常に単純です。整数を整数キーにハッシュし、0から始まる非常に長いビットシーケンスを選択し、キーのこの位置で0を1に変更することです。次に文字列が入ったとき、ハッシュ後の値キー、そしてこのビットの値も1の場合、文字列が存在することを意味します。
上記の方法に従うと、ハッシュアルゴリズムと違いはなく、ハッシュアルゴリズムの重複がまだあります。
ブルームフィルターは複数のキーにひもをハッシュするので、本をフォローします。
最初に16億個のバイナリ定数を作成し、次に16億個のバイナリビットをすべてゼロに設定します。各文字列について、8つの異なるランダムジェネレーター（f1、f2、...、f8）を使用して、8つの情報フィンガープリント（f1、f2、...、f8）を生成します。次に、乱数ジェネレーターGを使用して、これらの8つの情報フィンガープリントを8個の自然数G1、G2、...、1〜16億個のG8にマッピングします。次に、これらの8つの位置のすべてのバイナリビットを1に変更します。この方法でブルームフィルターが構築されます。
では、文字列がすでに存在するかどうかを検出する方法は？
ここで、8つの乱数ジェネレーター（F1、F2、...、F8）を使用して、この文字列の8つの情報指紋S1、S2、...、S8を生成し、これらの8つの情報指紋をブルームフィルターの8つのバイナリビット、つまりT1、T2、...、T8に対応します。文字列が存在する場合、明らかにT1、T2、...、T8に対応するバイナリビットは1でなければなりません。これは、文字列がすでに存在するかどうかを判断する方法です。
実際、ブルームフィルターはハッシュアルゴリズムの延長です。それは本質的にハッシュなので、間違いなく欠点があります。言い換えれば、間違いなく誤解があります。文字列は現れませんでしたが、ブルームフィルターの判断が表示されました。可能性は非常に少ないですが、それは存在します。
では、この確率を減らす方法は？まず、8つの情報指紋が16のエラーに拡張された場合、確率は間違いなく低下することを想像できますが、このようにして、ブルームフィルターが保存できる文字列の数も1倍減少することを考慮する必要があります。さらに、優れたハッシュ関数を選択すると、非常に優れたハッシュ関数を含む、文字列には多くのタイプのハッシュメソッドがあります。
ブロンズフィルターは、主に悪意のあるURLをフィルタリングするために使用されます。すべての悪意のあるURLはブロンズフィルターの上に構築され、ユーザーはURLによってアクセスされます。悪意のあるURLにある場合、ユーザーに通知されます。このようにして、判断に誤りがあることが多いいくつかのURLにホワイトリストを設定し、存在すると判断されたURLとホワイトリストにURLを一致させることもできます。彼らがホワイトリストにいる場合、それらはリリースされます。もちろん、このホワイトリストは大きすぎず、大きすぎることはなく、ブルームフィルターエラーの確率は非常に少ないです。興味のある読者は、ブルームフィルターのエラー率を確認できます。
以下は、ブルームフィルターのJavaバージョンのソースコードです。
java.util.bitsetをインポートします。 /*** * * @Author Xkey */public class Bloomfilter {private static final int default_size = 2 << 24; //ブルームフィルターのビット長さプライベート静的最終int []シード= {3,5,7、11、13、31、37、61}; private static simplehash [] func = new simplehash [seeds.length]; public static void addvalue（string value）{for（simplehash f：func）//文字列値を8以上の整数にハッシュし、これらの整数ビットのビットで1に1に変更（f.hash（value）、true）; } public static void add（string value）{if（value！= null）addValue（value）; } public static boolean contains（string value）{if（value == null）return false; boolean ret = true; （SimpleHash F：FUNC）//実際には、ここですべてを実行する必要はありません。 ret == falseを1回だけで誤り、文字列は含まれません。 ret = ret && bits.get（f.hash（value））; Retを返します。 } public static void main（string [] args）{string value = "www.vevb.com"; for（int i = 0; i <seeds.length; i ++）{func [i] = new simplehash（default_size、seeds [i]）; } add（value）; system.out.println（contains（value））; }} class simplehash {//このことは、C ++ private int Capの構造に相当します。プライベートイントシード; public simplehash（int cap、int seed）{this.cap = cap; this.seed = seed; } public int hash（string value）{//スタンドハッシュ、適切なハッシュ関数int result = 0を選択することが非常に重要です。 int len = value.length（）; for（int i = 0; i <len; i ++）{result = seed * result+value.charat（i）; } return（cap -1）＆result; }}概要：ブルームフィルターは、ハッシュするアルゴリズムの革新であり、スペースがほとんどなく、エラー率が低くなっています。要するに、この革新的なアイデアは学ぶ価値があり、BITのようなデータ型を使用しています。
ブルームフィルターのJava実装方法は、私があなたと共有したすべてのコンテンツです。参照を提供できることを願っています。wulin.comをもっとサポートできることを願っています。