ブルームフィルターの使い道は？ | NHN Cloud Meetup

確率的データ構造であるブルームフィルター（Bloom filter）は、ストレージを節約できる上、高速検索ができるため、HBase、Redisなど様々なデータベースで活用されているという話をよく聞きます。実際にどのように活用され、どのような原則でデータを含蓄的に表現できるかを簡単に説明した後、実際のデータ処理環境でどのように使用されているか、サンプルを使って紹介しようと思います。 ブルームフィルターの原理と実装 ブルームフィルターを簡単に説明すると、次のように言えます。 「どのような値が集合に属しているかをチェックするフィルタ、及びこれを構成するデータ型」 この構造を図式化してみましょう。 保存したい集合の値をn個のハッシュ関数（hash function）を経るようにして(1)、出力された各ビットをビットマップ配列に保存(2)します。 すべての値に対して、このプロセスを経ると、最終的に保