ブルームフィルター

ブルームフィルターは、セット内の要素の存在を迅速かつメモリ効率の高い方法で識別するように設計されたデータ構造として定義されます。

確率的データ構造という名前の特定のデータ構造 ブルームフィルターとして実装されています。このデータ構造は、要素がセットに存在するか存在しないかを識別するのに役立ちます。

ビットベクトルは基本データ構造として実装されます。 これが説明に使用する小さなものです

そのテーブルの各空のセルは、ビットとその下の番号をそのインデックスまたは位置で指定します。ブルームフィルターに要素を追加するには、要素を数回ハッシュし、それらのハッシュの位置またはインデックスにあるビットベクトルのビットを1に設定します。

ブルームフィルターの詳細な実装については、以下で説明します

ブルームフィルターは、最初にオブジェクトを追加してオブジェクトを追跡し、次にオブジェクトが以前に表示されたかどうかを確認するという2つのアクションをサポートします。

ブルームフィルターへのオブジェクトの追加

• 追加するオブジェクトのハッシュ値を計算します;
• これらのハッシュ値を実装して、特定のビットをブルームフィルター状態に設定します（ハッシュ値は設定するビットの位置です）。

ブルームフィルターにオブジェクトが含まれているかどうかの確認-

• 追加するオブジェクトのハッシュ値を計算します;
• 次に、これらのハッシュ値によってインデックス付けされたビットがブルームフィルター状態に設定されているかどうかを確認します。

オブジェクトのハッシュ値がブルームフィルターの状態に直接追加されないことに注意する必要があります。各ハッシュ関数は、設定または検証するビットを決定するだけです。例：1つのハッシュ関数のみが使用される場合、1つのビットのみが検証またはチェックされます。