ブロンフィルタの原理とGuavaのBloomFilterの使用を分析します

あるURLが20億のURLの集合にあるかどうかを判断し、所定のメモリ空間(例えば500 M)内で迅速に判断する必要があるという問題が発生したと仮定する.
多くの人が最初に思いついたのはHashSetを使うからHashSetベースHashMap理論的に時間的複雑度はO(1).速い目的を達成しましたが、空間の複雑さは?URL文字列はHashによってIntegerの値を得て、Integerは4バイトを占めて、その20億個のURLは理論的に必要とします:20 *4/1024/1024/1024=7.45Gのメモリ、空間の複雑さの要求を満たしません.
ここでは、ここでご紹介する「ブロンフィルター」をご紹介します.
ブロンフィルタとは
百科事典のブロンフィルターの紹介はこうです.
ブロンフィルタ(Bloom Filter)は1970年にブロンによって提案された.実際には長いバイナリベクトルと一連のランダムマッピング関数である.ブロンフィルタは、要素がセットにあるかどうかを取得するために使用できます.その利点は,空間効率とクエリー時間が一般的なアルゴリズムよりもずっと優れていることであり,一定の誤認識率と削除困難があることである.
抽象的に描かれているのではないでしょうか.では、その原理を直接理解しましょう.
やはり上記の例を例に挙げます.
ハッシュアルゴリズムで得られたIntegerのハッシュ値は最大で,Integer.MAX_VALUE = 2147483647であり,いずれのURLのハッシュも0~2147483647の間にあることを意味する.
では、セットのすべての可能な値を格納するために、2147483647の長さのbyte配列を定義することができる.このbyte配列を格納するには、システムは:2147483647/8/1024/1024=256Mのみ必要です.
例えば、あるURL(X)のハッシュが2であれば、このbyte配列に落ちるのは2位で1であり、このbyte配列は:000...00000010であり、繰り返して、この20億個の数をすべてハッシュしてbyte配列に落とす.
判断ロジック:
byte配列の2番目のビットが1であれば、このURL(X)が存在する可能性があります.どうして可能なの?他のURLがハッシュにぶつかってハッシュされた可能性もあるので、これが誤審です.
しかし、このbyte配列の2番目のビットが0であれば、このURL(X)は集合中には存在しないに違いない.
複数ハッシュ:
ハッシュ衝突による誤判確率を低減するために,このURL(X)を異なるハッシュアルゴリズムでN回ハッシュし,N個のハッシュ値を導出し,このbyte配列に落下し,このN個の位置がすべて1でなければ,このURL(X)は集合中に存在しないに違いない.
GuavaのBloomFilter
Guavaフレームワークは、ブロンフィルタの具体的な実装を提供しています.BloomFilterは、自分でアルゴリズムを書く必要がない実装を開発します.
BloomFilterの作成
BloomFilterでは、いくつかのリロードの静的createインスタンスを作成する方法が提供されています.

public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions, double fpp);
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp);
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions);
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions);

最終的に呼び出すか:

static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy);
//     ：
// funnel                   ， ：IntegerFunnel，LongFunnel，StringCharsetFunnel。
// expectedInsertions           
// fpp    ，   0.03。

BloomFilterにおけるbyte配列の空間サイズはexpectedInsertions,fppパラメータによって決定されます.方法を参照してください.

static long optimalNumOfBits(long n, double p) {
    if (p == 0) {
        p = Double.MIN_VALUE;
    }
    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}

本格的なbyte配列はクラス:BitArrayに維持されます.
使用
最後に、putおよびmightContainメソッドにより、要素を追加し、要素が存在するか否かを判断します.
アルゴリズムの特徴

ハッシュ判定を用いるため時間効率が高い.空間効率も大きなメリットです.

誤審の可能性があり、具体的なシーンでの使用が必要です.

ハッシュ衝突が見分けられないので削除操作がうまくできない.

シーンの操作

ブラックリスト

URLデポジット

単語スペルチェック

Key-ValueキャッシュシステムのKeyチェック

IDチェック、例えば受注システムがある受注IDが存在するか否かを問い合せ、存在しない場合はそのまま返す.