ブルームフィルタ

ブルームフィルタとは、ある要素が集合に含まれているかどうかを判定するための確率的なデータ構造です。最大の特徴は、メモリ使用量を極めて低く抑えながら高速に判定が行える点にあります。判定結果には2つのパターンが存在します。1つは、要素が確実に集合に含まれていないと判定される場合で、この結果に間違いはありません。もう1つは、要素が集合に含まれている可能性があると判定される場合です。後者の場合、実際には含まれていないにもかかわらず含まれていると判定される誤検出が発生する可能性がありますが、含まれているものを含まれていないと判定する誤否定は発生しません。