ブルームフィルターとは？仕組みと基本操作をわかりやすく解説

ブルームフィルター（Bloom Filter）とは、ある要素が集合に含まれているかどうかを、高速かつメモリ効率よく判定するために設計されたデータ構造です。

ブルームフィルターは確率的データ構造（probabilistic data structure）と呼ばれる特殊なデータ構造の一種で、要素が集合内に「存在する」か「存在しない」かを効率的に判別することを目的としています。厳密には、偽陽性（実際には存在しないのに存在すると判定される）の可能性はありますが、その代わりに極めて少ないメモリで大規模なデータを扱えるという大きな利点があります。

基礎となるビットベクトル

ブルームフィルターはビットベクトル（Bit Vector）を基盤となるデータ構造として使用します。以下は説明用の小さなビットベクトルの例です。

表の各空欄セルが1つのビットを表し、その下の数字はインデックス（位置）を示しています。

ブルームフィルターに要素を追加するには、対象の要素を複数回ハッシュ関数にかけてハッシュ値を計算し、そのハッシュ値に対応する位置のビットを「1」にセットします。

ブルームフィルターの基本的な操作

ブルームフィルターがサポートする操作は主に2つあります。1つ目はオブジェクトを追加して記録しておく操作、2つ目は特定のオブジェクトがすでに登録されているかどうかを確認する操作です。

1. オブジェクトの追加

• 追加したいオブジェクトに対してハッシュ値を計算します。
• 計算されたハッシュ値を使って、ブルームフィルターの状態（ビットベクトル）内の該当するビットをセットします。このとき、ハッシュ値がそのままセットすべきビットの位置を決定します。

2. オブジェクトの存在確認

• 確認したいオブジェクトに対してハッシュ値を計算します。
• 次に、それらのハッシュ値が指す位置のビットが、ブルームフィルターの状態内でセットされているかどうかを検証します。

重要なポイント：ハッシュ値そのものは保存されない

ここで注意すべき点があります。オブジェクトのハッシュ値そのものがブルームフィルターの状態に直接追加されるわけではありません。各ハッシュ関数は、どのビットをセットするか、あるいはどのビットを検証するかを決定する役割のみを担っています。

例えば、ハッシュ関数を1つだけ使用する場合は、検証時にチェックされるビットも1つだけになります。一般的には複数のハッシュ関数を使用することで、判定精度を高める設計が採用されます。