パラメータ入力
登録要素数 n
item
フィルタへ登録する要素数です。
ビット数 m
bit
ビット配列の長さです。
ハッシュ数 k
-
1要素あたり使うハッシュ関数の数です。
問い合わせ数
query
偽陽性数を見積もる問い合わせ回数です。
計算結果
—
偽陽性率
—
ビット占有率
—
最適ハッシュ数
—
期待誤ヒット
ビット配列占有
偽陽性率曲線
ハッシュ数感度
物理モデルと主要式
$$p=\left(1-e^{-kn/m}\right)^k,\quad k_{opt}=\frac{m}{n}\ln 2$$
Bloomフィルタは偽陰性を出さない代わりに偽陽性を許す確率的データ構造です。削除やカウントが必要な場合はCounting Bloom filterなどを検討します。