C++ で Bloom Filter を実装してみた | Now or NeverBloom Filter を勉強する機会があったので、実装してみた。 概要 Bloom Filter 自体の説明はよそに譲るとして、ざっくり特徴を言うと、 二分木やハッシュテーブル等のデータ構造と比べると、はるかにメモリ効率が良い キーの値をメモリ上で格納する必要がない 逆に言うと、キーの集合を復元できない false positive(追加していないキーに対して true と返す誤り)による誤検出の可能性があるが、false negative(追加しているキーに対して、false と返す誤り)はない false positive する確率は 1 – exp(- k * n / m)) * k の式から算出できる パラメータ k: ハッシュ関数の個数、n: 追加する要素数, m: ビット列の長さ 要素を追加するほど、false positive が起きやすい n = 10 のとき 0.02
